一种改进的决策树算法研究

佘为++韩昌豪

摘要：决策树算法是数据挖掘中的一个常用算法，它通过构造决策树来发现数据中蕴含的分类规则，如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树算法中常用的一种是ID3算法，该文针对传统ID3算法的缺点，提出一种改进的ID3算法，通过实验证实，改进的ID3算法在生成的决策树的规模和精度方面都比传统的ID3算法好，使用这种改进的ID3算法可以提高性能。

关键词：决策树；ID3算法；信息增益；剪枝

中图分类号： TP312 文献标识码：A 文章编号：1009-3044（2015）11-0091-01

1 ID3算法

决策树分类算法中的ID3算法是Quilan在1986年提出来的，也是决策树构造中的经典算法[1]。ID3算法是以信息论为基础，它使用信息熵和信息增益两个指标为衡量标准，选择信息增益最大的属性划分训练样本，从而生成决策树。

定义1、按类标签对训练集D的属性集A进行划分，信息熵为：

[infoD=-i=0mpilog2pi]

Pi为训练集D中属于第i类的概率。

定义2、按属性集A中每个属性进行划分，得到一组信息熵：

[infoAD=-j=0nDjDinfoDj]

Dj为属性集中每个属性的出现的次数，D为所有属性的总次数。

定义3、信息增益为：

Gain（A）=info（D）-infoA（D）

ID3算法对每个节点中选择Gain（A）中最大的属性A作为选择分支的属性。这种算法的缺点是：倾向于选择取值较多的属性[2]，在有些情况下这类属性可能不会提供什么有意义的信息，ID3学习简单逻辑表达式的能力差[3]。此外，ID3将注意力集中在属性的选择方面，而属性的选择对决策树的影响如何，仍无定论[4]。

2 改进的ID3算法

1）调整信息增益

针对ID3算法偏向于选择取值较多但实际中并不总是最优的属性作为测试属性的缺点，调整信息增益。Gain（A）= Gain（A） /X，其中X的取值大于等于1，主要由属性A的取值个数和使用者根据经验及领域知识来确定，一般取值个数越多则X越大。改进的ID3算法通过调整每个属性的信息增益，使生成决策树时数量少但又很重要的属性不会被淹没，最终使决策树克服了对取值多的属性的偏爱，因为属性取值越多，调整后的信息增益就越小，这个属性当然就很难被选中为判断属性了。

2）剪枝

剪枝方法主要是考虑在决策树的哪个位置产生叶子合适[5]。剪枝算法分前剪枝和后剪枝。前剪枝是在决策树构造过程中选取某个预定义的阀值，使得某些节点不再继续分裂，限制树的生长。后剪枝是将已生成的决策树做去分支处理[6]。前剪枝由于很难选取一个合适的阀值，应用困难。后剪枝的时间复杂度高，但生成的决策树准确度高，但主要应用的几种后剪枝算法都存在过剪枝或欠剪枝现象。由于各种剪枝算法都有缺点，所以本文提出采用灵活的剪枝方法进行剪枝。

剪枝方法为：首先，根据具体需要设定生成决策树的高度、精确度等信息，设定主要依据经验和领域知识来确定。然后，针对决策树节点a来说，对a进行剪枝，则产生的错误分配样本数为：[e'a=ea+12]。

未剪枝的子树错误分配样本数为：[E'Ta=E'（Ti）]。

未剪枝的子树误差为：[SeTi=Ca2]。

其中，e（a）为a节点的错误分配样本数，Ti（i=1，2，…，n）是Ta节点的子节点，Ca是Ta节点的子节点数。如果叶子节点的[e'a≤E'Ti+Se（Ti）]成立，那么Ta可以剪枝。

3实验测试结果

实验所用数据为UCI数据库中的Iris数据集（样本数209个，属性7个）、Breast数据集（样本数817个，属性11个）和Segmentation数据集（样本数2932个，属性26个）。对这三个数据集所有连续值的属性使用DBChi2算法对数据进行离散，随机 （下转第96页）

（上接第91页）

抽取每个数据集中的2/3用于训练样本集，其余的1/3用作测试样本集，然后分别用传统的ID3算法和改进的ID3算法构建决策树，最后通过测试样本集测试准确度。上述构造决策树的方法反复进行十次，得出的结果如表1。

表1 实验结果

[数据集＼&传统ID3算法的平均准确度＼&传统ID3算法的平均叶子数＼&改进ID3算法的平均准确度＼&改进ID3算法的平均叶子数＼&Iris＼&75%＼&7.4个＼&81%＼&5.6个＼&Breast＼&87%＼&8.2个＼&89%＼&6.3个＼&Segmentation＼&72%＼&11.2个＼&85%＼&9.6个＼&]

从表1中能明显的得出，改进的ID3算法平均的分类准确度更高，生成决策树的平均叶子数也高过传统的ID3算法，具有更低的复杂性。从实验还得出改进的ID3算法通过不断的学习调整信息增益，从而克服了传统ID3算法倾向于选择取值较多的属性的缺点，但是改进的ID3算法通过实验得出在时间复杂度上和传统ID3几乎一致。

4 结束语

改进的ID3算法调整了传统的ID3算法的信息增益计算方法，又加入了灵活的剪枝策略。它可以依靠经验或领域知识人工增强重要属性在分类决策中调整信息增益，从而减少非重要属性的信息量，特别是它可以减少ID3算法对取值较多的属性的依赖性，从而改善分类规则和结果。

参考文献：

[1] 赵微，苏健民.基于ID3算法决策树的研究与改进[J]. 科技信息， 2008（23）： 383.

[2] Quinlan J R， Induction of decision trees[J]. Machine Learning， 1986， 1（1）： 81-106.

[3] Tu P L， Chung J Y.A new decision-tree classification algorithm for machine learning[C]// Proceedings of the 1992 IEEE International Conference on Tools for Artificial Intelligence. Arlington Virginia， USA： IEEE Computer Society， 1992 370-377.

[4] Hong J R.A new algorithm of decision tree induction[J]. Chinese Journal of Computers， 1995， 18（6）： 470-473.

[5] 孙娟，王熙照. 规则简化与模糊决策树剪枝的比较[J]. 计算机工程， 2006，12（32）： 210-211.

[6] 李仁良，李义杰. 基于多策略的决策树剪枝算法及其应用[J]. 计算机仿真， 2010， 11（27）： 78-80.