决策树相关算法研究

摘要：ID3算法和C4.5算法是经典的决策树算法，通过对ID3算法和C4.5算法的数据结构、算法描述和分裂属性选取等方面进行比较，为其他研究者提供参考。

关键词：分类；ID3；C4.5

中图分类号：TP312文献标识码：A文章编号：1009-3044(2011)15-3572-03

An Association Explore Based on Decision Tree Algorithm

WANG Hui, HOU Chuan-yu

(School of Information Engineering, Suzhou University, Suzhou 234000, China)

Abstract: ID3 algorithm and C4.5algorithm is classic decision tree algorithm in data mining. The article has some comparisons about C4.5 algorithm and ID3 algorithm ,for example, data structure of decision tree, the process of algorithm of c4.5 and ID3, and the choice of division attribute and so on, in order to provide this for others.

Key words: categories; ID3; C4.5

随着计算机的普及和网络的高速发展，人们获得信息的途径越来越多，同时获取信息的量呈几何级数的方式增长。如何从海量信息获得有用知识用于决策，成为大家关注的问题。数据挖掘也就是从大量信息中挖掘出有用知识的过程。数据挖掘上的常用的分类方法有决策树方法，贝叶斯方法，神经网络方法，粗糙集方法，遗传方法等。以下通过以下几个方面对决策树上的分类算法ID3和C4.5进行比较。

1 ID3算法和C4.5算法的比较

ID3算法是Quinlan于1993年提出的[1-2]，它使用信息增益来选择分裂属性。ID3算法的根本问题是怎样选取树的每个节点的分裂属性。ID3算法[4]用“信息增益”去衡量给定的属性区分训练样例的能力。它在增长树的每一步都是使用信息增益标准从候选属性中选择属性。C4.5算法[5]是ID3算法的改进，它使用信息增益率来进行分裂属性的选择。

1.1 ID3算法信息增益与C4.5信息增益率的计算步骤

1）ID3算法信息增益计算的步骤

步骤 1. 若一个记录集合T，根据类别属性的值被分成互相独立的类c1,c2,…,ck，则识别T的一个元素所属哪个类所需要的信息量为，其中p为c1,c2,…,ck的概率分布，即。

步骤 2.先根据非类别属性X的值将T分成集合T1,T2……Tn则确定T中的一个元素类的信息量可以通过确定Ti的加权平均值来得到，即Info（Ti）的加权平均值为： Info（X，T）=。

步骤 3. 信息增益度是两个信息量之间的差值，其中一个信息量是需要确定的T的一个元素的信息量，另一个信息量是在已得到的属性X的值后需确定的T一个元素的信息量，信息增益度的公式为：

Gain（X,T）= Info（T）-Info（X，T）。

2）C4.5信息增益率的求解步骤

C4.5在ID3的基础上利用信息增益率来对分裂属性选择，步骤1、2、3同ID3。

步骤 4.增加了属性X的信息熵。

步骤 5.用信息增益去除属性X的信息熵，得到信息增益率。

1.2 ID3与C4.5数据结构[3,7]比较（见表1）

由于C4.5算法是ID3算法的改进，所以在C4.5计算增益率的结构体中增加Gain_ratio用于存储信息增益率。从表1比较可以看出ID3和C4.5的结构体基本上都是可以共用的。

1.3 ID3与C4.5的算法[4,8]比较（见表2）

ID3算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定集合的测试属性。对被选取的测试属性创建一个结点，并以该结点的属性标记，对该属性的每个值创建一个分支据此划分样本。直到划分的样本属于同一类为止，输出其类别值作为分类结果（即叶子节点）。C4.5以ID3类似的方法选择分裂属性，只是在以信息增益率最高的作为分裂属性选择的标准。

表2 ID3和C4.5算法的比较

基于上述分析，ID3树的构造过程是一种贪婪算法的思想，每次选择局部信息增益最高属性作为分裂属性，并不进行回溯。构造的树是多分枝的树，树的规模随训练样本的增加而扩大。C4.5可以在ID3的基础上，也就是在计算信息增益的函数中，根据信息增益率对要选择的分裂属性进行选择，这样其他部分仍可以使用ID3的模块，只需修改下标识符。C4.5还可在计算增益率之前，添加一个对连续值的划分模块，这样C4.5就可以对连续值属性进行处理。

2 利用气候训练集的计算实例

2.1 数据准备，

测试训练集（见表3）选取了50条数据进行测试分析。

2.2 ID3和C4.5的实例计算（根据表3数据）

1）ID3的信息增益计算

步骤1：类别C（运动）的信息熵计算

类别中u1=适合，u2=不适合, 。

则：

步骤 2：属性的条件熵的计算

属性V取“天气”，V1=晴（16），V2=多云（15），V3=雨（14），V4=阴（5）。

所以。

取值为晴的16个样本中有5个为合适和11个不合适， 根据步骤2有：

P(u1|v1)=5/16，P(u2|v1)=11/16

同理：多云 P(u1|v2)=15/15， P(u1|v2)=0/15；雨P(u1|v3)=9/14，P(u1|v3)=5/14；

阴P(u1|v3)=5/5，P(u1|v3)=0/5；

Info（v）的加权和如下：

同理：V取气温时：Info(C,V) =0.8785 ，V取湿度时： =0.6738，V取 风 时：=0.8904。

步骤3：属性V的信息增益

Gain(天气)=Info(C)-Info(C,V)=0.9044-0.55=0.3544

同理类似可得：Gain(气温)=0.0258，Gain(湿度)=0.2306，Gain(风)=0.014。

2）C4.5信息增益率计算

前三个步骤分别和ID3的步骤1、2、3相同。

步骤4：属性的信息熵V

由，则天气中：v1=晴（16），v2=多云（15），v3=雨（14） ，v4=阴（5）,p(v1)=16/50,p(v2)=15/50 p(v3)=14/50 p(v4)=5/50

则：

同理：Split_Info(气温)=1.4948Split_Info(湿度)=0.9988Split_Info(风)=0.971

步骤5：信息增益率

Gain_ratio(天气)=Gain(天气)/Split_info(天气)=0.1871

Gain_ratio(气温)=Gain(气温)/Split_info(气温)=0.0173

Gain_ratio(湿度)=Gain(湿度)/Split_info(湿度)=0.2309

Gain_ratio(风)=Gain(风)/Split_info(风)=0.0144

2.3 ID3和C4.5对属性取值个数较多的偏向比较

表5是通过表3中的数据计算出来的，其中ID3选择分裂属性为天气，C4.5选择分裂属性为湿度。表6是表4（表4和表3的数据仅有第二列不同，即天气那列，其余数据不变）中的数据计算出来的，ID3选择分裂属性为湿度，C4.5选择分裂属性为湿度。

由表5和表6可知在数据表3中第二列属性值个数为4，表4中的第二列属性值个数为2。ID3在表3的数据下选择分裂属性为天气，在表4的数据下选择分裂属性为湿度。但C4.5一直选择的分裂属性为湿度，可以看到属性值个数变动对ID3中的属性选择的偏向影响较大（如0.3544与0.0389）。

2.3根据ID3和C4.5算法构造的树（根据表3数据）

表7 ID3建树过程表

表8 C4.5建树过程表

由表8可知在左子树的风中有三个#，其中第二#个是因为其所有的记录都为一类，已完成分类，故也把它标记为已经选择过的。从#、 #、 # 、1.000可以看到其他属性选择过后，剩下的最后一个属性对记录的信息增益为1，分类能力很强。以上两棵树（图1，图2）比较可以看出：C4.5构造的树的高度比ID3构造的树的得到的规则较多，其分类的准确性比ID3要高。例如在ID3中的规则”天气=’阴’”＝＞适合，”天气=多云” ＝＞适合和我们的生活习惯相比较，决策因素太简单，也有些不符。而C4.5构造的决策规则要明显好于ID3，更准确些。

2.4 ID3和C4.5的特性比较（见表9）

表9为ID3和C4.5的特性比较。

3 结束语

通过对决策树上的ID3和C4.5的数据结构与算法描述算法比较，及利用训练数据集建树，可知：ID3算法的优点是使用了窗口的概念，以信息熵为选择分裂属性的标准，构建树的速度加快。C4.5除了ID3的优点外，增加了对连续属性值的离散化处理；缺失数据的处理；解决了ID3属性值偏向问题。

参考文献：

[1] Dunham M H.数据挖掘教程[M].北京:清华大学出版社,2005.

[2] 周爱华,申玉静.决策树技术在高校实验队伍评估中的应用[J].电脑知识与技术,2011,7(2):285-286.

[3] 程龙,蔡远文.数据挖掘C4.5算法的编程设计与增量学习改[J].计算机技术与自动化,2009(4):83-87.

[4] 李川.决策树分类算法_ID3算法及其讨论[J].软件导刊,2010(10):68-70.

[5] 王桂琴.决策树算法研究及应用黄道[J].电脑应用技术,2008(72):1-7.

[6] 路红梅.基于决策树的经典算法综述[J].宿州学院学报,2007,22(2):91-95.

[7] 乔增伟.孙卫祥.C4.5算法的两点改进[J].江苏工业学院学报,2008,20(4)56-59.

[8] 黄爱辉.决策树.C4.5算法的改进及应用[J].计算机技术,2009,9(1):35.

[9] 邵峰晶.于忠清.数据挖掘原理与算法[M].北京:中国水利水电出版社,2003:133-135.