1、简介
ID3算法(Iterative Dichotomiser 3 迭代二叉树3代)是一个由Ross Quinlan发明的用于决策树的算法。
C4.5算法是由Ross Quinlan开发的用于产生决策树的算法。该算法是对Ross Quinlan之前开发的ID3算法的一个扩展。C4.5算法产生的决策树可以被用作分类目的,因此该算法也可以用于统计分类。
C4.5算法与ID3算法一样使用了信息熵的概念,并和ID3一样通过学习数据来建立决策树。
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算法
- 计算分类信息$D$的信息熵$H\left( D \right)$;
- 计算每个属性对类别的期望信息量${{H}_{A}}\left( D \right)=\sum\limits_{j=1}^{{{n}_{A}}}{{{p}_{A=j}}H\left( {{D}_{A=j}} \right)}$(详细定义见下文的案例);
- 计算每个属性的信息增益$G\left( A \right)=H\left( D \right)-{{H}_{A}}\left( D \right)$;
- 选择信息增益最大的属性进行第1次分裂;
- 更新数据,重复上面的操作,直到不能再分,或达到指定的阈值。
案例
案例数据 | |||
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次分裂,如下图:
之后再新的数据重复上面的操作,直到不能再分,或达到指定的阈值。
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、关于剪枝
在实际构造决策树时,通常要进行剪枝,这时为了处理由于数据中的噪声和离群点导致的过分拟合问题。剪枝有两种:
先剪枝——在构造过程中,当某个节点满足剪枝条件,则直接停止此分支的构造。
后剪枝——先构造完成完整的决策树,再通过某些条件遍历树进行剪枝。
★ 参考资料
- 《数据挖掘十大算法》,ISBN 9787302310617,第一章
- http://blog.csdn.net/baiyangdfish/article/details/7023751
- http://blog.sina.com.cn/s/blog_6e85bf420100ohma.html
- http://blog.sina.com.cn/s/blog_68ffc7a40100urn3.html
- http://blog.sina.com.cn/s/blog_68ffc7a40100urn3.html
- http://zh.wikipedia.org/wiki/%E4%BF%A1%E6%81%AF%E7%86%B5
近期评论