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

1次阅读

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

决策树算法家族中，CART（Classification and Regression Trees）是最经典的实现之一。与 ID3 和 C4.5 不同，CART 有两大特点：

使用 基尼系数（Gini Index）作为分裂标准（分类任务）
能同时处理分类和回归任务（通过方差最小化）

基尼系数和熵都是衡量数据不纯度的指标，但计算方式不同：

# 基尼系数计算公式
gini = 1 - sum(p_i^2 for p_i in class_probabilities)

# 信息熵计算公式  
entropy = -sum(p_i * log2(p_i) for p_i in class_probabilities)

实际应用中，基尼系数计算更快（无需对数运算），而熵对不平衡数据更敏感。

对于每个特征，CART 会：

计算该特征所有可能划分点的基尼指数
选择使基尼指数最小的划分点

基尼指数计算公式：

Gini_index = p_left * Gini_left + p_right * Gini_right

假设我们有以下数据（二分类问题）：

年龄	收入	是否购买
青年	高	否
青年	低	否
中年	高	是
老年	中	是

以 ” 年龄 ” 特征为例：

计算整体基尼系数：1 – (0.5² + 0.5²) = 0.5
尝试划分点 ” 青年 ”：
左节点基尼：1 – (0² + 1²) = 0
右节点基尼：1 – (1² + 0²) = 0
基尼指数：0.50 + 0.50 = 0

这是完美的划分，因此会选择这个分裂点。

class DecisionNode:
    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 fit(self, X, y):
    # 终止条件 1：所有样本属于同一类
    if len(set(y)) == 1:
        return DecisionNode(value=y[0])

    # 终止条件 2：没有更多特征可用
    if self.max_depth is not None and self.current_depth >= self.max_depth:
        return DecisionNode(value=self._most_common_label(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 threshold in thresholds:
            left_idx = X[:, feature_idx] <= threshold
            gini = self._calculate_gini(y[left_idx], y[~left_idx])

            if gini < best_gini:
                best_gini = gini
                best_feature = feature_idx
                best_thresh = threshold

    # 递归构建子树
    left_idx = X[:, best_feature] <= best_thresh
    left = self.fit(X[left_idx], y[left_idx])
    right = self.fit(X[~left_idx], y[~left_idx])

    return DecisionNode(best_feature, best_thresh, left, right)

sklearn 中的 DecisionTreeClassifier 做了多项优化：