《2022年数据挖掘中决策树算法的探讨定义 .pdf》由会员分享，可在线阅读，更多相关《2022年数据挖掘中决策树算法的探讨定义 .pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据挖掘中决策树算法的探讨唐华松 , 姚耀文( 华南理工大学计算机系 , 广东广州 510640) 摘要: 决策树算法是 DM 的一个活跃的研究领域。首先给出了DM 中决策树算法的基本思想 , 然后讨论了决策树算法中的难点问题, 提出了利用熵与加权和的思想来选择取值的算法。关键词 : 数据挖掘 ; 决策树 ; 熵中图分类号 : TP301. 6 文献标识码 : A 文章编号 : 100123695 (2001) 0820018202 Research on Decision Tree in Data Mining TANG Hua2song , YAO Yao2wen ( Dept . of
2、Computer Science , South China 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 algorithmof Decision Tree in Data Mining , then discusses the difficult problemof
3、 selecting value on division in Decision Tree , and put forward an algorithm using the thoughts of entropy and weighted entropy to solve the problem with the examples. Key words : DM;Decision tree ;Entropy 1 引言数据库技术的迅速发展以及数据库管理系统的广泛应用 , 导致人们积累了越来越多的数据。巨增的数据背后蕴藏着丰富的知识, 而目前的数据库技术虽可以高效地实现数据的查询、统计等功能, 但
4、却无法发现数据中存在的关系和规则, 无法根据现有的数据预测未来的发展趋势。数据库中存在着大量的数据, 却缺乏挖掘数据背后隐藏的知识的手段, 出现了“数据爆炸而知识贫乏”的现象。在此背景下 , 数据库知识发现 (KDD) 及其核心技术数据挖掘 (DM) 便应运而生了。 KDD 的研究内容是 , 能自动地去处理数据库中大量的原始数据, 从中挖掘搜索出具有规律、富有意义的模式。它的发现过程主要有三个步骤 : 定义要发现的问题 ; 根据问题进行数据搜索、模式抽取 ; 评价所发现的知识的好坏。三者之中, 核心技术是第二步 , 即数据搜索及模式抽取方法。KDD = 问题处理 + DM+ 解释评价。由于问题
5、处理和解释评价的研究较成熟 , 所以目前 KDD 的研究和实现难点重点都集中在核心的 DM 上。DM 的核心技术算法主要有统计分析方法、神经元网络、决策树方法 , 遗传算法等。其中 , 决策树是一种名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 常用于预测模型的算法 , 它通过将大量数据有目的地分类, 从中找到一些具有商业价值的, 潜在的信息。2 决策树的基本思想决策树的结构 , 顾名思义 , 就像一棵树。它利用树的结构将数据记
6、录进行分类, 树的一个叶结点就代表某个条件下的一个记录集, 根据记录字段的不同取值建立树的分支 ; 在每个分支子集中重复建立下层结点和分支 , 便可生成一棵决策树。例如, 我们要分析一个网站的用户接受某项新服务的情况 , 可以从中选取 100 个用户 , 其中50 个接受这项新服务的 ,50 个拒绝这项新服务的 , 然后通过建立决策树来分析用户的情况 , 寻找一些潜在的规则信息。图1 网站某项新服务的决策树结构利用决策树进行分析 , 可以容易地找到一些具有商业价值的潜在的规则信息。如在上例中, 从决策树结构图可以看出 : 在接受这项新服务的用户中有60 % 是使用新帐号的 , 在拒绝这项新服务
7、的用户中有100 % 是使用旧帐号的 ; 也就是说 , 如果用户是使用新帐号的, 那么他就有 60 %的可能接受这项新服务 , 如果用户是使用旧帐号的 , 那么他就有 100 %的可能拒绝这项新服务。当然 , 还可以从决策树中找到其它的规则信息, 这里就不再举例说明了。3 决策树的技术难点建决策树 , 就是根据记录字段的不同取值建立树的分支 , 以及在每个分支子集中重复建立下层结点和分支。建决策树的关键在于建立分支时对记录字段不同取值的选择。选择不同的字段值, 会使划分出来的记录子集不同 , 影响决策树生长的快慢以及决策树结 8 1 计算机应用研究 2001 年? 1995-2004 Tsin
8、ghua Tongfang Optical Disc Co., Ltd. All rights reserved. 构的好坏 , 从而导致找到的规则信息的优劣。可见, 决策树算法的技术难点也就是选择一个好的分支取值。利用一个好的取值来产生分支, 不但可以加快决策树的生长 , 而且最重要的是 , 产生的决策树结构好 , 可以找到较好的规则信息。相反, 如果根据一名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 个差的取值来产生分支
9、, 不但减慢决策树的生长速度, 而且会使产生的决策树分支过细, 结构性差 , 从而难以发现一些本来可以找到的有用的规则信息。怎样的取值才算一个好的取值呢? 一个好的取值, 就是决策树根据此值来分裂时, 产生的分支子集中的记录在预测内容上尽可能一致。何谓子集中的记录在预测内容上尽可能一致呢? 举个例子 , 我们对学生的思想品德情况进行分析, 预测内容是在思想品德上是优或良 , 抽取10 个学生记录 , 其中5 个学生的思想品德是优 , 另5 个的是良 , 那么我们可以得到以下两个不同的划分 : 学号成绩学号成绩学号成绩学号成绩01 优03 良01 优02 优02 优05 良03 良04 优04
10、优06 良05 良06 良07 优08 良07 优08 良10 优09 良09 良10 优(A) (B) 图2 学生思想品德情况的两个划分在(A) 方案中 , 划分后的左分支子集的记录的思想品德都是优 , 右分支子集的记录的思想品德都是良, 即左分支 100 %优、0 %良, 右分支 100 %良、0 %优, 子集中的记录在预测内容上已尽可能一致。我们就可以从两个分支中寻找记录的共性, 以得到和学生思想品德情况有关的信息。在(B) 方案中 , 划分后的左分支子集中 3 条记录的思想品德是优 ,2 条记录的思想品德是良 , 右分支子集中2 条记录的思想品德是优 ,3 条记录的思想品德是良, 即左
11、分支 60 %优、40 %良, 右分支 60 %良、40 %优, 子集中的记录在预测内容上的一致性差, 还不能有效地总结出和学生思想品德情况有关的信息。怎样找到好的取值呢 ? 从上例 , 可以看出 , 好的取值分支后子集的记录的一致性好, 也就是记录的有序性好。通常 , 在系统学上 , 经常使用“熵”来表示事物的无序度。所以在这里 , 也可以引用“熵”来估量分支后子集有序性的好坏。熵 H =(2Pi) lg(Pi) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页
12、- - - - - - - - - 其中Pi 是指分支子集中记录取某值的可能性。如果子集的熵值越小 , 则子集记录的有序性越好 ; 如果熵值越大 , 则有序性越差。因此 , 我们可以对根据不同取值进行分裂后的左右分支的子集分别计算各自的熵值 , 选择熵值最小所对应的记录字段的取值, 这就是好的取值。如上例中 , Ha左, 右= (25/ 5) lg(5/ 5) + (20/ 5) lg(0/ 5) = 0. 0 Hb左, 右= (23/ 5) lg(3/ 5) + (22/ 5) lg(2/ 5) = 0. 3 要提出注意的是 , 如果左右分支子集的记录数相差太远 , 则可能导致新的情况 ,
13、此时只用熵值来判断可能选择不到好的取值。如上例, 也可以得到以下两个划分: (C) 左分支 : 优右分支 : 优, 优, 优, 优, 良, 良, 良, 良, 良(D) 左分支 : 优, 优, 优, 优, 良右分支 : 优, 良, 良, 良, 良Hc左= (21/ 1) lg(1/ 1) + (20/ 1) (0/ 1) = 0. 00 Hc右= (24/ 9) lg(4/ 9) + (25/ 9) (5/ 9) = 0. 99 Hd左= (24/ 5) lg(4/ 5) + (21/ 5) (1/ 5) = 0. 72 Hd右= (24/ 5) lg(4/ 5) + (21/ 5) (1/ 5
14、) = 0. 72 取左右分支的和平均值 , 则Hc平= (0 + 0. 99) / 2 = 0. 50 Hd平= (0. 72 + 0. 72) / 2 = 0. 72 选择小值 , 可能就选择 (C) 方案, 但从例子可以看出, (D) 方案才是较好的 , 因为它把同类的基本划分到一起了 , 而且如果像 (C) 方案那样 , 每次都只把一个数据划分出去 , 只会导致决策树结构的层次变得复杂, 同类型的记录无法有效地归到一起, 不利于从中发掘潜在的信息。要解决这个问题 , 可以利用“加权和”的思想, 根据分支子集所占的比重来给它一个权值, 然后计算加权熵, 通过比较加权熵的大小来选择取值。加
15、权熵 H加=Xi Hi 其中Xi 是指分支子集所占的比重 ,Hi 是指分支子集的熵, 则Hc加= 9/ 10 0. 99 + 1/ 10 0. 0 = 0. 89 Hd加= 1/ 2 0. 72 + 1/ 2 0. 72 = 0. 72 4 实验事例在实验事例中 , 我们构造一个包括 10 条记录的学生总评成绩的模型 , 以分析学生总评成绩在 85 分以上与何因素有关。我们提出两个方案, ( ) 方案每次选名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - -
16、 - - - - - - 择第一个取值来产生分支; ( ) 方案利用加权熵算法选择取值来产生分支。通过对两个方案产生的决策树进行比较 , 可以了解加权熵算法的优点。学号01 02 03 04 05 06 07 08 09 10 性别F M M F M M M F F M 年龄21 20 21 22 23 20 21 23 20 21 体育成绩 A A B A A A B B B A 思想品德优良优优良优良优优良发表论文 2 0 0 1 0 2 0 0 1 0 平时成绩 95 90 80 80 75 85 95 80 70 80 总评成绩 95 85 80 85 70 85 90 75 70 7
17、5 图3 学生总评成绩的情况在图4 中,Y表示学生的总评成绩在 85 分以上 ;N 表示学生的总评成绩在 85 分以下。由图 4 可见, 方案( ) 构造的决策树结构好 , 基本上将总评成绩在 85 分以上或以下的同类学生划分到一起, 容易得出“如果学生的平时成绩在 85 分以上 , 他的总评成绩就有 100 % 的可能在 85 分以上”、“如果学生的平时成绩在85 分以下, 他的总评成绩就有 5/ 6 即83. 3 % 的可能在 85 分以下”等规则信息。 (下转第 22 页) 9 1 第8 期唐华松等 : 数据挖掘中决策树算法的探讨? 1995-2004 Tsinghua Tongfang
18、 Optical Disc Co., Ltd. All rights reserved. 和即插即用 , 共同协作 , 形成最终的 GIS 应用。对于非GIS 专业人员而言 , 可以容易地通过对 GIS 组件的利用, 将GIS 功能嵌入应用程序中 , 大大提高了开发的效率及GIS 应用。 GIS 的互操作组件特别有利于GIS 专业人员的是 , 他们不必要再开发支持专用的开发软件或数据库 , 而是将更多的精力集中于 GIS 的“G ”(地学应用) , 从而使 GIS 产品达到更高的层次。4 讨论与展望地理信息及其应用是复杂的。要将现实世界复杂的事物、过程、现象映射到计算机中, 并依据人们的需要对
19、其进行处理 , 并不是一件容易的事情。虽然GIS 界名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 及IT界早已认识到信息共享与互操作的重要性, 并做了大量工作致力于它们的实现。到目前为止, 获得的成果离人们的目标还很远。在异构分布环境中 ,GIS 互操作适应网络化和社会化的需求 , 以分布式计算、面向对象技术、互联网络技术、开放式数据库技术等为支撑, 通过组件技术来实现互操作。而在互操作的实现过程中, 由于GIS 技术本身及计
20、算机技术的某些方面的不成熟, 目前还不能完全实现。GIS 技术本身的局限表现在 : 只对复杂现实世界的简单对象的特征有清晰的定义和描述, 而对复杂对象 , 如三维、四维、多维的讨论较少; 地理数据具有多重性的特征 , 在地理数据内部交换及转换中语义难免有不兼容, 用来实现数据无损转换的语义转换器在具体实现中工作难度很大。来自计算机技术方面的限制主要表现在: 作为支撑技术的分布式计算技术和面向对象技术自身尚未完全成熟 ;OGC 用于互操作规范组件的连接与通讯的实现规范 CORBA ,DCOM, SQL 彼此之间不能直接访问。目前对 GIS 互操作研究的基本单位是过程或对象, 而对粒度更大的应用间
21、的互操作考虑得较少等。目前还没有商业化的 GIS 软件能完全支持 GIS 互操作。而在 OGC 成员之间已有 GIS 互操作实现的成功实例。 GIS 互操作的实现将增进 GIS 与IT 界的协作能力, 这种协作无疑给 GIS 界造就了新的机遇、更广阔的市场、更多的收入。前景是美好的, 而地理信息共享和GIS 的互操作的完全实现 , 由于存在的种种障隘涉及计算机领域和 GIS 领域的疑难问题 , 需要IT 界和GIS 界的共同努力 , 还需要很长时间。我国目前在这个领域的研究还不是很多 , 有必要对国内 GIS 软件的互操作进行研究 , 同时跟踪 OpenGIS 的国际最新技术和热点 , 力争将
22、我国的地理信息和 GIS 软件融入到国际大舞台中。参考文献 : 1 李德仁 . 论地理信息学的形成及其在跨世纪中的发展C . 中国地理信息系统协会第二届年会论文集,1996 , 10. 2 黄裕霞 , 陈常松 , 何建邦 . GIS 的互操作 C . 中国地理信息系统协会、中国海外地理信息系统协会1998 年年会论文集,1998. 3 满晓麟 , 王书庆 , 石洞. 软件组件化技术及其在桥梁CAD 中的应用 J . 计算机应用研究 ,2000 ,17(9) :72274. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心
23、整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - 4 Zhong Ershun ,Song Guanfu ,Wang Erqi . Development of Components GIS Based on Applications. Proceedings of IEAS97& IWGIS 97C1 1997 , 1. 作者简介 : 骆成凤 (19762) ,女, 现为南京大学城市与资源学系地图学与地理信息系统专业硕士研究生, 主要研究方向为互操作性 GIS , 组件式地理信息系统的设计与实现。( 上接第 19 页) 图4 两个方案的决策树结构实
24、验中两个方案的比较表明, 利用加权熵算法来选择决策树的分支取值 , 不但可以加快决策树的生长, 而且最重要的是可以得到结构好的决策树, 便于从中挖掘好的规则信息。虽然计算加权熵需要一定的时间开销, 但随着记录数据的增大 , 这点开销不但因为决策树的快速生长得到弥补 , 而且会使总的运算时间减少, 从而提高算法的效率和性能。5 小结为了在数据挖掘的决策树算法中, 解决决策树分支取值的难点问题 , 我们提出了结合事例利用熵、加权和的思想来选择取值的算法。实验表明, 利用这个算法, 可以提高决策树的生长速度, 优化决策树的结构 , 发掘较好的规则信息。特别是在使用决策树算法来挖掘的数据越多 , 算法
25、的效率和性能就越好 , 算法的优越性就越明显。参考文献 : 1 美Harjinder S GILL1 数据仓库客户 / 服务器计算指南M1 王仲谋 , 刘书舟 1 北京: 清华大学出版社 ,19971 2 Alex Berson , Setphen J Smith1 Data Warehousing , Data Mining , &OLAPM1McGraw 2 Hill Book Co. ,August , 19991 作者简介 : 唐华松 (19762) ,女, 硕士研究生 , 研究方向为分布式计算。 2 2 计算机应用研究 2001 年名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - ? 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -