一种改进的决策树分类属性选择方法.pdf

2010，46（8）1概述近年来，数据挖掘技术在股票、房地产、医疗、教育等领域得到了广泛应用，为人们获取有价值的信息提供了有力手段。决策树是数据挖掘技术中最常用的方法之一，与其他的分类方法相比，具有速度快、精度高以及生成模式简单等优点1，在数据挖掘领域中有着不可替代的作用和地位。ID3 算法是最具有影响力的一种决策树生成算法，于 1986 年由 Quinlan 提出2-3。但是 ID3 算法存在以下不足4：（1）基于信息熵的计算方法偏向于特征值数目较多的属性，而特征值较多的属性往往不是最优，最符合实际的分类属性；（2）数据集越大，算法的计算量增加得越快；（3）当训练集增加或者减少时，该算法生成的决策树随之变化，这对动态变化数据集的学习是不合适的。针对 ID3 算法的不足，众多学者对其进行了深入研究，并提出了自己的改进方案。其中，文献5的作者创新性地利用泰勒公式和麦克劳林公式对 ID3 算法进行了简化，在较大程度上缩短了生成决策树的时间，但是作者没有考虑简化过程中带来的误差；在文献6中，作者针对 ID3 算法的取值偏向问题，引入了“兴趣度”的概念，对 ID3 算法进行了有效的改进，但是没能克服 ID3 算法存在的第（2）条缺点。文章对文献6提出的决策树算法进行了优化，有效缩短了该算法生成决策树的时间，同时弥补了优化过程中带来的误差，避免了文献5中出现的不足。除此之外，针对样本集中某一确定属性值的记录集合为空的情况，给出了自己的修改方案。2算法改进原理ID3 算法的基本原理7如下：设 E=F1F2Fn是 n 维有穷向量空间。其中 Fj是有穷离散符号集，E 中的元素 e=称为样例。其中 VjFj，j=1，2，n。设 PE 和 NE 是 E 的2 个样例集，分别叫做正例集和反例集。假设向量空间 E 中的正例集 PE 和反例集 NE 的大小分别为 P、N。由决策树的基本思想知 ID3 算法是基于如下两种假设：一种改进的决策树分类属性选择方法王苗1，柴瑞敏2WANG Miao1，CHAI Rui-min21.辽宁工程技术大学 研究生院，辽宁 葫芦岛 1251052.辽宁工程技术大学 电子与信息工程学院，辽宁 葫芦岛 1251051.Institute of Graduate，Liaoning Technical University，Huludao，Liaoning 125105，China2.School of Electronic and Information Engineering，Liaoning Technical University，Huludao，Liaoning 125105，ChinaE-mail：WANG Miao，CHAI Rui-min.Improved classification attribute selection scheme for decision tree.Computer Engineeringand Applications，2010，46（8）：127-129.Abstract：Analyze the basic principles and implementation steps of ID3 and point out the advantages and disadvantages of twoexisting improved classification algorithms.With the shortcoming of inclining to choose attributes having many values for ID3 andthe deficiencies of classification time and classification accuracy for existing two improved classification algorithms，a new attributeselection scheme is proposed and optimized with mathematical knowledge.Experiment results show that the optimized scheme canovercome the above disadvantage of ID3 and has the advantages of classification time and classification accuracy over theexisting 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文章编号：10028331（2010）08-0127-03文献标识码：A中图分类号：TP399基金项目：辽宁工程技术大学研究生科研立项基金（the Liaoning Technical University Graduate Research Foundation of China under GrantNo.Y200900501）。作者简介：王苗（1984-），女，硕士研究生，主要研究方向：数据挖掘；柴瑞敏（1969-），女，副教授，硕士生导师，主要研究方向：人工智能，数据挖掘。收稿日期：2009-10-21修回日期：2009-12-28Computer Engineering and Applications 计算机工程与应用127Computer Engineering and Applications 计算机工程与应用2010，46（8）（1）在向量空间 E 上的一棵正确决策树对任意样例的分类概率同 E 中的正反例的概率一致。（2）一棵决策树对一样例做出正确类别判断所需的信息为：I（p，n）=-pp+nlbpp+n-np+nlbnp+n（1）如果以属性 A 作为决策树的根，A 具有 V 个值V1，V2，Vv，它将 E 分成 V 个子集E1，E2，Ev，假设 Ei中含有 pi个正例和 ni个反例，那么子集 Ei所需的期望信息是 I（pi，ni），以属性 A 为根，所需的期望熵为：E（A）=vi=1pi+niP+NI（pi，ni）（2）以 A 为根的信息增益是：gain（A）=I（p，n）-E（A）（3）ID3 选择 gain（A）最大，也就是 E（A）最小的属性 A*作为根结点，对 A*的不同取值对应的 E 的 V 个子集 Ei递归调用上述过程生成 A*的子结点 B1，B2，Bv。详细算法8描述如下：输入：训练样本，各属性均取离散数值，可供归纳的候选属性集为：attribute_list。输出：决策树。处理流程：（1）创建一个结点 N；（2）若该结点中的所有样本均为同一个类别 C，则开始根结点对应所有的训练样本；（3）返回 N 作为一个叶结点，以类 C 标记；（4）如果 attribute_list 为空；（5）返回 N 作为一个叶结点，并标记为该结点所含样本中类别个数最多的类别；（6）选择 attribute_list 中具有最高信息增益的属性 test_attribute；（7）标记结点 N 为 test_attribute；（8）对于 test_attribute 中的每一个已知取值 ai，准备划分结点 N 所包含的样本集；（9）根据 test_attribute=ai条件，从结点 N 产生相应的一个分支，以表示该测试条件；（10）设 si为 test_attribute=ai条件所获得的样本集合；（11）若 si为空，则将相应叶结点标记为该结点所含样本中类别个数最多的类别；（12）否则将相应叶结点标记为 Generate_decision_tree（si，attribute_list-test_attribute）返回值。在文献5中，作者利用数学中的等价无穷小理论，将 ID3算法中的期望熵 E（A）近似为 e1（A）=ni=1nipini+pi计算每个属性的熵，从中选取熵值最小的属性作为决策树结点，但是没有弥补近似化简引入的误差，生成的决策树和 ID3 算法生成的决策树不相同，精确度有所降低。当选出以属性天气为决策树根结点之后，可以根据天气的 3 个属性值雨、多云、晴得出 3 个子树。这里以属性雨所在的子树为例说明为什么精确度会降低。在进行递归计算时，可以得出各属性的信息熵分别为：e1（气温）=414+1+101+0+111+1=1.3e1（湿度）=303+0+232+3=1.2e1（风）=202+0+323+2+101+0=1.2可以得出以下不等式成立：e1（风）=e1（湿度）e1（气温）。所以应该从属性风和湿度中选出一个属性作为决策树结点。但是在由 ID3 算法生成的决策树中，属性气温是结点。因此，文献5中算法生成的决策树和 ID3 算法生成的决策树不同，分类精确度会降低。大家通过表 2 中的实验数据也可以清楚地看到。文献6中改进的算法虽然通过引入兴趣度克服了 ID3 算法的取值偏向问题，但是在原来的信息熵计算基础之上引入了加法运算，与 ID3 算法相比，增加了生成决策树的时间。通过表 2 中的实验数据，大家也可以明显地观察到。3算法的优化（1）兴趣度6：给定 01，称为用户对不确定知识的兴趣度，其大小由决策者根据先验知识或领域知识来确定。引入兴趣度后，可以定义如下公式：E*（A）=vi=1（pi+niP+N+）I（pi，ni）（4）利用换底公式 lb=lnln2将式（4）化简为：E*（A）=vi=11（P+N）ln2（-pilnpipi+ni-nilnnipi+ni）+vi=11ln2（-pipi+nilnpipi+ni-nipi+nilnnipi+ni）对于每个训练集，（P+N）ln2 是常量且每一步都要计算，所以可以省略。又由泰勒公式和麦克劳林公式可知当 x 很小时，ln（1+x）x，进而可以将上式近似为：e（A）=vi=1（1+pi+ni）nipipi+ni但是，简化过程会引起误差，所以不能用上式直接作为选择分类属性的度量。这里假设每个属性的特征值个数为 M，经过多次实验证明将 M 乘以 e（A）可以有效弥补误差。因此，可以用下式作为选择分类属性的度量：e*（A）=vi=1（1+pi+ni）nipipi+niM（5）（2）当 si为空时，ID3 处理的方法是将相应叶结点标记为该结点所含样本中类别个数最多的类别。为使决策树结点数目尽量少，当 si为空时，跳过 ID3 中的步骤（11），继续查找其他非空样本子集作为下次递归的输入训练集，并产生相应的决策树分枝。在实际过程中，对于在决策树中不能找到的情况，与其给出一个不确定的、较高误差率的判断，不如给出无法判定的回答，让决策者通过其他方法做出决策。4实验对比分析采用文献9中提供的气候训练集，如表 1 所示。由 ID3 生成的决策树如图 1 所示9。根据调查测试，取天气的用户兴趣度=0.35，其他属性的用户兴趣度为 0。由改进后的信息熵计算公式，可以得到表 1中各属性的信息熵分别为：1282010，46（8）表 1气候训练集天气晴晴多云雨雨雨多云晴晴雨晴多云多云雨气温热热热适中冷冷冷适中冷适中适中适中热适中湿度高高高高正常正常正常高正常正常正常高正常高风力无风有风无风无风无风有风有风无风无风无风有风有风无风有风类别NNPPPNPNPPPPPN湿度风力天气NPNPP多云雨晴高正常有风无风图 1ID3 算法生成的决策树图 2改进后的算法生成的决策树湿度（1，2，3，14）天气（1，2，3，4，8，12，14）天气（5，6，7，9，10，11，13）风力（4，14）P（4）N（1，2，8）P（7，13）P（9，11）风力（5，6，10）P（3，12）N（14）P（5，10）N（6）无风有风无风有风多云多云正常雨晴雨晴高表 2实验数据结果算法ID3文献5文献6该文方案分类时间/s0.149 40.143 80.160 40.139 3分类精确率/（%）72.2871.2367.3673.55e*（天气）=（1+0.355）65+（1+0.354）04+（1+0.355）653=7.704e*（温度）=（44+86+34）3=9.249e*（湿度）=（127+67）2=5.142e*（风力）=（128+96）2=6通过比较可知：e*（湿度）e*（风力）e*（天气）e*（温度）。所以，首先选择湿度作为决策树根结点，对样本数据集进行分类，重复此过程可以得到最终决策树如图 2 所示。为使该文方案更具有鲁棒性，采用 UCI 机器学习数据库中的标准数据集 car evaluation 进行实验分析。数据集中共 1 728个实例，从中选取 1/4 的样例作为训练集，全部数据作为测试集。在相同的软硬件条件下，利用 MATLAB 和 WEKA 进行了100 次实验，求平均值后的实验数据如表 2 所示。从图 2 中可以直观地看出，在由改进后的算法生成的决策树中，天气属性离树根结点较远，改进后的算法有效降低了天气属性的重要度，在一定程度上克服了 ID3 算法取值偏向的缺陷。从表 2 中可以看出，该文方案的分类时间均短于 ID3、文献5和文献6中算法的分类时间、分类精确度均高于这 3 个算法的分类精确度。实验证明，该文提出的方法是更优越的。5总结及今后研究方向首先指出了 ID3 算法存在的缺点及现有两种改进算法的不足之处，在此基础上提出了一个新的改进方案，在一定程度上克服了 ID3 算法固有的缺点，同时优化了文献5-6中的方案。最后在 MATLAB 和 WEKA 中进行了实验，证明了改进后的方案是有效的。ID3 算法是决策树生成算法中提出最早且最经典的算法，在分类挖掘领域中被广泛应用。但是 ID3 算法只能对静态数据集提取静态的分类规则，无法解决变化的数据集及规则提取问题，所以“动态决策树”的研究将会是研究重点。除此之外，如何提高决策树的精度，并行决策树算法及寻找新的决策树算法也将会成为今后的工作方向。参考文献：1 丁祥武，王斌.一种基于 ID3 的前剪枝改进算法J.计算机与现代化，2008（9）.2 Han Jiawei，Kamber M.数据挖掘：概念与技术M.范明，孟小峰，译.北京：机械工业出版社，2001.3 Quinlan J R.Induction of decision treesJ.Machine Learning，1986，1：81-106.4 但小容，陈轩恕，刘飞，等.数据挖掘中决策树分类算法的研究与改进J.软件导刊，2009，8（2）.5 黄爱辉，陈湘涛.决策树 ID3 算法的改进J.计算机工程与科学，2009，31（6）：109-111.6 曲开社，成文丽，王俊红.ID3 算法的一种改进算法J.计算机工程与应用，2003，39（25）：104-107.7 唐华松，姚耀文.数据挖掘中决策树算法的探讨J.计算机应用研究，2001，18（8）：18-22.8 朱明.数据挖掘M.合肥：中国科学技术大学出版社，2002：67-68.9 陈文伟，黄金才，赵新昱.数据挖掘技术M.北京：北京工业大学出版社，2002.王苗，柴瑞敏：一种改进的决策树分类属性选择方法129