决策树实战：深入解析CART算法原理与实现细节

1次阅读

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

决策树算法因其直观易懂的特性，在机器学习领域广受欢迎。然而在实际应用中，我们常常会遇到几个关键问题：

过拟合问题：当特征维度较高时，决策树容易生成过于复杂的结构，导致在训练集上表现良好而在测试集上泛化能力差。
连续值处理：传统 ID3 算法只能处理离散特征，无法直接应用于现实世界中大量存在的连续值特征。
性能平衡：在模型可解释性和预测性能之间往往需要做出权衡取舍，这对算法实现提出了更高要求。

CART(Classification and Regression Trees)算法相比 ID3 和 C4.5 有几个显著优势：

基尼系数 vs 信息增益
ID3 使用信息增益作为特征选择标准：$IG(D,A) = H(D) – H(D|A)$
CART 采用基尼系数：$Gini(D) = 1 – \sum_{k=1}^K p_k^2$
计算复杂度更低，且对类别分布更敏感
连续值处理能力
CART 通过寻找最佳分割点自动处理连续特征
而 ID3 需要预先离散化连续特征
功能扩展性
CART 既能处理分类问题 (分类树) 也能处理回归问题(回归树)
ID3/C4.5 仅支持分类任务

def gini_impurity(y):
    """ 计算基尼不纯度

    Args:
        y: 目标值数组
    Returns:
        基尼不纯度值
    """
    _, counts = np.unique(y, return_counts=True)
    probabilities = counts / len(y)
    return 1 - np.sum(probabilities ** 2)

class DecisionNode:
    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              # 叶节点值

def build_tree(X, y, max_depth, min_samples_split, current_depth=0):
    # 终止条件检查
    if (current_depth >= max_depth or 
        len(y) < min_samples_split or 
        len(np.unique(y)) == 1):
        return DecisionNode(value=np.mean(y))

    # 寻找最佳分割
    best_gini = float('inf')
    best_feature, best_thresh = None, 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
            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_idx
                best_thresh = threshold

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

    return DecisionNode(feature_idx=best_feature, 
                       threshold=best_thresh,
                       left=left, 
                       right=right)

后剪枝 (Post-Pruning) 是在树构建完成后进行的优化过程：

从完全生长的树底部开始
尝试将某个内部节点变为叶节点
如果验证集准确率不下降，则进行剪枝
重复直至无法继续优化

max_depth：控制树的最大深度，防止过拟合
min_samples_split：节点分裂所需最小样本数
min_samples_leaf：叶节点所需最小样本数

from sklearn.tree import DecisionTreeClassifier

# 使用网格搜索调优
params = {'max_depth': [3, 5, 7, None],
    'min_samples_split': [2, 5, 10],
    'min_samples_leaf': [1, 2, 4]
}

grid_search = GridSearchCV(DecisionTreeClassifier(),
    param_grid=params,
    cv=5
)
grid_search.fit(X_train, y_train)

使用 class_weight 参数调整类别权重
对少数类样本进行过采样
采用分层抽样确保训练集分布均衡

from sklearn.tree import export_graphviz
import graphviz

dot_data = export_graphviz(
    tree_model,
    out_file=None, 
    feature_names=feature_names,
    class_names=target_names,
    filled=True,
    rounded=True
)
graph = graphviz.Source(dot_data)
graph.render("decision_tree")  # 生成 PDF 文件

训练阶段：$O(n_{features} \times n_{samples} \times log(n_{samples}))$
预测阶段：$O(tree_{depth})$

importance = tree_model.feature_importances_
for i, feature in enumerate(feature_names):
    print(f"{feature}: {importance[i]:.3f}")

from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(
    n_estimators=100,
    max_depth=5,
    random_state=42
)
rf.fit(X_train, y_train)