深入解析CART决策树原理：从数学基础到Python实现

1次阅读

没有评论

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

决策树的核心是选择最优分裂特征，CART 使用基尼系数(Gini Index)，而 ID3/C4.5 使用信息增益(熵)。两者的本质都是衡量数据不纯度(impurity)，但计算方式不同：

基尼系数：$Gini(p) = 1 – \sum_{k=1}^K p_k^2$，计算更简单（无需对数运算）
信息熵：$H(p) = -\sum_{k=1}^K p_k \log p_k$，对不均衡数据更敏感

以二分类为例，当类别概率为 [0.5, 0.5] 时：
– 基尼系数 = 1 – (0.25 + 0.25) = 0.5
– 信息熵 = -(0.5log0.5 + 0.5log0.5) ≈ 0.69

CART 采用 二分法 处理特征，对于每个特征的所有可能分割点计算基尼指数：

$Gini_index(D, a) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)$

示例数据集：
| 年龄 | 收入 | 是否购买 |
|——|——-|———-|
| 青年 | 低 | 否 |
| 青年 | 高 | 是 |
| 中年 | 高 | 是 |
| 老年 | 中 | 否 |

计算 ” 收入 = 低 ” 作为分割点的基尼指数：
1. 左子集 D1(收入 = 低)：[否] → Gini(D1)=0
2. 右子集 D2(收入≠低)：[是, 是, 否] → Gini(D2)=1-(2/3)²-(1/3)²≈0.444
3. 基尼指数 = (1/4)0 + (3/4)0.444 ≈ 0.333

class Node:
    def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
        self.feature = feature  # 分裂特征
        self.threshold = threshold  # 分裂阈值
        self.left = left  # 左子树
        self.right = right  # 右子树
        self.value = value  # 叶节点预测值

def build_tree(X, y, max_depth=3):
    # 终止条件：纯度 100% 或达到最大深度
    if len(set(y)) == 1 or max_depth == 0:
        return Node(value=max(set(y), key=list(y).count))

    best_gini = float('inf')
    best_feature, best_threshold = None, None

    # 遍历所有特征和可能的分割点
    for feature in range(X.shape[1]):
        thresholds = np.unique(X[:, feature])
        for threshold in thresholds:
            left_idx = X[:, feature] <= threshold
            gini = calculate_gini(y[left_idx], y[~left_idx])
            if gini < best_gini:
                best_gini = gini
                best_feature = feature
                best_threshold = threshold

    # 递归分裂
    left_idx = X[:, best_feature] <= best_threshold
    left = build_tree(X[left_idx], y[left_idx], max_depth-1)
    right = build_tree(X[~left_idx], y[~left_idx], max_depth-1)

    return Node(best_feature, best_threshold, left, right)

def plot_decision_boundary(model, X, y):
    x_min, x_max = X[:, 0].min()-1, X[:, 0].max()+1
    y_min, y_max = X[:, 1].min()-1, X[:, 1].max()+1
    xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.01),
                         np.arange(y_min, y_max, 0.01))
    Z = model.predict(np.c_[xx.ravel(), yy.ravel()])
    plt.contourf(xx, yy, Z.reshape(xx.shape), alpha=0.3)
    plt.scatter(X[:, 0], X[:, 1], c=y, edgecolor='k')

官方实现采用以下加速策略：
1. 预排序技术：对连续特征提前排序，加速最优分割点搜索
2. 并行计算 ：n_jobs 参数支持多线程处理特征
3. 内存优化 ：使用presort=False 时改为即时排序

关键参数示例：

from sklearn.tree import DecisionTreeClassifier
model = DecisionTreeClassifier(
    criterion='gini',  # 使用基尼系数
    max_depth=5,       # 控制过拟合
    min_samples_split=10,  # 节点最小样本数
    min_impurity_decrease=0.01  # 分裂最小增益
)