# 5.决策树——每次选一边

Decision tree



### 知识树

Knowledge tree

![1618575672562](assets/1618575672562.png)



### 一个小故事

A story

挑苹果：

![1618575710142](assets/1618575710142.png)

> 根据这些特征，如颜色是否是红色、硬度是否是硬、香味是否是香，如果全部满足绝对是好苹果，或者红色+硬但是无味也是好苹果，从上图可以看出来，只要做足够的循环判断即可得到结果。

如下图：

![1618576033128](assets/1618576033128.png)

> 一步步走下来，就能挑到好苹果。这就是决策树

1. 最顶端的叫根节点，所有样本的预测都是从根节点开始。
2. 每一个圆形节点表示判断，每个节点只对样本的某个属性进行判断。
3. 圆形节点是标记节点，走到圆形节点表示判断结束，将圆形节点中的标签作为对应的预测结果。

如何构建决策树：

1. 构建的决策树按顺序对每个特征进行判断（低效）
2. 每个判断节点都尽可能让一半进入A分支，另一半进入B分支（高效）

引入新的知识，信息熵



### 信息熵

Information entropy

1. 每走一步，我们都在确定苹果的好坏。
2. 在根节点时，我们对苹果的好坏一无所知。
3. 经过对颜色的判断后，如果是红色，我们明白好坏的概率是1/2。虽然还包含了1/2的不确定性。
4. 如果苹果红色的前提下又硬，我们100%确定它是好苹果。此时不确定性坍塌为0。
5. 这是一个减少不确定性的过程。

从整体来讲，我们希望决策树每走一步，不确定性都下降的快一些，让我们的判断步数无限小。

**什么是信息的不确定性？**

就是信息熵

在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量，设X是一个取有限个值的离散随机变量，其概率分布为

![1618576749908](assets/1618576749908.png)

则随机变量X的熵定义为

![1618576770871](assets/1618576770871.png)

> 面试可能会问到这个公式，还有交叉熵、相对熵

熵越大，则随机变量的不确定性越大。其中0 ≤ H(P) ≤ log n



### 举例计算

Example

假设投色子，6个的概率分别是1/6，计算如下：

![1618577639913](assets/1618577639913.png)

> 其中6个1/6（log左边的六分之一）加起来就是1

![1618577661694](assets/1618577661694.png)

> ![1618577700910](assets/1618577700910.png)

则最终=log6

这也解释了为什么上面H(P) ≤ log n

另外，均由分布的时候，熵最大，因为所有可能都是一样的，如上面的6个面都是1/6。



如果有1个坏苹果和9个好苹果时，我们可以认为大部分都是坏苹果。内部并不混乱，确定性很大，熵很小。



### 信息增益

Information gain

表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

特征A对训练集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：g(D, A) = H(D) - H(D|A)

当前的信息熵等于划分完（如划分成两个）的信息熵之和。



**信息增益算法**

输入：训练数据集D和特征A

输出：特征A对训练数据集D的信息

1. 计算数据集D的经验熵H(D)

   ![1618582986891](assets/1618582986891.png)

2. 计算特征A对数据集D的经验条件熵H(D|A)

   ![1618583056578](assets/1618583056578.png)

   ![1618583066653](assets/1618583066653.png)

3. 计算信息增益

   ![1618583156554](assets/1618583156554.png)



### 举个例子

Example

是否信贷

| ID   | 年龄 | 有工作 | 有自己房子 | 信贷情况 | 类别 |
| ---- | ---- | ------ | ---------- | -------- | ---- |
| 1    | 青年 | 否     | 否         | 一般     | 否   |
| 2    | 青年 | 否     | 否         | 好       | 否   |
| 3    | 青年 | 是     | 否         | 好       | 是   |
| 4    | 青年 | 是     | 是         | 一般     | 是   |
| 5    | 青年 | 否     | 否         | 一般     | 否   |
| 6    | 中年 | 否     | 否         | 一般     | 否   |
| 7    | 中年 | 否     | 否         | 好       | 否   |
| 8    | 中年 | 是     | 是         | 好       | 是   |
| 9    | 中年 | 否     | 是         | 非常好   | 是   |
| 10   | 中年 | 否     | 是         | 非常好   | 是   |
| 11   | 老年 | 否     | 是         | 非常好   | 是   |
| 12   | 老年 | 否     | 是         | 好       | 是   |
| 13   | 老年 | 是     | 否         | 好       | 是   |
| 14   | 老年 | 是     | 否         | 非常好   | 是   |
| 15   | 老年 | 否     | 否         | 一般     | 否   |



对上表所给的训练数据集D，根据信息增益准则选择最优特征。首先计算经验熵H(D)

![1618747519765](assets/1618747519765.png)

> 计算类别：一共15个类别，9个是，6个否

然后计算各特征对数据集D的信息增益，分别以A1,A2,A3,A4表示年龄、有工作、有自己房子和信贷情况4个特征，则

1. 首先计算年龄![1618747694405](assets/1618747694405.png)

   > H(D)=0.971上面计算了，H(D1)青年，H(D2)中年，H(D3)老年

2. 计算有工作

   ![1618747990121](assets/1618747990121.png)

   > H(D)=0.971，H(D1)是有工作，H(D2)是无工作

3. 计算有无房子

   ![1618748039172](assets/1618748039172.png)

4. 计算信贷情况

   ![1618748063199](assets/1618748063199.png)

有无房子是作为信贷的第一个划分，下降的最快



### 信息增益比

Information gain ratio

**信息增益比：**

如果以信息增益为划分依据，存在偏向选择取值较多的特征，信息增益是对这一问题进行矫正。

**举例**：

如上面的例子，后面加入了身份证这个特征，身份证又是唯一的，算法对样本画了个15叉树，一层就搞定了全部的分类。

这样会造成一个问题，划分会倾向于特征取值数目较多的，即分的更快。

但在预测集上就出现很大的问题了，即预测集的身份证肯定也是唯一的。

**定义：**

特征A对训练数据集D的信息增益比![1618748316870](assets/1618748316870.png)定义为其信息增益g(D,A)与训练数据集D关于特征A的经验熵H(D)之比：

![1618749594369](assets/1618749594369.png)

**计算**：

如上面的年龄，有3个类（青年、中年、老年），![1618749717493](assets/1618749717493.png)



信息增益比和信息增益的区别就是除以![1618749843112](assets/1618749843112.png)



### 决策树的构建

Build the decision tree

ID3算法：

- 输入：训练数据集D，特征A，阈值ε ；
- 输出：决策树T
  1. 若D中所有实例属于同一类![1618749968444](assets/1618749968444.png)，则T为单节点数，并将类![1618749968444](assets/1618749968444.png)作为该节点的类标记，返回T；
  2. 若A = Ø，则T为单节点树，并将D中实例数最大的类![1618749968444](assets/1618749968444.png)作为该节点的类标记，返回T；
  3. 否则，按算法计算A中各特征对D的信息增益，选择信息增益最大的特征Ag；
  4. 如果Ag的信息增益小于阈值ε，则置T为单节点树，并将D中实例数最大的类![1618749968444](assets/1618749968444.png)作为该节点的类标记，返回T；
  5. 否则，对Ag的每一个可能值ai，依![1618750408613](assets/1618750408613.png)将D分割为若干非空子集Di，将Di中实例最大的类作为标记，构建子节点，由节点及其子节点构成树T，返回T；
  6. 对第i个子节点，以Di为训练集，以A - {Ag}为特征集，递归地调用1~5步，得到树Ti，返回Ti。

C4.5算法，大体相同，只不过计算的是信息增益比，而不是信息增益。我们通常也是用C4.5作为决策树的算法，其区别也就在于多了个分母。



### 总结

Summarization

1. 决策树的核心思想：以树结构为基础，每个节点对某特征进行判断，进入分支，直到到达叶节点。

2. 决策树构造的核心思想：让信息熵快速下降，从而达到最少的判断次数获得标签。

3. 判断信息熵下降速度的方法：信息增益。

4. 构建决策树算法：ID3（使用信息增益）、C4.5（使用使用信息增益比）。

5. 信息增益会导致节点偏向选取取值角度的特征的问题。

   > 关于第5点的补充，统计学习和西瓜书都是给的这个解释，但还有另一种解释，就是信息增益导致大数问题——>概率是否准确的问题。

