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

《数据挖掘中决策树算法的探讨》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据挖掘中决策树算法的探讨唐华松，姚熠文(华南理工大学计算机系，广东广州510640)摘要：决策树莫法是DM的一个活跃的研究领域。首先给出了I)M中决策树其法的基本思想，然后讨论了决策树算法中的难点问题，提出了利用伙商与加权和的思想来选择取值的算法。关键词：数据挖掘；决策树；癇中图分类号：TP301.6文献标识码：A文章编号：100123695(2001)0820018202ResearchonDecisionTreeinDataMiningTANGHua2song,YAOYao2wen(Dept.ofComputerScience,SouthC

2、hinaUniversityofTechnology,GuangzhouGuangdong510640,China)Abstract:DecisionTreeisoneofheatedfieldsinDataMininginrecentyears.ThispaperfirstgivesthemainthoughtsofalgorithmofDecisionTreeinDataMining,thendiscussesthedifficuItproblemofselectingvalueondivisioninDecisionTree,andputf

3、orwardanalgorithmusingthethoughtsofentropyandweightedentropytosolvetheproblemwiththeexamples・Keywords:DM;Decisiontree;Entropy1弓I言数据库技术的迅速发展以及数据库管理系统的广泛应用，导致人们积累了越来越多的数据。巨增的数据背后蕴藏着丰富的如识，而目前的数据库技术虽可以高效地实现数据的查询、统计等功能，但却无法发现数据中存在的关系和规贝!J,无法根据现有的数据预测未来的发展趋势。数据库中存在着大量的数据，却缺乏挖掘数据背后隐

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

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

6、潜在的规则信息。图1网站某项新服务的决策树结构n碍受〕9拒偲丨彼用靳账、、使用旧味号使用时间V"年八•恵用时闾》I年

7、匕樓受护孚"1R檢受•“)爪萨

8、用户年鞋＜LV、'、用户年tb-25

9、2。按受宀并绘1(5矮受」0拒幻田1网站某项新朋务的快策树结构■••••••・••••••••»•••利用决策树进行分析，可以容易地找到一些具有商业价值的潜在的规则信息。如在上例中，从决策树结构图可以看出：在接受这项新服务的用户中有60%是使用新•帐号的，在拒绝这项新服务的用户中冇100%是使用旧帐号的；也就是说，如果用户是使用新•帐号的，那么他毓有60%的可能

10、接受这项新服务，如果用户是使用旧帐号的，那么他就冇100%的可能拒绝这项新服务。当然，还可以从决策树中找到其它的规则信息，这里就不再举例说明了。3决朿树的技术难点理决策树，就垒根据记录字段的不同取值建立树的分支，以及在每个分支子集中重复理立下层结点和分支。建决策树的关键在于建立分支时对记录字段不同取值的选择。选择不同的字段值，会使划分出来的记录子集不同，影响决策树生长的快慢以及决策树结•81•计算机应用研究2001年©1995-2004TsinghuciTongfangOpticalDiscCo.,Ltd.Allrightsreserved.构的

11、好坏，从而导致找到的规则信息的优劣。可见，决策树算法的技术难点也就是选择一个好的分支取值。利用一个好的取值来产生分支，不但可以加快决策树