2.8 决策树

1.决策树到底是什么：一串看得见的if-else

说起来，前面几章我们聊的都是神经网络，参数动不动上百万、上千万，模型像一只黑箱，输入进去输出出来，里头到底怎么决定的，人很难一眼看明白。这一章我们换一个脾气完全相反的模型，叫决策树。

决策树这东西，说穿了就是一串if-else规则，对数据层层划分，最后长成一棵倒过来的树。它从根节点开始，每个内部节点挑一个特征做判断（比如月收入是否高于8000），根据不同的回答走到不同的分支，这么一层层问下去，走到叶子节点就给出结论。叶子节点要么是一个类别（比如批准贷款或者拒绝贷款），要么是一个数值（比如预测这套房子卖多少钱）。根节点和内部节点负责提问，叶子节点负责给答案，结构十分清爽。

这模型最大的好处是直观可解释。把它画在纸上，从根走到叶子的每一条路径，都是一条人能读懂的规则。业务方站在你旁边，你指着树说这位客户因为月收入不到8000且信用记录有一笔逾期所以系统拒了，对方立刻就能明白。这种可解释性，在很多对合规和审计有要求的行业里（比如金融、医疗）特别吃香，监管要求你说清楚模型为啥这么判，决策树天然就站在有利那一边。

我之前翻过一本讲机器学习的书，周志华老师那本被大家叫做西瓜书，里头就用挑西瓜做例子。敲一敲声音清不清脆、根蒂够不够蜷、纹理是清晰还是模糊，一层层判断下来决定这瓜是好瓜还是坏瓜。这例子格外贴切，决策树本质上就是在模仿人做判断的那套流程，把一个老练挑瓜师傅脑子里的经验，原样搬到一棵树上来。

2.怎么挑特征做划分：三个流派

那么问题就来了，每一个节点到底该挑哪个特征来划分呢？这就是决策树算法的核心。不同的挑法，对应了三个经典的算法流派，分别是ID3、C4.5和CART。

ID3：信息增益，沿着熵下降最快的方向走

ID3是最早的一批决策树算法，它用的是信息增益。信息增益联系到1.4 节讲过的熵。熵记作 $H(D)$ ，其中 $D$ 是当前这一堆样本， $H$ 就是熵这个函数。熵衡量的是这一堆样本里类别有多乱，越乱熵越高，越纯熵越低。熵的定义是这样的：

H(D) = -\sum_{k=1}^{K} p_k \log_2 p_k

其中 $K$ 是类别的总数， $p_k$ 表示第 $k$ 类样本在 $D$ 里占的比例， $\log_2$ 是以2为底的对数。如果 $D$ 里所有样本都属于同一类，熵就是0，最纯。如果各类各占一半，熵达到最大，最乱。我们还记得1.4 节里强调的那句话吧，熵越小，不确定性越小。

如果用特征 $A$ 把 $D$ 划分成若干份，划分后每一份的熵加权平均一下，就得到条件熵 $H(D|A)$ ，其中 $A$ 是用来划分的特征。信息增益 $g(D,A)$ 就是划分前后熵的减少量：

g(D,A) = H(D) - H(D|A)

$g(D,A)$ 越大，说明用 $A$ 划分之后，样本整体变得更纯了，不确定性下降得越多。ID3的做法很直接，每一个节点都遍历所有可用的特征，挑信息增益最大的那个来划分。

我举个带数字的小例子。假设我们要决定今天要不要带伞，收集了10天的记录，其中4天带了伞、6天没带。先算原来的熵：

H(D) = -\frac{4}{10}\log_2\frac{4}{10} - \frac{6}{10}\log_2\frac{6}{10} \approx 0.97

现在用是否下雨这个特征来划分。下雨的5天里，4天带了伞、1天没带。不下雨的5天里，全都没带。先算两份各自的熵，下雨那一份是：

-\frac{4}{5}\log_2\frac{4}{5} - \frac{1}{5}\log_2\frac{1}{5} \approx 0.72

不下雨那一份全是没带的，熵为0。加权平均的条件熵就是 $H(D|A) = \frac{5}{10}\times 0.72 + \frac{5}{10}\times 0 = 0.36$ 。信息增益 $g(D,A) = 0.97 - 0.36 = 0.61$ 。

这个增益相当大，说明是否下雨这个特征对要不要带伞几乎一锤定音。这也很符合直觉，下雨天才带伞嘛。

C4.5：信息增益比，纠一纠ID3的偏心

ID3有个明显的毛病，它偏向取值多的特征。举个极端例子，如果把日期当作一个特征，每一天的取值都不一样，按日期一分，每一份里只有一个样本，纯得不能再纯，信息增益接近最大。可这棵树背下来日期却毫无泛化能力，遇到新的一天它就傻眼了。

C4.5为了纠正这个偏心，改用信息增益比。信息增益比 $g_R(D,A)$ 定义为信息增益除以一个校正项：

g_R(D,A) = \frac{g(D,A)}{H_A(D)}

分母 $H_A(D)$ 叫做特征 $A$ 的固有值，它衡量的是特征 $A$ 本身取值的均匀程度：

H_A(D) = -\sum_{i=1}^{n}\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|}

其中 $n$ 是特征 $A$ 取值的个数， $|D_i|$ 是取第 $i$ 个值的样本数， $|D|$ 是总样本数。 $A$ 取值越多、分得越均匀， $H_A(D)$ 就越大，拿它做分母一除，就把那种靠取值多占便宜的特征压下去了。这一手修正在工程上很管用，处理类似编号、日期这种高基数特征的时候，C4.5明显比ID3稳。

CART：基尼指数，算起来更省事

CART（Classification and Regression Tree，分类与回归树）是工程上用得最多的一个。它对分类任务用基尼指数，对回归任务用平方误差。基尼指数 $Gini(D)$ 的定义是这样的：

Gini(D) = 1 - \sum_{k=1}^{K}p_k^2

其中 $K$ 还是类别总数， $p_k$ 是第 $k$ 类的比例。基尼指数和数据集的纯度也呈反向关系，越纯基尼越小。它和熵想表达的东西几乎一样，但它不算对数，只算平方，计算上便宜得多，建树的时候速度更快。CART每个节点都挑让划分后基尼指数最小的那个特征和切分点。

值得一提的是，CART不仅做分类，还能做回归。回归树用平方误差当划分标准，把叶子节点里所有样本的目标值取个平均作为预测，划分时挑让左右两份的平方误差之和最小的那个切点。这思路和1.3 节里讲L2范数（也就是平方误差的根）是一脉相承的，最小化平方误差就等于让叶子的预测贴近这片样本目标值的平均（均值）。

CART还有个特点，它生成的是二叉树，每个节点只做是或否的二元判断。这样一来每次划分只问一个问题，树长得清爽，决策边界也更规整。scikit-learn里那个DecisionTreeClassifier，默认走的就是CART这条路。

3.剪枝：别让树死记硬背

决策树有个让人头疼的脾气，要是由着它长，它能把训练数据背得滚瓜烂熟。每片叶子只盖一两个样本的树，对训练集来说精度百分之百，可换个新数据进来，错得让你怀疑人生。这就是典型的过拟合。

为什么会这样呢？因为树的深度越深，每一片叶子覆盖的样本越少，划分出来的规则就越具体、越针对训练集里的偶然性，模型把噪声当成了规律。

我记得有一次，小张兴冲冲地拿一棵没限制深度的决策树去预测电商用户的流失，训练集准确率99%，一上测试集直接掉到65%，他还以为是特征没做够，折腾两天才明白是树把训练集里那点巧合全背下来了。这就是过拟合最典型的样子。

控制这种倾向的办法叫剪枝，分两类。一类叫预剪枝，意思是树还没长完就先拦着。常见的限制有最大深度（树最多长几层）、叶子节点最少样本数（一片叶子至少要盖几个样本）、节点最少样本数（一个节点想要继续划分至少得有多少样本）。这些参数一卡，树就没法无限细分下去。

另一类叫后剪枝，做法相反，先让树长满，再回头从叶子往上回砍。砍的时候看一棵子树被替换成单个叶子节点之后，在验证集上的表现是不是变好了，变好了就砍掉。后剪枝通常比预剪枝更稳，但要把大树先长出来，计算开销也更大。

实际工程里，预剪枝用得更多一些，因为它边长边卡，省时省力。要是真想榨干那一点点精度，再叠加后剪枝也来得及。两套办法也可以混着用，先把明显失控的长枝条预剪掉，再用后剪枝细修一遍。

优点有这么几条。第一，可解释性极强，前面说过，画出来人就能看懂，业务方和监管都买账。第二，能同时处理类别特征（比如性别、职业）和数值特征（比如收入、年龄），不用像神经网络那样先做一大堆编码。第三，对异常值比较稳，决策树按阈值切分，离群点只落进某一个区间，划分规则不会因为一两个离群点就被带偏太多。至于缺失值，原版的ID3和CART并不原生处理，遇到缺失需要借助C4.5的专门机制或在工程实现里加一条默认分支，不能笼统说它皮实。

缺点也得说清楚。第一，单棵树稳定性差。训练数据稍微动一下，挑出来的根节点特征就可能换了一个，整棵树的结构都跟着变。这种不稳定性使得单棵决策树在精度上往往比不过集成方法。第二，决策边界是轴对齐的阶梯状（因为按特征阈值一层层切），对一些斜着分布的类别分得不太利索。要表达复杂的边界，树就得长得很深，又容易过拟合。

正因为单棵树有这些短板，工程上几乎不直接拿一棵决策树上线，而是把它作为基学习器组合起来用。这就是下一章我们要聊的集成方法，Bagging、随机森林、Boosting、XGBoost、LightGBM、CatBoost这些耳熟能详的名字，其实都建立在决策树之上。把决策树这一章吃透了，后面这几位大佬的原理也就好懂了一大半。

5.两个真实场景里的影子

最后讲两个生活里的场景，帮大家把决策树的形象立起来。

第一个是银行贷款审批。一家银行要不要给一位申请人放贷，传统做法就是信贷员看材料做判断，这其实和决策树是一回事。一位申请人月薪1万2、信用历史5年无逾期、负债比不到30%、在本职岗位工作6年，系统沿着树一层层走：先看月收入是否过线（1万2过了），再看信用历史有没有严重逾期（没有），再看负债比是否合理（合理），最后叶子节点给出批准的结论。信贷员把这个判断逻辑画成决策树，每条审批路径都一清二楚，监管来检查也讲得明明白白。

第二个是医生看病。一位发热咳嗽的病人来了，医生脑子里其实也在走一棵决策树。先问发热多少天，再听肺有没有啰音，再看血常规白细胞高不高、淋巴比例如何，一步步排除流感、普通感冒、肺炎、肺结核。小说里写过的那些老中医，望闻问切四诊合参，走的也是层层划分的思路，每一步根据一个特征往下走。医生之所以能讲清楚诊断依据，正是因为他脑子里的判断路径是一棵可以画出来的树。当然真正的临床决策远比决策树复杂，但作为入门模型，决策树抓住了层层排除、逐步缩小可能性这个核心。

今天就先到这儿，下一章我们聊集成学习，把决策树凑成一支队伍，再见。

练习

Q1. ID3、C4.5、CART 三个决策树算法在"怎么挑划分特征"这件事上分别用什么标准，各自的脾气是什么？

ID3 用信息增益，挑让划分后熵下降最多的特征；C4.5 用信息增益比（信息增益除以特征的固有值），专门压住 ID3 偏向取值多特征的毛病；CART 分类用基尼指数、回归用平方误差，挑让划分后不纯度最小的特征。CART 因为不算对数只算平方，建树更快，而且生成的是二叉树。

Q2. 某节点有 10 个样本，其中 4 个正例、6 个负例。请手算它的熵 $H(D)$ 和基尼指数 $Gini(D)$ 。

熵 $H(D)=-\frac{4}{10}\log_2\frac{4}{10}-\frac{6}{10}\log_2\frac{6}{10}\approx 0.97$ 。基尼指数 $Gini(D)=1-(\frac{4}{10})^2-(\frac{6}{10})^2=1-0.16-0.36=0.48$ 。两者都衡量纯度，越纯越小；基尼不算对数所以计算更便宜。

Q3. 决策树为什么特别容易过拟合？预剪枝和后剪枝分别怎么治这个毛病？

决策树由着它长，会把每个叶子盖到极少的样本上，把训练集里的偶然性甚至噪声都背下来，所以训练集准但测试集垮。预剪枝是边长边卡，限制最大深度、叶子最少样本数等参数；后剪枝是先长满再从叶子往上回砍，看砍掉某棵子树后验证集是否变好。工程上预剪枝用得更多，省时省力。

Q4.（面试题） 如果把"样本编号"当作一个特征喂给 ID3，会发生什么？C4.5 又会怎样？这说明什么？

样本编号每个值只对应一个样本，按它一划分，每个子集都只有一个样本、熵全为 0，信息增益几乎拉满，ID3 会优先选它，结果树把编号背得滚瓜烂熟却毫无泛化能力。C4.5 用信息增益比，分母（固有值）会因为编号取值极多而变得很大，把这种"靠取值多占便宜"的特征压下去，所以更稳。这说明纯靠信息增益会偏向高基数特征，处理编号、日期这类特征要小心。