[笔记]ID3算法与C4.5算法

1、简介

ID3算法(Iterative Dichotomiser 3 迭代二叉树3代)是一个由Ross Quinlan发明的用于决策树算法

C4.5算法是由Ross Quinlan开发的用于产生决策树的算法。该算法是对Ross Quinlan之前开发的ID3算法的一个扩展。C4.5算法产生的决策树可以被用作分类目的,因此该算法也可以用于统计分类

C4.5算法与ID3算法一样使用了信息熵的概念,并和ID3一样通过学习数据来建立决策树。

以上内容来自维基百科,更多信息:ID3算法C4.5算法

2、熵(信息论)

假定在一个系统$S$内,存在多个事件$S=\left\{ {{E}_{1}},{{E}_{2}},\cdots ,{{E}_{n}} \right\}$,概率分布为$P=\left\{ {{p}_{1}},{{p}_{2}},\cdots ,{{p}_{n}} \right\}$,其中$\sum\limits_{i=1}^{n}{{{p}_{i}}}=1$,则每个事件本身的信息量为:

\[I\left( {{E}_{i}} \right)=-{{\log }_{2}}{{p}_{i}}\]

\[I\left( {{E}_{i}} \right)=-\ln {{p}_{i}}\]

两种定义本质是一样的,仅是单位不同而已。前者单位是:比特 / bit,后者单位是:纳特 / nats 。下面默认使用第一种定义。

信息熵(即信息论中据说的熵)定义为整个系统的平均信息量:

\[H\left( S \right)=\sum\limits_{i=1}^{n}{{{p}_{i}}I\left( {{E}_{i}} \right)}=-\sum\limits_{i=1}^{n}{{{p}_{i}}{{\log }_{2}}{{p}_{i}}}\]

例如:对于同一篇文章,一般来说,用汉语比用英语更省篇幅。这是由于,平均每个汉字的信息量(假设每个汉字出现频率相等时,$I\left( HanZi \right)={{\log }_{2}}2500$)大于字母的信息量($I\left( Letter \right)={{\log }_{2}}26$)。

信息熵的一些性质

  • 熵是非负的,即$H\left( S \right)\ge 0$。
  • 设$n$是系统$S$的事件总数,则$H\left( S \right)\le {{\log }_{2}}n$。当且仅当所有${{p}_{i}}$相等时等号成立。
  • 联合熵:$H\left( X,Y \right)\le H\left( X \right)+H\left( Y \right)$,当且仅当$X$与$Y$相互独立时等号成立。
  • 条件熵:$H\left( X|Y \right)=H\left( X,Y \right)-H\left( Y \right)\le H\left( X \right)$,当且仅当$X$与$Y$相互独立时等号成立。

3、ID3算法

  1. 计算分类信息$D$的信息熵$H\left( D \right)$;
  2. 计算每个属性对类别的期望信息量${{H}_{A}}\left( D \right)=\sum\limits_{j=1}^{{{n}_{A}}}{{{p}_{A=j}}H\left( {{D}_{A=j}} \right)}$(详细定义见下文的案例);
  3. 计算每个属性的信息增益$G\left( A \right)=H\left( D \right)-{{H}_{A}}\left( D \right)$;
  4. 选择信息增益最大的属性进行第1次分裂;
  5. 更新数据,重复上面的操作,直到不能再分,或达到指定的阈值。

案例

案例数据
A属性 B属性 C属性 D类别
1 1 2 类1
1 1 2 类1
1 1 3 类1
1 1 1 类2
1 1 2 类2
1 1 3 类2
1 0 1 类1
1 0 2 类1
1 0 1 类1
1 0 1 类1
10个1 6个1,4个0 4个1,4个2,2个3 7个类1,3个类2

 

这里,用$D$表示训练集的类别。则有:$H\left( D \right)=-\left( 0.7\times {{\log }_{2}}0.7+0.3\times {{\log }_{2}}0.3 \right)\approx 0.8813$。

[定义] 属性$A$对类别$D$的期望信息量为:

\[{{H}_{A}}\left( D \right)=\sum\limits_{j=1}^{{{n}_{A}}}{{{p}_{A=j}}H\left( {{D}_{A=j}} \right)}\]

其中,${{n}_{A}}$表示属性$A$中不同属性的个数,${{D}_{A=j}}$表示在$A=j$的情况下的$D$分布。计算过程如下:

${{H}_{A}}\left( D \right)=H\left( D \right)\approx 0.8813$

${{H}_{B}}\left( D \right)=0.6\left( -\frac{3}{6}{{\log }_{2}}\frac{3}{6}-\frac{3}{6}{{\log }_{2}}\frac{3}{6} \right)+0.4\left( -\frac{0}{4}{{\log }_{2}}\frac{0}{4}-\frac{4}{4}{{\log }_{2}}\frac{4}{4} \right)=0.6$

${{H}_{C}}\left( D \right)=0.4\left( -\frac{1}{4}{{\log }_{2}}\frac{1}{4}-\frac{3}{4}{{\log }_{2}}\frac{3}{4} \right)+0.4\left( -\frac{1}{4}{{\log }_{2}}\frac{1}{4}-\frac{3}{4}{{\log }_{2}}\frac{3}{4} \right)$

$+0.2\left( -\frac{1}{2}{{\log }_{2}}\frac{1}{2}-\frac{1}{2}{{\log }_{2}}\frac{1}{2} \right)\approx 0.8490$

信息增益定义为:

$G\left( A \right)=H\left( D \right)-{{H}_{A}}\left( D \right)=0$

$G\left( B \right)=H\left( D \right)-{{H}_{B}}\left( D \right)\approx 0.2813$

$G\left( C \right)=H\left( D \right)-{{H}_{C}}\left( D \right)\approx 0.0323$

由于$G\left( B \right)$最大,所以应该按属性$B$进行第1次分裂,如下图:

之后再新的数据重复上面的操作,直到不能再分,或达到指定的阈值。

ID3

4、C4.5算法

ID3算法存在一个问题,就是偏向于多值属性,例如,如果存在唯一标识属性ID,则ID3会选择它作为分裂属性,这样虽然使得划分充分纯净,但这种划分对分类几乎毫无用处。ID3的后继算法C4.5使用增益率(gain ratio)的信息增益扩充,试图克服这个偏倚。

C4.5算法首先定义了“分裂信息”(Split Information),其定义可以表示成:

\[Si\left( A \right)=-\sum\limits_{j=1}^{{{n}_{A}}}{{{p}_{A=j}}{{\log }_{2}}{{p}_{A=j}}=H\left( A \right)}\]

其中各符号意义与ID3算法相同,然后,增益率被定义为:

\[Gr\left( A \right)=\frac{G\left( A \right)}{Si\left( A \right)}\]

C4.5选择具有最大增益率的属性作为分裂属性,其具体应用与ID3类似,不再赘述。

5、关于决策树的几点补充说明

5.1、如果属性用完了怎么办

在决策树构造过程中可能会出现这种情况:所有属性都作为分裂属性用光了,但有的子集还不是纯净集,即集合内的元素不属于同一类别。在这种情况下,由于没有更多信息可以使用了,一般对这些子集进行“多数表决”,即使用此子集中出现次数最多的类别作为此节点类别,然后将此节点作为叶子节点。

5.2、关于剪枝

在实际构造决策树时,通常要进行剪枝,这时为了处理由于数据中的噪声和离群点导致的过分拟合问题。剪枝有两种:

先剪枝——在构造过程中,当某个节点满足剪枝条件,则直接停止此分支的构造。

后剪枝——先构造完成完整的决策树,再通过某些条件遍历树进行剪枝。

 

★ 参考资料

  1. 《数据挖掘十大算法》,ISBN 9787302310617,第一章
  2. http://blog.csdn.net/baiyangdfish/article/details/7023751
  3. http://blog.sina.com.cn/s/blog_6e85bf420100ohma.html
  4. http://blog.sina.com.cn/s/blog_68ffc7a40100urn3.html
  5. http://blog.sina.com.cn/s/blog_68ffc7a40100urn3.html
  6. http://zh.wikipedia.org/wiki/%E4%BF%A1%E6%81%AF%E7%86%B5

About the Author

野鹤

自由学者,爱好广泛,虽无一精通,却常乐在其中...

本博客已停止更新,请您移步到我的新博客阅读更多文章。