Decision Trees: 解释决策树的分裂准则（信息增益 / 基尼不纯度）。

Core Concept: 选择使子节点不纯度下降最多的特征；ID3 用信息增益，CART 用基尼。

三种不纯度度量：① <strong>熵</strong> H(D)=−Σpₖlog pₖ（ID3 用），信息增益 IG=H(D)−Σ(|Dᵥ|/|D|)H(Dᵥ) 度量分裂后的不确定性减少；② <strong>基尼不纯度</strong> Gini=1−Σpₖ²（CART 用），可理解为'随机抽两个样本类别不同的概率'，计算无需 log 故更快，且与熵的曲线形状相似（都在 p=0.5 时最大）；③ <strong>误分类率</strong> 1−max pₖ，对类别概率不敏感（不推荐用于分裂，因为它对概率变化不敏感，无法区分'0.5/0.5'与'0.4/0.6'的改善）。<strong>分裂选择</strong>：遍历所有特征与所有候选阈值，选使加权子节点不纯度最小的那个（贪心）。

关键性质与问题：① <strong>信息增益偏向多取值特征</strong>——若某特征取值极多（如用户 ID），每个取值对应一个样本，则每个子节点都纯，增益最大但无泛化意义。C4.5 用<strong>增益率</strong>（IG/分裂信息）校正，CART 用基尼 + 限制候选阈值（只考虑排序后相邻值的中点）来缓解。② <strong>贪心性</strong>——每次只做局部最优分裂，不保证全局最优树（找最优树是 NP-hard），这是集成方法（RF/GBDT）优于单树的原因之一。③ <strong>连续特征的处理</strong>——排序后取相邻值中点作为候选阈值，复杂度 O(n log n) 每特征；LightGBM 进一步用直方图分桶降到 O(#bins)。④ <strong>缺失值</strong>——CART 用代理分裂（surrogate splits，找与主分裂最相似的特征替代），或按缺失率加权分配到子节点；现代实现（XGBoost/LightGBM）用默认方向（学习缺失值的默认走向）。