决策树构建原理深度解析：从ID3算法到实战避坑指南

1次阅读

共计 2289 个字符，预计需要花费 6 分钟才能阅读完成。

决策树是一种模仿人类决策过程的树形结构模型。它的核心思想是通过对特征值的不断划分，最终达到分类或回归的目的。ID3 算法（Iterative Dichotomiser 3）是最早的决策树算法之一，由 Ross Quinlan 于 1986 年提出。

ID3 算法的关键在于使用信息增益来选择最佳划分特征。信息增益的计算基于信息熵的概念。对于数据集 D，其信息熵定义为：

$$
Entropy(D) = -\sum_{k=1}^{K}p_k\log_2p_k
$$

其中，$p_k$ 表示第 k 类样本在 D 中的比例。

在选择划分特征 A 时，计算其对数据集 D 的信息增益：

$$
Gain(D,A) = Entropy(D) – \sum_{v=1}^{V}\frac{|D_v|}{|D|}Entropy(D_v)
$$

其中，$D_v$ 表示 D 中特征 A 取值为 v 的子集。

ID3 倾向于选择取值较多的特征，C4.5 引入信息增益比来克服此问题
ID3 无法处理连续特征，C4.5 支持连续特征处理
ID3 没有剪枝机制，C4.5 包含后剪枝步骤

以下是一个基于 Python 的 ID3 算法实现，包含完整注释：

# Python 3.8+ 环境
import numpy as np
from collections import Counter

def entropy(y):
    """计算信息熵"""
    counts = Counter(y)
    probs = [count/len(y) for count in counts.values()]
    return -sum(p * np.log2(p) for p in probs)

def information_gain(X, y, feature_idx):
    """计算信息增益"""
    parent_entropy = entropy(y)

    # 按特征值分组
    feature_values = X[:, feature_idx]
    unique_values = set(feature_values)

    child_entropy = 0
    for value in unique_values:
        mask = feature_values == value
        child_y = y[mask]
        child_entropy += (len(child_y)/len(y)) * entropy(child_y)

    return parent_entropy - child_entropy

class DecisionTreeID3:
    def __init__(self, max_depth=5, min_samples_split=2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split

    def fit(self, X, y, depth=0):
        """递归构建决策树"""
        # 终止条件
        if depth >= self.max_depth or len(y) < self.min_samples_split or len(set(y)) == 1:
            return Counter(y).most_common(1)[0][0]

        # 选择最佳特征
        best_feature = None
        best_gain = -1
        for feature_idx in range(X.shape[1]):
            gain = information_gain(X, y, feature_idx)
            if gain > best_gain:
                best_gain = gain
                best_feature = feature_idx

        # 构建子树
        tree = {}
        feature_values = X[:, best_feature]
        unique_values = set(feature_values)

        for value in unique_values:
            mask = feature_values == value
            subtree = self.fit(X[mask], y[mask], depth+1)
            tree[(best_feature, value)] = subtree

        return tree