共计 1691 个字符，预计需要花费 5 分钟才能阅读完成。
算法背景
决策树是机器学习中最直观的算法之一，它通过树形结构模拟人类决策过程。CART（Classification And Regression Trees）作为决策树家族的重要成员，既能处理分类问题也能解决回归任务。与 ID3、C4.5 等算法相比，CART 有两大特点：
- 二叉树结构：每个节点只分裂为两个子节点
- 基尼系数与方差最小化：分别用于分类和回归问题
数学原理
分类问题：基尼系数
基尼系数衡量数据集的不纯度，计算公式为：
$$ Gini(p) = 1 – \sum_{k=1}^{K}p_k^2 $$
其中 $p_k$ 是第 k 类样本的比例。分裂时选择使基尼指数下降最多的特征：
$$ \Delta Gini = Gini(D) – \frac{|D_1|}{|D|}Gini(D_1) – \frac{|D_2|}{|D|}Gini(D_2) $$
回归问题：平方误差
对于回归树，通过最小化平方误差选择分裂点：
$$ \min_{j,s}\left[\min_{c_1} \sum_{x_i \in R_1(j,s)}(y_i – c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)}(y_i – c_2)^2 \right] $$
Python 实现
以下是核心代码框架（完整代码见 GitHub）：
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 gini(y):
_, counts = np.unique(y, return_counts=True)
return 1 - np.sum((counts/len(y))**2)
def best_split(X, y):
best_gain = -1
best_feature, best_thresh = None, None
for feature in range(X.shape[1]):
thresholds = np.unique(X[:, feature])
for thresh in thresholds:
left_idx = X[:, feature] <= thresh
gain = gini(y) - (len(y[left_idx])*gini(y[left_idx]) + len(y[~left_idx])*gini(y[~left_idx]))/len(y)
if gain > best_gain:
best_gain = gain
best_feature = feature
best_thresh = thresh
return best_feature, best_thresh实战建议
关键参数调优
max_depth：控制树的最大深度，通常从 3 开始尝试min_samples_split：节点分裂的最小样本数，防止过拟合criterion：分类任务用 ”gini”，回归任务用 ”mse”
sklearn 调用示例：
from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier(max_depth=5, min_samples_split=10)
clf.fit(X_train, y_train)避坑指南
过拟合问题
决策树容易过拟合训练数据，解决方法包括：
- 预剪枝：通过参数限制树的生长
- 后剪枝：先构建完整树再剪枝
- 交叉验证选择最优参数组合
算法比较
| 算法 | 树结构 | 分裂标准 | 任务类型 |
|---|---|---|---|
| ID3 | 多叉树 | 信息增益 | 分类 |
| C4.5 | 多叉树 | 增益率 | 分类 |
| CART | 二叉树 | 基尼系数 | 分类 / 回归 |
延伸思考
- 如何处理决策树对数据微小变化敏感的问题？
- 在类别不平衡的场景下，基尼系数是否仍然适用？
- 如何将决策树扩展到多输出任务？
通过本文的学习，相信你已经掌握了 CART 算法的核心思想。建议动手实现完整版本，并使用 sklearn 的 plot_tree 可视化决策过程，这能帮助更直观地理解算法行为。
正文完
