从零构建CART决策树：原理剖析与Python实战指南

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

为什么需要这篇指南

初学决策树时，我常被各种教程弄得晕头转向：要么满篇数学符号却不解释实际含义，要么代码只给片段无法直接运行。更头疼的是，不同算法（ID3、C4.5、CART）的差异很少被讲透。这种学习体验就像拿到一份没有组装说明的乐高零件——知道它们能拼出好东西，但不知从何下手。

决策树家族三兄弟

• ID3：最元老的算法，用信息增益选择特征，但只能处理离散值且容易偏爱多值特征
• C4.5：ID3 的升级版，引入信息增益率和连续值处理，但生成的树结构复杂
• CART：我们今天的主角，特点是：
• 永远生成二叉树（问答更直观）
• 可用基尼系数或平方误差作为分裂标准
• 既能分类也能回归

手把手实现 CART 的核心步骤

1. 基尼系数：数据纯度的尺子

公式看起来简单但很有深意：

Gini(D) = 1 - Σ(p_i)²

其中 p_i 是第 i 类样本的比例。比如一个袋子有 3 红球 7 蓝球：

def gini(y):
    _, counts = np.unique(y, return_counts=True)
    return 1 - np.sum((counts/len(y))**2)

# 计算示例
print(gini([0,0,0,1,1,1,1,1,1,1]))  # 输出 0.42

当所有样本同属一类时，基尼系数为 0——这就是我们要追求的目标。

2. 寻找最佳分裂点

对于每个特征，我们需要：

1. 排序特征值
2. 计算相邻值的中间点作为候选阈值
3. 评估按阈值分裂后的加权基尼系数

# 找出使基尼系数下降最多的分裂方式
def find_best_split(X, y):
    best_gini = float('inf')
    best_feature, best_thresh = None, None

    for feature in range(X.shape[1]):
        values = np.sort(np.unique(X[:, feature]))
        thresholds = (values[:-1] + values[1:]) / 2  # 相邻值中点

        for thresh in thresholds:
            left_idx = X[:, feature] <= thresh
            g = (len(y[left_idx])*gini(y[left_idx]) + 
                 len(y[~left_idx])*gini(y[~left_idx])) / len(y)
            if g < best_gini:
                best_gini = g
                best_feature, best_thresh = feature, thresh

    return best_feature, best_thresh

3. 递归建树与终止条件

递归过程就像玩 20 问游戏，需要设定停止条件：

1. 节点样本数小于预设值（防止过拟合）
2. 基尼系数已达 0（完美分类）
3. 没有更多特征可用

完整 Python 实现

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      # 叶节点的预测值

class CART:
    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):
        self.n_classes = len(np.unique(y))
        self.tree = self._grow_tree(X, y)

    def _grow_tree(self, X, y, depth=0):
        n_samples, n_features = X.shape
        n_labels = len(np.unique(y))

        # 终止条件检查
        if (depth >= self.max_depth 
            or n_labels == 1 
            or n_samples < self.min_samples_split):
            return Node(value=self._most_common_label(y))

        # 寻找最佳分裂
        best_feat, best_thresh = find_best_split(X, y)

        # 递归构建子树
        left_idx = X[:, best_feat] <= best_thresh
        left = self._grow_tree(X[left_idx], y[left_idx], depth+1)
        right = self._grow_tree(X[~left_idx], y[~left_idx], depth+1)
        return Node(best_feat, best_thresh, left, right)

    def _most_common_label(self, y):
        return np.bincount(y).argmax()

    def predict(self, X):
        return [self._traverse_tree(x, self.tree) for x in X]

    def _traverse_tree(self, x, node):
        if node.value is not None:
            return node.value
        if x[node.feature] <= node.threshold:
            return self._traverse_tree(x, node.left)
        return self._traverse_tree(x, node.right)

实战避坑指南

连续值处理的陷阱

• 阈值不要直接取唯一值，而要用相邻值中点
• 大数据集时可以先等频分桶再找分裂点

类别不平衡的解决方案

在计算基尼系数时加入类别权重：

weights = len(y) / (self.n_classes * np.bincount(y))
weighted_gini = 1 - np.sum(weights * (counts/len(y))**2)

剪枝策略

1. 预剪枝：通过 max_depth 和min_samples_split控制
2. 后剪枝：训练完整树后，自底向上合并信息增益不显著的节点

复杂度分析

• 训练时：O(n_features * n_samples * log(n_samples))
• 预测时：O(tree_depth)

下一步挑战

1. 实现特征重要性评估（统计每个特征被用作分裂点的次数）
2. 添加决策路径可视化（可以用 graphviz 库）
3. 尝试多特征组合分裂（比如 x1+x2>3）

通过这次实现，我发现 CART 就像数据界的福尔摩斯——通过不断提出是 / 否问题，最终揭开真相。希望这份指南能帮你越过理论到实践的鸿沟，下次遇到分类问题时，不妨亲手种一棵决策树试试！