决策树 CART 分裂

决策树是递归二分特征的判别模型, 每个节点用“特征 + 切分点”把样本分成左右两支, 分裂准则决定切分质量。熵: $H(D) = -\sum_{k=1}^{K} p_k \log_2 p_k$; Gini 不纯度: $G(D) = 1 - \sum_{k=1}^{K} p_k^2$, 二分类退化为 $G = 2p(1-p)$(类 1 概率 $p$, $p = 0.5$ 时最大 $0.5$)。CART 分类树贪心搜索特征 $A$ 与切分点 $v$, 使分裂前后 Gini 下降最大: $\Delta G(A, v) = G(D) - \frac{|D_L|}{|D|} G(D_L) - \frac{|D_R|}{|D|} G(D_R)$, 其中 $D_L = \{ x \mid x_A \leq v \}$, $D_R = D \setminus D_L$。ID3 用信息增益 $\text{Gain}(D, A) = H(D) - \sum_{v=1}^{V} \frac{|D_v|}{|D|} H(D_v)$, 它天然偏好取值多的特征 (划分越细 $H(D_v)$ 越小); C4.5 用增益比 $\text{Gain\_ratio}(D, A) = \frac{\text{Gain}(D, A)}{\text{IV}(A)}$, 其中固有值 $\text{IV}(A) = -\sum_{v=1}^{V} \frac{|D_v|}{|D|} \log_2 \frac{|D_v|}{|D|}$ 惩罚特征取值个数; CART 恒为二叉树 (每次只做一个二值切分), 分类用 Gini、回归用方差下降 $\text{err}(D) = \frac{1}{|D|} \sum_{i \in D} \left(y_i - \bar{y}_D\right)^2$。连续特征: 按特征值排序后只检查相邻样本的中点 $\frac{x^{(i)} + x^{(i+1)}}{2}$ 作为候选切分点 (任意区间内切分效果只由落在哪两个相邻点之间决定), 候选点最多 $n-1$ 个, 单特征排序 $O(n \log n)$。

面试必考的算法三连问 — “ID3 / C4.5 / CART 分裂准则区别”“为什么信息增益偏好取值多的特征”“连续特征怎么切”; 也是随机森林 (Gini 分裂)、XGBoost/LightGBM (结构增益/方差) 分裂逻辑的推导起点。

把“选哪个特征、在哪切”的指数级搜索 (最优决策树问题是 NP 难) 化为每步贪心的一次线性扫描 — 每个候选切分只需 $O(n)$ 算一次不纯度, 单节点复杂度 $O(d \cdot n \log n)$; 贪心不保证全局最优, 但配合剪枝与随机化 (随机森林) 在实践里足够好, 且分裂准则只依赖类别比例/方差, 对特征尺度不敏感、天然处理非线性。

白板推导 Gini 不纯度 $G = 1 - \sum_k p_k^2$: 二分类为什么退化为 $2p(1-p)$? 与熵 $H = -\sum_k p_k \log p_k$ 相比有何优缺点?

写出信息增益 $\text{Gain}(D, A) = H(D) - \sum_v \frac{|D_v|}{|D|} H(D_v)$ 并解释为什么它偏好取值多的特征; 增益比如何用固有值 $\text{IV}(A)$ 修正?

ID3 / C4.5 / CART 的分裂准则分别是什么? 为什么 CART 一定是二叉树?

连续特征如何切分? 为什么只用相邻样本中点 $\frac{x^{(i)} + x^{(i+1)}}{2}$ 作候选切分点? 单特征的时间复杂度是多少?

CART 回归树的分裂准则与叶子输出是什么? 为什么叶子输出是均值 $\bar{y}$?