ID3决策树手算指南：信息增益步骤详解与期末答题模板

期末周前，A同学把复习PPT截图发给我，问了一个很多人都会卡住的问题："信息增益我都背下来了，为什么一到手算决策树就不知道下一步该选谁？"如果这句话你也说过，这篇复习模板就是写给你的。ID3算法作为数据挖掘与机器学习入门课里的经典决策树方法，几乎每年都会以计算题或简答题的形式出现在期末试卷上，分值通常还不低。这篇文章按期末考场的真实需要来组织：先把熵和信息增益的直觉讲透，再带着你完整手算一棵决策树，然后拆解计算题、简答题、综合应用题的答题模板，最后整理那些"会做但总被扣分"的细节。适合正在备考、想快速形成知识闭环的同学，也适合考前想用半天时间把ID3彻底弄明白的零基础选手。

1. 为什么ID3年年出现在试卷上，却年年有人失分

1.1 一张期末卷里，ID3能串起多少知识点

很多人把ID3当成一个孤立的算法来复习，这是最亏的。实际上，ID3在一张数据挖掘或机器学习导论的期末试卷里，往往是连接多个考点的中枢。

先说它为什么常考。ID3的核心内容包括三块：信息熵、信息增益、递归建树。信息熵来自信息论，是理解所有"分类不确定性度量"的基础；信息增益做的事情是特征选择，本质上是评价"哪个属性对分类最有帮助"；递归建树则是分治思想在分类问题上的典型应用。这三个点恰好覆盖了这类课程最喜欢考的能力维度——公式理解、计算能力和算法逻辑。

而且ID3有一个非常实际的好处：它能手算。期末考试是纸笔环境，样本量不可能给太大，通常就是十几个样本、三四个特征。这种规模正好适合考察一个人是否真正理解建树流程。相比之下，神经网络、支持向量机那类算法更适合笔试出简答题，很难让你在考场上手算一遍反向传播。所以出题老师自然会把ID3选作计算大题的主力。

那为什么每年还是有人失分？我观察下来主要有三种情况。第一种是只背公式，没有走完过一棵完整的树。第二种是算熵的时候粗心，log算错、比例取错，一步错步步错。第三种是最可惜的——树建到一半不会收尾，不知道什么时候该停、叶子该怎么标。后面我会一节一节把这些问题全部堵上。

1.2 复习决策树最大的坑：只背公式，不做算例

我先泼一盆冷水：如果你只是把"信息增益 = H(D) - H(D|A)"抄在笔记本上，然后翻两页例题就算复习完了，考场上大概率还是会慌。

原因很简单。ID3的手算过程不是一个公式能搞定的，它是一套循环操作。你算完根节点的信息增益，选出第一个特征后，马上就要把数据集按这个特征拆开，然后对每一个分支子集重新计算熵和信息增益。这里的难点不在于公式，而在于样本集切换的瞬间，很多人会把原始数据的计数搞混。

举一个我在帮A同学复盘时看到的典型错误：他根节点选对了，下一步处理Sunny分支时，把原本不属于Sunny的样本也带进来一起算熵，算出来的增益自然混乱。这就是没有亲手练过完整算例的表现。

所以我对所有备考者的建议是：复习ID3，至少要独立手算一棵完整的树。不需要多，一棵14个样本的经典算例就够了。你把这棵树的每一个熵值、每一次递归都亲自算一遍，考场上不管数据换成什么，流程都不会断。这也是后面第三章我要带你完整做一遍的原因。

2. 先别急着套公式：把熵和信息增益的直觉打通

2.1 熵在度量"话都说到这份上了，还是没确定"

信息熵这个概念第一次接触时确实容易劝退，但它的直觉其实很朴素：熵度量的是一个系统里"不确定性"的大小。

我常用一个猜球的例子。假设口袋里有8个球，颜色各不相同，让你猜我摸出的是哪个。在你一无所知时，你需要问多少个"是/否"问题才能确定答案？答案是3个：先问是不是前4个里的，再问是不是前2个里的，最后确定具体是哪一颗。这里的信息量就是3比特，正好等于log2(8)。

如果口袋里的球不是均匀分布的，情况就不一样了。假如8个球里有7个红球、1个蓝球，我让你猜颜色，你最佳策略是直接猜红球，因为猜中的概率高达7/8。这时你几乎不需要问问题，不确定性很小。熵这个概念，就是把这些情况统一成一个公式：

H(D) = -Σ p(k) × log2(p(k))

其中p(k)是第k种类别在数据集D中出现的概率。公式前面那个负号，是因为log2(p)本身是负数，加个负号让熵为正。概率越平均，熵越大；概率越极端，熵越小。如果所有样本都属于同一个类别，p=1，log2(1)=0，熵就等于0——没有任何不确定性，这个节点已经"纯"了。

我在复习时会把几个常用值背下来，因为手算时频繁用到。比如log2(2)=1，log2(3)≈1.585，log2(5)≈2.3219，log2(7)≈2.8074。有了这几个底数，大部分熵都能快速估算，不用每步都掏计算器。

2.2 条件熵与信息增益，就是"知道某条信息后还剩多少不确定性"

熵理解了，条件熵就顺了。条件熵H(D|A)说的是：在已经知道特征A的取值之后，数据集D还剩多少不确定性。

它的计算逻辑是"分块加权"。先把数据集按特征A的每一个取值切成若干个子集，每个子集单独计算熵，然后再按子集样本数占总样本数的比例做加权平均。用公式写就是这样：

H(D|A) = Σ (|Dv| / |D|) × H(Dv)

其中v遍历特征A的所有取值，Dv是特征A取值为v的那一批样本。

有了熵和条件熵，信息增益就是两者相减：

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

这个差值代表的是：知道了特征A之后，数据集的不确定性减少了多少。减少得越多，说明这个特征对分类越有用。ID3的核心策略，就是每次在候选特征里挑信息增益最大的那个作为当前节点的分裂特征。

我记得第一次学到这里时总觉得有点绕，后来用一个类比就通透了：H(D)是你拿到一份杂乱数据时的困惑程度，H(D|A)是你先看了一列特征之后剩下的困惑程度。信息增益就是"这列特征帮你消除了多少困惑"。帮你消除困惑最多的那列，当然最值得优先拿来切分数据。这样一想，ID3其实一点也不神秘，它就是在做一道简单的选择题：每一步，都选当前最有用的问题来问。

3. 一鼓作气算出十四样本：从根节点长出一棵完整的树

3.1 样本与初始熵

理论再熟，不落地算一遍都是空的。下面这个数据集是各种教材里最经典的"打球"例子，14个样本，4个特征，类别是"打"或"不打"。我把属性名替换成中文，方便你对照计算。

第一步，算根节点的熵。14个样本里，"打"有9个，"不打"有5个：

H(D) = - (9/14) × log2(9/14) - (5/14) × log2(5/14)

约等于0.940。这个值先记住，后面所有特征的信息增益都要拿它相减。

3.2 四个特征的信息增益并列对比

接下来分别计算天气、温度、湿度、风力这四个特征的条件熵和信息增益。每一组我建议都按"切子集、算子集熵、加权求和、相减"四步走。

先看天气。晴有5个样本（1、2、8、9、11），其中"打"2个、"不打"3个，熵约0.971；阴有4个样本（3、7、12、13），全是"打"，熵为0；雨有5个样本（4、5、6、10、14），其中"打"3个、"不打"2个，熵约0.971。加权后条件熵为：

H(D|天气) = (5/14) × 0.971 + (4/14) × 0 + (5/14) × 0.971 ≈ 0.694

信息增益 = 0.940 - 0.694 = 0.246。

再看温度。热、温、凉三个取值对应的子集熵分别是1、0.918、0.811，加权条件熵约0.911，信息增益只有0.029。

接着看湿度。高湿度的7个样本里，"打"3个、"不打"4个，熵约0.985；正常湿度的7个样本里，"打"6个、"不打"1个，熵约0.592。条件熵约0.788，信息增益0.152。

最后看风力。无风的8个样本里，"打"6个、"不打"2个，熵约0.811；有风的6个样本里，"打"3个、"不打"3个，熵为1。条件熵约0.892，信息增益0.048。

把结果汇总成一张表：

天气的信息增益最大，所以根节点选择"天气"作为分裂特征。这就是ID3每一层都在做的事：比较增益，选最大。

3.3 对天气分支递归建树

根节点选好后，数据被切成三个分支：晴、阴、雨。接下来要对每一个分支重复刚才的过程。

阴这个分支最简单：里面4个样本全是"打"，熵为0，类别已经纯了，直接生成一个叶子节点，标注"打"。

晴这个分支需要继续分裂。这5个样本里"打"2个、"不打"3个，熵约0.971。再分别计算温度、湿度、风力的信息增益：

• 湿度：高湿度样本全是"不打"，正常湿度样本全是"打"，条件熵为0，信息增益0.971；
• 温度：条件熵0.4，信息增益0.571；
• 风力：条件熵约0.951，信息增益0.020。

湿度增益最大，所以晴的分支按湿度继续分。湿度高，叶子标"不打"；湿度正常，叶子标"打"。

雨这个分支同样还要继续。5个样本里"打"3个、"不打"2个，熵约0.971。再算温度、湿度、风力的增益：

• 风力：无风样本全是"打"，有风样本全是"不打"，条件熵为0，信息增益0.971；
• 温度：信息增益约0.020；
• 湿度：信息增益约0.020。

风力增益最大，所以雨的分支按风力继续分。无风，叶子标"打"；有风，叶子标"不打"。

到这里，整棵树已经完整了。

3.4 最终树与考试版解读

把刚才的过程整理成树形结构，就是下面这样：

天气

• 晴：看湿度
  • 高 -> 不打
  • 正常 -> 打
• 阴 -> 打
• 雨：看风力
  • 无风 -> 打
  • 有风 -> 不打

把这棵树翻译成规则，就变成了三条特别直观的判断逻辑：天气是阴就直接打；天气是晴就看湿度，湿度正常才打；天气是雨就看风力，无风才打。这也是考试里常见的一个追问角度——"请将生成的决策树转换为分类规则"，这种题其实就是把树从上到下读一遍，没有任何额外计算。

我建议你复习时也用Python快速验证一遍手算结果，免得哪里算错了自己还不知道。代码可以写得很简单：

import math def entropy(positive, negative): total = positive + negative if positive == 0 or negative == 0: return 0.0 p_pos = positive / total p_neg = negative / total return -p_pos * math.log2(p_pos) - p_neg * math.log2(p_neg) print(entropy(9, 5)) # 0.9403 print(entropy(3, 4)) # 0.9852 print(entropy(6, 1)) # 0.5917

这种几十行的验证脚本，比盲目刷十道题都管用。

4. 期末题就这三副面孔：计算、简答、综合分析怎么拿分

4.1 计算题：四步递进式答题模板

期末计算题最常见的问法就是："给定如下训练集，用ID3算法构造决策树。"这里有一个按步骤写就能稳定拿分的方法。

第一步，写初始熵。明确写出H(D)的计算公式，并把数值算出来。这一步不要跳，因为后面所有信息增益都要用到它。

第二步，逐特征计算。对每一个特征，先画出它的取值分布和每个子集中的正负样本数，再写出条件熵公式，最后算信息增益。这里强烈建议画一张汇总表，把每个特征的条件熵和信息增益都列出来。表格的好处是，即使你中间某一个熵值算错，判卷老师也能看到你的思路，过程分照样能拿到。

第三步，选增益最大的特征作为当前节点，并说明理由。注意理由要写清楚："信息增益越大，表示该特征对分类的不确定性减少越多，因此选择信息增益最大的XX作为分裂特征。"

第四步，递归处理各分支。每进入一个分支，都要在草稿纸上明确写出"当前分支包含哪几个样本"，再重复前两步。当某个分支的样本全部属于同一类别时，直接生成叶子节点并标注类别；当特征用尽但样本类别仍不统一时，用多数表决方式决定叶子类别。

整个答题过程中，最容易丢分的不是最后的树，而是中间的计数。我的习惯是：每切一个分支，就在样本表格上做标记，或者把每一分支的样本编号写出来，确保不重不漏。

4.2 简答题：三句话得分结构

简答题范围比较固定，常见的有这几种：什么是信息增益、为什么决策树选择信息增益作为特征选择标准、决策树有哪些优缺点、ID3与C4.5的区别。

这类题不要长篇大论，用"概念定义、计算逻辑、实际意义"的三句话结构就足够拿分。比如"为什么用信息增益作为特征选择标准"，可以这样组织：

信息增益表示引入某个特征后，数据集不确定性的减少量。它的计算方式是父节点熵减去该特征下的条件熵，差值越大说明该特征对分类的帮助越大。因此ID3在每一步都选择信息增益最大的特征，以期望用最少的判断次数得到更纯的分类结果。

这三句话分别覆盖了"是什么、怎么算、为什么用"，阅卷时基本不会扣分。如果你有余力，再加一句"信息增益的缺陷是对取值较多的特征有偏好，因此后来出现了基于信息增益率的C4.5算法"，直接给老师一种"你知识面完整"的感觉。

4.3 综合分析题里的常见变化

比简单计算题更进一步，有些卷子会把ID3放进一个更复杂的场景里考。比如给你一个带连续属性的数据集，或者问你"如果训练集中有一个编号属性，ID3会不会选中它？"

遇到连续属性，要知道ID3本身只能处理离散特征，但考试通常会引导你用C4.5的思路：对所有候选阈值点进行二分，例如按"温度是否大于等于某个值"把样本分成两组，再按信息增益去选最佳阈值。答题时不需要真正做大量阈值搜索，列出思路、写出分组方式即可。

遇到编号属性，要能解释清楚"编号的信息增益为什么那么大"。因为每个编号只对应一条样本，每个子集的熵都是0，条件熵为0，信息增益直接等于初始熵，所以ID3会优先选择编号来建树。但这棵树对没有见过的样本毫无泛化能力，这就是ID3偏向多值属性的典型例子。

这样的分析题，考的不是计算量，而是你是否真正理解了算法背后的动机和陷阱。只要你能从"信息增益对多值特征不公平"这个角度切入，分数基本就到手了。

5. 判卷复盘：那些"会做但被扣分"的细节

5.1 公式层的低级错误

我在帮同学复盘往年卷子时，发现很多丢分点其实不在算法思路，而在一些小到不值当的地方。

最常见的是log算错。有人复习时习惯用自然对数ln替代log2，平时觉得没事，考场上拿着计算器一按，好几个熵值就都偏了。信息论里的熵默认使用以2为底的对数，单位才是比特。如果你实在手算困难，可以先记住我前面列的几个常用对数近似值，比如log2(3)=1.585，log2(5)=2.3219，再用这些值组合出大部分答案。

第二个常见问题是条件熵被算成了简单平均。正确的条件熵必须按子集样本占比加权，不是把每个子集的熵直接加起来除以取值个数。比如天气属性有三个取值，条件熵是(5/14)×0.971加上(4/14)×0再加上(5/14)×0.971，而不是(0.971+0+0.971)÷3。这个区别很大，几乎每年都有人在这里栽跟头。

第三个问题是不写公式直接填答案。期末卷子的判分逻辑通常是看过程，你即使答案算对了，没有展示条件熵的分子分母，也可能被扣掉过程分。宁可多写两行，也不要让老师去猜。

5.2 建树过程中的结构性失误

除了公式错误，建树过程本身也有几个高频翻车点。

第一，子集纯了还继续分裂。很多同学一旦进入"机械计算"状态，看到某个分支已经全是同一类别，还非要继续算熵、选特征、再分一层。这是错的。纯节点的熵为0，信息增益也是0，没有继续分裂的意义，直接停下来生成叶子节点。

第二，递归分支时样本集没有同步更新。根节点选天气之后，晴的分支里就只能包含序号为1、2、8、9、11这5个样本，后面的计算全部基于这5个样本，不能再把阴和雨的样本混进来。这一条看起来简单，实际特别容易出错，尤其当样本表格没有重新誊写时，眼睛一花就把整列数据都拿去算了。

第三，叶子节点只标了特征取值，没标类别。比如晴、湿度高那个分支，正确的写法是叶子节点标注"不打"，而不是标注"湿度高"。叶子节点的意义是给出分类结论，很多同学画树到最后，忘了在叶子上写类别，白白丢分。

第四，特征用完但子集不纯。理论上如果所有特征都用尽了，类别还是不一致，就要用多数表决。比如剩下3个样本是"打打不打"，叶子就标"打"。这是ID3建树的收尾规则，别漏掉。

5.3 考场上的检查技巧

时间允许的话，我会用三个小检查来确认手算结果是否靠谱。

第一个检查是看条件熵与信息增益的正负关系。条件熵是加权平均，信息增益不应该小于0。如果你算出某个特征的信息增益是负数，说明中间某一步计算出了方向性问题，赶紧回头检查。

第二个检查是核对各分支样本数。你在任何一层对特征取值分组时，所有子集的样本数量加起来，必须等于父节点的样本总数。这是最简单的账，却是最有效的防呆手段。

第三个检查是看最终树是否符合直觉。比如样例树里"阴天一定打、雨天看风、晴天看湿度"，这个结果符合日常经验，说明整体结构大概率没问题。如果算出来的树特别反直觉，通常不是数据的问题，而是某一步的熵算错了。

6. 拔高题看这里：ID3的局限与C4.5的改进方向

6.1 "编号为什么会被ID3选中"：多值偏向问题的考场问法

很多复习资料会把ID3的不足列成几条，但考试更爱考的是一种具体的辨析：如果训练集里增加一个"编号"特征，ID3建树会怎么样？

答案是：ID3会优先选择编号作为根节点的分裂特征。原因很好理解，编号的每一个取值都只对应一条样本，按它切分后每个子集都是纯的，条件熵为0，信息增益直接等于数据集初始熵，是理论上的最大值。但这条路径对真实分类毫无帮助，因为编号是一个完全随机的标识，无法泛化到新样本。

这个问题背后的本质，是信息增益度量对取值数目较多的特征有天然偏好。取值越多的特征，越容易被切得碎，每一块子集就越容易变纯，信息增益也就显得越高。但这个"高"是虚假的，它反映的是特征过拟合了训练数据，而不是真正抓住了分类规律。

答这种题时，我会先摆出计算结果，再点明"多值偏好"四个字，最后补充一句"C4.5使用信息增益率来缓解这个问题"。这样，一道4分或6分的简答题，基本就能拿满。

6.2 信息增益率与C4.5的三个主要改进

C4.5对ID3的改进，是期末简答和填空题的高频考点，务必记牢。

最重要的改进就是把信息增益换成了信息增益率。增益率在信息增益的基础上再除以一个"分裂信息"：

GainRatio(D, A) = g(D, A) / SplitInfo(A)

其中SplitInfo(A) = -Σ (|Dv| / |D|) × log2(|Dv| / |D|)，它度量的是特征A本身划分数据的"细致程度"。取值越多的特征，分裂信息越大，增益率被压缩得越厉害，从而削弱了ID3对多值特征的偏好。

第二个改进是支持连续属性。ID3只能处理离散取值，C4.5则可以把连续属性按阈值二分，比如温度小于等于25度和大于25度，再计算各种阈值切分下的增益率，选最优阈值。

第三个改进是引入剪枝和缺失值处理。决策树如果完全生长，往往在训练集上表现很好，但泛化能力差。C4.5通过后剪枝去掉一些不可靠的分支，也设计了缺失值的处理策略，让样本能按比例进入不同分支。

复习时可以把ID3和C4.5放在一张表里对照记，考前只看表就够了：

这张表本身就是一个很好的简答题答案模板，背下来比临时组织语言稳妥得多。

6.3 备考时把ID3和C4.5做成一个知识组块

我复习这类算法有一个自己的习惯：不孤立地背某一个算法，而是把一个算法和它的"下一代版本"放在一起，当成一个故事来记。

ID3的起源逻辑很清楚：从数据里找信息增益最大的特征来分叉。但它有个毛病——偏爱取值多的特征。于是C4.5出现，用增益率做修正，顺便补齐了连续属性和剪枝。再往后，分类回归树用基尼系数替代熵，走的是另一条更轻量的路线。这样串下来，每一个算法都不是孤立的，而是对前一个问题的回应。

考试前如果你只有半天时间，我的建议是：花两小时把第三章节的完整算例亲手算一遍，花一小时背熟信息增益和增益率的公式，再花一小时过上面这张对比表和几个常见简答题答案。这套流程走完，ID3相关的大题和简答题基本不会再有意外。

说到底，决策树这东西，公式只是骨架，手算才是肌肉记忆。你那一遍算下来，比刷十遍题都踏实。