[omscs-ml] 从 ID3 到 Gini Impurity：决策树如何选择 split？

---

1. 决策树在做什么？

决策树的目标是把训练样本一步步分开，直到叶子节点里的样本尽可能“纯”。

比如我们想预测一个人是否买咖啡：

天气	价格	距离	是否买咖啡
晴天	便宜	近	Yes
晴天	贵	远	No
阴天	便宜	远	Yes
雨天	便宜	近	No

决策树可能学出类似这样的规则：

如果天气 = 阴天 → Yes
如果天气 = 晴天，再看价格
如果天气 = 雨天，再看距离

核心问题是：

每一步应该选择哪个 feature 来 split？

ID3 的答案是：选择 information gain 最大 的 attribute。

---

2. Entropy：衡量一个 node 有多混乱

Entropy 用来衡量一个 node 里面的 label 混乱程度。

公式是：

$$Entropy(S) = -\sum_{k=1}^{K} p_k \log_2 p_k$$

其中：

• $S$：当前 node 里的样本集合

• $K$：类别数量

• $p_k$：第 $k$ 类在当前 node 里的比例

对于二分类来说，如果一个 node 里面全是同一类，比如全是 Yes：

$$Entropy(S)=0$$

说明这个 node 完全纯。

如果一个 node 里 Yes 和 No 各一半：

$$p_{Yes}=0.5, \quad p_{No}=0.5$$

那么：

$$Entropy(S)= -0.5\log_2(0.5)-0.5\log_2(0.5)=1$$

说明这个 node 最混乱。

简单记忆：

Node 里的 label 分布	Entropy
100% Yes, 0% No	0
90% Yes, 10% No	较低
50% Yes, 50% No	最高，二分类中为 1

---

3. Information Gain：split 之后混乱程度下降了多少

Information gain 的公式是：

$$Gain(S,A)=Entropy(S)-\sum_v \frac{|S_v|}{|S|}Entropy(S_v)$$

含义是：

$$\text{Gain} = \text{split 前的混乱程度} - \text{split 后的加权平均混乱程度}$$

其中：

• $S$：当前 node 的所有样本

• $A$：候选 attribute

• $v$：attribute $A$ 的不同取值

• $S_v$：$A=v$ 的那一组样本

• $\frac{|S_v|}{|S|}$：这一组样本在当前 node 中的比例

所以，information gain 越大，说明这个 feature 越能把数据分干净。

---

4. Information Gain 的完整数字例子

假设当前 node 有 10 个样本：

Label	数量
Yes	6
No	4

所以 split 前：

$$p_{Yes}=0.6, \quad p_{No}=0.4$$ $$Entropy(S)= -0.6\log_2(0.6)-0.4\log_2(0.4)=0.971$$

现在我们考虑用 Weather 来 split：

Weather	Yes	No	Total
Sunny	1	3	4
Rainy	2	1	3
Overcast	3	0	3

4.1 Sunny 的 entropy

Sunny 里面有 1 个 Yes，3 个 No：

$$Entropy(Sunny)= -\frac{1}{4}\log_2\frac{1}{4}-\frac{3}{4}\log_2\frac{3}{4}=0.811$$

4.2 Rainy 的 entropy

Rainy 里面有 2 个 Yes，1 个 No：

$$Entropy(Rainy)= -\frac{2}{3}\log_2\frac{2}{3}-\frac{1}{3}\log_2\frac{1}{3}=0.918$$

4.3 Overcast 的 entropy

Overcast 里面全是 Yes：

$$Entropy(Overcast)=0$$

4.4 Split 后的 weighted entropy

注意这里不是简单平均，而是按照每个 child node 的样本数加权：

$$WeightedEntropy = \frac{4}{10}(0.811)+\frac{3}{10}(0.918)+\frac{3}{10}(0)$$ $$WeightedEntropy=0.324+0.275+0=0.599$$

所以：

$$Gain(S,Weather)=0.971-0.599=0.372$$

也就是说，用 Weather split 后，混乱程度从 0.971 降到了 0.599，下降了 0.372。

---

5. 为什么 high-cardinality attribute 会有问题？

如果一个 attribute 有很多很多取值，比如 100 种天气细分类，ID3 可能会产生很多分支：

WeatherExactType
├── 小雨转阴
├── 雷阵雨
├── 晴间多云
├── 大雾
├── 沙尘暴
└── ...

这会带来一个经典问题：information gain 偏爱取值很多的 attribute。

极端例子是 Student_ID。如果每个学生 ID 都唯一，用它 split 后，每个 child node 只有一个样本，于是每个 child node 都是纯的：

$$Entropy(S_v)=0$$

那么 split 后的 weighted entropy 是 0：

$$Gain(S,Student\_ID)=Entropy(S)-0$$

这看起来 gain 很高，但实际上没有泛化能力。因为来了一个新的 student ID，模型根本不知道该怎么处理。

这就是 overfitting：

模型把训练集记住了，但没有学到真正可泛化的规律。

常见解决方法包括：

1. 使用 gain ratio，对取值很多的 attribute 加惩罚。
2. 限制树的深度，比如 max_depth=3。
3. 限制叶子节点最小样本数，比如 min_samples_leaf=10。
4. 剪枝，先长树再删掉不可靠的小分支。
5. 把太细的类别合并成更粗的类别。

---

6. 为什么说有很多 possible trees？

如果固定训练数据、固定 feature、固定算法、固定 tie-breaking rule，ID3 最后通常会输出一棵 tree。

但是从理论上说，能解释同一批 training data 的 decision trees 可能有很多棵。

比如：

Sample	A	B	Label
1	low	red	No
2	low	red	No
3	high	blue	Yes
4	high	blue	Yes

用 A split 可以完美分类：

A
├── low  → No
└── high → Yes

用 B split 也可以完美分类：

B
├── red  → No
└── blue → Yes

两棵树都能解释训练数据。

如果它们的 gain 一样，ID3 需要靠 tie-breaking 选一个。比如某些 implementation 会选 feature list 中排在前面的那个。

重点是：

ID3 不是枚举所有 possible trees 再找全局最优，而是一个 greedy algorithm。

它每一步只做当前 node 上看起来最好的选择。

---

7. Inductive bias 是什么？

Inductive 的意思是“归纳式的”。

机器学习里的 induction 是：

从有限的 training examples 中归纳出一般规律，然后预测没见过的新样本。

但是训练数据通常无法唯一决定真实规律。也就是说，有很多模型都可能解释训练数据。

所以学习算法必须有某种偏好。这个偏好就叫 inductive bias。

对于 ID3 来说，它的 inductive bias 包括：

1. Good splits at top：偏好把 information gain 高的 feature 放在树的上层。
2. Correct over incorrect：偏好能正确分类训练数据的 tree。
3. Shorter trees：偏好更短、更简单的 tree。

所以：

ID3 的 inductive bias 是一种 preference bias：很多 tree 都可以选，但 ID3 偏好某些 tree。

这和 restriction bias 不一样。

• Restriction bias：直接限制哪些模型能被考虑，比如只允许 linear model。

• Preference bias：模型都可以考虑，但算法更喜欢某些模型，比如更短的 tree。

---

8. Continuous attribute 怎么办？

如果 feature 是连续数值，比如：

Age = 22, 25, 28, 35, 40, 50
Temperature = 36.5, 37.2, 38.9
Income = 52000, 81000, 130000

不能直接对每个数值建立一个 branch，否则很容易 overfit。

常见做法是找一个 threshold，把 continuous attribute 变成 binary split：

$$A \leq t ?$$

比如：

Age ≤ 26.5?
├── True
└── False

8.1 如何选择 threshold？

假设数据如下：

Age	Label
22	No
25	No
28	Yes
35	Yes
40	Yes
50	No

先按照 Age 排序，然后取相邻数值之间的 midpoint 作为候选 threshold：

23.5   between 22 and 25
26.5   between 25 and 28
31.5   between 28 and 35
37.5   between 35 and 40
45.0   between 40 and 50

然后对每个 threshold 都计算一次 information gain，选择 gain 最大的那个。

比如试：

Age ≤ 26.5

左边：

Age	Label
22	No
25	No

左边完全纯：

$$Entropy(left)=0$$

右边：

Age	Label
28	Yes
35	Yes
40	Yes
50	No

右边有 3 个 Yes，1 个 No：

$$Entropy(right)= -\frac{3}{4}\log_2\frac{3}{4}-\frac{1}{4}\log_2\frac{1}{4}=0.811$$

原始 node 中 Yes=3，No=3：

$$Entropy(S)=1$$

所以 weighted entropy 是：

$$\frac{2}{6}(0)+\frac{4}{6}(0.811)=0.541$$

information gain 是：

$$Gain(S, Age \leq 26.5)=1-0.541=0.459$$

再对其他 threshold 重复计算，选 gain 最大的 threshold。

---

9. Gini impurity 是什么？

Gini impurity 也是衡量 node 混乱程度的指标，常用于 CART 决策树，也就是很多库中默认的 decision tree 方法。

公式是：

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

其中：

• $S$：当前 node 的样本集合

• $K$：类别数量

• $p_k$：第 $k$ 类在当前 node 中的比例

对于二分类，如果当前 node 里有 6 个 Yes，4 个 No：

$$p_{Yes}=0.6, \quad p_{No}=0.4$$

那么：

$$Gini(S)=1-(0.6^2+0.4^2)$$ $$Gini(S)=1-(0.36+0.16)=0.48$$

Gini impurity 越低，node 越纯。

Node 里的 label 分布	Gini impurity
100% Yes, 0% No	0
90% Yes, 10% No	0.18
50% Yes, 50% No	0.5

---

10. 用 Gini impurity 选择 split

仍然用这个 Weather 例子：

Weather	Yes	No	Total
Sunny	1	3	4
Rainy	2	1	3
Overcast	3	0	3

10.1 Sunny 的 Gini

$$Gini(Sunny)=1-\left[\left(\frac{1}{4}\right)^2+\left(\frac{3}{4}\right)^2\right]$$ $$Gini(Sunny)=1-(0.0625+0.5625)=0.375$$

10.2 Rainy 的 Gini

$$Gini(Rainy)=1-\left[\left(\frac{2}{3}\right)^2+\left(\frac{1}{3}\right)^2\right]$$ $$Gini(Rainy)=1-\left(\frac{4}{9}+\frac{1}{9}\right)=\frac{4}{9}=0.444$$

10.3 Overcast 的 Gini

Overcast 里面全是 Yes：

$$Gini(Overcast)=1-(1^2+0^2)=0$$

10.4 Split 后的 weighted Gini

$$WeightedGini=\frac{4}{10}(0.375)+\frac{3}{10}(0.444)+\frac{3}{10}(0)$$ $$WeightedGini=0.150+0.133+0=0.283$$

Split 前：

$$Gini(S)=0.48$$

Split 后：

$$WeightedGini=0.283$$

Gini decrease 是：

$$0.48-0.283=0.197$$

用 Gini 的决策树会选择让 weighted Gini 最小，或者让 Gini decrease 最大的 split。

---

11. Entropy / Information Gain vs Gini Impurity

Entropy 和 Gini impurity 都是在衡量 node 的 impurity。

指标	公式	二分类最大值	常见算法
Entropy	$-\sum p_k\log_2 p_k$	1	ID3 / C4.5
Gini impurity	$1-\sum p_k^2$	0.5	CART / sklearn default

两者直觉很像：

• node 越纯，值越低。

• node 越混，值越高。

• split 的目标是让 child nodes 的加权 impurity 尽可能低。

实际使用中，Gini 和 entropy 的结果通常很接近。Gini 计算更简单，不需要 log，所以在 CART 中很常见。

---

12. 总结

ID3 决策树的核心思想是：

选择最能降低混乱程度的 feature
→ split 数据
→ 在 child node 上重复
→ 得到一棵 decision tree

其中：

• Entropy 衡量一个 node 的 label 混乱程度。

• Information gain 衡量某个 split 让 entropy 降低了多少。

• High-cardinality feature 容易被 information gain 偏爱，可能导致 overfitting。

• Inductive bias 是学习算法从训练数据归纳规律时自带的偏好。

• Continuous attribute 通常通过 threshold split 处理，比如 $Age \leq 26.5$。

• Gini impurity 是另一种 impurity 指标，常用于 CART 和 sklearn 的 decision tree。

一句话记住：

决策树不是在“理解世界”，而是在不断问：当前用哪个问题 split，能让 child nodes 变得最纯？