决策树ID3算法

1. 决策树ID3算法的信息论基础

机器学习算法其实很古老，作为一个码农经常会不停的敲if, else if, else,其实就已经在用到决策树的思想了。只是你有没有想过，有这么多条件，用哪个条件特征先做if，哪个条件特征后做if比较优呢？怎么准确的定量选择这个标准就是决策树机器学习算法的关键了。1970年代，一个叫昆兰的大牛找到了用信息论中的熵来度量决策树的决策选择过程，方法一出，它的简洁和高效就引起了轰动，昆兰把这个算法叫做ID3。下面我们就看看ID3算法是怎么选择特征的。

首先，我们需要熟悉信息论中熵的概念。熵度量了事物的不确定性，越不确定的事物，它的熵就越大。具体的，随机变量X的熵的表达式如下：

$$H(X)=-\sum _{i=1}^n{p}_{i}log{p}_i$$

其中n代表X的n种不同的离散取值。而$$p_i$$代表了X取值为i的概率，log为以2或者e为底的对数。举个例子，比如X有2个可能的取值，而这两个取值各为1/2时X的熵最大，此时X具有最大的不确定性。值为$$H(X)=-(\frac{1}{2}log\frac{1}{2}+\frac{1}{2}log\frac{1}{2})=log2$$。如果一个值概率大于1/2，另一个值概率小于1/2，则不确定性减少，对应的熵也会减少。比如一个概率1/3，一个概率2/3，则对应熵为$$H(X)=-(\frac{1}{3}log\frac{1}{3}+\frac{2}{3}log\frac{2}{3})=log3-\frac{2}{3}log2<log2)$$

熟悉了一个变量X的熵，很容易推广到多个个变量的联合熵，这里给出两个变量X和Y的联合熵表达式：

$$H(X,Y)=-\sum _{i=1}^{n}p(x_i,y_i)logp(x_i,y_i)$$

有了联合熵，又可以得到条件熵的表达式H(X|Y)，条件熵类似于条件概率,它度量了我们的X在知道Y以后剩下的不确定性。表达式如下：

$$H(X|Y)=-\sum _{i=1}^{n}p(x_i,y_i)logp(x_i|y_i)=\sum _{j=1}^{n}p(y_j)H(X|y_j)$$

好吧，绕了一大圈，终于可以重新回到ID3算法了。我们刚才提到H(X)度量了X的不确定性，条件熵H(X|Y)度量了我们在知道Y以后X剩下的不确定性，那么H(X)-H(X|Y)呢？从上面的描述大家可以看出，它度量了X在知道Y以后不确定性减少程度，这个度量我们在信息论中称为互信息，，记为I(X,Y)。在决策树ID3算法中叫做信息增益。ID3算法就是用信息增益来判断当前节点应该用什么特征来构建决策树。信息增益大，则越适合用来分类。

上面一堆概念，大家估计比较晕，用下面这个图很容易明白他们的关系。左边的椭圆代表H(X),右边的椭圆代表H(Y),中间重合的部分就是我们的互信息或者信息增益I(X,Y), 左边的椭圆去掉重合部分就是H(X|Y),右边的椭圆去掉重合部分就是H(Y|X)。两个椭圆的并就是H(X,Y)。

2. 决策树ID3算法的思路

上面提到ID3算法就是用信息增益大小来判断当前节点应该用什么特征来构建决策树，用计算出的信息增益最大的特征来建立决策树的当前节点。这里我们举一个信息增益计算的具体的例子。比如我们有15个样本D，输出为0或者1。其中有9个输出为0， 6个输出为1。 样本中有个特征A，取值为A1，A2和A3。在取值为A1的样本的输出中，有3个输出为1， 2个输出为0，取值为A2的样本输出中,2个输出为1,3个输出为0， 在取值为A3的样本中，4个输出为1，1个输出为0.

样本D的熵为：$$H(D)=-(\frac{9}{15}lo{g}_2\frac{9}{15}+\frac{6}{15}lo{g}_2\frac{6}{15})=0.971$$

样本D在特征下的条件熵为： $$H(D|A)=\frac{5}{15}H(D1)+\frac{5}{15}H(D2)+\frac{5}{15}H(D3)$$

$$=-\frac{5}{15}(\frac{3}{5}lo{g}_2\frac{3}{5}+\frac{2}{5}lo{g}_2\frac{2}{5})-\frac{5}{15}(\frac{2}{5}lo{g}_2\frac{2}{5}+\frac{3}{5}lo{g}_2\frac{3}{5})-\frac{5}{15}(\frac{4}{5}lo{g}_2\frac{4}{5}+\frac{1}{5}lo{g}_2\frac{1}{5})=0.888$$

对应的信息增益为$$I(D,A)=H(D)-H(D|A)=0.083$$

下面我们看看具体算法过程大概是怎么样的。

输入的是m个样本，样本输出集合为D，每个样本有n个离散特征，特征集合即为A，输出为决策树T。

算法的过程为：

1)初始化信息增益的阈值ϵ

2）判断样本是否为同一类输出Di，如果是则返回单节点树T。标记类别为Di

3) 判断特征是否为空，如果是则返回单节点树T，标记类别为样本中输出类别D实例数最多的类别。

4）计算A中的各个特征（一共n个）对输出D的信息增益，选择信息增益最大的特征Ag

5) 如果Ag的信息增益小于阈值ϵ，则返回单节点树T，标记类别为样本中输出类别D实例数最多的类别。

6）否则，按特征Ag的不同取值Agi将对应的样本输出D分成不同的类别Di。每个类别产生一个子节点。对应特征值为Agi。返回增加了节点的数T。

7）对于所有的子节点，令D=Di,A=A−{Ag}递归调用2-6步，得到子树Ti并返回。

3. 决策树ID3算法的不足

ID3算法虽然提出了新思路，但是还是有很多值得改进的地方。

a)ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。

b)ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。如果校正这个问题呢？

c) ID3算法对于缺失值的情况没有做考虑

d) 没有考虑过拟合的问题