CART决策树算法原理与实现：从数学推导到Python实战

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

为什么需要决策树？

在机器学习领域，决策树因其出色的可解释性而广受欢迎。相比于黑箱模型如神经网络，决策树能够直接展示决策逻辑，这对于医疗诊断、金融风控等需要解释性的场景至关重要。CART（Classification and Regression Trees）作为决策树家族的重要成员，与 ID3/C4.5 的主要区别在于：

• 使用基尼系数而非信息增益
• 支持连续特征处理
• 能够同时处理分类和回归任务

基尼系数数学原理

基尼系数衡量的是数据集的不纯度，计算公式为：

$$ Gini(D) = 1 – \sum_{k=1}^{K} (\frac{|C_k|}{|D|})^2 $$

其中 $C_k$ 表示第 k 类样本的数量。我们来看一个简单的特征分割示例：

 原始数据集 [5A,5B]  按特征 X 分割后
     / \
 [3A,1B]  [2A,4B]

计算分割后的基尼指数：

$$ Gini_{split} = \frac{4}{10} \times (1 – (\frac{3}{4})^2 – (\frac{1}{4})^2) + \frac{6}{10} \times (1 – (\frac{2}{6})^2 – (\frac{4}{6})^2) $$

Python 实现详解

1. 定义节点类

class Node:
    """ 决策树节点类
    Attributes:
        feature_idx: int, 分裂特征索引
        threshold: float, 分裂阈值
        left: Node, 左子树
        right: Node, 右子树
        value: Any, 叶节点预测值
    """
    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

2. 核心构建函数

def build_tree(X, y, depth=0, max_depth=None, min_samples_split=2):
    """递归构建决策树"""
    n_samples, n_features = X.shape

    # 终止条件检查
    if (max_depth and depth >= max_depth) or (n_samples < min_samples_split):
        return Node(value=np.argmax(np.bincount(y)))

    # 寻找最佳分裂
    best_gini = float('inf')
    best_feature, best_threshold = None, None

    for feature_idx in range(n_features):
        thresholds = np.unique(X[:, feature_idx])
        for threshold in thresholds:
            # 计算基尼指数
            left_indices = X[:, feature_idx] <= threshold
            gini = calculate_gini(y[left_indices], y[~left_indices])

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

    # 递归构建子树
    left_indices = X[:, best_feature] <= best_threshold
    left = build_tree(X[left_indices], y[left_indices], depth+1, max_depth, min_samples_split)
    right = build_tree(X[~left_indices], y[~left_indices], depth+1, max_depth, min_samples_split)

    return Node(feature_idx=best_feature, threshold=best_threshold, left=left, right=right)

3. 预测函数实现

def predict(node, x):
    """递归预测单个样本"""
    if node.value is not None:
        return node.value

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

关键问题与解决方案

类别特征处理

对于类别型特征，常见的处理方式包括：

1. 独热编码（One-Hot Encoding）
2. 目标编码（Target Encoding）
3. 基于类别统计量构造新特征

连续值分箱陷阱

• 避免等宽分箱导致的数据分布不均
• 推荐使用等频分箱或基于决策树的最优分箱

样本不均衡处理

可以通过调整类别权重来解决：

class_weight = {0:1, 1:5}  # 少数类样本权重设为 5 

性能优化方向

1. 递归改迭代 ：使用栈结构实现非递归构建
2. 并行化 ：对特征搜索过程进行并行计算

动手挑战

尝试实现代价复杂度剪枝（Cost-Complexity Pruning），关键步骤包括：

1. 计算每个节点的 α 值
2. 从叶节点开始剪枝
3. 使用交叉验证确定最优 α

完整的实现代码和测试案例可以参考项目仓库。通过这篇文章，你应该已经掌握了 CART 决策树的核心原理和实现方法，快动手试试吧！