[doc] 基于属性-值对的信息增益优化算法

[doc] 基于属性-值对的信息增益优化算法 基于属性-值对的信息增益优化算法 第26卷第3期太原科技大学Vo1.26No.3 2005年9月JOURNALOFTAIYUANUNIVERSITYOFSCIENCEANDTECHNOLO GYSep.2005 文章编号:1673—2057(2005)03—0199—04 基于属性一值对的信息增益优化算法 孙超利,张继福 (太原科技大学计算机科学与技术学院,太原030024) 摘要:偏向于取值较多的属性是ID3算法的一个缺陷,目前已提出的决策树的优化 算法对ID3算法的改进,部分解决了该缺陷,但仅适用于两值属性的样例集,对于多值属 性效果并不明显.针对该优化算法的不足,通过将属性和属性值对应成一个属性,提出了 属性.值对的信息增益优化算法GBT.通过理论和实验分析,明该算法不仅克服了ID3 算法偏向于取值多属性的缺陷,同时解决了优化算法对多值属性效果不明显的不足. 关键词:数据挖掘;决策树;信息增益;信息熵;属性.值对 中图分类号:TP301.6文献标识码:A — ‘一*十一—’一一—’一-—’一-—’一*—’一-—’一-十-—’一-—’一-+ 一—’一-+-+ 决策树方法是常用的数据挖掘方法之一,多用 于预测模型的算法,它着眼于从一组无次序,无规 则的事例中推理出决策树表示形式的分类规则. 对于给定的测试集,正确选择父结点或该决策树子 树的父结点能够大大减少决策树的结点数以及树 的深度,因此为了能得到理想的决策树,即期望非 叶结点到达各后代叶结点的平均路径最短,使生成 的决策树平均深度较小,提高分类速度和准确率, Quinlan在文献[1]中提出了后来称之为ID3的算 法.ID3是基于信息熵的决策树分类算法,根据属 性集的取值选择实例的类别,Quinlan的主要工作是 引进了信息论中的互信息,称其为信息增益. ID3由于其理论清晰,方法简单,学习能力较 强,适于处理大规模的学习问,在实际应用中解 决了许多问题,特别是对于非增量式学习任务,ID3 算法常常是建立决策树的很好的选择.然而ID3算 法也存在它自身的一些缺陷,比如对于增量式学习 任务来说,由于ID3不能增量的接受训练例,这就使 得每增加一次实例都必须抛弃原有决策树,重新构 造新的决策树,造成极大的开销,于是ID3算法被 Quinlan自己扩充为C4.5算法;又比如ID3在建 树时,每个结点仅含一个特征,是一种单变元的算 法,特征间的强调性不够,因此1992年Pei—leiTu 采用了基于相关性的启发式j;而其中ID3的 最大一个缺陷是互信息的计算依赖于特征值数目 较多的特征,而数目较多的特征不一定是最优的属 性,决策树的优化算法J,即两次信息增益的优化 算法,每当选择一个新的属性时,该算法不仅考虑 该属性带来的信息增益,而且还考虑选择该属性后 继续选择的属性带来的信息增益,即同时考虑树的 两层结点. 两次信息增益优化算法解决了ID3算法的一个 明显缺点,即互信息的计算依赖特征值数目较多的 特征,但是大量实验表明,该算法更多的是适用于 收稿日期:2~5-04.14 作者简介:孙超利(1978一),女,硕士,研究方向:数据挖掘,数据库理论 与应用. 20O太原科技大学2005钽 两值属性的样例集,对于多值属性的效果并不明 显.为此,本文针对该算法不足进行了改进,把属 性和属性值对应成一个属性,这样每个属性一值对就 是两值属性,该算法不仅克服了ID3算法偏向于取 值多的属性的不合理性,而且生成的新的样例集正 好符合了两次信息增益优化算法适用于两值属性 的测试集的需求,同时解决了两次信息增益优化算 法对多值属性效果不明显的缺点. lID3及其改进算法] ID3算法是以信息熵的下降速度作为选取测试 属性的而提出来的一种算法,信息熵的下降也 就是信息不确定性的下降.ID3算法开始时,所有 的数据都在根结点,属性都是种类字段,所有记录 用所选属性递归的进行分割,直到一个结点上的数 据都属于同一个类别或者没有属性可以再用于对 数据进行分割.算法核心是在决策树中各级结点 上选择属性,用信息增益率作为属性选择的标准, 使得在每一非叶结点进行测试时,能获得关于被测 试例子最大的类别信息,使用该属性将例子集分成 子集后,系统的熵值最小. 设训练实例集为,目的是将训练实例分为n 类.设属于第i类的训练实例个数是C,X中总的训 练实例个数为IXI.若选择测试属性a进行测试,在 得知a=aj的情况下属于第i类的实例个数为C个 ,记: p(口=)= 即:P(C;口=ai)为测试属性a的取值为口时它属 于第i类的概率.此时决策树对分类的不确定性程 度就是训练实例集对属性的信息熵, H(Xj)=一?p(C,口=aj)log2p(Ci;口=aj) 又因为在选择测试属性a后伸出的每个a=a叶结 点对于分类信息的条件熵为: H(X/a):?p(C;口=aj)H(Xj)(1) 因此属性a对于分类提供的信息量,(X;a)为 ,(X;a)=一H(X)一H(X/a)(2) 公式(1)的值越小则式(2)的值越大,说明选择 测试属性a对于分类提供的信息越大,选择a之后 对分类的不确定程度越小.Quinlan的ID3算法就是 选择使得,(X;口)最大的属性作为测试属性,即选择 使得公式(1)最小的属性a. 虽然ID3算法得到了广泛的应用,但它仍存在 着许多缺陷.Bratko的研究小组在用ID3算法构造 决策树的时候发现,有些属性在按照熵值最小的原 则被ID3算法列为应该首先判断的属性,但是医学 专家却认为这些属性在判断病情时并不那么重要, 因此,Kononenko等人认为Quinlan的熵函数并不理 想,有偏向于取值较多的属性的缺陷.为此,提 出了许多不同的改进算法,例如:两次信息增益优 化算法等. 两次信息增益优化算法是以ID3为基础的,每 当选择一个新的属性时,算法不仅仅考虑该属性带 来的信息增益,而且考虑到选择该属性后继续选择 的属性带来的信息增益,即同时考虑树的两层结 点. 设A为侯选属性,A有个属性值,对应的概率 分别为P.,P,…,P,按照最小信息熵原理对属性A 扩展,{B.,,…,B}为个子结点选择的属性,分 别对应的信息熵为(B.),H(B),…,(B),则 (A)=P?H(B)(3) l 算法选择属性A的标准是A使得日(A)最小. 由于该算法不是计算选择A后带来的信息增 益,而是继续选择A的后继属性,计算系统的熵值, 同时考虑树的两层结点,因此在一定程度上能很好 的解决ID3算法偏向于取值较多的属性的缺陷.但 是该算法也存在着一定的缺点,大量试验表明,该 算法对于具有两值属性的数据集具有更好的优化 性能,但对于多值属性效果并不明显. 2基于属性一值对的两次信息增益优化 由于属性的取值往往对实例的分类与属性有 着同样的影响,而已有的决策树归纳学习算法只注 意到属性的选取,而把属性的取值置于次要地位. 因此,可把属性与属性的取值统一考虑,避免只选 取属性进行分类的弊端. 设A为侯选属性,A有个属性值,,,…, 本文把属性A和属性值分别对应起来,这样可以组 合得到个新属性,分别为A=.,A=-.,A= ,这个新属性都只有两个值,要么为l,要么为0, 第26卷第3期孙超利,等:基于属性一值对的信息增益优化算法201 当原属性的值满足时,取属性A=的值为1, 当不满足时取值为0.因此每个新属性所对应都是 两个值,它所形成的决策树一定是一个二叉树.在 此基础上,利用两次信息增益优化算法,不仅可以 克服ID3算法中偏向于取值多的属性的不合理性, 而且不管是多值也好,还是两值也好,都具有很好 的优化性能. 利用两次信息增益优化算法,可以得到信息熵 为0的子节点,然后再继续递归调用两次信息增益 算法,而错过了图1的这几种结束情况的选取机会, 从而耗费构造决策树的时间,而且构造的决策树树 偏大一些.基于这种考虑,本文在得到一个节点的 时候(比如节点),简单地判断各个子节点的特性, 如果符合上述几种特例就此结束向下的节点构造. 图1A的子节点的几种特殊情况 Fig.1Somekindsofspecialconditions aboutsubnodesofA 3基于属性一值对的信息增益优化算法 基于上述属性一值对的两次信息增益优化思想, 可给出如下算法. 算法:GBT(generate—binary—tree) 输入:训练样本samples;侯选属性的集合attrib. ute—— list 输出:一棵二叉树 (1)读取训练样本数据文件的维数 (2)分配数据存储空间 (3)将数据读入,并存储每个属性的不同属性 值,建立一虚表samplesl,存放属性一值对的值,即 1或0,侯选属性的集合attribute—listl (4)创建结点N (5)ifsamplesl都在同一个类Cthen (6)返回N作为叶节点,以类C标记; (7)ifattribute—listl为空then (8)返回N作为叶节点,标记为samplesl中最 普通的类; (9)对于每个测试属性test—attribute (10)iftest—attribute=Athen (11)ifA处于图1的三种情况之一then (12)加上树叶或最后区分的节点,叶节点中标 记为samplesl中最普通的类 (13)else设是A的后继属性,求得对应的信息 熵 (14)选择信息熵和对应概率的乘积的和的最 小值的属性.值对test—attribute; (15)标记节点N为test—attribute (16)递归调用(4)到(15) (17)结束 由于上述算法把每个属性和他们的若干值分 别捆绑对应起来,作为一个属性看待,因此该算法 所形成的决策树肯定是一个二叉树.看起来好像 增加了属性的个数,而本质上并没有,而且数据存 储依旧是原来的数据集合.而且本文也并不是纯 粹的利用文献[4]所提出的两次信息增益优化算 法,因为文献[4]的算法是将下层节点的信息增益 传递上来,经过计算,然后选择信息熵最小的那个 属性作为该节点,然后递归调用该算法,从而构造 出一棵决策树.而如果只是单单递归调用该算法 来构造决策树,正如文献[6]所说那样,有些数据集 构造的决策树并不如预想的那么理想.原因很简 单,在选出某个属性作为节点的时候,针对它的子 节点不能简单地再次调用该算法,而要根据该子节 点的特点进行处理.因此在上述算法中根据图1的 几种情况对文献[4]的算法进行了改进. 需要强调的是,对于那些只有两值属性的数据 集,尽管生成属性.值对没什么意义,但是上述算法 也比文献[4]所构造的决策树更加简洁,更接近于 理想的决策树.因此该算法比ID3以及文献[4]所 提出的改进算法在算法以及存储结构上更简单. 4实验分析 F—family是测试集FAM的家族,常用来测试生 成决策树性能.其中/7,=k+2(k为正整数).测试集 FAM有/7,个属性,前k个属性相当于地址位,后面的 2个属性相当于数据位.由地址位决定例子的类别与 某一个数据位相等.所有属性和类取值均为0和J.例 如,FAM6有6个属性F1,,乃,,,和一个类 202太原科技大学2005年 别c.这样样本的个数就是2.=64个.类别c的值由 属性F1,,乃,,,的不同取值来确定,即:C = !F1&&!F2&&F3Il!FI&&F2&& ;F4IlF1&&! F2&&F5F1&&&&f16. 本文利用上述测试集进行测试,并将ID3,两次 信息增益优化算法以及本文提出的算法构造的决 由表1可知:1)对于FAM6,ID3得到的决策树 叶结点数为18个,而与最理想决策树的8个叶结点 相距甚远;2)从图中还可以看到本文所提出的属性一 值对两次信息增益优化算法基本上优越于文献[4] 所提出的两次信息增益优化算法,有些甚至已经达 到了理想的决策树状态. 表1决策树特性对比 Tab.1characteristicc.mparis.n.fdecisiontree5结论 (叶结点数,树高)FAM6FAM6AFAM6BFAMll ID3(18,5)(22,6)(22,6)(54,6) 两次信息增 益优化算法(12,4)(12,5)(12,5)(40,5) 属性一值对两次信 息增益优化算法(8,3)(11,5)(18,5)(16,4) 理想的决策树(8,3)(12,4)(12,4)(16,4) 策树来和最优决策树进行比较,情况如图2所示. 参考文献: 本文针对文献[4]中所提出的算法对于多值属 性的效果不明显的缺陷,利用它对于两值属性的优 势,提出了属性一值对的信息增益优化算法.通过对 使用同一个实例集用不同的算法建立的决策树的分 析比较,得出使用属性一值对的信息增益优化算法比 ID3算法以及文献[2]所提出的信息增益优化算法都 有改进,所得到的决策树更接近于理想的决策树. [1]Quinlan,J.R.LearningEfficientClassificationProceduresandTheirAppl icationtoChessEndGames[J].InR.S.Michalski, J.G.CarbonellandT.M.Mitchell(Eds.),MachineLearning:AnArtificialInte lligenceApproach,Springer,PaloAlto,CA: Tioga,1983,I,463-482. [2]QuinlanJ.R..Inductionofdecisiontrees[J].MachineLearning,1986,1,(1 ):81—106 [3]TuPei—lei,ChungJen—yao.Anewdecision—treeclassificationalgorithmformachinelearning.Inproceedingsofthe1992 IEEEInternationalConferenceonToolsforArtificialIntelligence[J].Arlington,VA,1992,370—377. [4]刘小虎,李生.决策树的优化算法[J].软件,1998,9(10):797—800. [5]史忠植.知识发现[M].北京:清华大学出版社,2002.24—36. [6]张维东,张凯,董青,孙维华.利用决策树进行数据挖掘中的信息熵 计算[J].计算机工程,2001,27(3):71—89. [7]QuinlanJ.R..C4.5:ProgramsforMachinelearning,MorganKaufmannpublishersInc.,SanMateo,CA,1993,1—302. TheInformationGainAlgorithmBasedonAttribute.valuePairs SUNChao-li.ZHANGJi.fu (CollegeofComputerScienceandTechnology,TaiyuanUniversityofScienceand Technology,Taiyuan030024,China) Abstract:OneofthedisadvantagesofID3algorithmisthatitiseasytoselectthoseattributeswhosevalueismore. TheoptimumalgorithmonID3presentedrecentlycansolvesomedisadvantagesofID3,butitisonlygoodtothe datasetsthattheattributeonlyhastwovalueswhileisnotSOgoodtothosethattheattributehasmorethantwoval? ues.Tosolvethisdisadvantage,thispaperpresentsanewapproachonID3algQ hm——theinformationgainof attribute—valuepairs——t0optimizethedecisiontree,thisalgorithmcombi nestheattributewithitsvalueasone attribute.Byanalyzingtheoriesandexperiments,thispapershowsthatthisalgorithmnotonlysolvesthedisadvan— tageofID3,butthenewtestsetscanalsomeettheneedsofthealgorithm,whichcansolvethedisadvantageof thatalgorithm. Keywords:dataMining,decisiontree,informationgain,informationentropy,attribute?valuepairs