【精品】数据挖掘中决策树算法的探讨

1、数据挖掘中 决礙树算法的 探讨唐华松，姚翅文(华南理工大学计算机系，广东广州510640)摘 要：决策树算法是dm的一个活販的研究领域。首先给出了dm中决策树算法的基 本思想，然后讨论了决策树算法中的难点问题，提出了利用小商与加权和的思想来选择取值的算法。关键词：数据挖掘；决策树；炳中图分类号：tp301. 6文献标识码：a文章编号：100123695 (2001)0820018202research on decision tree in data miningtang iiua2song , yao yao2wen(dept . of computer science , south ch

2、ina university of technology , guangzhou guangdong 510640 , china)abstract : decision tree is one of heated fields in data mining in recent years. this paper first gives the main thoughts of algorithmofdecision tree in data mining , then discusses the difficult problemof selecting value on division

3、in decision tree , and put forward an algorithm using the thoughts of entropy and weighted entropy to solve the problem with the exampleskey words : dm;decision tree ;entropy1 弓i言数据库技术的迅速发展以及数据库管理系统的广 泛应用，导致人们积累了越来越多的数据。巨增的数 据背后蕴藏着丰富的知识，而目前的数据库技术虽可 以高效地实现数据的查询、统计等功务匕但却无法发现 数据中存在的关系和规贝！j,无法根据现有的数据预测

4、未来的发展趋势。数据库中存在着大量的数据，却缺 乏挖掘数据背后隐藏的知识的手段，出现了 “数据爆炸 而知识贫乏”的现象。在此背景下，数据库知识发现(kdd)及其核心技术-数据挖掘(dm) 便应运而生了。kdd的研究内容是， 能自动地去处理数据库中大量的原始数据，从中挖掘 搜索出具有规律、富有息义的模式。它的发现过程主 要有三个步骤:定义要发现的问题；根据问题进行数据 搜索、模式抽取；评价所发现的知识的好坏。三者之 中，核技术是第二步，即数据搜索及模式抽取方法。kdd = 问题处理+ dm+ 解释评价。由于问题处理和解 释评价的研究较成熟，所以目前kdd 的研究和实现难 点重点都集中在核心的dm

5、上。dm的核心技术算法主要有统计分析方法、神经元网络、决策树方法，遗传算法等。其中，决策树是一种常用于预测模型的算法，它通过将大量数据有目的地 分类，从中找到一些具有商业价值的，潜在的信息。2 决策树的基本思想决策树的结构，顾名思义，就像一棵树。它利用树 的 结构将数据记录进行分类，树的一个叶结点就代农 某个条件下的一个记录集，根据记录字段的不同取值 建立树的分支;在每个分支子集中重复建立下层结点和分支，便可生成一棵决策树。例如，我们要分析一个网站的用户接受某项新服务的情况，可以从中选取100 个用户，其中50 个接受这 项新服务的，50 个拒绝这项新服务的，然后通过理立决 策树来分析用户的情

6、况，寻找一些潜在的规则信息。图1网站某项新服务的决疏树结构便用时何-1'偎用i年用户年龄az 、用户弧許二 25|20桜受刀护厂|5聂受拒笛2,樓受5怔暫5襪受.40帝绝1田i网站臬项新服务的决策树緒构 利用决策树进行分析，可以容易地找到一些具有商业价值的潜在的规则信息。如在上例中，从决策树 结构图可以看出：在接受这项新服务的用户中有60 %是使用新帐号的，在拒绝这项新服务的用户中 有100 % 是使用旧帐号的；也就是说，如果用户是使用 新帐号 的，那么他就有60 %的可能接受这项新服务，如果用户 是使用旧 帐号的，那么 他就有100 %的可能拒绝这项新 服务。当然，还可以从决策树中找

7、到其它的规则信息， 这里就不再举例说明了。3 决策树的技术堆点建决策树，就是根据记录字段的不同取值建立树的分支，以及在每个分支子集中重复建立下层结点和分支。建决策树的关键在于建立分支时对记录字段不同取值的选择。选择不同的字段值，会使划分出来的记录子集不同，影响决策树生长的快慢以及决策树结 8 1 计算机应用研究2001年© 1995-2004 tsinghua tongfang optical disc co., ltd. all rights reserved.构的好坏，从而导致找到的规则信息的优劣。可见，决策树算法的技术难点也就是选择一个好的分支取值。利用一个好的取值来产生分支，

8、不但可以加快决策树的生长，而且最重要的是，产生的决策树结构好，可以找到较好的规则信息。相反，如果根据一个差的取值来产生分支，不但减慢决策树的生长速度， 而且会使产生的决策树分支过细，结构性差，从而难以 发现一些本来可以找到的有用的规则信息。怎样的取值才算一个好的取值呢？ 一个好的取值，就是决策树根据此值来分裂时，产生的分支子集中 的记录在预测内容上尽可能一致。何谓子集中的记录 在预测内容上尽可能一致呢？ 举个例子，我们对学生 的思想品德情况进行分析，预测内容是在思想品德上 是优或良，抽取10 个学生记录，其中5 个学生的思想品 德是优，另5 个的是良，那么我们可以得到以下两个不 同的划分：学号

9、成绩学号01020407成绩学号成绩学号成绩10优03优05优06优08优09m01 良03 良05 良07良09优02良04良06优08良10(a)(b)杓0102040710料03050608094艮艮艮19.艮030507w如<优良良优 栉02c406懵 呦til良良悅良2学生思想品徳怡况的两个划分在(a) 方案中，划分后的左分支子集的记录的思想 品德都是优，右分支子集的记录的思想品德都是良，即 左分支100 %优、0 %更，右分支100 %良、0 %优，子集中 的记录在预测内容上已尽可能一致。我们就可以从两 个分支中寻找记录的共性，以谒到利学生思想品德情 况有关的信息。在(b)

10、方案中，划分后的左分支子集中3 条记录的 思想品德是优，2 条记录的思想品德赴良，右分支子集 中2 条记录的思想品徳是优，3 条记录的思想品徳是 良，即左分支60 %优.40 %良，右分支60 %良.40 %优， 子集中的记录在预测内容上的一致性差，还不能有效 地总结出和学生思想品德情况有关的信息。怎样找到好的取值呢？ 从上例，可以看出，好的取 值分支后子集的记录的一致性好，也就是记录的有序 性好。通常，在系统学上，经常使用“炳”来表示事物的 无序度。所以在这里，也可以弓i用 “炳” 来估量分支后 子集有序性的好坏。烦h二工(2pi) x lg(pi)其中pi是指分支子集中记录取某值的可能性。

11、如果子集的炳值越小，则子集记录的有序性越好;如果癇值越大，则有序性越差。因此，我们可以对根据 不同取值进行分裂后的左右分支的子集分别计算各自 的蜩值，选择烦值最小所对应的记录字段的取值，这就 是好的取值。如上例中，ha左，右二(25/5)xlg(5/ 5) + (20/ 5)xlg(0/5)二 0.0hb左，右二(23/5)xlg(3/ 5) + (22/ 5)xlg(2/5) = 0.3要提出注意的是，如果左右分支子集的记录数相差太远，则可另岂导致新的情况，此时只用炳值来判断可矣岂选择不到好的取值。如上例，也可以得到以下两个划分：(0左分支：优右分支：优，优，优，优，気，m, 気(d) 左分

12、支：优，优，优，优，良右分支：优，良，良，良，良he左二(21/ 1)xlg(l/ 1)+ (20/ 1)x (0/ 1)=0.00he右二(24/ 9)xlg(4/ 9)+ (25/ 9)x (5/ 9)=0.99hd左二(24/ 5)xlg(4/ 5)+ (21/ 5)x (1/ 5)=0.72hd右二(24/ 5)xlg(4/ 5)+ (21/ 5)x (1/ 5)=0.72取左右分支的和平均值，则he平二(0 + 0. 99)/ 2=0. 50hd平二(0. 72 + 0.72)/ 2 = 0. 72选择小值，可能就选择(c) 方案，但从例子可以舌 出，(d)方案才是较好的，因为它把同

13、类的基本划分到 一起了，而且如果像(c) 方案那样，每次都只把一个数 据划分出去，只会导致决策树结构的层次变得复杂，同 类型的录无法有效地归到一起，不利于从中发掘潜 在的佶息。要解决这个问题，可以利用 “加权和”的思想，根据 分支子集所占的比重来给它一个权值，然后计算加权 癇，通过比较加权小商的大小来选择取值。加权炳h加二xi x hi其中xi是指分支子集所占的比董，hi是指分支子集的 m,贝!jhe加二 9/ 10 x0. 99 + 1/ 10 x0. 0 = 0. 89hd加二 1/ 2 x0. 72 + 1/ 2 x0. 72 = 0. 724 实验事例在实验事例中，我们构造一个包括10

14、 条记录的学 生总评成绩的模型，以分析学生总评成绩在85分以上 与何因素有关。我们提出两个方案，(i ) 方案每次选择第一个取值来产生分支；（n） 方案利用加权烦卑法 选择取值来产生分支。通过对两个方案产生的决策树学号01 0203 04 05 0607 08 09 10进行比较，可以了解加权烦算法的优点。学号0102co(h0606070910性别fmmfmmmffm213021222330212j3021aabaaapdba优ft优优ft优便优ttft发表伦文20010200i0959030758595wt)95858085708590757)75田3学生总评成绩的怡况性别f m m年龄2

15、1 2021 22 23 2021 23 20 21体育成绩a aba思想品德优良优优良优良优优良发表论文2 0 0 1 0 20 0 10平时成绩95 90 80 8075 8595807080总评成绩95 85 80 8570 8590757075图3学生总评成绩的情况在图4中，y表示学生的总评成绩在85 分以上；n表示学生的总评成绩在85 分以下。由图4 可见，方案（ii）构造的决策树结构好，基本上将总评成绩在85分以上或以下的同类学生划分到一起，容易得出“如果学生的平时成绩在85分以上，他的总评成绩就有100 %的可能在85分以上”、“如果学生的平时成绩在85分以下，他的总评成绩就有5

16、/ 6即83. 3 %的可能在85分以下”等规则信息。（下转第22页） 9 1 第8 期唐华松等：数据挖掘中决策树葬法的探讨© 1995-2004 tsinghua tongfang optical disc co., ltd. all rights reserved. 和即插即用，共同协作，形成最终的gts 应用。对于非gis 专业人员而言，可以容易地通过对gis 组件的利用，将gis 功能嵌入应用程序中，大大提高了开发的效 率及gis应用。gis的互操作组件特别有利于gis专业 人员的是，他们不必要再开发支持专用的开发软件或 数据库，而是将更多的精力集中于gis 的（地学应用），

17、从而使gis 产品达到更高的层次。4讨论与展盥地理信息及其应用是复杂的。要将现实世界复杂的事物、过程、现象映射到计算机中，并依据人们的需要对其进行处理，并不是一件容易的事情。虽然gis界及it界早已认识到信息共享与互操作的重要性，并做 了大量工作致力于它们的实现。到 目 前为止，获得的 成果离人们的 目标还很远。在异构分布环境中，gis 互操作适应网络化和社会 化的需求，以分布式计算. 面向对象技术. 互联网络技 术.开放式数据库技术等为支撑，通过组件技术来实现 互操作。而在互操作的实现过程中，由于gis技术本身 及计算机技术的某些方面的不成熟，目前还不能完全 实现。g1s 技术本身的局限表现

18、在：只对复杂现实世界的 简单对象的特征有清晰的定义和描述，而对复杂对象， 如三维、四维、多维的讨论较少；地理数据兵冇多重性 的特征，在地理数据内部交换及转换中语义难免有不 兼容，用来实现数据无损转换的语义转换器在具体实 现中工作难度很大。来自计算机技术方面的限制主要表现在：作为支撑技术的分布式计算技术和面向对象技术自身尚未完 全成熟；ogc 用于互操作规范组件的连接与通讯的实 现规范c0r13a , dcom, sql彼此之间不能直接访问。 目前对gjls 互操作研究的基本单位是过程或对象，而对 粒度更大的应用间的互操作考虑彳导较少等。目前还没有商业化的gis 软件能完全支持gis 互 操作。

19、而在ogc 成员之间已有gis 互操作实现的成功 实例。gis 互操作的实现将增进gis 与it 界的协作能 力，这种协作无疑给gis 界造就了新的机遇、更广阔的 市场、更多的收入。前景是美好的，而地理信息共享和 gis 的互操作的完全实现，由于存在的种种障隘涉及计 算机领域和gis 领域的疑难问题，需要it 界和gis 界 的共同努力，还需要很长时间。我国目 前在这个领域 的研究还不是很多，冇必要对国内gts 软件的互操作进 行研究，同 时跟踪opengis 的国际最新技术和热点，力 争将我国的地理信息和gis 软件砂入到国际大舞台中。 参考文献：1 李德仁. 论地理信息学的形成及其在跨世纪

20、中的发展c 中国地理信息系统协会第二届年会论文集,1996 ,10.2 黄裕霞，陈常松，何理邦.g1s的互操作c 中国地理借 息系统协会、中国海外地理信息系统协会1998 年年会论 文集,1998.3 满晓麟，王书庆，石洞. 软件组件化技术及其在桥梁cad 中的应用j .计算机应用研究,2000 , 17 (9) : 72274.4 zhong ershun , song guanfu , wang erqi . development of componcnts gis based on applications. procccdings of ieas' 97& iwgis ' 97c 1 1997 , 1.作者简介：骆成凤(19762),女，现为南京大学城市与资源学系地图学与地 理信息系统专业硕士研究生，主要研究方向为互操作性gis , 组件式地理信息 系统