Computer Engineering and Applications 计算机工程与应用2010，46（8）127
一种改进的决策树分类属性选择方法
王苗1，柴瑞敏2WANG Miao 1，CHAI Rui-min 2
辽宁葫芦岛1251051. 辽宁工程技术大学研究生院，
辽宁葫芦岛1251052. 辽宁工程技术大学电子与信息工程学院，
1.Institute of Graduate ，Liaoning Technical University ，Huludao ，Liaoning 125105，China 2.School of Electronic and Information Engineering ，Liaoning Technical University ，Huludao ，Liaoning 125105，China E-mail ：hsmobei16525@sina.com
WANG Miao ，CHAI Rui -min.Improved classification attribute selection scheme for decision tree.Computer Engineering
（8）：and Applications ，2010，46127-129. Abstract ：Analyze the basic principles and implementation steps of ID3and point out the advantages and disadvantages of two existing improved classification algorithms.With the shortcoming of inclining to choose attributes having many values for ID3and
the deficiencies of classification time and classification accuracy for existing two improved classification algorithms ，a new attribute selection scheme is proposed and optimized with mathematical knowledge.Experiment results show that the optimized scheme can overcome the above disadvantage of ID3and has the advantages of classification time and classification accuracy over the existing two classification algorithms. Key words ：data mining ；decision tree ；attributes selection 摘要：分析了ID3算法的基本原理、实现步骤及现有两种改进分类算法的优缺点，针对ID3算法的取值偏向问题和现有两种改进算法在分类时间、分类精确度方面存在的不足，提出了一种新的分类属性选择方案，并利用数学知识对其进行了优化。经实验证明，优化后的方案克服了ID3算法的取值偏向问题，同时在分类时间及分类精确度方面优于ID3算法及现有两种改进的分类算法。关键词：数据挖掘；决策树；属性选择DOI ：10.3778/j.issn.1002-8331.2010.08.036
文章编号：（2010）1002－833108-0127-03
文献标识码：A
中图分类号：TP399
1概述
近年来，数据挖掘技术在股票、房地产、医疗、教育等领域得到了广泛应用，为人们获取有价值的信息提供了有力手段。决策树是数据挖掘技术中最常用的方法之一，与其他的分类方法相比，具有速度快、精度高以及生成模式简单等优点[1]，在数据挖掘领域中有着不可替代的作用和地位。ID3算法是最具有影响力的一种决策树生成算法，于1986年由Quinlan 提出[2-3]。但是ID3算法存在以下不足[4]：
（1）基于信息熵的计算方法偏向于特征值数目较多的属性，而特征值较多的属性往往不是最优，最符合实际的分类属性；
（2）数据集越大，算法的计算量增加得越快；
（3）当训练集增加或者减少时，该算法生成的决策树随之变化，这对动态变化数据集的学习是不合适的。
针对ID3算法的不足，众多学者对其进行了深入研究，并提出了自己的改进方案。其中，文献[5]的作者创新性地利用泰勒公式和麦克劳林公式对ID3算法进行了简化，在较大程度上
缩短了生成决策树的时间，但是作者没有考虑简化过程中带来
的误差；在文献[6]中，作者针对ID3算法的取值偏向问题，引入了“兴趣度”的概念，对ID3算法进行了有效的改进，但是没能克服ID3算法存在的第（2）条缺点。文章对文献[6]提出的决策树算法进行了优化，有效缩短了该算法生成决策树的时间，同时弥补了优化过程中带来的误差，避免了文献[5]中出现的不足。除此之外，针对样本集中某一确定属性值的记录集合为空的情况，给出了自己的修改方案。
2算法改进原理
设E=F1×F 2×…×F n 是n 维有穷ID3算法的基本原理[7]如下：
向量空间。其中F j 是有穷离散符号集，E 中的元素e=称为样例。j =1，2，n 。
分别叫做正例集和反例集。假设向量空间E 中的2个样例集，
正例集PE 和反例集NE 的大小分别为P 、N 。由决策树的基本思想知ID3算法是基于如下两种假设：
基金项目：辽宁工程技术大学研究生科研立项基金（the Liaoning Technical University Graduate Research Foundation of China under Grant
）。No.Y200900501
，。收稿日期：2009-10-21
修回日期：2009-12-28
1282010，46（8）Computer Engineering and Applications 计算机工程与应用
3×02×3）e （湿度=+=1.21
3+02+32×03×21×0）++=1.2e （=1风
2+03+21+0
可以得出以下不等式成立：）））。所e （=e （
中算法生成的决策树和ID3算法生成的决策树不同，分类精确度会降低。大家通过表2中的实验数据也可以清楚地看到。文献[6]中改进的算法虽然通过引入兴趣度克服了ID3算法的取
（2）
值偏向问题，但是在原来的信息熵计算基础之上引入了加法运增加了生成决策树的时间。通过表2中的算，与ID3算法相比，
（3）
实验数据，大家也可以明显地观察到。
（1）在向量空间E 上的一棵正确决策树对任意样例的分类概率同E 中的正反例的概率一致。
（2）一棵决策树对一样例做出正确类别判断所需的信息为：p p n n （）I p ，n =-lb -lb
p+np+np+np+n
（1）
如果以属性A 作为决策树的根，…，A 具有V 个值{V 1，V 2，
它将E 分成V 个子集{E 1，…，假设E i 中含有p i 个正V v }，E 2，E v }，那么子集E i 所需的期望信息是I （p i ，以属例和n i 个反例，n ）i ，性A 为根，所需的期望熵为：
p +n（A ）E =Σi i （I p i ，n ）i
i =1P+N以A 为根的信息增益是：
（A ）（p ，）（A ）gain =In -E
（A ）最大，也就是E （A ）最小的属性A *作为ID3选择gain
根结点，对A *的不同取值对应的E 的V 个子集E i 递归调用上述过程生成A *的子结点B 1，…，B 2，B v 。
详细算法[8]描述如下：
输入：训练样本，各属性均取离散数值，可供归纳的候选属性集为：attribute_list。
输出：决策树。处理流程：
（1）创建一个结点N ；
）若该结点中的所有样本均为同一个类别C ，则开始根（2
结点对应所有的训练样本；
（3）返回N 作为一个叶结点，以类C 标记；（4）如果attribute_list为空；
（5）返回N 作为一个叶结点，并标记为该结点所含样本中类别个数最多的类别；
（6）选择attribute_list中具有最高信息增益的属性test_at－tribute ；（7）标记结点N 为test_attribute；
（8）对于test_attribute中的每一个已知取值a i ，准备划分结点N 所包含的样本集；
（9）根据test_attribute=ai 条件，从结点N 产生相应的一个分支，以表示该测试条件；
（10）设s i 为test_attribute=ai 条件所获得的样本集合；（11）若s i 为空，则将相应叶结点标记为该结点所含样本中类别个数最多的类别；
（12）否则将相应叶结点标记为Generate_decision_tree（s i ，）返回值。attribute_list-test_attribute在文献[5]中，作者利用数学中的等价无穷小理论，将ID3算法中的期望熵E （A ）近似为e （）=Σ1A
i =1n
v
3算法的优化
（1）兴趣度[6]：给定0≤α≤1，α称为用户对不确定知识的
兴趣度，其大小由决策者根据先验知识或领域知识来确定。引入兴趣度后，可以定义如下公式：
）（E （A =Σ
*
i =1v
p i +ni
）（+αI p i ，n i ）
P+N
（4）
利用换底公式lb λ=ln λ将式（4）化简为：
ln 2
p i n 1）-p i ln E （A =Σ-n i ln i +
）P+Nln 2p i +ni p i +ni i =1（
*
v
1-Σαln
2p +n
i =1
i
v
p i
ln
i
p i n n
-i ln i p i +ni p i +ni p i +ni
对于每个训练集，（P+N）所ln2是常量且每一步都要计算，以可以省略。又由泰勒公式和麦克劳林公式可知当x 很小时，（1+x）进而可以将上式近似为：ln ≈x ，
n p （A ）（1+αi i e =Σp i +ni p i +ni i =1
但是，简化过程会引起误差，所以不能用上式直接作为选择分类属性的度量。这里假设每个属性的特征值个数为M ，经过多次实验证明将M 乘以e （A ）可以有效弥补误差。因此，可以用下式作为选择分类属性的度量：
n p *
）（1+αi i M e （A =Σp i +ni p i +ni i =1
v v
（5）
（2）当s i 为空时，ID3处理的方法是将相应叶结点标记为该结点所含样本中类别个数最多的类别。为使决策树结点数目尽量少，当s i 为空时，跳过ID3中的步骤（11），继续查找其他非空样本子集作为下次递归的输入训练集，并产生相应的决策树分枝。在实际过程中，对于在决策树中不能找到的情况，与其给出一个不确定的、较高误差率的判断，不如给出无法判定的回答，让决策者通过其他方法做出决策。
n i p i
计算每个属性n i +pi
的熵，从中选取熵值最小的属性作为决策树结点，但是没有弥补近似化简引入的误差，生成的决策树和ID3算法生成的决策树不相同，精确度有所降低。当选出以属性天气为决策树根结点之后，可以根据天气的3个属性值雨、多云、晴得出3个子树。这里以属性雨所在的子树为例说明为什么精确度会降低。在进行递归计算时，可以得出各属性的信息熵分别为：
4实验对比分析
采用文献[9]中提供的气候训练集，如表1所示。由ID3生成的决策树如图1所示[9]。
根据调查测试，取天气的用户兴趣度α=0.35，其他属性的
0。1中各属性的信息熵分别为：
王
表1
天气晴晴多云雨雨雨多云晴晴雨晴多云多云雨
气温热热热适中冷冷冷适中冷适中适中适中热适中
苗，柴瑞敏：一种改进的决策树分类属性选择方法
2010，46（8）129
气候训练集
湿度高高高高正常正常正常高正常正常正常高正常高天气
风力无风有风无风无风无风有风有风无风无风无风有风有风无风有风
类别N N P P P N P N P P P P P N
的标准数据集car evaluation 进行实验分析。数据集中共1728
个实例，从中选取1/4的样例作为训练集，全部数据作为测试集。在相同的软硬件条件下，利用MATLAB 和WEKA 进行了求平均值后的实验数据如表2所示。100次实验，
表2
算法ID3文献[5]文献[6]该文方案
实验数据结果
分类精确率（）/%
72.2871.2367.3673.55
0.14940.14380.16040.1393
分类时间/s
从图2中可以直观地看出，在由改进后的算法生成的决策树中，天气属性离树根结点较远，改进后的算法有效降低了天气属性的重要度，在一定程度上克服了ID3算法取值偏向的缺该文方案的分类时间均短于ID3、文献陷。从表2中可以看出，
分类精确度均高于这3个算法[5]和文献[6]中算法的分类时间、
的分类精确度。实验证明，该文提出的方法是更优越的。
晴湿度
多云P
雨风力
5
P
总结及今后研究方向
首先指出了ID3算法存在的缺点及现有两种改进算法的
高N
正常
P
有风N
无风
不足之处，在此基础上提出了一个新的改进方案，在一定程度上克服了ID3算法固有的缺点，同时优化了文献[5-6]中的方案。最后在MATLAB 和WEKA 中进行了实验，证明了改进后的方案是有效的。
ID3算法是决策树生成算法中提出最早且最经典的算法，但是ID3算法只能对静态数据在分类挖掘领域中被广泛应用。
集提取静态的分类规则，无法解决变化的数据集及规则提取问题，所以“动态决策树”的研究将会是研究重点。除此之外，如何提高决策树的精度，并行决策树算法及寻找新的决策树算法也将会成为今后的工作方向。
图1
*
ID3算法生成的决策树
6（0.350）（1+0.35e （天气=[×+1+×+
5544
6（1+0.35×]×3=7.70455
*
温度）（4+8+3e （=×3=9.249
464
*
湿度）（12+6e （=×2=5.142
77
）（12+9e （风力=×2=686
****
通过比较可知：湿度）风力）天气）温度）。所e （
*
参考文献：
王斌. 一种基于ID3的前剪枝改进算法[J].计算机与现代[1]丁祥武，
化，（9）2008.
概念与技术[M].范明，孟小峰，译. [2]Han Jiawei ，Kamber M. 数据挖掘：
北京：机械工业出版社，2001.
[3]Quinlan J R.Induction of decision trees[J].MachineLearning ，1986，
1：81-106.
陈轩恕，刘飞，等. 数据挖掘中决策树分类算法的研究与改[4]但小容，
（2）进[J].软件导刊，2009，8.
陈湘涛. 决策树ID3算法的改进[J].计算机工程与科学，[5]黄爱辉，
（6）：2009，31109-111.
成文丽，王俊红.ID3算法的一种改进算法[J].计算机工程与[6]曲开社，
（25）：应用，2003，39104-107.
姚耀文. 数据挖掘中决策树算法的探讨[J].计算机应用研[7]唐华松，
究，（8）：2001，1818-22.
中国科学技术大学出版社，[8]朱明. 数据挖掘[M].合肥：2002：67-68. 黄金才，赵新昱. 数据挖掘技术[M].北京：北京工业大学出[9]陈文伟，
版社，2002.
重复此过程可以得到最终决策树如图2所示。
湿度（1，2，3，
…，）14高
天气（1，2，3，）4，8，12，14雨
多
云
晴
多云
正常
天气（5，6，7，
）9，10，11，13晴
雨
N 风力P P P 风力（5，（，）（7，12，8（4，）（3，））（9，）6，14121311）10
无有有无风风风风（4）P
（14）N
（5，）P 10
（6）N
图2改进后的算法生成的决策树
为使该文方案更具有鲁棒性，采用UCI 机器学习数据库中