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

1次阅读

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

在机器学习项目中，特征工程直接影响模型效果。决策树作为可解释性极强的算法，能自动完成特征选择，输出清晰的判断规则。但许多教程用信息增益（ID3 算法）讲解分裂过程，而 scikit-learn 等工具实际默认使用基尼系数（CART 算法），这种差异常让初学者困惑。

基尼系数 vs 信息增益
基尼系数计算节点不纯度：$Gini(p) = 1 – \sum_{k=1}^K p_k^2$
相比信息增益，基尼系数计算更快（无对数运算），且对类别不平衡更敏感
CART 与 ID3/C4.5 的关键区别
CART 是二叉树结构，每次分裂产生两个子节点
支持连续特征和回归任务（ID3 仅处理离散分类）
无信息增益率计算（C4.5 的特性）

def gini_impurity(y):
    """计算节点的基尼不纯度"""
    _, counts = np.unique(y, return_counts=True)
    probabilities = counts / len(y)
    return 1 - np.sum(probabilities ** 2)

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

    for feature_idx in range(X.shape[1]):  # 遍历所有特征
        thresholds = np.unique(X[:, feature_idx])  # 所有可能的分裂值
        for threshold in thresholds:
            left_mask = X[:, feature_idx] <= threshold
            gini = (len(y[left_mask]) * gini_impurity(y[left_mask]) + 
                    len(y[~left_mask]) * gini_impurity(y[~left_mask])) / len(y)
            if gini < best_gini:
                best_gini = gini
                best_feature, best_threshold = feature_idx, threshold
    return best_feature, best_threshold

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

def build_tree(X, y, max_depth=5, min_samples_split=2):
    # 终止条件 1：样本数过少
    if len(y) < min_samples_split:
        return Node(value=np.argmax(np.bincount(y)))

    # 终止条件 2：所有样本同类
    if len(np.unique(y)) == 1:
        return Node(value=y[0])

    # 终止条件 3：达到最大深度
    if max_depth <= 0:
        return Node(value=np.argmax(np.bincount(y)))

    feature, threshold = find_best_split(X, y)
    left_mask = X[:, feature] <= 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 Node(feature, threshold, left, right)

预剪枝策略
限制最大深度（max_depth）防止过拟合
设置最小分裂样本数（min_samples_split）
后剪枝方法
代价复杂度剪枝（CCP）
验证集准确率判断子树是否保留

连续特征处理
错误做法：直接按类别特征处理
正确方案：排序后尝试所有可能的分割点
类别不平衡问题
错误现象：模型总是预测多数类
解决方案：使用 class_weight 参数或过采样
缺失值处理
错误做法：直接删除含缺失值的样本
推荐方案：分裂时增加缺失值分支方向

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris

# 加载数据
X, y = load_iris(return_X_y=True)

# 自实现模型
my_tree = build_tree(X, y, max_depth=3)

# sklearn 对比
sk_tree = DecisionTreeClassifier(criterion='gini', max_depth=3)
sk_tree.fit(X, y)

# 打印前 5 个样本预测结果
print("自实现结果:", [predict(my_tree, x) for x in X[:5]])
print("sklearn 结果:", sk_tree.predict(X[:5]))

当前算法全程使用 CPU 计算，当特征维度很高时，暴力搜索会成为性能瓶颈。如何改进？