很多人学决策树都卡在同一个地方图能看懂节点能画出来数据集一换自己也敢上手跑可真被问到“为什么这个特征排在最上面”“信息增益为什么不直接用准确率”“剪枝到底在剪什么”就开始支支吾吾。我当初也是这样所以专门抽了一个周末把决策树从ID3到CART的公式完整手推了一遍。这篇就是我推完之后留下的完整笔记每个关键公式都配了一个可以直接拿纸笔验算的小例子。这篇文章的定位很明确已经会调库训练决策树但想把“树为什么长这样”真正想明白的人。我会从信息熵的数学来源开始一路推到ID3的信息增益、C4.5的信息增益比、CART的Gini系数、连续特征分裂和剪枝代价最后再落到工程里的特征重要性和超参数语义。不需要你是数学系背景只要记得对数运算、期望、条件概率、简单求导就能跟着走完全程。1. 从“会调参”到“能手推”的距离1.1 为什么搞懂决策树必须过一遍公式调个决策树模型其实十分钟就够fit一下看一眼feature_importances_完事。但如果你不知道这些参数在优化什么遇到问题只能瞎试。比如为什么min_samples_leaf从1调到5树的准确率反而明显上升为什么同一个特征在A数据集上排在重要度第一在B数据集上几乎排不上号为什么对高基数离散特征比如用户ID做独热编码之后特征重要度会虚高为什么某些场景下CART比C4.5更不容易被高基数特征带偏这些问题只看API文档永远得不到答案。只有把公式推到“每个符号背后对应什么数据”的程度你才真正拥有解释一棵树的能力。这也是我给自己的硬性要求不靠记忆靠推导。1.2 手推需要的前置知识说句实话决策树公式的门槛不高比线性回归的矩阵求导友好多了。你只需要四样东西对数运算知道 $\log_2 0.5 -1$$\log_2 0.25 -2$ 这种程度即可。期望熵本质就是一个期望值也就是“加权重平均”。条件概率$P(y|x)$ 或者说“某个子集里各类别占比”。一元求导回归树里求最优输出值时用一下。如果你这些概念看着眼熟但有点生疏完全不影响阅读。我会在推导到每一步时把含义拆开讲。1.3 整篇文章统一使用的例子为了不让每个公式都搞一套新数据我直接构造一个8个样本的小数据集后面所有计算都围着它转。假设我们要预测用户会不会产生二次购买行为总共有两个特征X1是否看过活动页0/1二值X2注册渠道类型0/1/2三种取值标签A代表会复购B代表不会复购。样本如下样本X1X2标签100A200A301A402B511A612B712B811B先做一个快速统计方便后面算标签A类4个B类4个。X104个样本A3个B1个X114个样本A1个B3个。X202个样本全是AX213个样本A2个B1个X223个样本全是B。好了数据固定。接下来所有的分裂准则都会在这个数据集上跑一遍。2. 信息熵从哪来可加性、联合熵与条件熵2.1 信息量的可加性锁定了对数函数信息熵的公式长这样$$ H(X) -\sum_{i} P(x_i) \log_2 P(x_i) $$很多人背得滚瓜烂熟但没想过一个问题为什么偏偏是对数答案是“可加性”。设想你收到一个消息明天有雨地铁停运。这件事包含的信息量应该等于“明天有雨”的信息量加上“地铁停运”的信息量。如果把“明天有雨”记作 $x$“地铁停运”记作 $y$那就是$$ I(x, y) I(x) I(y) $$如果 $x$ 和 $y$ 相互独立联合发生的概率是 $P(x,y) P(x)P(y)$。那么什么样的“信息量函数”能同时满足相乘的概率变成相加的信息量只有对数函数$$ I(x) -\log_b P(x) $$底数取2是因为二进制编码里每个比特恰好对应“二选一”的不确定性信息量单位就是比特。一个概率为0.5的事件信息量是1比特一个概率为0.25的事件信息量是2比特。熵就是随机变量所有可能取值的“信息量期望”$$ H(X) \sum_i P(x_i) I(x_i) -\sum_i P(x_i) \log_2 P(x_i) $$换个角度说熵度量的是一个分布的平均不确定度。分布越均匀、各类概率越接近熵越大分布越偏、某个类概率接近1不确定性越小熵越小。2.2 联合熵到条件熵的一条链决策树分裂要看“知道某个特征之后标签的不确定性下降多少”这就必须用到条件熵。$H(Y|X)$ 的定义是在已知X取值的前提下Y还剩下多少平均不确定度。先看在X取具体值 $x_i$ 时Y的条件熵$$ H(Y \mid X x_i) -\sum_j P(y_j \mid x_i) \log_2 P(y_j \mid x_i) $$再把所有X取值按概率加权平均$$ H(Y \mid X) \sum_i P(x_i) H(Y \mid X x_i) $$这个式子写开后其实等价于联合熵减掉 $H(X)$。我来完整演算一遍$$ \begin{aligned} H(X, Y) -\sum_{i,j} P(x_i, y_j) \log_2 P(x_i, y_j) \ -\sum_{i,j} P(x_i, y_j) \log_2 \left[ P(x_i) P(y_j \mid x_i) \right] \ -\sum_{i,j} P(x_i, y_j) \log_2 P(x_i) - \sum_{i,j} P(x_i, y_j) \log_2 P(y_j \mid x_i) \ -\sum_i P(x_i) \log_2 P(x_i) \sum_i P(x_i) \left[ -\sum_j P(y_j \mid x_i) \log_2 P(y_j \mid x_i) \right] \ H(X) H(Y \mid X) \end{aligned} $$所以$$ H(Y \mid X) H(X, Y) - H(X) $$这个关系式特别重要。它说明条件熵是“X和Y联合起来的不确定性”减去“X本身的不确定性”剩下的就是Y里跟X无关的那部分不确定性。2.3 先用8个样本把熵算一遍回到我们的示例数据。先算标签D的经验熵。经验熵就是用频率代替概率直接数数$$ H(D) -\frac{4}{8} \log_2 \frac{4}{8} - \frac{4}{8} \log_2 \frac{4}{8} 1 $$4个A、4个B完美对半开熵正好取到最大值1比特。后面我们看任何一个特征只要能把这两种标签分开一点点条件熵就会小于1信息增益就会大于0。3. ID3的信息增益第一次把“纯度”变成数字3.1 信息增益公式的本质不确定性减少量ID3算法的分裂准则就是信息增益。公式$$ g(D, A) H(D) - H(D \mid A) $$翻译成人话分裂前整个数据集有 $H(D)$ 的不确定性按特征A分成几个子集之后平均不确定性降到了 $H(D|A)$。降下去的那部分就是从A身上获得的信息量。计算时用频率估计概率$$ H(D \mid A) \sum_{i1}^{n} \frac{\lvert D_i \rvert}{\lvert D \rvert} H(D_i) $$其中 $D_i$ 是按特征A第i个取值切出来的子集$H(D_i)$ 是子集内部的经验熵。3.2 三个特征的手推对比先算按X1分裂X10的4个样本里A3个B1个$$ H(D_{\text{X1}0}) -\frac{3}{4} \log_2 \frac{3}{4} - \frac{1}{4} \log_2 \frac{1}{4} 0.8113 $$X11的4个样本里A1个B3个熵同样$$ H(D_{\text{X1}1}) 0.8113 $$条件熵$$ H(D \mid X1) \frac{4}{8} \times 0.8113 \frac{4}{8} \times 0.8113 0.8113 $$信息增益$$ g(D, X1) 1 - 0.8113 0.1887 $$再算按X2分裂X20有2个样本全是A熵是0。X21有3个样本A2个B1个$$ H(D_{\text{X2}1}) -\frac{2}{3} \log_2 \frac{2}{3} - \frac{1}{3} \log_2 \frac{1}{3} 0.9183 $$X22有3个样本全是B熵也是0。条件熵$$ H(D \mid X2) \frac{2}{8} \times 0 \frac{3}{8} \times 0.9183 \frac{3}{8} \times 0 0.3444 $$信息增益$$ g(D, X2) 1 - 0.3444 0.6556 $$现在假设还有一个特征X3它是每个样本唯一的“消息ID”。X3有8个不同取值每个取值只对应1个样本所以每个子集都只剩一个类别子集熵全是0。条件熵$$ H(D \mid X3) \sum_{i1}^{8} \frac{1}{8} \times 0 0 $$信息增益直接拉到最大值$$ g(D, X3) 1 $$ID3会满心欢喜地选X3作为根节点分裂特征。3.3 多取值特征为什么会让信息增益失真看到这里问题已经很清楚了X3把每个样本都单独切成一个节点训练集上熵降到0增益达到1比特完美。但它对未见过的样本毫无泛化能力——新样本根本不会和你训练集里任何一个样本共享ID取值。这就是信息增益的固有缺陷它无条件地奖励“取值多”的特征。取值越多切出的子集越细每个子集越可能纯条件熵就越低。这属于典型的过拟合信号。这个问题在数学上叫“多值特征偏好”ID3算法没有做任何惩罚所以实际使用中容易被那种高基数的ID类特征带偏。也正是这个缺陷直接催生了C4.5的信息增益比。4. C4.5的信息增益比增益除以固有值纠正了什么4.1 固有值 HA(D) 到底在衡量什么C4.5做了一件很朴素的事把信息增益除以一个“特征自身熵值”也就是固有值intrinsic value$$ g_R(D, A) \frac{g(D, A)}{H_A(D)} $$其中$$ H_A(D) -\sum_{i1}^{n} \frac{\lvert D_i \rvert}{\lvert D \rvert} \log_2 \frac{\lvert D_i \rvert}{\lvert D \rvert} $$这个式子把“特征A取值分布”的熵单独算了一遍。它的含义是如果特征A取值越多、越分散$H_A(D)$ 就越大信息增益除以它以后就会被压得越低。回到我们的直觉X3有8个取值每个取值占比1/8$H_A(D)$ 等于 $\log_2 8 3$。这对一个三分支特征来说惩罚非常重。4.2 同一份数据上计算增益比X1是二值特征两个取值各4个样本$$ H_{A}(X1) -\frac{4}{8} \log_2 \frac{4}{8} - \frac{4}{8} \log_2 \frac{4}{8} 1 $$增益比$$ g_R(D, X1) \frac{0.1887}{1} 0.1887 $$X2是三分支特征取值占比分别是2/8、3/8、3/8$$ H_{A}(X2) -\frac{2}{8} \log_2 \frac{2}{8} - \frac{3}{8} \log_2 \frac{3}{8} - \frac{3}{8} \log_2 \frac{3}{8} $$算一算$$ H_{A}(X2) 0.5 0.5306 0.5306 1.5612 $$增益比$$ g_R(D, X2) \frac{0.6556}{1.5612} 0.42 $$X3的固有值是3增益比$$ g_R(D, X3) \frac{1}{3} 0.3333 $$对比结果一目了然特征信息增益固有值增益比X10.18871.00000.1887X20.65561.56120.4200X3ID类1.00003.00000.3333ID3按信息增益会选X3C4.5按增益比会选X2。X2在三种渠道中确实携带了更多有意义的区分信息选它显然是更理智的。4.3 增益比的副作用从“偏爱多取值”变成“偏爱少取值”增益比不是免费的午餐。除以固有值之后惩罚方向反转了取值特别少的特征——尤其是二值特征——固有值小增益比容易被放大。极端情况下某个特征每个样本取值都不同信息增益是1增益比是1/3而一个只取两个值的特征就算信息增益只有0.4增益比也可能超过0.4。所以C4.5在实际实现里不是直接用增益比选特征而是先用信息增益过滤出一批“合格候选”再从这些候选中挑增益比最高的。这是一种工程上的折中最优解既要避免ID3对多取值的盲目偏向也不能反过来让取值少的特征轻松夺得头筹。我在这里放一句话后面工程部分还会用到高基数特征的偏好问题是决策树分裂准则设计中的核心矛盾C4.5只是缓解并没有根除。5. CART的Gini系数不纯度度量的另一种打开方式5.1 Gini系数的定义和二分类特例CART没有继续沿用熵而是换了一种不纯度度量Gini系数。它的定义是$$ \text{Gini}(p) \sum_k p_k (1 - p_k) 1 - \sum_k p_k^2 $$有一个很直观的概率解释从样本集里随机抽两个样本它们类别不一致的概率。全是同一类时概率为0最不纯时概率最大。注意这也是一个“期望”形式的度量和熵有异曲同工之处。二分类时设一个类别占比为 $p$另一个为 $1-p$$$ \text{Gini}(p) 2p(1-p) $$在集合D上用频率估计概率$$ \text{Gini}(D) 1 - \sum_{k1}^{K} \left( \frac{\lvert C_k \rvert}{\lvert D \rvert} \right)^2 $$按特征A分裂后的Gini指数还是老套路——子Gini按样本量加权平均$$ \text{Gini}(D, A) \sum_{i1}^{n} \frac{\lvert D_i \rvert}{\lvert D \rvert} \text{Gini}(D_i) $$CART每次选的是“让Gini指数最小”或者说让Gini下降最多的分裂方式。5.2 熵和Gini的近似关系从泰勒展开看为什么两种度量长得不太一样出来的树却往往差不多因为它们本质上是近亲。对熵的单类项 $-p \ln p$在 $p1$ 附近做一阶泰勒展开$$ -\ln p \approx 1 - p $$于是$$ -p \ln p \approx p(1-p) $$熵近似成了若干个 $p(1-p)$ 的和这正是Gini系数的形式。区别只是对数底数换算$\ln 2$带来的常数缩放。所以从数学近似角度看Gini系数相当于对熵做了一阶泰勒近似。这也是为什么你实际训练时换“entropy”还是“gini”往往对最终准确率影响很小——它们优化的目标函数在大多数区间内增减方向一致。5.3 手推Gini分裂结果和熵不一致在哪里还是那份8个样本的数据。初始Gini$$ \text{Gini}(D) 1 - \left(\frac{4}{8}\right)^2 - \left(\frac{4}{8}\right)^2 0.5 $$按X1分裂X10子集A3B1$$ \text{Gini}(D_{\text{X1}0}) 1 - \left(\frac{3}{4}\right)^2 - \left(\frac{1}{4}\right)^2 0.375 $$X11子集A1B3Gini同样0.375。加权$$ \text{Gini}(D, X1) \frac{4}{8} \times 0.375 \frac{4}{8} \times 0.375 0.375 $$按X2分裂X20子集全AGini为0X21子集A2B1$$ \text{Gini}(D_{\text{X2}1}) 1 - \left(\frac{2}{3}\right)^2 - \left(\frac{1}{3}\right)^2 \frac{4}{9} \approx 0.4444 $$X22子集全BGini为0。加权$$ \text{Gini}(D, X2) \frac{2}{8} \times 0 \frac{3}{8} \times \frac{4}{9} \frac{3}{8} \times 0 \frac{1}{6} \approx 0.1667 $$结果CART同样会选择X2作为根节点。而且因为CART只做二叉树那个“取值8个的ID特征”在二分切分时必须强制分成两组不会像ID3那样轻轻松松把条件熵降到0。这种树形结构上的限制进一步削弱了高基数特征的绝对优势。6. 连续特征与回归树的最小二乘分裂6.1 连续特征变成二分阈值排序、试切、比较现实数据里连续特征比离散特征更常见所以决策树面对的另一个核心问题是阈值怎么找做法很朴素先把特征x的所有取值排序然后取相邻两个值的中间点作为候选切分点逐个尝试找让分裂指标最优的阈值。比如候选点$$ s_i \frac{x_i x_{i1}}{2} $$分类树用Gini或熵评估回归树则用平方误差。为什么不需要试所有实数因为在一个区间内移动切分点只改变“哪些样本分到左边”的边界最优切分点一定会落在某个相邻样本取值之间取中间值就够了。6.2 为什么区域输出取均值最小二乘求导CART回归树把输入空间划分成若干区域 $R_1, R_2, \dots, R_M$每个区域的输出是一个常数 $c_m$。目标是让总平方误差最小$$ \min \sum_{m1}^{M} \sum_{x_i \in R_m} (y_i - c_m)^2 $$固定区域划分 $R_m$ 后最优 $c_m$ 怎么求对 $c_m$ 求导$$ \frac{\partial}{\partial c_m} \sum_{x_i \in R_m} (y_i - c_m)^2 -2 \sum_{x_i \in R_m} (y_i - c_m) $$令导数为0$$ \sum_{x_i \in R_m} y_i - n_m c_m 0 $$得到$$ c_m \frac{1}{n_m} \sum_{x_i \in R_m} y_i $$这就是区域样本的均值。所以“叶子节点输出均值”不是拍脑袋定的而是最小二乘下的最优解。6.3 6个样本的一维回归手推我另外构造一个6个样本的一维回归数据特征x和目标y如下x123456y1.51.82.25.15.66.0肉眼能看出数据大概分两段前三个在2附近后三个在5.5附近。候选切分点是1.5、2.5、3.5、4.5、5.5。我们逐个算平方误差。先把每个候选点的左右两侧最优输出算出来切分点 s1.5左区域只有样本1输出 $c_11.5$误差0右区域5个样本输出均值4.14误差约15.75。总误差15.75。切分点 s2.5左区域样本1和2均值1.65误差0.045右区域样本3~6均值4.725误差约8.91。总误差约8.95。切分点 s3.5左区域样本1~3均值 $5.5/3 \approx 1.8333$误差约0.247右区域样本4~6均值 $16.7/3 \approx 5.5667$误差约0.407。总误差约0.654。切分点 s4.5左区域样本1~4均值2.65误差约8.25右区域样本5和6均值5.8误差0.08。总误差约8.33。切分点 s5.5左区域样本1~5均值3.24误差约15.21右区域样本6误差0。总误差约15.21。汇总切分点左误差右误差总误差1.50.0015.7515.752.50.058.918.953.50.250.410.654.58.250.088.335.515.210.0015.21最优切分点在3.5总误差最小。分裂后左叶子输出1.8333右叶子输出5.5667完美还原了二段结构。这个手推过程其实就是回归树在每一层做的事遍历特征和切分点挑平方误差下降最大的一次分裂。7. 剪枝的数学代价C(T)α|T|怎么决定剪不剪7.1 损失函数的结构与α的语义树长得太深几乎必然过拟合。剪枝就是给树的复杂度上一把锁。CART后剪枝的损失函数结构非常优雅$$ C_{\alpha}(T) C(T) \alpha \lvert T \rvert $$其中 $C(T)$ 是训练误差分类树可以是误分类率或不纯度指标回归树是平方误差$\lvert T \rvert$ 是叶子节点数$\alpha$ 是复杂度惩罚系数。这个式子展示了“准确”和“简洁”的互换$\alpha$ 越大每多一个叶子节点付出的代价越高树越倾向被剪短$\alpha0$ 时完全不惩罚复杂度树可以肆无忌惮长满。7.2 g(t) 的推导和剪枝门槛对一个内部节点 $t$设它的子树为 $T_t$。剪枝前子树 $T_t$ 的损失$$ C_{\alpha}(T_t) C(T_t) \alpha \lvert T_t \rvert $$如果把这个节点直接变成叶子剪掉整棵子树损失$$ C_{\alpha}(t) C(t) \alpha $$什么时候该剪剪完之后的损失更小也就是$$ C(t) \alpha \le C(T_t) \alpha \lvert T_t \rvert $$移项$$ \alpha \ge \frac{C(t) - C(T_t)}{\lvert T_t \rvert - 1} $$于是定义每个内部节点的剪枝门槛$$ g(t) \frac{C(t) - C(T_t)}{\lvert T_t \rvert - 1} $$这个 $g(t)$ 的语义是要让“剪掉 $T_t$ 换成单叶子”这件事划算$\alpha$ 至少要达到这个值。$C(t) - C(T_t)$ 是剪掉后多出来的训练误差这部分是代价$\lvert T_t \rvert - 1$ 是省下的叶子节点数这部分是收益。两者相除就是“平均省一个叶子节点需要支付多少误差代价”。CART的剪枝策略是自底向上逐个算 $g(t)$先剪掉 $g(t)$ 最小也就是最容易达成剪枝条件的节点形成一组嵌套子树序列再通过交叉验证选最优的 $\alpha$ 和对应的子树。7.3 一个内部节点的剪枝手算实例假设某个内部节点 $t$直接当叶子时训练误差 $C(t)0.2$保留子树两个叶子节点时训练误差 $C(T_t)0.1$叶子数量 $\lvert T_t \rvert 2$。先算门槛$$ g(t) \frac{0.2 - 0.1}{2 - 1} 0.1 $$分别取两个 $\alpha$ 试一下当 $\alpha0.05$不剪$$ C_{\alpha}(T_t) 0.1 0.05 \times 2 0.2 $$剪掉$$ C_{\alpha}(t) 0.2 0.05 0.25 $$不剪更小说明此时保住低训练误差是划算的。当 $\alpha0.2$不剪$$ C_{\alpha}(T_t) 0.1 0.2 \times 2 0.5 $$剪掉$$ C_{\alpha}(t) 0.2 0.2 0.4 $$剪完更小应该剪。这也很直观地说明了一件事$\alpha$ 控制的就是你对模型复杂度的“嫌弃”程度。你越嫌弃叶子多就越要牺牲一点训练误差去换简洁结构。8. 公式落到工程特征重要性、超参数和实际踩坑8.1 特征重要性是怎么从分裂算出来的很多框架会直接给你feature_importances_但它的底层就是前面这套不纯度公式。某个特征 $j$ 的重要性是它在一棵树所有分裂节点上“不纯度下降量”的加权累加$$ \text{Importance}j \frac{\sum{t \in \text{nodes using } j} \frac{N_t}{N} \cdot \Delta \text{Impurity}t}{\sum{\text{all nodes}} \frac{N_t}{N} \cdot \Delta \text{Impurity}_t} $$其中 $N_t$ 是节点t的样本数$N$ 是根节点总样本数$\Delta \text{Impurity}_t$ 是分裂前后不纯度的下降量。最后归一化让所有特征重要度之和为1。这也解释了我开头提到的那个怪象高基数特征的重要度虚高。因为分类树会把高基数特征的切分点切得非常细每次分裂都带走一大块不纯度累加起来数值自然高。和ID3的信息增益偏好同一个根源。8.2 核心超参数对应的公式语义掌握了公式再看调参就非常通透。我用一个表格把常用超参数和数学含义对应起来超参数对应公式里的角色直观效果max_depth限制递归层数相当于强剪枝直接封顶复杂度min_samples_split限制可分裂节点的最小样本数样本太少的节点不分裂防止继续切噪声min_samples_leaf限制叶子最小样本数每个叶子必须有一定规模拟合曲线更平滑max_features每次分裂随机抽特征的个数增加随机性降低树与树之间相关性min_impurity_decrease分裂要求不纯度下降量阈值等价于给每次分裂设收益下限ccp_alpha前面剪枝公式里的 $\alpha$越小树越复杂越大树越简单你说min_samples_leaf为什么管用看公式就懂了。如果一个叶子只有1个样本那这个叶子所在分支对 $H(D|A)$ 的贡献几乎为0整条路径都是在记忆单个样本。设成5或10之后每个叶子至少要“代表”一批样本才被保留强迫树学出更一般化的规律。8.3 几个常见的“理解偏差”与个人建议最后聊几个我实际项目里反复遇到的坑。第一个坑Gini和entropy的区别没那么大。很多人纠结到底用哪个指标反复搜索“gini vs entropy”实际上在绝大多数数据集上两者最终准确率差距在0.5%以内。与其纠结指标不如把max_depth和min_samples_leaf调一遍。第二个坑特征重要性不要裸看。高基数的类别特征比如地区编码、渠道ID重要度容易被系统性抬高。如果你想拿重要度做特征筛选要么先对高基数特征做目标编码要么用随机置换检验permutation importance做交叉验证。第三个坑预剪枝在某些时候比后剪枝更实用。CART理论上的最小代价复杂度剪枝很优雅但工程上如果你用的是sklearnccp_alpha需要你自己扫描选择。相比之下先把max_depth限制在合理范围内再把min_samples_leaf调大往往几分钟就能拿到一个足够稳的基线模型。第四个坑类别不平衡会影响分裂方向。Gini和熵在计算时都在跟“多数类占比”较劲如果数据里B类只占5%初始不纯度里多数类占绝对主导树会倾向于切出更多A类区域。改损失权重往往比单纯调参会更有针对性。我自己现在带新人看决策树都会让他们先把这套公式在纸上走一遍尤其是把第3节那个8样本例子完整算一次。算完以后再去看feature_importances_或者调ccp_alpha心态完全不一样——你知道每个输出背后的数学在干什么而不是对着参数瞎猜。这种从公式到直觉的闭环才是学机器学习的正路。 
长河君 · 2026/10/16 12:30:27 · 阅读 1.2k 决策树算法核心：从信息熵到剪枝的公式推导与工程实践
很多人学决策树都卡在同一个地方图能看懂节点能画出来数据集一换自己也敢上手跑可真被问到“为什么这个特征排在最上面”“信息增益为什么不直接用准确率”“剪枝到底在剪什么”就开始支支吾吾。我当初也是这样所以专门抽了一个周末把决策树从ID3到CART的公式完整手推了一遍。这篇就是我推完之后留下的完整笔记每个关键公式都配了一个可以直接拿纸笔验算的小例子。这篇文章的定位很明确已经会调库训练决策树但想把“树为什么长这样”真正想明白的人。我会从信息熵的数学来源开始一路推到ID3的信息增益、C4.5的信息增益比、CART的Gini系数、连续特征分裂和剪枝代价最后再落到工程里的特征重要性和超参数语义。不需要你是数学系背景只要记得对数运算、期望、条件概率、简单求导就能跟着走完全程。1. 从“会调参”到“能手推”的距离1.1 为什么搞懂决策树必须过一遍公式调个决策树模型其实十分钟就够fit一下看一眼feature_importances_完事。但如果你不知道这些参数在优化什么遇到问题只能瞎试。比如为什么min_samples_leaf从1调到5树的准确率反而明显上升为什么同一个特征在A数据集上排在重要度第一在B数据集上几乎排不上号为什么对高基数离散特征比如用户ID做独热编码之后特征重要度会虚高为什么某些场景下CART比C4.5更不容易被高基数特征带偏这些问题只看API文档永远得不到答案。只有把公式推到“每个符号背后对应什么数据”的程度你才真正拥有解释一棵树的能力。这也是我给自己的硬性要求不靠记忆靠推导。1.2 手推需要的前置知识说句实话决策树公式的门槛不高比线性回归的矩阵求导友好多了。你只需要四样东西对数运算知道 $\log_2 0.5 -1$$\log_2 0.25 -2$ 这种程度即可。期望熵本质就是一个期望值也就是“加权重平均”。条件概率$P(y|x)$ 或者说“某个子集里各类别占比”。一元求导回归树里求最优输出值时用一下。如果你这些概念看着眼熟但有点生疏完全不影响阅读。我会在推导到每一步时把含义拆开讲。1.3 整篇文章统一使用的例子为了不让每个公式都搞一套新数据我直接构造一个8个样本的小数据集后面所有计算都围着它转。假设我们要预测用户会不会产生二次购买行为总共有两个特征X1是否看过活动页0/1二值X2注册渠道类型0/1/2三种取值标签A代表会复购B代表不会复购。样本如下样本X1X2标签100A200A301A402B511A612B712B811B先做一个快速统计方便后面算标签A类4个B类4个。X104个样本A3个B1个X114个样本A1个B3个。X202个样本全是AX213个样本A2个B1个X223个样本全是B。好了数据固定。接下来所有的分裂准则都会在这个数据集上跑一遍。2. 信息熵从哪来可加性、联合熵与条件熵2.1 信息量的可加性锁定了对数函数信息熵的公式长这样$$ H(X) -\sum_{i} P(x_i) \log_2 P(x_i) $$很多人背得滚瓜烂熟但没想过一个问题为什么偏偏是对数答案是“可加性”。设想你收到一个消息明天有雨地铁停运。这件事包含的信息量应该等于“明天有雨”的信息量加上“地铁停运”的信息量。如果把“明天有雨”记作 $x$“地铁停运”记作 $y$那就是$$ I(x, y) I(x) I(y) $$如果 $x$ 和 $y$ 相互独立联合发生的概率是 $P(x,y) P(x)P(y)$。那么什么样的“信息量函数”能同时满足相乘的概率变成相加的信息量只有对数函数$$ I(x) -\log_b P(x) $$底数取2是因为二进制编码里每个比特恰好对应“二选一”的不确定性信息量单位就是比特。一个概率为0.5的事件信息量是1比特一个概率为0.25的事件信息量是2比特。熵就是随机变量所有可能取值的“信息量期望”$$ H(X) \sum_i P(x_i) I(x_i) -\sum_i P(x_i) \log_2 P(x_i) $$换个角度说熵度量的是一个分布的平均不确定度。分布越均匀、各类概率越接近熵越大分布越偏、某个类概率接近1不确定性越小熵越小。2.2 联合熵到条件熵的一条链决策树分裂要看“知道某个特征之后标签的不确定性下降多少”这就必须用到条件熵。$H(Y|X)$ 的定义是在已知X取值的前提下Y还剩下多少平均不确定度。先看在X取具体值 $x_i$ 时Y的条件熵$$ H(Y \mid X x_i) -\sum_j P(y_j \mid x_i) \log_2 P(y_j \mid x_i) $$再把所有X取值按概率加权平均$$ H(Y \mid X) \sum_i P(x_i) H(Y \mid X x_i) $$这个式子写开后其实等价于联合熵减掉 $H(X)$。我来完整演算一遍$$ \begin{aligned} H(X, Y) -\sum_{i,j} P(x_i, y_j) \log_2 P(x_i, y_j) \ -\sum_{i,j} P(x_i, y_j) \log_2 \left[ P(x_i) P(y_j \mid x_i) \right] \ -\sum_{i,j} P(x_i, y_j) \log_2 P(x_i) - \sum_{i,j} P(x_i, y_j) \log_2 P(y_j \mid x_i) \ -\sum_i P(x_i) \log_2 P(x_i) \sum_i P(x_i) \left[ -\sum_j P(y_j \mid x_i) \log_2 P(y_j \mid x_i) \right] \ H(X) H(Y \mid X) \end{aligned} $$所以$$ H(Y \mid X) H(X, Y) - H(X) $$这个关系式特别重要。它说明条件熵是“X和Y联合起来的不确定性”减去“X本身的不确定性”剩下的就是Y里跟X无关的那部分不确定性。2.3 先用8个样本把熵算一遍回到我们的示例数据。先算标签D的经验熵。经验熵就是用频率代替概率直接数数$$ H(D) -\frac{4}{8} \log_2 \frac{4}{8} - \frac{4}{8} \log_2 \frac{4}{8} 1 $$4个A、4个B完美对半开熵正好取到最大值1比特。后面我们看任何一个特征只要能把这两种标签分开一点点条件熵就会小于1信息增益就会大于0。3. ID3的信息增益第一次把“纯度”变成数字3.1 信息增益公式的本质不确定性减少量ID3算法的分裂准则就是信息增益。公式$$ g(D, A) H(D) - H(D \mid A) $$翻译成人话分裂前整个数据集有 $H(D)$ 的不确定性按特征A分成几个子集之后平均不确定性降到了 $H(D|A)$。降下去的那部分就是从A身上获得的信息量。计算时用频率估计概率$$ H(D \mid A) \sum_{i1}^{n} \frac{\lvert D_i \rvert}{\lvert D \rvert} H(D_i) $$其中 $D_i$ 是按特征A第i个取值切出来的子集$H(D_i)$ 是子集内部的经验熵。3.2 三个特征的手推对比先算按X1分裂X10的4个样本里A3个B1个$$ H(D_{\text{X1}0}) -\frac{3}{4} \log_2 \frac{3}{4} - \frac{1}{4} \log_2 \frac{1}{4} 0.8113 $$X11的4个样本里A1个B3个熵同样$$ H(D_{\text{X1}1}) 0.8113 $$条件熵$$ H(D \mid X1) \frac{4}{8} \times 0.8113 \frac{4}{8} \times 0.8113 0.8113 $$信息增益$$ g(D, X1) 1 - 0.8113 0.1887 $$再算按X2分裂X20有2个样本全是A熵是0。X21有3个样本A2个B1个$$ H(D_{\text{X2}1}) -\frac{2}{3} \log_2 \frac{2}{3} - \frac{1}{3} \log_2 \frac{1}{3} 0.9183 $$X22有3个样本全是B熵也是0。条件熵$$ H(D \mid X2) \frac{2}{8} \times 0 \frac{3}{8} \times 0.9183 \frac{3}{8} \times 0 0.3444 $$信息增益$$ g(D, X2) 1 - 0.3444 0.6556 $$现在假设还有一个特征X3它是每个样本唯一的“消息ID”。X3有8个不同取值每个取值只对应1个样本所以每个子集都只剩一个类别子集熵全是0。条件熵$$ H(D \mid X3) \sum_{i1}^{8} \frac{1}{8} \times 0 0 $$信息增益直接拉到最大值$$ g(D, X3) 1 $$ID3会满心欢喜地选X3作为根节点分裂特征。3.3 多取值特征为什么会让信息增益失真看到这里问题已经很清楚了X3把每个样本都单独切成一个节点训练集上熵降到0增益达到1比特完美。但它对未见过的样本毫无泛化能力——新样本根本不会和你训练集里任何一个样本共享ID取值。这就是信息增益的固有缺陷它无条件地奖励“取值多”的特征。取值越多切出的子集越细每个子集越可能纯条件熵就越低。这属于典型的过拟合信号。这个问题在数学上叫“多值特征偏好”ID3算法没有做任何惩罚所以实际使用中容易被那种高基数的ID类特征带偏。也正是这个缺陷直接催生了C4.5的信息增益比。4. C4.5的信息增益比增益除以固有值纠正了什么4.1 固有值 HA(D) 到底在衡量什么C4.5做了一件很朴素的事把信息增益除以一个“特征自身熵值”也就是固有值intrinsic value$$ g_R(D, A) \frac{g(D, A)}{H_A(D)} $$其中$$ H_A(D) -\sum_{i1}^{n} \frac{\lvert D_i \rvert}{\lvert D \rvert} \log_2 \frac{\lvert D_i \rvert}{\lvert D \rvert} $$这个式子把“特征A取值分布”的熵单独算了一遍。它的含义是如果特征A取值越多、越分散$H_A(D)$ 就越大信息增益除以它以后就会被压得越低。回到我们的直觉X3有8个取值每个取值占比1/8$H_A(D)$ 等于 $\log_2 8 3$。这对一个三分支特征来说惩罚非常重。4.2 同一份数据上计算增益比X1是二值特征两个取值各4个样本$$ H_{A}(X1) -\frac{4}{8} \log_2 \frac{4}{8} - \frac{4}{8} \log_2 \frac{4}{8} 1 $$增益比$$ g_R(D, X1) \frac{0.1887}{1} 0.1887 $$X2是三分支特征取值占比分别是2/8、3/8、3/8$$ H_{A}(X2) -\frac{2}{8} \log_2 \frac{2}{8} - \frac{3}{8} \log_2 \frac{3}{8} - \frac{3}{8} \log_2 \frac{3}{8} $$算一算$$ H_{A}(X2) 0.5 0.5306 0.5306 1.5612 $$增益比$$ g_R(D, X2) \frac{0.6556}{1.5612} 0.42 $$X3的固有值是3增益比$$ g_R(D, X3) \frac{1}{3} 0.3333 $$对比结果一目了然特征信息增益固有值增益比X10.18871.00000.1887X20.65561.56120.4200X3ID类1.00003.00000.3333ID3按信息增益会选X3C4.5按增益比会选X2。X2在三种渠道中确实携带了更多有意义的区分信息选它显然是更理智的。4.3 增益比的副作用从“偏爱多取值”变成“偏爱少取值”增益比不是免费的午餐。除以固有值之后惩罚方向反转了取值特别少的特征——尤其是二值特征——固有值小增益比容易被放大。极端情况下某个特征每个样本取值都不同信息增益是1增益比是1/3而一个只取两个值的特征就算信息增益只有0.4增益比也可能超过0.4。所以C4.5在实际实现里不是直接用增益比选特征而是先用信息增益过滤出一批“合格候选”再从这些候选中挑增益比最高的。这是一种工程上的折中最优解既要避免ID3对多取值的盲目偏向也不能反过来让取值少的特征轻松夺得头筹。我在这里放一句话后面工程部分还会用到高基数特征的偏好问题是决策树分裂准则设计中的核心矛盾C4.5只是缓解并没有根除。5. CART的Gini系数不纯度度量的另一种打开方式5.1 Gini系数的定义和二分类特例CART没有继续沿用熵而是换了一种不纯度度量Gini系数。它的定义是$$ \text{Gini}(p) \sum_k p_k (1 - p_k) 1 - \sum_k p_k^2 $$有一个很直观的概率解释从样本集里随机抽两个样本它们类别不一致的概率。全是同一类时概率为0最不纯时概率最大。注意这也是一个“期望”形式的度量和熵有异曲同工之处。二分类时设一个类别占比为 $p$另一个为 $1-p$$$ \text{Gini}(p) 2p(1-p) $$在集合D上用频率估计概率$$ \text{Gini}(D) 1 - \sum_{k1}^{K} \left( \frac{\lvert C_k \rvert}{\lvert D \rvert} \right)^2 $$按特征A分裂后的Gini指数还是老套路——子Gini按样本量加权平均$$ \text{Gini}(D, A) \sum_{i1}^{n} \frac{\lvert D_i \rvert}{\lvert D \rvert} \text{Gini}(D_i) $$CART每次选的是“让Gini指数最小”或者说让Gini下降最多的分裂方式。5.2 熵和Gini的近似关系从泰勒展开看为什么两种度量长得不太一样出来的树却往往差不多因为它们本质上是近亲。对熵的单类项 $-p \ln p$在 $p1$ 附近做一阶泰勒展开$$ -\ln p \approx 1 - p $$于是$$ -p \ln p \approx p(1-p) $$熵近似成了若干个 $p(1-p)$ 的和这正是Gini系数的形式。区别只是对数底数换算$\ln 2$带来的常数缩放。所以从数学近似角度看Gini系数相当于对熵做了一阶泰勒近似。这也是为什么你实际训练时换“entropy”还是“gini”往往对最终准确率影响很小——它们优化的目标函数在大多数区间内增减方向一致。5.3 手推Gini分裂结果和熵不一致在哪里还是那份8个样本的数据。初始Gini$$ \text{Gini}(D) 1 - \left(\frac{4}{8}\right)^2 - \left(\frac{4}{8}\right)^2 0.5 $$按X1分裂X10子集A3B1$$ \text{Gini}(D_{\text{X1}0}) 1 - \left(\frac{3}{4}\right)^2 - \left(\frac{1}{4}\right)^2 0.375 $$X11子集A1B3Gini同样0.375。加权$$ \text{Gini}(D, X1) \frac{4}{8} \times 0.375 \frac{4}{8} \times 0.375 0.375 $$按X2分裂X20子集全AGini为0X21子集A2B1$$ \text{Gini}(D_{\text{X2}1}) 1 - \left(\frac{2}{3}\right)^2 - \left(\frac{1}{3}\right)^2 \frac{4}{9} \approx 0.4444 $$X22子集全BGini为0。加权$$ \text{Gini}(D, X2) \frac{2}{8} \times 0 \frac{3}{8} \times \frac{4}{9} \frac{3}{8} \times 0 \frac{1}{6} \approx 0.1667 $$结果CART同样会选择X2作为根节点。而且因为CART只做二叉树那个“取值8个的ID特征”在二分切分时必须强制分成两组不会像ID3那样轻轻松松把条件熵降到0。这种树形结构上的限制进一步削弱了高基数特征的绝对优势。6. 连续特征与回归树的最小二乘分裂6.1 连续特征变成二分阈值排序、试切、比较现实数据里连续特征比离散特征更常见所以决策树面对的另一个核心问题是阈值怎么找做法很朴素先把特征x的所有取值排序然后取相邻两个值的中间点作为候选切分点逐个尝试找让分裂指标最优的阈值。比如候选点$$ s_i \frac{x_i x_{i1}}{2} $$分类树用Gini或熵评估回归树则用平方误差。为什么不需要试所有实数因为在一个区间内移动切分点只改变“哪些样本分到左边”的边界最优切分点一定会落在某个相邻样本取值之间取中间值就够了。6.2 为什么区域输出取均值最小二乘求导CART回归树把输入空间划分成若干区域 $R_1, R_2, \dots, R_M$每个区域的输出是一个常数 $c_m$。目标是让总平方误差最小$$ \min \sum_{m1}^{M} \sum_{x_i \in R_m} (y_i - c_m)^2 $$固定区域划分 $R_m$ 后最优 $c_m$ 怎么求对 $c_m$ 求导$$ \frac{\partial}{\partial c_m} \sum_{x_i \in R_m} (y_i - c_m)^2 -2 \sum_{x_i \in R_m} (y_i - c_m) $$令导数为0$$ \sum_{x_i \in R_m} y_i - n_m c_m 0 $$得到$$ c_m \frac{1}{n_m} \sum_{x_i \in R_m} y_i $$这就是区域样本的均值。所以“叶子节点输出均值”不是拍脑袋定的而是最小二乘下的最优解。6.3 6个样本的一维回归手推我另外构造一个6个样本的一维回归数据特征x和目标y如下x123456y1.51.82.25.15.66.0肉眼能看出数据大概分两段前三个在2附近后三个在5.5附近。候选切分点是1.5、2.5、3.5、4.5、5.5。我们逐个算平方误差。先把每个候选点的左右两侧最优输出算出来切分点 s1.5左区域只有样本1输出 $c_11.5$误差0右区域5个样本输出均值4.14误差约15.75。总误差15.75。切分点 s2.5左区域样本1和2均值1.65误差0.045右区域样本3~6均值4.725误差约8.91。总误差约8.95。切分点 s3.5左区域样本1~3均值 $5.5/3 \approx 1.8333$误差约0.247右区域样本4~6均值 $16.7/3 \approx 5.5667$误差约0.407。总误差约0.654。切分点 s4.5左区域样本1~4均值2.65误差约8.25右区域样本5和6均值5.8误差0.08。总误差约8.33。切分点 s5.5左区域样本1~5均值3.24误差约15.21右区域样本6误差0。总误差约15.21。汇总切分点左误差右误差总误差1.50.0015.7515.752.50.058.918.953.50.250.410.654.58.250.088.335.515.210.0015.21最优切分点在3.5总误差最小。分裂后左叶子输出1.8333右叶子输出5.5667完美还原了二段结构。这个手推过程其实就是回归树在每一层做的事遍历特征和切分点挑平方误差下降最大的一次分裂。7. 剪枝的数学代价C(T)α|T|怎么决定剪不剪7.1 损失函数的结构与α的语义树长得太深几乎必然过拟合。剪枝就是给树的复杂度上一把锁。CART后剪枝的损失函数结构非常优雅$$ C_{\alpha}(T) C(T) \alpha \lvert T \rvert $$其中 $C(T)$ 是训练误差分类树可以是误分类率或不纯度指标回归树是平方误差$\lvert T \rvert$ 是叶子节点数$\alpha$ 是复杂度惩罚系数。这个式子展示了“准确”和“简洁”的互换$\alpha$ 越大每多一个叶子节点付出的代价越高树越倾向被剪短$\alpha0$ 时完全不惩罚复杂度树可以肆无忌惮长满。7.2 g(t) 的推导和剪枝门槛对一个内部节点 $t$设它的子树为 $T_t$。剪枝前子树 $T_t$ 的损失$$ C_{\alpha}(T_t) C(T_t) \alpha \lvert T_t \rvert $$如果把这个节点直接变成叶子剪掉整棵子树损失$$ C_{\alpha}(t) C(t) \alpha $$什么时候该剪剪完之后的损失更小也就是$$ C(t) \alpha \le C(T_t) \alpha \lvert T_t \rvert $$移项$$ \alpha \ge \frac{C(t) - C(T_t)}{\lvert T_t \rvert - 1} $$于是定义每个内部节点的剪枝门槛$$ g(t) \frac{C(t) - C(T_t)}{\lvert T_t \rvert - 1} $$这个 $g(t)$ 的语义是要让“剪掉 $T_t$ 换成单叶子”这件事划算$\alpha$ 至少要达到这个值。$C(t) - C(T_t)$ 是剪掉后多出来的训练误差这部分是代价$\lvert T_t \rvert - 1$ 是省下的叶子节点数这部分是收益。两者相除就是“平均省一个叶子节点需要支付多少误差代价”。CART的剪枝策略是自底向上逐个算 $g(t)$先剪掉 $g(t)$ 最小也就是最容易达成剪枝条件的节点形成一组嵌套子树序列再通过交叉验证选最优的 $\alpha$ 和对应的子树。7.3 一个内部节点的剪枝手算实例假设某个内部节点 $t$直接当叶子时训练误差 $C(t)0.2$保留子树两个叶子节点时训练误差 $C(T_t)0.1$叶子数量 $\lvert T_t \rvert 2$。先算门槛$$ g(t) \frac{0.2 - 0.1}{2 - 1} 0.1 $$分别取两个 $\alpha$ 试一下当 $\alpha0.05$不剪$$ C_{\alpha}(T_t) 0.1 0.05 \times 2 0.2 $$剪掉$$ C_{\alpha}(t) 0.2 0.05 0.25 $$不剪更小说明此时保住低训练误差是划算的。当 $\alpha0.2$不剪$$ C_{\alpha}(T_t) 0.1 0.2 \times 2 0.5 $$剪掉$$ C_{\alpha}(t) 0.2 0.2 0.4 $$剪完更小应该剪。这也很直观地说明了一件事$\alpha$ 控制的就是你对模型复杂度的“嫌弃”程度。你越嫌弃叶子多就越要牺牲一点训练误差去换简洁结构。8. 公式落到工程特征重要性、超参数和实际踩坑8.1 特征重要性是怎么从分裂算出来的很多框架会直接给你feature_importances_但它的底层就是前面这套不纯度公式。某个特征 $j$ 的重要性是它在一棵树所有分裂节点上“不纯度下降量”的加权累加$$ \text{Importance}j \frac{\sum{t \in \text{nodes using } j} \frac{N_t}{N} \cdot \Delta \text{Impurity}t}{\sum{\text{all nodes}} \frac{N_t}{N} \cdot \Delta \text{Impurity}_t} $$其中 $N_t$ 是节点t的样本数$N$ 是根节点总样本数$\Delta \text{Impurity}_t$ 是分裂前后不纯度的下降量。最后归一化让所有特征重要度之和为1。这也解释了我开头提到的那个怪象高基数特征的重要度虚高。因为分类树会把高基数特征的切分点切得非常细每次分裂都带走一大块不纯度累加起来数值自然高。和ID3的信息增益偏好同一个根源。8.2 核心超参数对应的公式语义掌握了公式再看调参就非常通透。我用一个表格把常用超参数和数学含义对应起来超参数对应公式里的角色直观效果max_depth限制递归层数相当于强剪枝直接封顶复杂度min_samples_split限制可分裂节点的最小样本数样本太少的节点不分裂防止继续切噪声min_samples_leaf限制叶子最小样本数每个叶子必须有一定规模拟合曲线更平滑max_features每次分裂随机抽特征的个数增加随机性降低树与树之间相关性min_impurity_decrease分裂要求不纯度下降量阈值等价于给每次分裂设收益下限ccp_alpha前面剪枝公式里的 $\alpha$越小树越复杂越大树越简单你说min_samples_leaf为什么管用看公式就懂了。如果一个叶子只有1个样本那这个叶子所在分支对 $H(D|A)$ 的贡献几乎为0整条路径都是在记忆单个样本。设成5或10之后每个叶子至少要“代表”一批样本才被保留强迫树学出更一般化的规律。8.3 几个常见的“理解偏差”与个人建议最后聊几个我实际项目里反复遇到的坑。第一个坑Gini和entropy的区别没那么大。很多人纠结到底用哪个指标反复搜索“gini vs entropy”实际上在绝大多数数据集上两者最终准确率差距在0.5%以内。与其纠结指标不如把max_depth和min_samples_leaf调一遍。第二个坑特征重要性不要裸看。高基数的类别特征比如地区编码、渠道ID重要度容易被系统性抬高。如果你想拿重要度做特征筛选要么先对高基数特征做目标编码要么用随机置换检验permutation importance做交叉验证。第三个坑预剪枝在某些时候比后剪枝更实用。CART理论上的最小代价复杂度剪枝很优雅但工程上如果你用的是sklearnccp_alpha需要你自己扫描选择。相比之下先把max_depth限制在合理范围内再把min_samples_leaf调大往往几分钟就能拿到一个足够稳的基线模型。第四个坑类别不平衡会影响分裂方向。Gini和熵在计算时都在跟“多数类占比”较劲如果数据里B类只占5%初始不纯度里多数类占绝对主导树会倾向于切出更多A类区域。改损失权重往往比单纯调参会更有针对性。我自己现在带新人看决策树都会让他们先把这套公式在纸上走一遍尤其是把第3节那个8样本例子完整算一次。算完以后再去看feature_importances_或者调ccp_alpha心态完全不一样——你知道每个输出背后的数学在干什么而不是对着参数瞎猜。这种从公式到直觉的闭环才是学机器学习的正路。