决策树实战：从零开始用CART算法构建高效分类模型

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

背景痛点：为什么我们需要 CART 算法

决策树是机器学习中最直观的算法之一，但初学者常遇到两个核心问题：

• 特征选择困难：面对十几个甚至上百个特征时，如何选择最优分裂点？信息增益（ID3）或增益率（C4.5）的计算复杂度较高，且对连续值处理不够高效
• 过拟合陷阱：树模型容易生长得过深，导致在训练集上表现完美但测试集上效果骤降。手动剪枝需要反复尝试，缺乏量化标准

算法对比：CART 的独特优势

与其他决策树算法相比，CART（Classification and Regression Trees）有两大特点：

1. 二叉树结构：每个节点只分裂为两个子节点，简化决策路径
2. 基尼系数：使用 $Gini = 1-\sum_{k=1}^K p_k^2$ 作为分裂标准，计算效率比信息熵更高

与 ID3/C4.5 的对比：

核心实现：手写 CART 分类树

1. 基尼系数计算

计算数据集 $D$ 的基尼系数：

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

2. 寻找最佳分裂点

对每个特征的所有可能切分点进行评估：

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

    for feature in range(X.shape[1]):
        thresholds = np.unique(X[:, feature])
        for threshold in thresholds:
            left_idx = X[:, feature] <= threshold
            gini = (len(y[left_idx]) * gini_impurity(y[left_idx]) + 
                    len(y[~left_idx]) * gini_impurity(y[~left_idx])) / len(y)
            if gini < best_gini:
                best_gini = gini
                best_feature = feature
                best_threshold = threshold
    return best_feature, best_threshold

3. 递归构建决策树

核心递归逻辑（预剪枝参数已添加）：

class TreeNode:
    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=3, min_samples_leaf=5):
    # 终止条件 1：所有样本属于同一类
    if len(np.unique(y)) == 1:
        return TreeNode(value=y[0])

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

    # 寻找最优分裂
    feature, threshold = find_best_split(X, y)

    # 分裂数据集
    left_idx = X[:, feature] <= threshold
    left = build_tree(X[left_idx], y[left_idx], max_depth-1, min_samples_leaf)
    right = build_tree(X[~left_idx], y[~left_idx], max_depth-1, min_samples_leaf)

    return TreeNode(feature, threshold, left, right)

实战优化：sklearn 调参指南

关键参数解析

from sklearn.tree import DecisionTreeClassifier

# 推荐初始参数
clf = DecisionTreeClassifier(
    criterion='gini',       # 分裂标准
    max_depth=5,            # 最大深度
    min_samples_split=10,   # 节点最小样本数
    min_samples_leaf=5,     # 叶节点最小样本数
    class_weight='balanced' # 处理类别不平衡
)

交叉验证选择最优深度

from sklearn.model_selection import GridSearchCV

param_grid = {'max_depth': range(3, 15)}
grid = GridSearchCV(clf, param_grid, cv=5)
grid.fit(X_train, y_train)

print("最佳深度:", grid.best_params_['max_depth'])

避坑指南

类别不平衡处理

• 设置 class_weight='balanced' 自动调整类别权重
• 手动指定权重字典：class_weight={0:1, 1:3}表示正样本重要性是负样本的 3 倍

特征重要性误区

• 重要性是相对值，总和为 1
• 高重要性特征不一定代表因果关系
• 存在相关性强的特征时，重要性会被分散

延伸思考

1. 回归问题：将基尼系数改为均方误差（MSE）即可处理连续目标值
2. 随机森林：CART 是随机森林的基学习器，通过 bagging 降低方差

# CART 回归树示例
from sklearn.tree import DecisionTreeRegressor
reg = DecisionTreeRegressor(criterion='mse', max_depth=3)

总结

通过本文的实践，你会发现 CART 算法：

1. 比 ID3/C4.5 更适合处理连续特征
2. 二叉树结构让模型解释性更强
3. 通过预剪枝参数可以有效控制过拟合

建议在实际项目中先使用默认参数快速验证效果，再逐步调整 max_depth 和min_samples_leaf等关键参数。当遇到高维数据时，可以结合特征重要性进行特征筛选。