2023年7月29日发(作者：)

分类论文决策树相关算法论文：决策树相关算法研究

摘要：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算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定集合的测试属性。对被选取的测试属性创建一个结点，并以该结点的属性标记，对该属性的每个值创建一个分支据此划分样本。直到划分的样本属于同一类为