基于 ID3 算法的决策树 -Iterative Dichotomiser 3

Note: 本文侧重讲解ID3算法背后的原理以及如何使用，⭐ 想要了解ID3算法其背后原理的朋友阅读⭐。在很多平台中都有决策树的包，调用现成的包往往只需要一行代码就可以实现复杂的决策树，非常简单，固本文不再赘述。

ID3 概念

ID3算法是由Ross Quinlan基于奥卡姆剃刀理论（Occam’s razor）所设计的一种追求精简的决策树。该算法使用一种从上到下，从root 到leaf的贪心算法区分数据建立决策树。

算法

分类过程
1. 计算数据中所有特征的information gain
2. 设information gain最高的特征为决策点
3. 根据决策点分割数据
4. 用更新的数据重复这个过程
停止条件
1. 分割数据后数据集中的特征都相同
2. 没有剩余特征，所有特征都被使用过

判断最佳决策点

用来判断最佳决策点的方法有很多，包括：

Entropy,
Information gain,
Gini index,
Gain Ratio,
Reduction in Variance
Chi-Square
其中information gain是比较常用的一种基于Entropy的判断方法。

首先介绍Entropy 的概念

Entropy可以理解为测量数据有多“不纯”(impurity)的指标，(1)比如一幅扑克牌中全都是黑桃A，我们就可以说这副牌非常的“纯”; (2)当全是黑桃A的扑克牌中混入红桃K后，这个数据集就不再单一，我们可以说这个数据集有一些“不纯”；(3)当这副扑克完全由不一样的牌组成时，数据集中没有相同的特征，我们所以我们可以称这样的情况为完全“不纯”。
Entropy的公式
- $\sum_{i=1}^{c} p_ilog_2p_i$
- pi为每一个可能结果的概率
Entropy 栗子🌰
- 在一幅有52张牌的扑克里（没有王牌）随便抽一张特定花色特定数字的牌的概率为1/52
- $\sum_{i=1}^{52} \frac{1}{52}log_2\frac{1}{52} = 5.7$

Information Gain (信息增益) 则是基于Entropy计算每次分隔数据后 {增加的信息量}/{减少的Entropy} 是多少

Information Gain 公式
- $\sum_{i}\frac{\lvert S_i \rvert}{\lvert S \rvert}Entropy(S_i)$
栗子🌰

如下表所示，计算特征Contains Images（简称CI）的Information Gain

$-(\frac{3}{6}log_2\frac{3}{6}+\frac{3}{6}log_2\frac{3}{6})=1$
$IG_{CI} = 1-(\frac{2}{6}(-(\frac{1}{2}log_2\frac{1}{2}+\frac{1}{2}log_2\frac{1}{2}))+\frac{4}{6}(-(\frac{2}{4}log_2\frac{2}{4}+\frac{2}{4}log_2\frac{2}{4})))=0$

第一个2/6代表在binary特征CI中，有2个为true；后面括号里的为在CI为true的情况下的Entropy(Si)，可以看到两个true分别对应CLASS中的一个spam和一个ham，每一个的概率都是1/2，所以有了后面括号里的Entropy(1/2)+Entropy(1/2)

Entropy 越低越好
Information Gain (信息增益) 越高越好

通过ID3建立决策树

了解了Information Gain后，有小学数学基础就可以搭建决策树了。用如下数据举个栗子，这里用R语言进行计算。

要求： 通过ID3算法预测每种产品的quality

首先读取数据，改用1 hot encoding
计算初始Entropy (S0)以及IG

因为ID3是基于二叉树的分类，而A0中有三种分类，所以我们需要把A0转换到Binary，这里考虑三种情况：{1, 2 or 3}, {2, 1 or 3}, {3, 1 or 2}. 所以Information Gain 结果的第一行为A0在分为不同情况下的信息增益，而第二行是A1,A2,A3 的信息增益

我们可以看到4个特征中IG最高的为A2 (0.42)

选择A2为决策点分割数据

分割后的数据如下表所示，在A2等于0时,所有的Q都时一样的，达到了我们的停止条件，可以不用管这个分支去看A2!=0的分支。

这时我们的决策树如下，其实到这里就时决策树的全部内容了，后面的就是重复前面的步骤就可以了。
计算新数据的初始Entropy并找到IG最高的特征

因为A2已经作为决策点在上一层使用过了，所以在IG结果的第二行可以看到只有两个数据，分别是A1和A3，这里看到A1有最高的IG，所以选用A1做决策点

根据A1分割后的数据如下，当A1!=1是，Class都是一样的，达到停止条件，去看A1=1的branch

现在我们的决策数长成了这样

5. 继续重复，胜利在望
这时我们仅需要处理这个小数据集了

计算Entropy和IG