数据挖掘中决策树算法的探讨

数据挖掘中决策树算法的探讨唐华松,姚耀文(华南理工大学计算机系,广东广州510640)摘要:决策树算法是DM的一个活跃的研究领域。首先给出了DM中决策树算法的基本思想,然后讨论了决策树算法中的难点问题,提出了利用熵与加权和的思想来选择取值的算法。关键词:数据挖掘;决策树;熵中图分类号:TP301.6文献标识码:A文章编号:100123695(2001)0820018202ResearchonDecisionTreeinDataMiningTANGHua2song,YAOYao2wen(Dept.ofComputerScience,SouthChinaUniversityofTechnology,GuangzhouGuangdong510640,China)Abstract:DecisionTreeisoneofheatedfieldsinDataMininginrecentyears.ThispaperfirstgivesthemainthoughtsofalgorithmofDecisionTreeinDataMining,thendiscussesthedifficultproblemofselectingvalueondivisioninDecisionTree,andputforwardanalgorithmusingthethoughtsofentropyandweightedentropytosolvetheproblemwiththeexamples.Keywords:DM;Decisiontree;Entropy1引言数据库技术的迅速发展以及数据库管理系统的广泛应用,导致人们积累了越来越多的数据。巨增的数据背后蕴藏着丰富的知识,而目前的数据库技术虽可以高效地实现数据的查询、统计等功能,但却无法发现数据中存在的关系和规则,无法根据现有的数据预测未来的发展趋势。数据库中存在着大量的数据,却缺乏挖掘数据背后隐藏的知识的手段,出现了“数据爆炸而知识贫乏”的现象。在此背景下,数据库知识发现(KDD)及其核心技术—数据挖掘(DM)便应运而生了。KDD的研究内容是,能自动地去处理数据库中大量的原始数据,从中挖掘搜索出具有规律、富有意义的模式。它的发现过程主要有三个步骤:定义要发现的问题;根据问题进行数据搜索、模式抽取;评价所发现的知识的好坏。三者之中,核心技术是第二步,即数据搜索及模式抽取方法。KDD=问题处理+DM+解释评价。由于问题处理和解释评价的研究较成熟,所以目前KDD的研究和实现难点重点都集中在核心的DM上。DM的核心技术算法主要有统计分析方法、神经元网络、决策树方法,遗传算法等。其中,决策树是一种常用于预测模型的算法,它通过将大量数据有目的地分类,从中找到一些具有商业价值的,潜在的信息。2决策树的基本思想决策树的结构,顾名思义,就像一棵树。它利用树的结构将数据记录进行分类,树的一个叶结点就代表某个条件下的一个记录集,根据记录字段的不同取值建立树的分支;在每个分支子集中重复建立下层结点和分支,便可生成一棵决策树。例如,我们要分析一个网站的用户接受某项新服务的情况,可以从中选取100个用户,其中50个接受这项新服务的,50个拒绝这项新服务的,然后通过建立决策树来分析用户的情况,寻找一些潜在的规则信息。图1网站某项新服务的决策树结构利用决策树进行分析,可以容易地找到一些具有商业价值的潜在的规则信息。如在上例中,从决策树结构图可以看出:在接受这项新服务的用户中有60%是使用新帐号的,在拒绝这项新服务的用户中有100%是使用旧帐号的;也就是说,如果用户是使用新帐号的,那么他就有60%的可能接受这项新服务,如果用户是使用旧帐号的,那么他就有100%的可能拒绝这项新服务。当然,还可以从决策树中找到其它的规则信息,这里就不再举例说明了。3决策树的技术难点建决策树,就是根据记录字段的不同取值建立树的分支,以及在每个分支子集中重复建立下层结点和分支。建决策树的关键在于建立分支时对记录字段不同取值的选择。选择不同的字段值,会使划分出来的记录子集不同,影响决策树生长的快慢以及决策树结·81·计算机应用研究2001年©1995-2004TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.构的好坏,从而导致找到的规则信息的优劣。可见,决策树算法的技术难点也就是选择一个好的分支取值。利用一个好的取值来产生分支,不但可以加快决策树的生长,而且最重要的是,产生的决策树结构好,可以找到较好的规则信息。相反,如果根据一个差的取值来产生分支,不但减慢决策树的生长速度,而且会使产生的决策树分支过细,结构性差,从而难以发现一些本来可以找到的有用的规则信息。怎样的取值才算一个好的取值呢?一个好的取值,就是决策树根据此值来分裂时,产生的分支子集中的记录在预测内容上尽可能一致。何谓子集中的记录在预测内容上尽可能一致呢?举个例子,我们对学生的思想品德情况进行分析,预测内容是在思想品德上是优或良,抽取10个学生记录,其中5个学生的思想品德是优,另5个的是良,那么我们可以得到以下两个不同的划分:学号成绩学号成绩学号成绩学号成绩01优03良01优02优02优05良03良04优04优06良05良06良07优08良07优08良10优09良09良10优(A)(B)图2学生思想品德情况的两个划分在(A)方案中,划分后的左分支子集的记录的思想品德都是优,右分支子集的记录的思想品德都是良,即左分支100%优、0%良,右分支100%良、0%优,子集中的记录在预测内容上已尽可能一致。我们就可以从两个分支中寻找记录的共性,以得到和学生思想品德情况有关的信息。在(B)方案中,划分后的左分支子集中3条记录的思想品德是优,2条记录的思想品德是良,右分支子集中2条记录的思想品德是优,3条记录的思想品德是良,即左分支60%优、40%良,右分支60%良、40%优,子集中的记录在预测内容上的一致性差,还不能有效地总结出和学生思想品德情况有关的信息。怎样找到好的取值呢?从上例,可以看出,好的取值分支后子集的记录的一致性好,也就是记录的有序性好。通常,在系统学上,经常使用“熵”来表示事物的无序度。所以在这里,也可以引用“熵”来估量分支后子集有序性的好坏。熵H=Σ(2Pi)×lg(Pi)其中Pi是指分支子集中记录取某值的可能性。如果子集的熵值越小,则子集记录的有序性越好;如果熵值越大,则有序性越差。因此,我们可以对根据不同取值进行分裂后的左右分支的子集分别计算各自的熵值,选择熵值最小所对应的记录字段的取值,这就是好的取值。如上例中,Ha左,右=(25/5)×lg(5/5)+(20/5)×lg(0/5)=0.0Hb左,右=(23/5)×lg(3/5)+(22/5)×lg(2/5)=0.3要提出注意的是,如果左右分支子集的记录数相差太远,则可能导致新的情况,此时只用熵值来判断可能选择不到好的取值。如上例,也可以得到以下两个划分:(C)左分支:优右分支:优,优,优,优,良,良,良,良,良(D)左分支:优,优,优,优,良右分支:优,良,良,良,良Hc左=(21/1)×lg(1/1)+(20/1)×(0/1)=0.00Hc右=(24/9)×lg(4/9)+(25/9)×(5/9)=0.99Hd左=(24/5)×lg(4/5)+(21/5)×(1/5)=0.72Hd右=(24/5)×lg(4/5)+(21/5)×(1/5)=0.72取左右分支的和平均值,则Hc平=(0+0.99)/2=0.50Hd平=(0.72+0.72)/2=0.72选择小值,可能就选择(C)方案,但从例子可以看出,(D)方案才是较好的,因为它把同类的基本划分到一起了,而且如果像(C)方案那样,每次都只把一个数据划分出去,只会导致决策树结构的层次变得复杂,同类型的记录无法有效地归到一起,不利于从中发掘潜在的信息。要解决这个问题,可以利用“加权和”的思想,根据分支子集所占的比重来给它一个权值,然后计算加权熵,通过比较加权熵的大小来选择取值。加权熵H加=ΣXi×Hi其中Xi是指分支子集所占的比重,Hi是指分支子集的熵,则Hc加=9/10×0.99+1/10×0.0=0.89Hd加=1/2×0.72+1/2×0.72=0.724实验事例在实验事例中,我们构造一个包括10条记录的学生总评成绩的模型,以分析学生总评成绩在85分以上与何因素有关。我们提出两个方案,(Ⅰ)方案每次选择第一个取值来产生分支;(Ⅱ)方案利用加权熵算法选择取值来产生分支。通过对两个方案产生的决策树进行比较,可以了解加权熵算法的优点。学号01020304050607080910性别FMMFMMMFFM年龄21202122232021232021体育成绩AABAAABBBA思想品德优良优优良优良优优良发表论文2001020010平时成绩95908080758595807080总评成绩95858085708590757075图3学生总评成绩的情况在图4中,Y表示学生的总评成绩在85分以上;N表示学生的总评成绩在85分以下。由图4可见,方案(Ⅱ)构造的决策树结构好,基本上将总评成绩在85分以上或以下的同类学生划分到一起,容易得出“如果学生的平时成绩在85分以上,他的总评成绩就有100%的可能在85分以上”、“如果学生的平时成绩在85分以下,他的总评成绩就有5/6即83.3%的可能在85分以下”等规则信息。(下转第22页)·91·第8期唐华松等:数据挖掘中决策树算法的探讨©1995-2004TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.和即插即用,共同协作,形成最终的GIS应用。对于非GIS专业人员而言,可以容易地通过对GIS组件的利用,将GIS功能嵌入应用程序中,大大提高了开发的效率及GIS应用。GIS的互操作组件特别有利于GIS专业人员的是,他们不必要再开发支持专用的开发软件或数据库,而是将更多的精力集中于GIS的“G”(地学应用),从而使GIS产品达到更高的层次。4讨论与展望地理信息及其应用是复杂的。要将现实世界复杂的事物、过程、现象映射到计算机中,并依据人们的需要对其进行处理,并不是一件容易的事情。虽然GIS界及IT界早已认识到信息共享与互操作的重要性,并做了大量工作致力于它们的实现。到目前为止,获得的成果离人们的目标还很远。在异构分布环境中,GIS互操作适应网络化和社会化的需求,以分布式计算、面向对象技术、互联网络技术、开放式数据库技术等为支撑,通过组件技术来实现互操作。而在互操作的实现过程中,由于GIS技术本身及计算机技术的某些方面的不成熟,目前还不能完全实现。GIS技术本身的局限表现在:只对复杂现实世界的简单对象的特征有清晰的定义和描述,而对复杂对象,如三维、四维、多维的讨论较少;地理数据具有多重性的特征,在地理数据内部交换及转换中语义难免有不兼容,用来实现数据无损转换的语义转换器在具体实现中工作难度很大。来自计算机技术方面的限制主要表现在:作为支撑技术的分布式计算技术和面向对象技术自身尚未完全成熟;OGC用于互操作规范组件的连接与通讯的实现规范CORBA,DCOM,SQL彼此之间不能直接访问。目前对GIS互操作研究的基本单位是过程或对象,而对粒度更大的应用间的互操作考虑得较少等。目前还没有商业化的GIS软件能完全支持GIS互操作。而在OGC成员之间已有GIS互操作实现的成功实例。GIS互操作的实现将增进GIS与IT界的协作能力,这种协作无疑给GIS界造就了新的机遇、更广阔的市场、更多的收入。前景是美好的,而地理信息共享和GIS的互操作的完全实现,由于存在的种种障隘涉及计算机领域和GIS领域的疑难问题,需要IT界和GIS界的共同努力,还需要很长时间。我国目前在这个领域的研究还不是很多,有必要对国内GIS软件的互操作进行研究,同时跟踪OpenGIS的国际最新技术和热点,力争将我国的地理信息和GIS软件融入到国际大舞台中。参考文献:[1]李德仁.论地理信息学