决策树算法-id3

## 1 问题描述

我们统计了 14 天的气象数据，数据指标包括 `outlook、temperature、humidity、windy`，并且已知这些天气是否打球，如果给出新一天的气象指标数据，判断一下会不会去打球。

气象数据如下表：

| outlook  | temperature | humidity | windy | play |
| -------- | ----------- | -------- | ----- | ---- |
| sunny    | hot         | high     | FALSE | no   |
| sunny    | hot         | high     | TRUE  | no   |
| overcast | hot         | high     | FALSE | yes  |
| rainy    | mild        | high     | FALSE | yes  |
| rainy    | cool        | normal   | FALSE | yes  |
| rainy    | cool        | normal   | TRUE  | no   |
| overcast | cool        | normal   | TRUE  | yes  |
| sunny    | mild        | high     | FALSE | no   |
| sunny    | cool        | normal   | FALSE | yes  |
| rainy    | mild        | normal   | FALSE | yes  |
| sunny    | mild        | normal   | TRUE  | yes  |
| overcast | mild        | high     | TRUE  | yes  |
| overcast | hot         | normal   | FALSE | yes  |
| rainy    | mild        | high     | TRUE  | no   |

## 2 预备知识

### 2.1 信息熵

![](/media/202103/2021-03-30_153615.png)

![20170819201517201 (727×201)](/media/202103/2021-03-30_154653.png)

### 2.2 信息增益

![20170819201245769 (835×498)](/media/202103/2021-03-30_154802.png)

![20170819201302423 (832×498)](/media/202103/2021-03-30_154826.png)

## 3 预测过程

如果一个属性的信息增益越大，这个属性作为一棵树的根节点就能使这棵树更简洁，比如：

* 如果风力弱，就去玩；风力强，再按天气、温度等情况讨论，此时用风力作为这棵树的根节点就很有价值。
* 如果风力弱，再又天气晴朗，就去玩；如果风力强，再又怎么怎么分情况讨论，这棵树相比就不够简洁了。

### 3.1 计算分类系统熵

类别是是否出去玩。取值为 `yes` 的有 9 个，取值为 `no` 的有 5 个，即说这个样本里有 9 个正例，5 个负例，记为 `S(9+,5-)`，其中 `S` 是样本的意思（Sample）。那么

$$
P(c1)=9/14, P(c2)=5/14
$$

这里熵记为 $Entropy(S)$，计算公式为：

$$
Entropy(S)=-(9/14)\ast\log2(9/14)-(5/14)\ast\log2(5/14)
$$

### 3.2 计算不同特征值下系统的信息增益

#### 3.2.1 windy

当 `windy` 固定为 `False` 时：记录有 8 条，其中正例 6 个，负例 2 个。则其对应的熵为：

$$
Entropy(False)=-(6/8)\ast\log2(6/8)-(2/8)\ast\log(2/8)={0.811}
$$

同样，取值为 `True` 的记录有 6 条，正例负例各 3 个。则其对应的熵为：

$$
Entropy(True)=-(3/6)\ast\log(3/6)-(3/6)\ast\log(3/6)=1.0
$$

所以，对于一个 `windy` 属性固定的分类系统的熵为：

$$
Entropy(windy)=(8/14)\ast Entropy(False)+(6/14)\ast Entropy(True)
$$

因此其对应的信息增益为：

$$
Gain(windy)=Entropy(S)-Entropy(windy)=0.048
$$

#### 3.2.2 其他特征

$$
\begin{array}{l}Gain(humidity)={0.151}\\Gain(outlook)=0.247\\Gain(temperature)=0.029\end{array}
$$

最后按照信息增益最大的原则选 `outlook` 为根节点。子节点重复上面的步骤，直到得到一颗决策树为止。

### 3.3 预测结果

按照上面的步骤最后得到的决策树如下：

![20170819201823694 (533×425)](/media/202103/2021-03-30_163805.png)

## 4 优缺点

### 4.1 优点

1. 假设空间包含所有的决策树，搜索空间完整。
2. 健壮性好，不易受噪声影响。
3. 可以训练缺少属性值的实例。

### 4.2 缺点

1. 没有剪枝策略，容易过拟合。
2. 信息增益准则对可取数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1。
3. 只能用于处理离散分布的特征。
4. 没有考虑缺失值。

## 5 参考文献

1. [分类算法之决策树 ID3 详解](https://blog.csdn.net/qq_36330643/article/details/77415451);
2. [对 ID3 算法的理解及其优缺点](https://blog.csdn.net/weixin_45834080/article/details/103036401);
3. [【机器学习】决策树（上）——ID3、C4.5、CART（非常详细）](https://zhuanlan.zhihu.com/p/85731206?utm_source=wechat_timeline);