决策树实战：深入解析CART算法构造流程与工程实现

1次阅读

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

在机器学习实践中，决策树因其直观性、可解释性而广受欢迎，但在实际应用中，过拟合、特征重要性误判等问题常常困扰着开发者。本文将从 CART（Classification and Regression Trees）算法入手，系统剖析决策树构建的核心流程，并提供可落地的工程实现方案。

决策树在实际应用中常见的问题包括：

过拟合：模型在训练集上表现良好，但在测试集上泛化能力差
特征重要性误判：某些特征被错误地赋予过高或过低的重要性
计算效率低：当数据集规模较大时，训练时间过长

这些问题往往源于算法实现中的细节处理不当，如节点分裂条件、剪枝策略等。

CART 算法使用 Gini 系数作为分裂标准，其定义为：

$$
Gini(p) = 1 – \sum_{k=1}^{K} p_k^2
$$

其中，$p_k$ 是第 $k$ 类样本在当前节点中的比例。与 ID3/C4.5 算法相比，CART 的主要区别在于：

ID3 使用信息增益，C4.5 使用信息增益比，而 CART 使用 Gini 系数
CART 生成的是二叉树，而 ID3/C4.5 可以生成多叉树
CART 可以处理连续值和缺失值

def build_tree(X, y, max_depth, min_samples_split, current_depth=0):
    # 终止条件 1：所有样本属于同一类别
    if len(np.unique(y)) == 1:
        return LeafNode(y)

    # 终止条件 2：达到最大深度
    if current_depth >= max_depth:
        return LeafNode(y)

    # 终止条件 3：样本数小于最小分裂数
    if len(y) < min_samples_split:
        return LeafNode(y)

    # 寻找最佳分裂点
    best_feature, best_threshold = find_best_split(X, y)

    # 递归构建左右子树
    left_idx = X[:, best_feature] <= best_threshold
    right_idx = ~left_idx

    left_subtree = build_tree(X[left_idx], y[left_idx], 
                             max_depth, min_samples_split, current_depth+1)
    right_subtree = build_tree(X[right_idx], y[right_idx],
                              max_depth, min_samples_split, current_depth+1)

    return DecisionNode(best_feature, best_threshold, left_subtree, right_subtree)

def gini_impurity(y):
    """
    计算 Gini 不纯度
    时间复杂度：O(K), K 为类别数
    """
    _, counts = np.unique(y, return_counts=True)
    probabilities = counts / len(y)
    return 1 - np.sum(probabilities**2)

def find_best_split(X, y):
    """
    寻找最佳分裂特征和阈值
    时间复杂度：O(m*n), m 为特征数，n 为样本数
    """best_gini = float('inf')
    best_feature = None
    best_threshold = None

    for feature_idx in range(X.shape[1]):
        thresholds = np.unique(X[:, feature_idx])
        for threshold in thresholds:
            left_idx = X[:, feature_idx] <= threshold
            if np.sum(left_idx) == 0 or np.sum(~left_idx) == 0:
                continue

            gini_left = gini_impurity(y[left_idx])
            gini_right = gini_impurity(y[~left_idx])

            weighted_gini = (len(y[left_idx]) * gini_left + 
                            len(y[~left_idx]) * gini_right) / len(y)

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

    return best_feature, best_threshold

def prune_tree(node, alpha, X_val, y_val):
    """
    后剪枝：代价复杂度剪枝
    时间复杂度：O(n), n 为节点数
    """
    if isinstance(node, LeafNode):
        return node

    # 递归剪枝左右子树
    node.left = prune_tree(node.left, alpha, X_val, y_val)
    node.right = prune_tree(node.right, alpha, X_val, y_val)

    # 计算剪枝前后的损失
    original_loss = compute_loss(node, X_val, y_val) + alpha * count_leaves(node)
    merged_loss = compute_loss(LeafNode(y_val), X_val, y_val) + alpha * 1

    if merged_loss <= original_loss:
        return LeafNode(y_val)
    else:
        return node

sklearn 的 DecisionTreeClassifier 在实现上做了多项优化：

预排序优化：对连续特征值进行预排序，加快最佳分割点的搜索
并行计算：利用多线程处理不同特征的分裂计算
内存优化：使用高效的数据结构存储树结构
增量学习：支持部分拟合（partial_fit）

这些优化使得 sklearn 的实现在大规模数据集上仍能保持较高效率。

在工程实践中，以下三点需要特别注意：

特征离散化：对于连续特征，离散化可以提升模型鲁棒性
类别不平衡处理：使用 class_weight 参数或过采样 / 欠采样技术
特征相关性检查：高度相关的特征可能导致重要性评估偏差

使用乳腺癌数据集进行验证：

from sklearn.datasets import load_breast_cancer
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report
import matplotlib.pyplot as plt

# 加载数据
data = load_breast_cancer()
X, y = data.data, data.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 训练模型
clf = DecisionTreeClassifier(max_depth=3, random_state=42)
clf.fit(X_train, y_train)

# 评估
print(classification_report(y_test, clf.predict(X_test)))

# 特征重要性可视化
importances = clf.feature_importances_
indices = np.argsort(importances)[::-1]
plt.figure(figsize=(10, 6))
plt.title("Feature Importances")
plt.bar(range(X.shape[1]), importances[indices], align="center")
plt.xticks(range(X.shape[1]), data.feature_names[indices], rotation=90)
plt.tight_layout()
plt.show()

本文从 CART 算法的原理入手，详细讲解了决策树的构建流程、优化技巧和工程实践中的注意事项。通过手写实现和 sklearn 的对比分析，我们深入理解了决策树在工业级应用中的关键点。在实际项目中，合理设置参数、进行适当的剪枝和特征处理，可以显著提升模型的性能和稳定性。

正文完