ID3决策树算法：根节点选择示例

ID3决策树算法：根节点选择示例

一、题目描述

给定一个关于游戏策略的样本数据集，要求使用ID3算法找出决策树的根节点。

数据集如下：

二、核心原理

ID3算法通过计算每个属性的信息增益 (Information Gain) 来选择最优的划分属性。信息增益越大的属性，越能有效地降低数据集的“不纯度”，因此被选为当前的分裂节点。根节点就是所有属性中信息增益最大的那一个。

三、计算过程

第一步：计算整个数据集的初始信息熵 $H(S)$

信息熵代表了数据集的不确定性程度。对于目标“策略”来说，有两种结果：战斗（2次）和逃跑（2次）。

• $P(战斗) = 2/4 = 0.5$
• $P(逃跑) = 2/4 = 0.5$

根据信息熵公式 $H(S) = -\sum p_i \log_2(p_i)$：
$$H(S) = - (0.5 \log_2(0.5) + 0.5 \log_2(0.5)) = 1$$

第二步：计算每个属性的信息增益 $\text{Gain}(S, A)$

信息增益的公式为：$\text{Gain}(S, A) = H(S) - \sum_{v} \frac{|S_v|}{|S|} H(S_v)$

1. 属性“武器”

   • 划分子集：{机枪 (2条), 步枪 (2条)}
   • 信息增益: $\text{Gain}(S, 武器) = H(S) - \left( \frac{2}{4}H(S_{机枪}) + \frac{2}{4}H(S_{步枪}) \right) = 1 - \left( 0.5 \times 1 + 0.5 \times 1 \right) = 0$

2. 属性“子弹数量”

   • 划分子集：{多 (3条), 少 (1条)}
   • $H(S_{多}) = -(\frac{2}{3}\log_2\frac{2}{3} + \frac{1}{3}\log_2\frac{1}{3}) \approx 0.918$
   • $H(S_{少}) = 0$ （纯集合）
   • 信息增益: $\text{Gain}(S, 子弹数量) = H(S) - \left( \frac{3}{4}H(S_{多}) + \frac{1}{4}H(S_{少}) \right) = 1 - (0.75 \times 0.918 + 0.25 \times 0) \approx 0.311$

3. 属性“生命值”

   • 划分子集：{多 (2条), 少 (2条)}
   • 信息增益: $\text{Gain}(S, 生命值) = H(S) - \left( \frac{2}{4}H(S_{多}) + \frac{2}{4}H(S_{少}) \right) = 1 - (0.5 \times 1 + 0.5 \times 1) = 0$

四、结论

比较所有属性的信息增益：

属性 “子弹数量” 的信息增益最大，因此ID3算法选择它作为决策树的 根节点。