深入解析CART决策树：从算法原理到工程实践

1次阅读

没有评论

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

决策树模型在工业界有广泛的应用场景，尤其是在需要可解释性的领域。典型的例子包括：

金融风控评分卡（判断用户信用风险）
医疗诊断决策支持（根据症状判断疾病）
客户分群与营销策略（基于用户特征制定个性化方案）

然而，传统决策树实现存在几个关键问题：

容易过拟合，特别是在特征维度高的情况下
特征重要性可能会随数据分布变化而漂移
对连续特征处理不够鲁棒
树结构不稳定，小的数据变化可能导致完全不同的树

决策树算法主要有三种，它们在特征选择标准上有所不同：

使用信息增益作为特征选择标准：

$$ Gain(D,A) = Ent(D) – \sum_{v=1}^V \frac{|D^v|}{|D|}Ent(D^v) $$

其中：

$$ Ent(D) = -\sum_{k=1}^K p_k \log_2 p_k $$

改进 ID3，使用信息增益比：

$$ Gain_ratio(D,A) = \frac{Gain(D,A)}{IV(A)} $$

$$ IV(A) = -\sum_{v=1}^V \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|} $$

使用 Gini 系数作为划分标准：

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

$$ Gini_index(D,A) = \sum_{v=1}^V \frac{|D^v|}{|D|} Gini(D^v) $$

CART 算法的优势在于：

可以处理连续值和离散值
生成的二叉树结构计算效率高
Gini 系数计算比熵计算更快

对于连续特征，通常需要先进行离散化（分箱）处理：

# 等频分箱示例
import pandas as pd

def equal_freq_bin(data, col, n_bins=5):
    _, bins = pd.qcut(data[col], q=n_bins, retbins=True, duplicates='drop')
    return pd.cut(data[col], bins=bins, include_lowest=True)

# 等宽分箱示例
def equal_width_bin(data, col, n_bins=5):
    min_val = data[col].min()
    max_val = data[col].max()
    width = (max_val - min_val) / n_bins
    bins = [min_val + i * width for i in range(n_bins + 1)]
    return pd.cut(data[col], bins=bins, include_lowest=True)

CART 树的构建是一个递归过程，终止条件包括：

当前节点样本数小于 min_samples_split
当前节点 Gini 系数小于阈值
树深度达到 max_depth
所有特征都已使用

from sklearn.tree import DecisionTreeClassifier

# 初始化决策树
clf = DecisionTreeClassifier(
    criterion='gini',  # 使用 Gini 系数
    max_depth=5,       # 最大深度
    min_samples_split=20,  # 最小分裂样本数
    min_samples_leaf=10,   # 叶节点最小样本数
    random_state=42
)

# 训练模型
clf.fit(X_train, y_train)

代价复杂度剪枝 (Cost-Complexity Pruning) 公式：

$$ R_\alpha(T) = R(T) + \alpha|\tilde{T}| $$

其中 $R(T)$ 是误分类率，$|\tilde{T}|$ 是叶节点数，$\alpha$ 是复杂度参数。

# 获取剪枝路径
path = clf.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas, impurities = path.ccp_alphas, path.impurities

# 对每个 alpha 训练一个剪枝后的树
pruned_clfs = []
for ccp_alpha in ccp_alphas:
    pruned_clf = DecisionTreeClassifier(random_state=42, ccp_alpha=ccp_alpha)
    pruned_clf.fit(X_train, y_train)
    pruned_clfs.append(pruned_clf)

# 选择最优的 alpha 值
best_alpha = ccp_alphas[np.argmax(test_scores)]
best_clf = DecisionTreeClassifier(random_state=42, ccp_alpha=best_alpha)
best_clf.fit(X_train, y_train)

import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import GridSearchCV
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split

# 加载数据
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.3, random_state=42)

# 定义参数网格
param_grid = {'max_depth': [3, 5, 7, None],
    'min_samples_split': [2, 5, 10],
    'min_samples_leaf': [1, 2, 4],
    'criterion': ['gini']
}

# 网格搜索
grid_search = GridSearchCV(DecisionTreeClassifier(random_state=42),
    param_grid=param_grid,
    cv=5,
    scoring='accuracy'
)
grid_search.fit(X_train, y_train)

# 最佳模型
best_clf = grid_search.best_estimator_
print(f"Best params: {grid_search.best_params_}")
print(f"Test accuracy: {best_clf.score(X_test, y_test):.4f}")

# 特征重要性可视化
importances = best_clf.feature_importances_
indices = np.argsort(importances)[::-1]

plt.figure(figsize=(12, 6))
plt.title("Feature Importance")
plt.bar(range(X.shape[1]), importances[indices], align="center")
plt.xticks(range(X.shape[1]), data.feature_names[indices], rotation=90)
plt.xlim([-1, X.shape[1]])
plt.tight_layout()
plt.show()