深入解析CART决策树的计算步骤：从数学原理到Python实现

1次阅读

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

决策树的核心是选择最优分裂特征，CART 算法使用基尼系数(Gini Index)，而 ID3/C4.5 使用信息熵(Entropy)。两者都衡量数据不纯度，但有显著差异：

基尼系数：计算概率平方和的补数，公式为 $Gini = 1 – \sum_{k=1}^K p_k^2$
计算速度更快（无对数运算）
对类别分布变化更敏感
信息熵：基于信息论的概念，公式为 $H = -\sum_{k=1}^K p_k \log_2 p_k$
对不平衡数据更鲁棒
倾向于产生更平衡的树

实际应用中，两者结果通常差异不大，但基尼系数计算效率更高，这是 CART 算法选择它的主要原因。

单特征基尼计算
对于特征 A 的可能取值 $a_i$，计算分裂后的加权基尼系数：
$$Gini_{split} = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)$$
连续特征处理
排序特征值
取相邻值中点作为候选切分点
选择使基尼系数降低最多的切分点
最优特征选择
遍历所有特征和切分点，选择使 $Gini_{split}$ 最小的组合

import numpy as np
from sklearn.datasets import load_iris

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

def gini(y):
    """计算基尼系数"""
    classes = np.unique(y)
    gini = 1.0
    for cls in classes:
        p = len(y[y == cls]) / len(y)
        gini -= p**2
    return gini

def find_best_split(X, y):
    """寻找最佳分裂特征和阈值"""
    best_gini = float('inf')
    best_feature, best_thresh = None, None

    for feature_idx in range(X.shape[1]):
        thresholds = np.unique(X[:, feature_idx])
        for thresh in thresholds:
            left_idx = X[:, feature_idx] <= thresh
            left_gini = gini(y[left_idx])
            right_gini = gini(y[~left_idx])
            weighted_gini = (left_gini * len(y[left_idx]) + right_gini * len(y[~left_idx])) / len(y)

            if weighted_gini < best_gini:
                best_gini = weighted_gini
                best_feature = feature_idx
                best_thresh = thresh

    return best_feature, best_thresh