1. 为什么西瓜书选“挑西瓜”来讲决策树1.1 一个挑瓜场景里的隐含决策逻辑你有没有过这种经历西瓜书从线性模型一路读到决策树公式突然变多例子也跟着变多眼睛看懂了合上书又讲不清楚。我也卡过这一章卡到后来把手算过程老老实实抄了三遍才通。今天这篇就把决策树DT这章从头到尾拆一遍不绕弯子把书上那些“跳步”的地方补上。先说决策树到底在干什么。你去菜市场挑西瓜会先看瓜蒂是不是新鲜再看纹路是不是清晰敲两下听声音是浊是脆。这套经验凑在一起就是一个if-else规则链若纹路清晰且敲声浊响则多半是好瓜若纹路模糊则大概率不是好瓜。决策树算法做的事情就是让机器从数据里自动学出这样一棵规则树。《机器学习》这本书里大名鼎鼎的西瓜数据集就是用来讲这件事的极好素材。为什么选西瓜而不是别的因为西瓜数据集天然覆盖了决策树章节要讲的所有考点有离散属性色泽、根蒂、敲声、纹理、脐部、触感有连续属性密度、含糖率有缺失值的情况还是二分类问题好瓜/坏瓜。一个例子贯穿全章背后其实是精心设计过的教学结构。你要把这章学透不能光记结论得知道周志华老师为什么在每个小节换不同的处理策略。1.2 西瓜书第4章的主线其实是四个问题整个决策树章节看似内容很多实际上就是在回答四个问题第一每到一个节点到底用哪个属性来划分这是属性选择度量问题对应的是信息增益、增益率、基尼指数这三套标准分别对应ID3、C4.5、CART算法。第二树一层层往下长什么时候该停如果不停树会为了把训练样本全分对而疯狂长分支结果就是过拟合。这对应剪枝处理包括预剪枝和后剪枝。第三数据里出现连续值或者缺失值怎么办书上专门讲了连续值的二分法以及C4.5那套带权重的缺失值处理方式。第四能不能不只用一个属性划分而用多个属性组合出更灵活的边界这就是多变量决策树的内容。把这四个问题挂在脑子里再看书第4章的脉络一下就清楚了。很多同学觉得决策树杂是因为把本章当知识清单背而不是当作“四个决策问题”的组合拳来理解。1.3 西瓜数据集2.0的基本盘先认识一下接下来要反复用到的数据集。西瓜数据集2.0有17条样本其中好瓜8个、坏瓜9个每个样本有6个离散属性、2个连续属性。离散属性包括色泽青绿、乌黑、浅白根蒂蜷缩、稍蜷、硬挺敲声浊响、沉闷、清脆纹理清晰、稍糊、模糊脐部凹陷、稍凹、平坦触感硬滑、软粘。连续属性是密度和含糖率。这个数据集的分类难度适中不是那种随便一个属性就能彻底分开的数据所以卡在某个属性上继续深挖的余地很大非常适合演示“为什么一步选不对后面就全偏了”。包括后面讲剪枝时的验证集精度也是在这套数据上做的。你需要把这张表的结构记在心里。因为接下来手算信息增益时我要带你把17条样本逐个掰开看每个计数都会用到这组数据。纸上得来终觉浅决策树这一章尤其如此哪怕你看懂了公式也要亲手算一遍才算真懂。2. “信息增益”手算一遍才算真正看懂ID3选属性2.1 熵的直觉信息量就是“惊讶程度”信息熵这个概念初看公式吓人其实直觉非常简单。你可以把它理解成“对一件事的惊讶程度”。掷一枚硬币正反面各有50%概率结果出来之前你完全无法预测惊讶程度最大如果一枚硬币几乎每次都是正面那你就不会惊讶信息量就小。熵衡量的就是这种不确定性概率分布越均匀熵越大越偏斜熵越小。用天气打比方。在一个常年晴天的城市明天下不下雨很好预测天气的熵很低在一个每天随机晴雨的沿海城市明天天气极不确定熵就很高。对分类问题来说同理一个节点里两个类别的样本各占一半你最拿不准如果全是同一类就不需要再划分了。公式是Ent(D) - ∑ p_k · log₂(p_k)p_k表示第k类样本占比。二分类的话p取0.5时熵是1p接近0或1时熵趋近0。西瓜数据集里17个样本中好瓜8个、坏瓜9个比例非常接近一半一半所以根节点的熵大约是0.998接近最大值1。也就是说在没做任何划分之前判断一个西瓜是好是坏的难度接近“抛硬币”。2.2 根节点手算色泽、根蒂、敲声的信息增益信息增益的概念一句话就能说明白用某个属性把数据切开之后不确定性减少了多少。减少得越多说明这个属性越能帮我们做判断。公式是Gain(D, a) Ent(D) - ∑ (|Dᵛ| / |D|) · Ent(Dᵛ)其中Dᵛ表示属性a取值为v的那批子样本。先算根节点的基础熵上面说了大约是0.998。然后逐个属性算划分后的加权熵两者一减就是信息增益。拿“色泽”举例。17个样本里青绿6个3好3坏乌黑6个4好2坏浅白5个1好4坏。三个子集合的熵分别是青绿Ent1.000乌黑Ent约0.918浅白Ent约0.722。加权后的总熵是(6/17)×1.000 (6/17)×0.918 (5/17)×0.722 ≈ 0.889所以色泽的信息增益 0.998 - 0.889 0.109。按同样的算法规规矩矩把所有离散属性都过一遍结果就是书上表4.1的数据纹理的信息增益0.381最大脐部0.289排第二根蒂0.143敲声0.141色泽0.109触感0.006垫底。于是根节点选纹理。你看到“纹理清晰”分支下面好瓜比例高就会自然想继续往下分“纹理模糊”分支全是坏瓜直接标成叶子就行。这棵树的生长逻辑其实每一步都是重复上面的计算区别只是换到子数据集上继续算。2.3 信息增益的局限编号属性为什么“作弊”成功看到这里你可以试着想一个极端问题如果数据集里加一列“编号”每个样本一个独一无二的值用信息增益会怎么选答案非常尴尬。编号这个属性有17个取值划分成17个分支每个分支恰好一个样本分支内纯得一塌糊涂熵全是0。加权的总熵是0信息增益直接拉满到0.998碾压纹理。但这棵树对新样本完全没有泛化能力因为编号这个属性跟“瓜好不好”没有任何关系它只是把训练集背下来了。这就是ID3算法用信息增益做属性选择时著名的“偏科”问题它天然偏爱取值数很多的属性。你越能分我越选你可分得多不等于分得对。决策树章节从ID3讲到C4.5核心动机之一就是修掉这个毛病。理解不了这一点后面增益率那部分就不知道为什么存在。3. C4.5的增益率信息增益的“偏科”是怎么被修正的3.1 固有值给“爱分裂”的属性加个惩罚C4.5给出的纠正办法是增益率gain ratio。它的思路很直接一个属性如果取值特别多天然就能把数据切成很多小片熵降得快是“作弊”。那就把“取值多”这个特征本身做成惩罚项在算信息增益之后再除以一个量这个量叫固有值Intrinsic ValueIV(a) - ∑ (|Dᵛ| / |D|) · log₂(|Dᵛ| / |D|)你看这个公式跟信息熵长得一模一样只不过它衡量的是“这个属性自身取值分布的均匀程度”。色泽有3个取值比例是6/6/5分布均匀IV算出来大约在1.5左右。编号有17个取值每个分支只占1/17IV就是log₂17≈4.09。把信息增益除以这个固有值编号属性的增益率立刻被压到很低作弊无效。这就是增益率公式Gain_ratio(D, a) Gain(D, a) / IV(a)它等于是说你信息增益高但如果是因为你本身爱把数据切碎我就扣你的分。3.2 西瓜书的双阶段选择不是简单地选增益率最大如果你准备考试或者面试只看公式推导容易踩一个坑以为C4.5就是选增益率最大的属性。其实周志华老师在书上写得很清楚C4.5的做法是先算信息增益把信息增益高于平均水平的属性过滤出来再在这一小批属性里挑增益率最高的。为什么绕这么一圈因为增益率也有自己的毛病它在惩罚取值多的属性的同时会反过来偏爱取值数较少的属性。一个属性只有两个取值且分布极不均匀IV就会很小除出来的增益率虚高。如果直接全局选增益率最大很可能选到这种没什么区分度的属性。两阶段策略相当于中庸了一下——先用信息增益筛掉明显不行的再用增益率在质量过关的候选人里压一压“爱分裂”的倾向。放到西瓜数据集上虽然书上没有把每个属性的增益率都列出来但纹理的增益本来就高IV也不算离谱大概率仍然能胜出。重点是你要记住增益率不是独立替代信息增益而是与它配合使用。3.3 增益率在剪枝和其他场景里别乱用还有一个容易混淆的地方C4.5用的增益率主要用在“节点分裂时的属性选择”不会用在剪枝判断里。做剪枝的时候无论你是预剪枝还是后剪枝验证集精度才是最终裁判。精度不涨就剪精度涨就留这跟上不上增益率没关系。另外处理连续属性时书里选最佳划分点用的判据仍然是信息增益也不套增益率。原因很简单候选划分点都是同一个连续属性产生的固有值大同小异套增益率没意义。你把增益率的适用范围记成“离散属性的选择阶段”基本就不会出大错。4. 剪枝才是决策树的胜负手预剪枝与后剪枝的取舍4.1 一棵完全生长的树为什么容易过拟合如果不做任何限制让决策树一直生长它会做一件很恐怖的事把每个训练样本都单独用一个叶子节点装起来。训练集精度100%看起来完美可它记住的是训练样本的“名字”不是背后的规律。换一批新样本准确率往往掉得惨不忍睹。这就好比一个学生把练习册的答案一字不差背下来碰上题目改了数字就不会做。决策树天生表达能力太强尤其在属性多、样本少的时候几乎必然过拟合。过拟合的结果是泛化能力差而机器学习模型的真正价值恰恰在于“对新样本的预测能力”而不是对旧样本的复读。所以长树是学习剪枝是克制。用一点点训练精度换来更大的泛化空间这笔买卖在大多数情况下都划算。西瓜书这一节的核心矛盾就是什么时候该克制、克制到什么程度。4.2 预剪枝边生长边检查省时间但容易“近视”预剪枝的思想用一句话概括每次准备分裂一个节点先用验证集比较一下划分前后精度如果划分后验证集精度没有提升就压根不让它长。听起来很美不需要树长完整再动手。但预剪枝有一个固有的缺点它只看眼前一步不知道两步之后会不会柳暗花明。很多属性单独看没什么用但再往下分一层就能把数据完美切开。预剪枝在第一步就把这条路堵死了结果就是树长得太浅欠拟合。西瓜书里的例子也很典型根据脐部划分后某些分支看似纯度提升有限预剪枝就不让纹理继续参与划分于是整棵树只保留根节点附近的少量分支。你在验证集上得到一个还行的精度但如果你把树放开来长会发现某些深层分支比浅层的更可靠、更能提升验证精度。这就是“因果”和“果因”的问题当前节点看不出来的价值可能是指向后续更优划分的桥。从工程实践讲预剪枝的开销小训练速度快适合数据量大、特征多的场景但它有可能过早砍掉潜力股。你需要在业务里权衡如果你的数据噪声大贪多确实容易出错预剪枝保守一点反而更好如果数据相对干净预剪枝常常会欠拟合。4.3 后剪枝先生长再修剪西瓜书中42.9%到71.4%的变化后剪枝走的是另一条路线先把树养到最大让它把训练集吃透然后自底向上考察每个内部节点尝试把它替换成叶子节点用验证集看精度是否下降。不下降就剪掉子树只保留这个叶子精度上涨或持平就接受修剪精度下降就保留原来的子树结构。这里有一个我非常喜欢的数字对比在西瓜数据集上不剪枝的完整树在验证集上精度只有42.9%而后剪枝之后精度提升到71.4%。为什么完整树反而不行因为完整树把训练集背得太死验证集上一点面子不给。后剪枝大刀阔斧地砍掉大量冗余分支保留下来的都是经过验证集检验的“真本事”。后剪枝的开销比预剪枝大要先完整建树再做反向扫描训练时间更长。但它通常能保住更多有用的结构泛化性能一般比预剪枝更好这也是为什么在经典对比实验里后剪枝的胜率更高。实战中你如果只允许用一种剪枝策略优先级通常是后剪枝高于预剪枝。4.4 工程里的剪枝选择参数限制与代价复杂度剪枝落到工具层面你打开scikit-learn的DecisionTreeClassifier会发现它默认完全不剪枝只是给你留了一堆参数来限制树的生长。min_samples_split、min_samples_leaf、max_depth、max_leaf_nodes本质都是“参数化预剪枝”一开始就不允许长太深、不允许叶子样本太少。scikit-learn从0.22版本开始提供了基于代价复杂度cost complexity pruning的ccp_alpha参数。这属于后剪枝的路线先生成完整树再通过ccp_alpha控制剪枝强度。实际操作时一个很常见的工作流是先不设限制让树/D树长满再画一条“不同ccp_alpha下验证集精度”的曲线选择一个让精度保持在高位的较小alpha值。这个流程比瞎调max_depth更科学因为它相当于在完整树的基础上系统性地做最优裁剪。顺带提醒一个新手容易踩的坑决策树不需要特征缩放因为它只看特征的相对顺序和阈值不受平移和缩放影响。很多人先把数据标准化再喂树纯属多此一举。树模型和线性模型在这一点的处理逻辑完全不同。5. CART的基尼指数不取对数也能衡量纯度5.1 基尼值的含义随机抽两个样本“打架”的概率信息熵要算对数公式虽然不复杂但真跑大数据量时也是有开销的。CART算法选择了另一个度量——基尼值。它的定义极其优雅从数据集中随机抽两个样本它们的类别不一致的概率。公式是Gini(D) 1 - ∑ p_k²如果某个节点里全是好瓜随机抽两个样本类别必然相同基尼值为0最纯如果两类各占一半抽两个样本类别不一致的概率是0.5基尼值最大。节点越不纯基尼值越大越纯基尼值越小。所以CART分类树在选属性时用的是“基尼指数”Gini_index(D, a) ∑ (|Dᵛ| / |D|) · Gini(Dᵛ)信息增益是越大越好基尼指数是越小越好。方向反了别记混。“随机抽两个样本打架的概率”这个解释是我见过最形象的机器学习比喻之一。它不是从信息量出发而是从“分类错误”出发数据越不纯随手抓两个样本就越容易出不同类别分类器要犯的错误概率就越高。5.2 熵、基尼、分类误差率的三角对比很多教材会把信息熵、基尼指数、分类误差率放在一张图里对比。二分类问题下纵轴是“不纯度”横轴是正样本占比p三条曲线的形状非常接近都在p0.5时达到最高点在两端降到0。它们之间的差别也很微妙。分类误差率在p小于某个阈值之前保持一条直线到达阈值点突然拐弯是个分段折线对“不纯度”的刻画最粗糙信息熵的曲线最弯在接近两端时斜率趋近无穷大意味着它对“几乎纯净”的状态非常敏感基尼指数居中没有对数运算形状上和信息熵Top接近。实操中在大多数数据集上用基尼指数和信息熵选出来的划分差别很小。你选gini还是entropy更多是计算开销和习惯问题而不是一个明显的性能差异问题。可以记住一个结论熵对纯度变化的判断更敏感基尼在超大样本上计算更快普通数据集二者基本等价。5.3 同一棵数据不同判据为什么可能选出不同的根回到西瓜数据集。如果换成基尼指数在17条样本上重新选根某些属性的排序可能会和信息增益下的排序有差异。这不是算法有bug而是两种判据对“不纯度下降多少”的计分方式不同。信息增益是用熵的差值衡量基尼指数是用混乱概率差衡量二者对同一个分裂方案打出的分数比例不一样。理解这一点比记住某个具体数据集的结论重要得多。因为你做项目时换了数据最优判据可能完全变化。哪怕gini和entropy常给出相近的结果也不意味着你可以完全忽略它们之间的细微差别。遇到敏感业务花时间在两个判据下都跑一遍用验证集看最终精度比站在理论层面争论谁更优更有价值。5.4 sklearn里的决策树与西瓜书的主要差异这里要特别提醒一个坑西瓜书里讲的决策树默认数据本身就是离散类别值比如“青绿”“乌黑”。但scikit-learn的DecisionTreeClassifier不接受字符串类型的类别特征你需要提前做编码比如OneHotEncoder。等价于把每个离散取值变成一列0/1特征。CART本身是二叉树而ID3/C4.5可以生成多叉树。你打开sklearn源码或者画出来的树图会发现离散特征编码后每个节点只做一次“是否等于某个值”的判断一路分下去。这跟西瓜书里的多叉划分不一样但本质逻辑一致每次分裂都是在降低节点不纯度。还有一个常见误解sklearn的决策树不是严格意义上的CART原版它在实现上做了修改和优化。比如它支持entropy作为划分标准而原始CART并不用熵比如它对连续特征找最优切分点的方式和数据存储做了优化。你如果论文里引用说“scikit-learn实现了基于CART优化的决策树”更严谨。6. 连续值、缺失值、多变量把课本上的决策树拉到现实数据里6.1 连续属性怎么选划分点排序后找中点真实数据里到处都是连续值比如西瓜的密度、含糖率。连续属性没法像离散属性那样直接列出几个取值分成好几叉常规做法是二分法。先把连续值从小到大排序对任意相邻两个取值的中点是候选划分点然后逐个算信息增益找信息增益最大的那个点作为划分阈值。比如“密度”属性17个样本排序后出现许多候选划分点算下来最优阈值往往落在0.381附近。划分规则就是“密度≤0.381”进左分支“密度0.381”进右分支。含糖率同理可能最佳阈值在0.126附近。有一个书上老提但大家常忽略的细节连续属性可以在一条路径上被重复使用。比如第一次用“密度≤0.381”划分之后在某个分支里还可以继续用“密度≤0.203”再划分。这是因为连续值是范围的判断一次阈值只能切一刀多次阈值才能逐步逼近真实边界。离散属性则不同每个离散属性用一次就基本不再选它因为取值被分尽了。6.2 缺失值C4.5那一套带权重的玩法现实数据里缺失值非常常见如果哪个属性有缺失就删样本数据量很快就不够用。西瓜书里的缺失值处理继承的是C4.5的思路核心是两个问题属性有缺失时怎么算信息增益样本有缺失时划分到哪个分支第一个问题计算属性a的信息增益时只使用在处理样本集合中那些在属性a上没有缺失的样本。信息增益要通过无缺失的样本比例做加权修正避免因为样本量少了导致数值失真。第二个问题有缺失值的样本不再硬性划入某一个分支而是带着一个权重同时进入所有分支权重等于该分支样本数量占无缺失样本总数的比例。你可以想象成一个缺失了“色泽”的西瓜无法判断它是青绿还是乌黑那就开三份“分灵子”按青绿分支的比例进入青绿分支按乌黑分支的比例进入乌黑分支按浅白分支的比例进入浅白分支。后面的熵计算再把每个分支的样本权重加起来算。这套方法比直接删样本或者均值填充要稳。因为均值填充会把一个本来不确定的值强行变成一个确定值扭曲了原始分布的随机性。C4.5的思路相当于在计算时保留了不确定性而且让缺失样本的影响根据分支规模自然分摊。工程上用sklearn时默认不接受缺失值要么提前填补要么换用支持缺失值的算法如某些梯度提升库。这倒是教材和工具的差异点实际项目里要留意。6.3 多变量决策树从轴平行划分到斜划分普通决策树每个内部节点只考察一个属性画到二维平面上每一刀都是平行于坐标轴的直线。西瓜书正文里也提到这样的“轴平行划分”在某些场景下会非常笨拙。比如决策边界如果是45度斜线普通决策树就要用好几段阶梯状折线去逼近它树又深又长。多变量决策树想解决这个问题每个内部节点不再只挑一个属性而是用多个属性的线性组合作为划分条件。比如不是“密度≤0.381”而是“0.2×密度 0.8×含糖率 ≤ 阈值”。这样做出来的边界是斜的能一步就切开斜向分布的数据树的结构会更紧凑。代价也很明显可解释性大大下降。原本“纹理是否清晰”一句话就能解释多变量节点变成一堆系数加权组合用户看不懂。从模型演进的角度看多变量决策树已经有点接近线性模型与树的结合体它提醒你一件事决策树不是死板的if-else集合它只是一个框架节点内部的判别函数完全可以替换成更灵活的模型。实践项目里其实很少直接用多变量决策树因为它的复杂度高、可解释性弱、实现库也不常见。但你要知道它的存在意义面试里如果被问到“决策树只能做轴平行划分吗”你能把它和斜划分、线性判别结合起来的思路讲明白就胜过大多数背概念的人。我个人啃完这章最大的体会是别急着调库跑模型先把西瓜数据集上纹理那一列的信息增益手算明白再对照sklearn在鸢尾花数据集上的结果看gini和entropy的差异。等你能从根节点一路算到叶子决策树才真正从书里长到你脑子里。按这个思路学一遍再回头复习就是降维打击。