使用ID3算法根据信息增益构建决策树

- - 1. 计算数据集的熵（Entropy of the dataset）
  - 2. 按特征划分数据集并计算条件熵
  - - （1）特征 `election`
    - （2）特征 `season`
    - （3）特征 `oil price`
  - 3. 总结信息增益
  - 4 根节点选择
  - 5. 根据 `oil price` 划分数据集
  - - (1) 子集 1: `oil price = rise`
    - (2) 子集 2: `oil price = fall`
  - 6. 对 `oil price = rise` 的子集继续划分
  - - (1) 特征 `election`
    - (2) 特征 `season`
    - (3) 选择划分特征
  - 7. 根据 `election` 划分子集
  - - (1) 子集 1: `election = yes`
    - (2) 子集 2: `election = no`
  - 8. 对 `election = yes` 的子集继续划分
  - 9. 构建完整决策树

根据ID3（信息增益）方法利用以下数据集构建决策树。

election	season	oil price	stock price
no	winter	rise	rise
no	summer	fall	fall
no	summer	rise	rise
yes	winter	rise	fall
no	winter	fall	fall
yes	summer	rise	rise
yes	summer	fall	fall
yes	winter	fall	fall

1. 计算数据集的熵（Entropy of the dataset）

熵的公式为：

$\sum_{i=1}^n p_i \log_2(p_i)$

其中 $p_i$ 是每个类别的概率。

在数据集中，最后一列 stock price 有两种可能的值：rise 和 fall。统计每种值的频率：

rise 出现了 3 次。
fall 出现了 5 次。
数据集总共有 8 条记录。

因此，rise 的概率 $\frac{3}{8}$ ，fall 的概率 $\frac{5}{8}$ 。

熵 $H (S)$ 为：

$\left( \frac{3}{8} \log_2 \frac{3}{8} + \frac{5}{8} \log_2 \frac{5}{8} \right)$

计算：

$\left( 0.375 \log_2 0.375 + 0.625 \log_2 0.625 \right)$

$\log_2 0.375 \approx -1.415, \quad \log_2 0.625 \approx -0.678$

$\left( 0.375 \times -1.415 + 0.625 \times -0.678 \right)$

$\left( -0.5306 - 0.42375 \right) = 0.95435$

数据集的熵为 $\approx 0.954$ 。

2. 按特征划分数据集并计算条件熵

我们需要分别计算每个特征（election、season、oil price）的条件熵。

（1）特征 `election`

election 有两个取值：yes 和 no。

当 election = yes 时，有 4 条记录，其中：
- rise 出现 1 次，fall 出现 3 次。
- 熵为：
  $\left( \frac{1}{4} \log_2 \frac{1}{4} + \frac{3}{4} \log_2 \frac{3}{4} \right)$
  $\left( 0.25 \times -2 + 0.75 \times -0.415 \right) = 0.811$
当 election = no 时，有 4 条记录，其中：
- rise 出现 2 次，fall 出现 2 次。
- 熵为：
  $\left( \frac{2}{4} \log_2 \frac{2}{4} + \frac{2}{4} \log_2 \frac{2}{4} \right)$
  $\left( 0.5 \times -1 + 0.5 \times -1 \right) = 1$

条件熵 $H (S ∣ e l ec t i o n)$ 为：

$\frac{4}{8} H(S|election=yes) + \frac{4}{8} H(S|election=no)$

$\times 0.811 + 0.5 \times 1 = 0.9055$

信息增益 $I G (S, e l ec t i o n)$ 为：

$I G (S, e l ec t i o n) = H (S) - H (S ∣ e l ec t i o n)$

$I G (S, e l ec t i o n) = 0.954 - 0.9055 = 0.0485$

（2）特征 `season`

season 有两个取值：winter 和 summer。

当 season = winter 时，有 4 条记录，其中：
- rise 出现 1 次，fall 出现 3 次。
- 熵为：
  $\left( \frac{1}{4} \log_2 \frac{1}{4} + \frac{3}{4} \log_2 \frac{3}{4} \right) = 0.811$
当 season = summer 时，有 4 条记录，其中：
- rise 出现 2 次，fall 出现 2 次。
- 熵为：
  $\left( \frac{2}{4} \log_2 \frac{2}{4} + \frac{2}{4} \log_2 \frac{2}{4} \right) = 1$

条件熵 $H (S ∣ se a so n)$ 为：

$\frac{4}{8} H(S|season=winter) + \frac{4}{8} H(S|season=summer)$

$\times 0.811 + 0.5 \times 1 = 0.9055$

信息增益 $I G (S, se a so n)$ 为：

$I G (S, se a so n) = H (S) - H (S ∣ se a so n)$

$I G (S, se a so n) = 0.954 - 0.9055 = 0.0485$

（3）特征 `oil price`

oil price 有两个取值：rise 和 fall。

当 oil price = rise 时，有 4 条记录，其中：
- rise 出现 3 次，fall 出现 1 次。
- 熵为：
  $\left( \frac{3}{4} \log_2 \frac{3}{4} + \frac{1}{4} \log_2 \frac{1}{4} \right)$
  $\left( 0.75 \times -0.415 + 0.25 \times -2 \right) = 0.811$
当 oil price = fall 时，有 4 条记录，其中：
- rise 出现 0 次，fall 出现 4 次。
- 熵为：
  $\left( \frac{0}{4} \log_2 \frac{0}{4} + \frac{4}{4} \log_2 \frac{4}{4} \right) = 0$

条件熵 $H (S ∣ o i lp r i ce)$ 为：

$\frac{4}{8} H(S|oil price=rise) + \frac{4}{8} H(S|oil price=fall)$

$\times 0.811 + 0.5 \times 0 = 0.4055$

信息增益 $I G (S, o i lp r i ce)$ 为：

$I G (S, o i lp r i ce) = H (S) - H (S ∣ o i lp r i ce)$

$I G (S, o i lp r i ce) = 0.954 - 0.4055 = 0.5485$

3. 总结信息增益

$I G (S, e l ec t i o n) = 0.0485$
$I G (S, se a so n) = 0.0485$
$I G (S, o i lp r i ce) = 0.5485$

因此，oil price 是信息增益最大的特征。

4 根节点选择

在上一步中，我们计算了各特征的信息增益：

$I G (S, e l ec t i o n) = 0.0485$
$I G (S, se a so n) = 0.0485$
$I G (S, o i lp r i ce) = 0.5485$

由于 oil price 的信息增益最大，我们选择 oil price 作为根节点。

5. 根据 `oil price` 划分数据集

oil price 有两个取值：rise 和 fall。

(1) 子集 1: `oil price = rise`

当 oil price = rise 时，数据如下：

election	season	oil price	stock price
no	winter	rise	rise
no	summer	rise	rise
yes	winter	rise	fall
yes	summer	rise	rise

stock price = rise 出现 3 次。
stock price = fall 出现 1 次。

熵为：

$\left( \frac{3}{4} \log_2 \frac{3}{4} + \frac{1}{4} \log_2 \frac{1}{4} \right)$

$\left( 0.75 \times -0.415 + 0.25 \times -2 \right) = 0.811$

由于熵不为 0，oil price = rise 的子集还需要进一步划分。

(2) 子集 2: `oil price = fall`

当 oil price = fall 时，数据如下：

election	season	oil price	stock price
no	summer	fall	fall
no	winter	fall	fall
yes	summer	fall	fall
yes	winter	fall	fall

stock price = rise 出现 0 次。
stock price = fall 出现 4 次。

熵为：

$\left( \frac{0}{4} \log_2 \frac{0}{4} + \frac{4}{4} \log_2 \frac{4}{4} \right) = 0$

由于熵为 0，oil price = fall 的子集是纯的，不需要进一步划分。此时，stock price = fall 是叶节点。

6. 对 `oil price = rise` 的子集继续划分

现在我们只需要处理 oil price = rise 的子集：

election	season	oil price	stock price
no	winter	rise	rise
no	summer	rise	rise
yes	winter	rise	fall
yes	summer	rise	rise

我们再次计算剩余特征的信息增益。

(1) 特征 `election`

election 有两个取值：yes 和 no。

当 election = yes 时，有 2 条记录，其中：
- rise 出现 1 次，fall 出现 1 次。
- 熵为：
  $\left( \frac{1}{2} \log_2 \frac{1}{2} + \frac{1}{2} \log_2 \frac{1}{2} \right) = 1$
当 election = no 时，有 2 条记录，其中：
- rise 出现 2 次，fall 出现 0 次。
- 熵为：
  $\left( \frac{2}{2} \log_2 \frac{2}{2} + \frac{0}{2} \log_2 \frac{0}{2} \right) = 0$

条件熵 $H (S ∣ e l ec t i o n)$ 为：

$\frac{2}{4} H(S|election=yes) + \frac{2}{4} H(S|election=no)$

$\times 1 + 0.5 \times 0 = 0.5$

信息增益 $I G (S, e l ec t i o n)$ 为：

$I G (S, e l ec t i o n) = H (S ∣ o i lp r i ce = r i se) - H (S ∣ e l ec t i o n)$

$I G (S, e l ec t i o n) = 0.811 - 0.5 = 0.311$

(2) 特征 `season`

season 有两个取值：winter 和 summer。

当 season = winter 时，有 2 条记录，其中：
- rise 出现 1 次，fall 出现 1 次。
- 熵为：
  $\left( \frac{1}{2} \log_2 \frac{1}{2} + \frac{1}{2} \log_2 \frac{1}{2} \right) = 1$
当 season = summer 时，有 2 条记录，其中：
- rise 出现 2 次，fall 出现 0 次。
- 熵为：
  $\left( \frac{2}{2} \log_2 \frac{2}{2} + \frac{0}{2} \log_2 \frac{0}{2} \right) = 0$

条件熵 $H (S ∣ se a so n)$ 为：

$\frac{2}{4} H(S|season=winter) + \frac{2}{4} H(S|season=summer)$

$\times 1 + 0.5 \times 0 = 0.5$

信息增益 $I G (S, se a so n)$ 为：

$I G (S, se a so n) = H (S ∣ o i lp r i ce = r i se) - H (S ∣ se a so n)$

$I G (S, se a so n) = 0.811 - 0.5 = 0.311$

(3) 选择划分特征

election 和 season 的信息增益相同（均为 0.311）。我们可以任选一个作为划分特征。这里选择 election。

7. 根据 `election` 划分子集

(1) 子集 1: `election = yes`

当 election = yes 时，数据如下：

election	season	oil price	stock price
yes	winter	rise	fall
yes	summer	rise	rise

stock price = rise 出现 1 次。
stock price = fall 出现 1 次。

熵为：

$\left( \frac{1}{2} \log_2 \frac{1}{2} + \frac{1}{2} \log_2 \frac{1}{2} \right) = 1$

由于熵不为 0，还需要进一步划分。

(2) 子集 2: `election = no`

当 election = no 时，数据如下：

election	season	oil price	stock price
no	winter	rise	rise
no	summer	rise	rise

stock price = rise 出现 2 次。
stock price = fall 出现 0 次。

熵为：

$\left( \frac{2}{2} \log_2 \frac{2}{2} + \frac{0}{2} \log_2 \frac{0}{2} \right) = 0$

此时，stock price = rise 是叶节点。

8. 对 `election = yes` 的子集继续划分

对于 election = yes 的子集：

election	season	oil price	stock price
yes	winter	rise	fall
yes	summer	rise	rise

我们可以选择 season 作为划分特征。

当 season = winter 时，stock price = fall。
当 season = summer 时，stock price = rise。

此时，两个子集都是纯的。

9. 构建完整决策树

最终决策树如下：

oil price?
├── fall: stock price = fall
└── rise:├── election?│   ├── no: stock price = rise│   └── yes:│       ├── season?│       │   ├── winter: stock price = fall│       │   └── summer: stock price = rise