分类论文决策树相关算法论文：决策树相关算法研究
摘要：id3算法和c4.5算法是经典的决策树算法，通过对id3算法和c4.5算法的数据结构、算法描述和分裂属性选取等方面进行比较，为其他研究者提供参考。
关键词：分类；id3；c4.5
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
