共计 2059 个字符，预计需要花费 6 分钟才能阅读完成。
初学者的决策树困境
刚开始接触决策树时，我常被各种教程弄得晕头转向：要么是满屏数学公式却不解释实际用途，要么给个 sklearn 调包示例了事。最头疼的是，当我想自己实现时，发现连最基本的节点分裂逻辑都写不出来——这就像给了菜谱却不教怎么开火。
决策树家族三兄弟
决策树算法主要有三大流派：
- ID3：用信息增益选特征，只能处理离散值，容易过拟合
- C4.5：改进版用信息增益率，支持连续值，但树结构复杂
- CART（本期主角）：采用二叉树结构，既可用基尼系数也能用平方误差，既能分类也能回归
CART 的优势在于它的二叉树特性：每个节点只分左右两支，这种结构在代码实现时递归逻辑更简单，计算效率也更高。
手撕 CART 核心原理
1. 基尼系数：数据不纯度测量仪
基尼系数公式看似吓人，其实理解后很简单：
Gini = 1 - Σ(p_i)^2 # p_i 是第 i 类样本占比举个例子，一个袋子有 3 红球 7 蓝球：
Gini = 1 - (0.3² + 0.7²) = 0.42计算分裂后的加权基尼系数：
Gini_split = (N_left/N_total)*Gini_left + (N_right/N_total)*Gini_right2. 特征选择：寻找最佳拆包姿势
对于每个特征，我们需要：
- 排序特征值
- 计算相邻值的中间点作为候选分割阈值
- 评估每个阈值划分后的基尼系数
- 选择使基尼系数下降最多的划分方案
3. 停止条件：什么时候该收手
- 节点样本数小于预设 min_samples
- 基尼系数下降小于阈值
- 达到最大树深度
Python 实战：从零搭建 CART 树
class Node:
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 # 叶节点预测值
class CART:
def __init__(self, max_depth=5, min_samples_split=2):
self.max_depth = max_depth
self.min_samples_split = min_samples_split
def _gini(self, y):
# 计算基尼系数
classes = np.unique(y)
return 1 - sum([(np.sum(y == c) / len(y))**2 for c in classes])
def _best_split(self, X, 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 = self._weighted_gini(y[left_idx], y[~left_idx])
if gini < best_gini:
best_gini = gini
best_feature = feature_idx
best_thresh = threshold
return best_feature, best_thresh
def fit(self, X, y):
self.n_classes = len(np.unique(y))
self.tree = self._grow_tree(X, y)
def predict(self, X):
return np.array([self._traverse_tree(x, self.tree) for x in X])六大避坑指南
- 连续值处理：
- 排序后取相邻值中点作为候选阈值
-
边界情况要单独处理
-
类别不平衡：
- 在基尼系数计算中加入类别权重
-
使用 class_weight 参数
-
剪枝策略：
- 预剪枝：控制 max_depth/min_samples_split
-
后剪枝：用验证集评估剪枝收益
-
缺失值处理：
-
常见方法：分配到使基尼系数下降更多的分支
-
特征重要性：
- 统计特征在分裂时带来的基尼下降总量
-
归一化后得到重要性评分
-
计算效率：
- 提前对特征值排序可加速分裂点查找
- 对于大数据集可考虑特征采样
性能优化方向
- 时间复杂度：O(n_features * n_samples * log(n_samples))
- 空间复杂度：O(2^max_depth)
- 实用技巧：
- 对连续特征只考虑百分位点作为候选阈值
- 并行化特征搜索过程
下一步挑战
试着给决策树添加这些高级功能：
- 可视化决策路径（可以用 graphviz 库）
- 实现回归树模式（改用平方误差）
- 尝试多特征组合分裂
完整代码已放在 GitHub 仓库（虚构地址），包含更多注释和测试案例。其实决策树就像乐高积木，理解基础原理后，各种改进都是在这个框架上叠加新模块。
正文完
