深入解析CART决策树算法实现：从数学原理到Python实战

1次阅读

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

决策树通过自动选择最具区分度的特征进行数据分割，有效减少人工特征筛选的工作量。其天然的可解释性允许工程师直观理解特征重要性排名，辅助业务逻辑验证。树结构的分层判断机制，能够同时处理数值型和类别型特征，避免复杂的特征编码预处理。

信息熵衡量数据集的混乱程度，计算公式：
```
H(D) = -Σ(p_i * log2(p_i))
```
其中 p_i 表示第 i 类样本所占比例
信息增益计算方式：
```
Gain(D,A) = H(D) - Σ(|D_v|/|D|)*H(D_v)
```
容易偏向取值多的特征

引入分裂信息进行校正：

Gain_ratio(D,A) = Gain(D,A) / IV(A)
IV(A) = -Σ(|D_v|/|D|)*log2(|D_v|/|D|)

缓解了 ID3 的偏好问题

计算数据集纯度：
```
Gini(D) = 1 - Σ(p_i^2)
```
表示随机抽取两个样本类别不一致的概率
分裂时选择使基尼指数最小的划分：
```
Gini_index(D,A) = Σ(|D_v|/|D|)*Gini(D_v)
```

class TreeNode:
    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_impurity(y):
    m = y.shape[0]
    if m == 0:
        return 0
    p = np.bincount(y) / m
    return 1 - np.sum(p**2)

寻找最佳分裂特征与阈值：

def find_best_split(X, y):
    best_gini = float('inf')
    best_feature, best_thresh = None, None

    for feature_idx in range(X.shape[1]):
        # 对数值型特征排序后尝试相邻值中点作为候选阈值
        values = np.unique(X[:, feature_idx])
        thresholds = (values[:-1] + values[1:]) / 2

        for thresh in thresholds:
            left_mask = X[:, feature_idx] <= thresh
            right_mask = ~left_mask

            gini_left = gini_impurity(y[left_mask])
            gini_right = gini_impurity(y[right_mask])

            # 加权平均基尼指数
            curr_gini = (left_mask.sum() * gini_left + 
                         right_mask.sum() * gini_right) / y.shape[0]

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

    return best_feature, best_thresh

递归构建主函数：

def build_tree(X, y, max_depth=5, min_samples_split=2):
    # 终止条件 1：样本全属同一类别
    if len(np.unique(y)) == 1:
        return TreeNode(value=y[0])

    # 终止条件 2：达到最大深度或样本不足
    if max_depth <= 1 or len(y) < min_samples_split:
        return TreeNode(value=np.bincount(y).argmax())

    # 寻找最佳分裂
    feature_idx, threshold = find_best_split(X, y)
    if feature_idx is None:
        return TreeNode(value=np.bincount(y).argmax())

    # 递归构建子树
    left_mask = X[:, feature_idx] <= threshold
    left = build_tree(X[left_mask], y[left_mask], 
                     max_depth-1, min_samples_split)
    right = build_tree(X[~left_mask], y[~left_mask],
                      max_depth-1, min_samples_split)

    return TreeNode(feature_idx, threshold, left, right)

最大深度限制：通过 max_depth 参数防止过度生长
最小分裂样本数：min_samples_split避免对微小变异敏感
叶节点最小样本：min_samples_leaf保证预测可靠性

计算剪枝前后的验证集准确率
自底向上合并叶节点
保留使准确率提升的合并操作

def prune_tree(node, X_val, y_val):
    if node.value is not None:
        return node

    # 递归处理子树
    node.left = prune_tree(node.left, X_val, y_val)
    node.right = prune_tree(node.right, X_val, y_val)

    # 计算合并前后的准确率
    original_acc = evaluate(node, X_val, y_val)
    merged_value = np.bincount(y_val).argmax()
    temp_acc = (y_val == merged_value).mean()

    if temp_acc >= original_acc:
        return TreeNode(value=merged_value)
    return node

对于有序类别：转化为数值编码（如学历：小学 =1，中学 =2）
对于无序类别：采用 one-hot 编码
避免直接使用字符串标签，确保所有输入为数值类型

训练阶段：
将缺失作为特殊值处理
分配样本到使基尼系数下降更多的分支
预测阶段：
按照训练时学到的分配比例走多路径
或默认走样本更多的分支

提前排序特征值加速阈值搜索
对于大规模数据采用分位点采样
考虑使用近似算法加速

如何改进当前实现以支持回归任务（需修改分裂指标为方差）？
当特征维度极高时，怎样优化特征选择过程（特征采样 / 近似算法）？
能否实现增量学习机制，允许模型在新数据到达时部分更新树结构？

基尼系数：计算简便，偏向等概率分布
交叉熵：对概率变化更敏感，计算涉及对数
实际效果差异通常小于 2%

假设某二分类数据集：
– 特征 A 分裂后：左节点[3 正,1 负]，右节点[2 正,4 负]
– 基尼指数计算：

Gini_left = 1 - (3/4)^2 - (1/4)^2 = 0.375
Gini_right = 1 - (2/6)^2 - (4/6)^2 ≈ 0.444
Gini_index = (4/10)*0.375 + (6/10)*0.444 ≈ 0.416

– 对比未分裂时的基尼系数 0.5，增益为 0.084

浅树：高偏差（欠拟合），但方差小
深树：低偏差，但方差大（过拟合）
通过交叉验证选择最优深度
实践中常设置 max_depth=3-8 作为起点

import numpy as np

class CARTClassifier:
    def __init__(self, max_depth=5, min_samples_split=2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.tree = None

    def fit(self, X, y):
        self.tree = build_tree(X, y, 
                              self.max_depth, 
                              self.min_samples_split)

    def predict(self, X):
        return np.array([self._predict(x) for x in X])

    def _predict(self, x, node=None):
        if node is None:
            node = self.tree

        if node.value is not None:
            return node.value

        if x[node.feature_idx] <= node.threshold:
            return self._predict(x, node.left)
        else:
            return self._predict(x, node.right)

决策树作为基础模型，其实现过程揭示了机器学习算法的多个核心思想：通过递归分解问题、基于纯度的特征选择、防止过拟合的剪枝策略等。理解这些底层机制对后续学习随机森林、GBDT 等集成方法大有裨益。建议读者尝试在以下方向扩展当前实现：