决策树id3分类算法研究.pdf

浙江工业大学硕士学位论文 决策树i d 3 分类算法研究 作者姓名： 指导教师： 章晓 何熊熊教授 浙江工业大学信息工程学院 2 0 14 年4 月 d i s s e r t a t i o ns u b m i t t e dt oz h e j i a n gu n i v e r s i t yo ft e c h n o l o g y f o rt h e d e g r e eo fm a s t e r r e s e a r c ho nt h ei d 3 a l g o r i t h m so f d e c i s i o nt r e e c a n d i d a t e ：z h a n gx i a o a d v i s o r ：p r o f h ex i o n g x i o n g c o l l e g eo fi n f o r m a t i o ne n g i n e e r i n g z h e ji a n gu n i v e r s i t yo ft e c h n o l o g y a p r 2 0 1 4 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均己在文中 以明确方式标明。本人承担本声明的法律责任。 作者签名：绰嘲 日期：聊年上月力6 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密饧。 ( 请在以上相应方框内打“寸) 作者签名：牵闩蛆 导师签名：彳可饿锹 日期：加倍年乡月2 占日 日期：砰年月j o e t 浙江工业大学硕士学位论文 决策树i d 3 分类算法研究 摘要 数据挖掘技术能够从海量数据中挖掘有价值的信息，是处理大数据最有效的技术方法 之一。分类是数据挖掘中最重要的内容之一，分类技术被广泛应用在科研和智能商业活动 中。决策树方法又是分类技术最重要的方法之一。经过将近5 0 年的研究发展，已经出现 了多种先进的决策树分类算法。其中，i d 3 ( i t e r a t i v ed i c h o t o m i z e ) 算法是最著名的决策树算 法，也是其他多数决策树算法的研究基础。因为理论清晰，方法简单，容易实现，易于理 解，且分类效果较好，i d 3 算法被学者们广泛研究。然而i d 3 算法也有显著的缺点：如选 择分裂属性时，倾向于选择那些有较多属性值的属性；决策树在构建过程中，没有对树进 行优化：i d 3 算法的表达式逻辑性有待加强等。 对i d 3 算法的研究，本文主要做了如下工作： 1 、从理论上讨论分析了i d 3 算法多值偏向的原因。在理论分析过程中，主要做了以 下两方面的尝试创新：( 1 ) 基于粗糙集理论创造性引入属性重要度概念。( 2 ) 分析了属性 在增加属性值时对其他属性的属性重要度的影响。 2 、提出了改进的决策树算法一一s 3 算法。针对i d 3 算法的一些不足，s i d 3 算法引 入与属性值个数相关函数，简化i d 3 算法表达式，增加前剪枝技术。经过实验验证，s i d 3 算法克服了i d 3 算法在属性选择时的偏向多值属性缺点，减少了计算量，增强了算法的逻 辑性，增加剪枝技术，优化决策树。综合来讲，s i d 3 算法在构建决策树时效率更高、构建 的决策树的形状结构更加合理及判别精确率更加高。 3 、最后基于v i s u a ls t u d i o 平台，用cs h a r p 编程语言软件实现基于i d 3 及s i d 3 算法 的决策树智能系统，并应用在数字医疗诊断方面。 关键词：数据挖掘，决策树，i d 3 算法，多值偏向，s i d 3 算法，医疗诊断 浙江工业大学硕士学位论文 r e s e a r c ho n t h ei d 3a l g o r i t h m so fd e c i s i o n t r e e a b s t r a c t a so n eo ft h em o s te f f e c t i v em e t h o d sf o rd e a l i n gw i t hb i gd a t a , d a t am i n i n gt e c h n o l o g yc a n o b t a i nv a l u a b l ei n f o r m a t i o nf r o mm a s s i v ed a t a b e i n go n eo ft h em o s ti m p o r t a n ts u b je c t so fd a t a m i n i n g ，c l a s s i f i c a t i o nt e c h n i q u ei sw i d e l yu s e di ns c i e n t i f i cr e s e a r c ha n db u s i n e s si n t e l l i g e n c e a c t i v i t i e s f u r t h e r m o r e ，d e c i s i o nt r e et e c h n i q u ei so n eo ft h em o s ti m p o r t a n tm e t h o d so f c l a s s i f i c a t i o nt e c h n i q u e s d u r i n gt h ep a s t5 0y e a r s ，m a n yi n t e l l i g e n td e c i s i o nt r e ec o n s t r u c t i o n a l g o r i t h m sh a v eb e e np r o p o s e d t h ei d 3 ( i t e r a t i v ed i c h o t o m i z e ) a l g o r i t h mi so n eo ft h em o s t r e p r e s e n t a t i v em e t h o d s ，w h i c hi st h eb a s i so fm a n yo t h e rd e c i s i o nt r e em e t h o d s t h ei d 3 a l g o r i t h mh a sa t t r a c t e di n c r e a s i n g l yg r o w i n gi n t e r e s t sf r o mr e s e a r c h e r sb o t ha th o m ea n da b r o a d f o ri t sm a n ys u p e r i o rc h a r a c t e r i s t i c ss u c ha sc l e a r , s i m p l e ，c o n v e n i e n tt oi m p l e m e n t ，e a s yt o u n d e r s t a n d ，b e t t e rc l a s s i f i c a t i o nr e s u l t s ，a n ds oo n h o w e v e r , t h ei d 3a l g o r i t h ma l s oh a sm a n y d r a w b a c k s ，s u c ha sc h o o s i n gt h o s ea t t r i b u t e sw i t hm o r ea t t r i b u t ev a l u e sw h e nc h o o s i n gt h es p l i t p r o p e r t y , n oo p t i m i z a t i o nt ot r e e sw h e nc o n s t r u c t i n g ，a n dt h el o g i ce x p r e s s i o nn e e d st ob e s t r e n g t h e n e de t c t h i sp a p e ra i m st os t u d yi d 3a l g o r i t h ma n dt h em a i nw o r ka n di n n o v a t i o no ft h i sp a p e ri s s u m m a r i z e da sf o l l o w s f i r s t l y , t h i sp a p e ra n a l y s e st h er e a s o no ft h em u l t i - v a l u eb i a sp r o b l e mo fi d 3a l g o r i t h m t h e o r e t i c a l l y i nt h ep r o c e s so ft h e o r e t i c a la n a l y s i s ，t h i sp a p e ra t t e m p t st om a k ei n n o v a t i o ni nt h e f o l l o w i n gt w oa s p e c t s 1 ) t h ec o n c e p to fa t t r i b u t ei m p o r t a n c ei si n t r o d u c e db a s e do nr o u g hs e t t h e o r e m ；2 ) w ea n a l y z et h ei n f l u e n c eo fa t t r i b u t e sm u l t i v a l u eo nt h eo t h e ra t t r i b u t e s s e c o n d l y ，an o v e lm o d i f i e dd e c i s i o nt r e ea l g o r i t h mi sp r o p o s e d ，w h i c hi sd e f i n e da ss i d 3 a l g o r i t h m f o rt h el a c ko ft h ei d 3a l g o r i t h m ，t h en e ws i d 3a l g o r i t h mi n t r o d u c e saf u n c t i o n r e l a t e dt h en u m b e ro ft h ea t t r i b u t e sv a l u e ，s i m p l i f i e st h ee x p r e s s i o no fi d 3a l g o r i t h ma n da d d s p r u n i n gt e c h n o l o g y t h ee x p e r i m e n ts h o w st h a t s i d 3 a l g o r i t h mo v e r c o m e st h el a c k o f m u l t i - v a l u eb i a s ，r e d u c e st h ea m o u n to fc a l c u l a t i o n ，e n h a n c e st h ea l g o r i t h ml o g i c ，i n c r e a s e st h e p r u n i n gt e c h n i q u e st oo p t i m i z ed e c i s i o nt r e ec o n s t r u c t e d o v e r a l l ，u s i n gs i d 3a l g o r i t h mt o 浙江工业大学硕士学位论文 c o n s t r u c tad e c i s i o nt r e e ，i tw i l lb ef a s t e r , m o r er e a s o n a b l ei nt r e es h a p ea n dh i # e ri na c c u r a c y r a t e f i n a l l y , o nt h ev i s u a ls t u d i op l a t f o r m ，w i t hcs h a r pp r o g r a m m i n gl a n g u a g e ，ad e c i s i o nt r e e i n t e l l i g e n ts y s t e mc o n s t r u c t e db a s e dt h ei d 3a l g o r i t h ma n ds i d 3a l g o r i t h mi s r e a l i z e d i n a d d i t i o n ，w ea t t e m p tt oi m p l e m e n ti tt ot h ed i g i t a lm e d i c a ld i a g n o s t i c s k e yw o r d s ：d a t am i n i n g ，d e c i s i o nt r e e ，i d 3a l g o r i t h m ，m u l t i v a l u eb i a s ，s i d 3a l g o r i t h m ， m e d i c a ld i a g n o s t i c s 浙江工业大学硕士学位论文 目录 摘! 要i 第l 章绪论l 1 1 研究背景及意义1 1 2 发展历史及趋势3 1 2 1 发展历史3 1 2 2 发展趋势5 1 3 论文主要内容一5 第2 章数据挖掘及决策树基本理论7 2 1 引言一7 2 2 数据挖掘基本理论7 2 2 1 数据挖掘的定义7 2 2 _ 2 数据挖掘的功能 2 2 3 数据挖掘常用的方法 2 2 4 数据挖掘的步骤 8 9 1 0 2 3 决策树基本理论1 2 2 4 决策树算法中研究的基本内容1 4 2 4 1 数据预处理1 4 2 5 2 6 第3 章 3 1 3 2 3 3 3 4 2 4 2 属性选择标准 2 4 3 剪枝技术 2 4 4 性能评价 2 4 5 属性选择的度量方法 1 5 1 5 1 6 1 7 常用的决策树算法介绍1 9 2 5 1i d 3 算法1 9 2 5 2c a r t 算法2 1 2 5 3 其它算法2 2 本章小结2 2 m 3 算法属性多值偏向理论分析及优化。2 3 引言2 3 属性多值偏向理论分析2 3 3 2 1 粗糙集理论2 3 3 2 2 理论分析方法2 4 3 2 3 理论分析过程2 5 3 2 4 对其它属性的影响2 6 3 2 5 实验结果及分析2 8 i d 3 算法的优化2 8 3 3 1 算法表达式逻辑性优化2 8 3 3 2s i d 3 算法2 9 3 3 3 实验结果及分析3 0 本章小结3 3 浙江工业大学硕士学位论文 第4 章决策树在数字医疗中的应用。3 5 4 1 引言3 5 4 2 数据挖掘在数字医疗中的应用3 5 4 3 s i d 3 算法在医疗诊断中的应用3 7 4 3 1 基于决策树的乳腺癌细胞诊断系统3 7 4 3 2系统流程3 7 4 3 3 系统实现及比较分析3 9 4 4 本章小结4 8 第5 章总结与展望。4 9 5 1总结4 9 5 2 展望5 0 参考文献5 1 致谢5 4 攻读学位期间参加的科研项目和成果。5 5 浙江工业大学硕士学位论文 第1 章绪论 1 1 研究背景及意义 能源、材料和信息是支配人类社会的三大要素。随着计算机技术的快速发展，信息要 素愈发显示出其重要性和支配力，它将人类社会由工业化时代推向信息化畴代，使当今社 会几乎所有机构及个人都卷入到数据浪潮中。进入2 l 世纪以来，随着信息技术进一步发 展及人们生活全方位需求的激增，信息社会的数据信息以爆炸式的方式迅速增长。大多数 学者称当今社会为大数据的时代。随着过去十几年里移动互联网的快速发展，电子商务及 社交网络的兴起，人们可以随时随地产生、分享、消耗大量的数据。全球主干通信网每天 传输万兆兆字节数据。据权威的a l e x a 统计，去年中国最大的门户网站的日均流量达到7 2 6 0 万次，前十的门户网站最少也有1 0 0 0 万次。收索引擎支持的数十亿次w e b 收索每天要处 理数万兆字节数据。去年在由阿里巴巴策划的“双十一 全民购物活动当天，淘宝网最高 峰访问量超过1 0 0 0 9 b s 。据美国互联网数据中心指出，互联网上的数据每年将增长5 0 ， 每两年便将翻一番，而目前世界上9 0 以上的数据是最近几年才产生的。数据的爆炸式 增长、广泛可用和巨大数量使得我们的时代成为真正的数据时代。 然而，面对海洋般多的数据，人们往往找不到有价值的信息。大量的数据往往被描述 为“数据极大丰富，信息相当贫乏”。面对大数据，人们不能再用以往传统方法去处理。 目前主流的数据库系统，仅仅提供存储备份、查询及简单的数据分析等功能，这远远不能 满足人们的进一步需求。因此，急需功能强大的工具，能够从这些海量数据中挖掘更有价 值的信息，把这些数据转化成有组织、有次序，能够被人们理解的可视化知识。数据挖掘 技术正是在这样的需求下快速发展。 数据挖掘是一个从庞杂数据中获取有价值知识的过程。这些数据往往是巨大的、不完 整的、复杂的、模糊的、格式不统一的，人们不易理解的。经过十几年的快速发展，数据 挖掘已经是当今人们热点研究的内容之一。它的主要功能可以分为以下几大类：概念描述、 关联分析、分类与预测、聚类分析、偏差分析等等。其中，分类和预测是数据挖掘中十分 重要的内容之一，广泛应用在电信、银行、超市等金融商业智能活动中。分类的过程是根 据己知样本数据得出的分类函数或者分类模型，来判断其它未知数据的类别。分类模型中 构造分类器或者找到分类函数是重点。数据挖掘中分类的方法有很多，如：决策树方法、 浙江工业大学硕士学位论文 遗传算法、粗糙集理论、k 最邻近方法、聚类算法、人工神经网络算法等等。其中，决 策树因为其特有的优点，成为最常用的分类方法之一。决策树最后形成的分类模型或者分 类器以二叉树或者多叉树的形式表现出来。树的最顶层节点是根节点，表示整个数据集合， 中间的节点是内部节点，表示非类别属性的一个测试，末梢节点是叶子节点，表示一个类 别集合。连接每个节点的分支是代表测试的一个输出。从根节点到叶子节点的一条路劲， 称为一条分类规则。一棵决策树可以有一条或多条分类规则。图1 1 为一棵简单的决策树 示意图。人们可以通过决策树直观、准确得到分类规则，并对未知数据做出客观、准确分 类判断。决策树作为应用最为广泛的分类方法之一，有以下几个优点。 1 、决策树易于理解和实现，人们在学习过程中不需要使用者了解很多的背景知识， 这同时是它的能够直接体现数据的特点，只要通过解释后都有能力去理解决策树所表达的 意义。 2 、可以通过静态测试来对模型进行评测，可以测定模型可信度；如果给定一个观察 的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。 3 、决策树模型与实际问题比较贴近，实用价值比较高，可以解决相当多的实际问题。 当然决策树也存在一些缺点：对于处理大样本数据，生产的决策树比较庞大，花费的 时间较长，可理解性较差等。 目前常用的决策树算法有：i d 3 ，c 4 5 ，c 5 0 ，c h a i d ，c a r t ，q u e s t 等。 图1 - 1 决策树模型示意图 2 浙江工业大学硕士学位论文 1 2 发展历史及趋势 1 2 1 发展历史 决策树算法的发展过程是一个由简单到复杂，有浅入深，单一领域应用到多领域应用 的过程。 1 9 6 6 年，h u n t 等人研发出一个概念学习系统( c o n c e p t i o nl e a r n i n gs y s t e m ) 【1 1 ，该学 习系统首次提出决策树概念学习理念。这为后来研究决策树理论发展提供了基础。 1 9 7 9 年，著名的迭代分类器i d 3 算法【2 】最早由j r q u i n l a n 提出。i d 3 算法首次把信 息论引入决策树理论。建树过程采用分治策略，采用信息增益作为属性的选择标准，选择 决策树的各级节点的属性。 1 9 8 3 年，a p a t t e r s o n 和t n i b l e t t 提出扩展i d 3 算法，类似概念学习系统( a c l s ， a n a l o gc o n c e p tl e a r n i n gs y s t e m ) 算法【3 1 。a c l s 算法主要改进是可以处理取任意整数值 的属性，这扩展了决策树算法的应用范围，比如图像挖掘方面。 1 9 8 4 年，l b r e i m a n 等人提出了分类及回归树( c a r t ：c l a s s i f i c a t i o na n dr e g r e s s i o nt r e e ) 算法【4 1 。与i d 3 的主要区别是：( 1 ) 属性选择的方法不同，这种方法采用g i n i 指数来选择测试属性。( 2 ) 每个非叶子节点的分支只有两条，也叫做二叉树。在该算法 中，引入决策树剪枝的概念，提出误差复杂性剪枝( e c p ：e r r o r - c o m p l e x i t yp r u n i n g ) 的 剪枝方法。这在一定程度上减小了噪音数据的影响，优化了构成的决策树。之后，不断有 的新剪枝算法被提出来，如最小错误率剪枝( m e p ：m i n i m u m e r r o rp r u n i n g ) 方法【5 1 ，减 少错误率剪枝( r e p ：r e d u c e d - e r r o rp r u n i n g ) 方法【6 1 。 1 9 9 2 年，k k i r a 和l r e n d e l l 两位学者提出基于属性间依赖度的r e l i e f 算法【7 1 。 r e l i e f 算法是分类算法中的十分重要的一种算法，是决策树发展过程中的一个重大突 破。在决策树算法中，考虑周边实例，引入局部信息。局部信息的优势在于它能够在其他 属性的背景下评估每一个属性。此前的决策树算法都只能单独的评估一个属性，忽略了属 性间存在的关联。这样，建成的决策树更加健壮、性能更加优秀。 1 9 9 2 年，q u i n l a n 提出了i d 3 的改进算法c 4 5 算法【8 】。c 4 5 在预测变量的缺省值处 理、剪枝技术、派生规则等方面做了一些大改进。c 4 5 还采取了信息增益率来选择分裂 属性，克服了i d 3 在选择分裂属性时选取属性值较多的属性的不足。 1 9 9 6 年，m m e h a t 和r a g r a w a l 等人提出了一种新的监督学习( s l i q ：s u p e r v i s e d l e a r n i n gi nq u s e t ) 分类算法【9 】。这种算法优点是计算速度快、规模可伸缩，可以处理大 数据问题。同年，j s h a f e r 和r a g r a w a l 提出s p r i n t ( s c a l a b l ep a r a l l e l i z a b l ei n d u c t i o no f 浙江工业大学硕士学位论文 d e c i s i o nt r e e s ) 分类算 ：去【1 0 】，这是一种并行归纳可伸缩的决策树算法。1 9 9 8 年，j c e h r k e 和r r a m a k r i s h n a n 提出了雨林( r a i nf o r e s t ) 分类算法【1 1 l 。这一算法在处理大数据规模 时，可以快速建树。 2 0 0 0 年，r r a s t o g i 和k s h i m 提出p u b l i c ( a d e c i s i o nt r e et h a ti n t e g r a t e s b u i l d i n ga n dp r u n i n g ) 分类算法【1 2 1 。该算法在具备c a r t 算法的优点之外，计算速度更 快，效率更佳，得到的决策树性能更优。 2 0 0 2 年，s r u 画e r i 提出了高效c 4 5 算法- - e c 4 5 ( e f f i c i e n tc 4 5 ) 算法【1 3 l 。c 4 5 算法在构建树的过程中采用二分收索方法，并在连续属性局部阀值的寻找方法上也做了一 定的突破改进。相比c 4 5 ，e 4 5 效率更快，计算时内存占用也更多。 2 0 0 5 年，w p e d r y c z 和a z e n o n 提出了一种新的决策树算法，c 一模糊( c f d t ： c f u z z yd e c i s i o nt r e e ) 算法【1 4 1 。与传统的决策树算法不同的是，该算法采用模糊聚类 算法来处理样本的分化问题。主要优点是：一、不用离散化，可以直接处理连续的属性值： 二、综合考虑多个属性。 2 0 0 7 年，c q i 提出一种改进的模糊决策树算法( m f d t ，m o d i f i e df u z z yd e c i s i o nt r e e s ) 1 5 1 。在构建决策树树的过程中，该算法综合了模糊决策树算法与传统决策树算 法的分裂属性的选择方法。如果是多值属性或者连续属性，该算法采用模糊聚类方法。其 他的属性则采用信息熵的计算方法。该算法生成的决策树模型准确率，效率都很高。 国内也有很多学者研究决策树算法，并取得了一定的成果。 1 9 9 8 年，刘小虎博士与李生教授提出一种改进的i d 3 算法一m d 3 算法【1 6 】。该算 法在选择测试属性时，不仅仅考虑该属性带来的信息增益，还要考虑到该属性后选择的属 性带来的信息增益，同时考虑两层节点。这种算法改善了算法的可读性，也使构建的决策 树更加合理。 2 0 0 5 年，黄定轩等学者提出了一类加权连续属性的多变量决策树构造方法【1 7 】。该算 法综合把粗糙集理论与模糊聚类理论应用到了决策树理论当中。同年，韩松来，张辉，周 华平从理论角度分析了i d 3 算法、g i n i 指数算法、五2 统计算法及r e l i i e f 算法这些决策树 常用算法的多值偏向问题【1 8 】。2 0 0 6 年，阳东升博士等人基于组织协作网与决策树描述分 析提出了基于决策个体在任务上的协作关系设计最佳决策树【1 9 1 。2 0 0 7 年，胡学刚，张冬 艳提出基于粗糙集的混合变量决策树构造理论【2 0 l 。 4 浙江工业大学硕士学位论文 1 2 2 发展趋势 综合分析决策树的发展历程及当下的社会需求，决策树算法理论在以下几个方向上有 进一步的发展。 l 、构建的决策树分类精度不断提高 分类精度是决策树的根本，是评估一棵决策树优劣的重要标准之一。算法的改进是以 保持或提高决策树精度为前提。 2 、决策树算法应用范围不断扩大 纵观决策树发展历程，一些新的算法不断提出，使对数据集的约束不断的减少，决策 树可以处理更多的实际问题。 3 、算法的效率不断提高 效率也是考察算法的基本指标之一。随着需要处理问题越发复杂及数据量越来越大， 算法效率问题的重要性愈来愈重要。提高算法效率通常有两种方式，一是针对实际问题， 提出针对性的优化算法；二是软硬件条件的提升，从而提升效率。 4 、与其他算法不断的融合 人们遇到的问题往往是复杂的，只用决策树理论不能解决。所以需要综合其他数据挖 掘算法，取长补短，发挥各个算法的优势，扩大算法的应用范围。现在已经有：粗糙集与 决策树融合，神经网络与决策树融合，关联规则与决策树融合等等。 5 、算法的软件实现 随着计算机技术的发展，算法可视化己经实现。如何让操作界面更加人性化智能化， 最终达到人机一体一直是计算机技术发展的一个方向。 1 3 论文主要内容 本文主要内容是研究数据挖掘中的常用决策树i d 3 分类算法。 文章的主要内容安排如下： 第一章介绍决策树算法研究背景，研究意义，发展历程、现状及发展趋势，给出本 论文的内容写作安排。 第二章首先介绍了数据挖掘算法基础理论知识，重点介绍数据挖掘常用方法。接着 介绍决策树1 1 ) 3 算法相关的知识，阐述了决策树的基本理论，研究的基本内容及常用的 决策树算法介绍，重点分析i d 3 决策树算法。 浙江工业大学硕士学位论文 第三章分析决策树多值偏向缺点，提出改进算法。从理论上分析了i d 3 决策树算法 多值偏向的原因，并针对i d 3 算法的一些不足，提出自己的改进方法，得到新的决策树 算法，实验论证提出的新决策树方法的优越性。 第四章主要介绍数据挖掘在数字医疗中的作用，软件实现决策树算法在数字医疗诊 断中的应用，比较基于i d 3 算法及新算法构建的决策树在该医疗诊断系统的性能。最后得 出结论。 6 浙江工业大学硕士学位论文 第2 章数据挖掘及决策树基本理论 2 1引言 移动互联网时代，几乎每个人、每个企业都被卷入数据的海洋中。在面对大量数据时， 我们必须要用一种新的方法来处理它们。数据挖掘技术正是处理大数据最好的工具之一。 1 9 8 9 年，知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s ek d d ) 首次在十一届联合人工智能学 术会议上提出。1 9 9 5 年，数据挖掘技术在首届的k d d 国际学术年会上被分为工程领域的 数据挖掘与科学领域的知识发现。之后，数据挖掘成为人们研究的热点，广泛应用于当今 商业、工程及科学研究等领域。分类和预测是数据挖掘的主要功能之一。作为最常用的数 据挖掘算法之一，决策树算法主要应用在数据的分类和预测。据统计，近几年决策树算法 应用比例占所有数据挖掘方法高达1 4 一1 9 2 4 - 2 5 1 ，并且应用范围正逐年扩大，比例也随着 增高。 本章主要介绍数据挖掘及决策树分类算法一些基本理论，着重介绍决策树算法研究的 基本内容及几种常用的决策树算法。 2 2 数据挖掘基本理论 2 2 1 数据挖掘的定义 从技术角度上定义数据挖掘为：从大量的、不完整的、有噪音的、模糊的、随机的数 据中，提取隐含在其中的、事先人们不知道的、但又是潜在有用的信息和知识的过程【2 l 】。 数据必须是真实的、大量的。数据又往往是含噪声的，来源多样的，格式不统一的，需要 被处理转化的。数据挖掘的主题是明确的，发现的知识是用户感兴趣的、可理解的。 从商业角度定义数据挖掘为：数据挖掘是一种新的商务智能技术。其主要特点是面向 特定商业主题，对特定数据库中的数据进行抽取、转换、分析，构建面向特定业务的数据 仓库，辅助决策层的商业决策。 数据挖掘被很多人称为数据库中的知识发现。数据挖掘技术是基于多门学科综合发 展起来的。数据库技术、人工智能、数据统计是数据挖掘发展起来的三大基础技术。图2 一l 简要描述了数据挖掘技术的学科基础【2 2 】。 7 浙江工业大学硕士学位论文 图2 - 1数据挖掘技术的基础 2 2 2 数据挖掘的功能 数据挖掘的最终目的是在大量数据中发现有利用价值的信息。具体功能有以下几个方 面【2 l 】： 1 、概念描述 概念描述( c o n c e p td e s c r i p t i o n ) ，就是对某类对象的本质内涵进行描述，对这类对象 的主要特征进行概括。具体的描述可分为区别性( d i s c r i m i n a t i o n ) 描述和特征性 ( c h a r a c t e r i z a t i o n ) 描述。前者用于描述不同类对象间的特征区别，后者用于描述某类对象 的共同特征。 2 、关联分析 若两个或多个变量之间存在某种规律性关系，就称为关联。数据关联是一类十分重要 的可被发现的知识。关联分析是从大量数据对象中发现数据对象之间隐含的、有价值的关 联。用关联函数描述数据对象之间的关联程度，这种关联程度是不确定的，因此关联分析 生成的规则有可信度，有时也称为不确定度。关联可分为简单关联、时序关联、因果关联 竺 寸0 3 、分类与预测 ( 1 ) 分类( c l a s s i f i c a t i o n ) 是数据挖掘中一项十分重要的任务。分类的过程是指通过 一个分类函数，或者分类模型，把数据库中的对象映射到给定类别中的一个。分类的过程 也是构造分类器的过程。找到分类函数或分类模型是构造分类器是重点。本文研究的i d 3 决策树就是属于分类模型中的一种。 浙江工业大学硕士学位论文 ( 2 ) 预测( p r e d i c t i o n ) 是利用历史数据建立模型，再运用最新数据作为输入值，获 得未来变化的趋势或者评估特定样本可能具有的属性值或者取值范围。 4 、聚类分析 聚类( c l u s t e r i n g ) 是根据数据对象的不同特征，将其划分为不同的对象类，这里类通 常称为簇。其目的是使得属于同一类别的对象之间的距离尽可能小，而属不同类别对象之 间的距离尽可能大。 与分类不同，聚类过程是无监督学习过程。无监督学习是指不需要预先定义的类或带 类标记的训练实例，而是由聚类学习算法自动确定实例标记。而分类学习的实例或数据对 象要有类别标记。聚类是观察式学习，而不是示例式的学习。 5 、偏差分析 偏差分析( d e v i a t i o na n a l y s i s ) 又称为比较分析，是对差异和极端特例的描述，揭示事 物偏离常规的异常现象。其基本思想是探测观测结果与历史记录或标准之间有意义的差 别。偏差包括不满足规则的特例、分类中的反常实例、模式的例外、观测结果与模型预测 的偏差及量值随时间的变化等。 2 2 3 数据挖掘常用的方法 数据挖掘常用方法有以下几种【2 3 】： 1 、聚类分析 聚类分析( c l u s t e r i n ga n a l y s i s ) 一直是数据挖掘领域比较活跃的研究领域。聚类技术 的发展主要基于传统的统计学、机器学习和生物学等学科。8 0 年代初，m c h a l s k i 提出了概 念聚类技术要点：在划分对象时不仅考虑对象之间的距离，还要求划分出的类具有某种内 涵描述。这避免了传统技术的某些片面性。数据聚类生成的组称为簇，簇是数据对象的集 合。聚类分析的过程就是同一个簇内的任意两个对象具有较高的相似性，不同簇的任意两 个对象的之间具有较高的相异性。 用于数据挖掘的聚类分析有划分的方法、层次的方法、基于密度的方法、局域网格的 方法和基于模型的方法等。 2 、决策树 决策树( d e c i s i o nt r e e ) 是数据挖掘最重要是最常用的方法之一，主要应用于数据挖 掘中的分类和预测。决策树是知识的一种呈现方式。决策树中从项点到每个结点的路径都 是一条分类规则。决策树算法最先基于信息论发展起来，经过几十年发展，目前常用的算 法有：i d 3 ，c 4 5 ，c h a i d ，c a r t 等算法。其中i d 3 ，c 4 5 是比较常用的算法。 9 浙江工业大学硕士学位论文 3 、人工神经网络 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，简写为a n n s ) 也简称为神经网络( n n s ) 或称作连接模型( c o n n e c t i o nm o d e l ) ，通过模仿人的神经网络结构和某些工作机制而建立 的一种数学计算模型。神经网络模仿人的神经结构，将大量简单的单个神经元连接，构成 复杂的网络结构。通过自主学习，网络间的各个神经元的连接强度增强，进而能够进行复 杂、智能运算。神经网络有并行、容错、可以硬件实现及自我学习、自我组织等特殊优点， 能够解决许多其他方法不能够解决的复杂问题，因此得到较普遍的应用。 4 、关联规则挖掘 关联规则挖掘是数据挖掘最活跃的研究方法之一。其基本思路：一是找到所有支持度 大于最小支持度的频繁项集，即频集；二是使用第一步找到的频集产生期望的规则。其核 心方法是基于频集理论的递推方法。 关联规则由a g r a w a l 在1 9 9 3 年提出，最初动机是针对“购物篮”进行分析，发现顾客 购买的不同商品之间的联系，由这些联系找出顾客购买行为模式。目前关联规则广泛应用 于电信、金融、商业智能等方面。 5 、粗糙集 粗糙集( r o u g hs e t ) 理论是一种分析不完整和不确定数据集的数学理论方法，能有效 地分析不精确，不一致( i n c o n s i s t e n t ) 、不完整( i n c o m p l e t e ) 等各种不完备的信息，对数 据进行分析和推理，提取其隐含的有价值的知识，揭示潜在的规律。 粗糙集是一种处理不确定性知识的方法。粗糙集理论的主要思想是利用已知的知识 库，来( 近似) 刻画不确定的知识。粗糙集理论建立在分类机制的基础上，将分类理解为 在特定空间上的等价关系，而等价关系构成了对该空间的划分，引入上近似( u p p e r a p p r o x i m a t i o n ) 和下近似( 1 0 w e ra p p r o x i m a t i o n ) 等概念来刻画知识的不确定性和模糊性。 此外，常用的数据挖掘方法还有统计分析、遗传算法、w e b 页面挖掘等。 2 2 4 数据挖掘的步骤 一个完整的数据挖掘过程一般包括以下几个步骤【4 】：确定业务对象、数据准备、数据 挖掘、结果分析与知识同化。具体步骤如图2 2 。 1 0 浙江工业大学硕士学位论文 图2 - 2 数据挖掘一个循环过程 1 、确定业务对象 首先要非常清晰地定义研究的业务对象，认清数据挖掘的主题。数据挖掘的最终结果 不可预测，但要探索的问题应是有预见的。理解主题和实际业务是数据挖掘过程最基本要 求。 2 、数据准备 数据准备充分是保证数据挖掘得以成功的重要保证。在整个数据挖掘任务中