（控制科学与工程专业论文）基于关联度函数的决策树分类算法研究.pdf

国防科学技术大学研究生院学位论文 摘要 数据挖掘，又称为数据库中的知识发现，是一个可以从大量数据中自动提取有用模式 的过程。分类是数据挖掘的重要内容之一，而在分类算法中以决策树算法应用最为广泛。 现存的决策树算法普遍地存在着一个问题属性选择时的多值偏向。多值偏向可能 导致从数据集中归纳出错误的知识，使决策树的性能下降。 本论文针对上述问题，主要作了如下工作：从实验和理论两个方面分析了决策树算 法的多值偏向问题；提出了一种避免了多值偏向问题的决策树算法a f 算法；实现 了a f 算法，并把它应用到医学领域中的病人分类问题中。 本文主要有两个创新点：第一，提出了一种从理论上分析多值偏向问题的方法。实验 方法是分析决策树算法中的多值偏向问题的传统方法，其缺点是需要具备该数据领域的专 家知识。本文提出的分析多值偏向问题的理论方法，使得在缺乏专家知识的情况下，仍然 能够对决策树算法的多值偏向问题作出判断。第二，提出了种新的基于关联度函数的决 策树算法a f 算法。在深入分析多值偏向问题的基础上，本文提出了一种克服了多值偏 向问题的决策树算法a f 算法。通过评估发现，a f 算法在总体性能上要优于目前被广 泛采用的i d 3 算法。 关键词：数据挖掘；分类；预测；决策树：多值偏向；i d 3 ：a f 第f 页 国防科学技术大学研究生院学位论文 a b s t r a c t d a t am i n i n g ，w h i c hi sa l s oc a l l e dk n o w l e d g ed i s c o v e r yi nd a t a b a s e ，i sap m c e s sw h i c hi s u s e dt oa u t o m a t i c a l l yr e f i n eu s e f u lp a t t e m sf r o md a t as e t c l a s s i f i c a t i o na 1 1 dp r e d i c t i o ni so n eo f m em a i ns u m e c t so fd a 瞳am i n j n g ，w 1 1 i l ed e c i s i o nt r e ea l g o r i t h r ni st h em o s tp o p u l a rc l a s s i 6 c a t i o n a l g o r i t h ma m o n ga l lc l a s s i f i c a t i o n 甜g o r i t h m s b u tm o s to ft l l ee x i s t e n td e c i s i o nt r e e “g o r i t h m ss u 行hap r o b l e m ，n a m e l ym u l t i v a l u eb i o s ， i nm ep m c e s so fa t t r i b u t es e l e c t i o n m u l t i v a l u eb i o sm a yr e s u l t i ni n d u c i n gw r o n gk n o w l e d g e f r o md a t as e t ，a n dc o n s e q u e n n yr e s u hi nt h ed e c l i n eo f 也ep e r f b n n a n c eo f d e c i s i o nt r e e a c c o r d i n gt ot l l ep r o b l e ma b o v e ，t 1 1 i sp a p e rm a i n l yi l l u s t r a t e st h r e ep r o b l e m sf i r s t ，t h i s p 印e ra i l a l y s e st h em u l t i v a l u eb i o sp r o b l e mo fd e c i s i o nt r e ea l g o r i t l l me x p e r i m e n t a l l ya n d 血e o r e t i c a l l ys e c o n d ，t h i sp a p e rp r o p o s e san e wd e c i s i o nt r e ea l g o r i m m ，a fa l g o r i m m ，w h i c h a v o i d sm u l t i v a l u eb i o s t h i r d ，w ei m p l e m e n tt h ea fa l g o r i t m ，a i l du s ei tt oc l a s s i f yp a t i e n t si n t 1 1 ef i e l do fi a t r 0 1 0 9 y w h a ti sn e wi nm i sp 印e r ? f i r s t ，t 1 1 i sp a p e rp r o p o s e sat h e o r e t i c a lm e t h o df o ra n a i y s i n gt h e m u l t i v a l eb i o sp r o b l e mo fd e c i s i o nt r e ea l g o r i t l l m e x p e 血n e n ti st h et r a d i t i o n a lm e t h o df o r a n a l y s i n gm u l t i v a l u eb i o so fd i s i o nt r e ea i g o r i m m ，b u ti th a saf a u l tt h a tw em u s th a v e 出e e x p e n i s eo ft 1 1 es p e c i 矗cf i e l d ，t h i sp a p e rp r o p o s e sat 1 1 e o r e t i c a lm e t l l o d ，晰t hw h i c hw ec a i l a 1 1 a l y s et h em u l t i v a l u eb i o sp r o b l e mw i t h o u tt 1 1 ee x p e r t i s eo fs p e c i f i cf i e l d s e c o n d ，t h i sp a p e r p r o p o s e san e wd e c i s i o nt r e ea l g o r i m m ，a fa l g o r i t l l r i l ，w h i c hi sb a s e do na s s o c i a t i o nf u n c t i o n o nt h eb a s i so fa n a l y s i n gt h e m u l t i v a l u eb i o s ，t h i sp a p e rp r o p o s e san e wd e c i s i o nt r e ea l g o r i t ， a fa l g o r i t 1 1 1 1 ，w h i c ha v o i d st h em u l t i v a l u eb i o sp r o b l e m t h r o u 曲e v a l u a t i o n ，w e 矗n da f a l g o t h mi sb e t t e ri nm a n ya s p e c t st 1 1 a ni d 3a l g o r i t h mw h i c hi sw i d e l yu s e di nm a n yf l e l d s k e y w o r d s ：d a t am i n i n g ；c l a s s i f i c a t i o n ；p r e d i c t i o n ；d e c i s i o t r e e ；m u l t i v a l u eb i o s ；i d 3 ；a f 第页 独创性声明 y8 8 5 8 2 6 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：基士差送廑量数盟达薤挝佥娄簦洼婴蕉 学位论文作者签名：鲤毖老 日 期：圳夕年，月夕日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定，本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权) 学位论文题目： 基士差送廑函熬盟迭筮挝佥差差洼堑塞 学位论文作者签名：幺毖蒸 日 期：加歹年f 月7 日 作者指导老师签名： 酗霉辜日期：知。譬年i f 月c 日 i 国防科学技术大学研究生院学位论文 第一章绪论 鄂1 决策树算法研究的意义 计算机与信息技术经历了半个世纪的发展，给人类社会带来了巨大的变化与影响。在 支配人类社会发展的三大要素( 能源、材料和信息) 中，信息愈来愈显示出其重要性和支 配力，它将人类社会由工业化时代推向信息化时代。随着人类活动范围的扩展，生活节奏 的加快，以及技术的进步，人们能以更快速更容易更廉价的方式获取和存储数据，这就使 得数据及其信息量以指数方式增长。早在二十世纪八十年代，据粗略估算，全球信息量每 隔_ _ 二十个月就增加一倍。而进入九十年代，全世界所拥有的数据库及其所存储的数据规模 增长更快。一个巾等规模的企业每天要产生1 0 0 船以上来自生产经营等多方面的商业数据。 美国政府部门的一个典型大数据库每天要接收约5 t b 的数据量，在1 5 秒到1 分钟时间里，要 维持的数据量达到3 0 0 t b ，存档数据达1 5 一j 0 0 p b 。在科研方面，以美国宇航局的数据库为 例，每天从卫星下载的数据量就达3 4 t b 之多，而为了研究的需要，这些数据要保存七年 之久。九十年代互联嘲的出现与发展，阻及随之而来的企业内部网和企业外部网以及虚拟 私有网的产生和应用，使整个世界互联形成一个小小的地球村，人们可以跨越时空在网上 交换信息和协同工作。这样，展现在人们面前的已不是局限于本部门，本单位和本行业的 庞大数据库，而是浩瀚无垠的信息海洋。据估计，1 9 9 3 年全球数据存贮容量约为二千t b 到2 0 年增加到三百万t b ，面对这极度膨胀的数据量和信息量，人们受到“信息爆炸”、“混 沌信息空间”和“数据过剩”的巨大压力。 f i g u r e l 1 人类活动所涉及数据与知识之间的关系描述 然而，人类的各项活动都是基于人类的知识和智慧的，即对外部世界的观察和了解， 而数据仅仅是人们用各种工具和手段观察外部世界所得到的原始材料，它本身没有任何意 义。从数据到知识再到智慧，需要经过分析、加工处理和精炼。如f i g u r e ll 所示，数据 是原材料，它只是描述发生_ r 什么事情，井不能构成次策或行动的可靠基础。通过对数掘 进行分析找出其中的关系，赋予数据某种意义，这就形成所谓信息。信息虽给出了数士 j 中 一些有一定意义的东西，但它往往和人们需要完成的任务没有直接联系，也还不能作为判 一些有定意义的东西，但它往往和人们需要完成的任务设有直接联系，也还不能作为判 第l 页 国防科学技术大学研究生院学位论文 断、决策和行动的依据。对信息进行再加工，即进行更深入的归纳分析，方能获得更有用 的信息，即知识。而所谓知识，可定义为“信息块中的一组逻辑关系，其关系是通过上下 文或过程的贴近度发现的”。在大量知识积累的基础上，总结出原理和法则，就形成所谓 智慧。事实上，人类社会的文明发展史，就是在各种活动中知识的创造、交流、再创造， 不断积累的螺旋式上升的历史。 计算机与信息技术的发展，加速了人类知识创造与知识交流的这种进程，据德国世 界报的资料分析，如果说1 9 世纪时科学定律( 包括新的化学分子式，新的物理关系和新 的医学认识) 的认识数量一百年增长一倍，到本世纪6 0 年代中期以后，每五年就增长倍。 这其中知识起着关键的作用。当数据量极度增长时，如果没有有效的方法来帮助从中提取 有用的信息和知识，那么面对浩瀚的数据海洋，人类显然就会感到像大海捞针一样束手无 策。据估计，目前一个大型企业数据库中的数据，约只有百分之七得到了很好应用。因此 目前人类陷入了一个尴尬的境地，即“丰富的数据”而“贫乏的知识”。于是在这个数据 和信息大爆炸的时代中，数据挖掘顺应时代的需求而诞生。 分类和预测是数据挖掘的重要内容之一，并且已经广泛地应用于许多领域，如医疗诊 断、天气预报、顾客分类、身份识别等。在数据挖掘中可用于分类的算法很多，如决策树、 贝叶斯定理、贝叶斯网络、神经网络等。在这些分类算法中，以决策树算法的应用最为广 泛，主要有以下原因：决策树算法的复杂度较小，速度快；决策树算法的抗噪声能力 强；决策树算法的可伸缩性强，既可用于小数据集，也可用于海量数据集。正因为如此， 决策树算法也就成为数据挖掘研究中最活跃的领域之一。 f i g u r e l 2 给出了决策树的一般形式，从形式上看决策树是一个类似于流程图的有向 图，但它与流程图有本质的区别。流程图表达的是一个过程，而决策树表达的则是知识。 如f i g u r e l 2 所示，决策树由节点和分支组成，其中节点又分为内节点和叶节点。每一个 内节点，如图中的n l 、n 2 1 、n 2 2 ，代表一个属性；每一个叶节点，如图中的l 1 、l 2 、l 3 、 l 4 ，代表一个类别；每一个分支，如图中的r 1 、r 2 、r 3 、“、r 5 、r 6 ，代表属性上的一个 测试。 f i g u r e l2 决策树的一般形式 使用决策树表达知识直观而简洁。首先，从决策树中可以直接观察出属性之间的相对 重要性。从决策树的的根节点开始，沿着每一条路径向下，属性对于分类的重要性逐渐下 国防科学技术大学研究生院学位论文 降。其次，从根节点到叶节点的每一条路径代表一条知识( 规则) ，因此从叶节点的总数 可以很容易地统计出知识( 规则) 的总量。最后，决策树表达知识的形式简洁，每一个节 点可以在多条知识( 规则) 中出现，避免了表达上的重复。 1 2 决策树算法研究的历史与现状 1 2 1 决策树算法研究的发展过程 从第一个具有实用价值的决策树算法的提出到今天决策树算法被广泛应用于各个领 域，决策树算法的发展经历了一个由简单到复杂、由浅显到深入的过程。以下是决策树算 法发展过程中的一些重要进展： 1 9 7 9 年，j r q u i n l a n 提出了i d 3 算法【l j ，该算法是第一个具有实用价值并被广泛采用 的决策树算法。i d 3 算法采用信息增益作为属性选择的标准，它选择信息增益最大的属性 并把它赋给当前的内节点。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 算法 2 】oa c l s 算法的主 要改进是允许属性取任意的整数值，而i d 3 算法只允许属性取特定数据集中的值，a c l s 算 法的这种改进极大地扩展了决策树算法的应用范围，使决策树可以处理一些比较复杂的任 务，比如图像识别等。 1 9 8 4 年，i k o n o n e n k o 、i b r a t k o 和e r o s k a r 把i d 3 算法扩展为a s s i s t a n t 算法【3 l 。 a s s i t a n t 算法进一步减少了对属性取值的约束，在a s s i s t a n t 中属性可以取任意实数值； 并且a s s i s t a n t 算法允许类别的取值之间有交集，而在i d 3 算法和a c l s 算法中这是不允许 的。 1 9 8 4 年，a h a r t 提出了c h i s q u a r e 统计算法【4 j ，该算法采用一个统计量作为属性选取 标准，该统计量用于度量属性与类别的关联程度，如果关联程度越大则此统计量的取值越 大。c h i s q u a r e 统计算法选择使该统计量最大的属性并把它赋给当前的内节点。 1 9 8 4 年，l b r e i f 【l a n 、j f r e i d n l a n 、r o l s h e n 和c s t o n e 提出了决策树剪枝的概念，并 提出了叫做e r r o r c o m p l e x i t yp r u n i n g 的剪枝方法【2 l l 。用于生成决策树的训练集一般都存 在噪声数据，而噪声数据会导致决策树过度复杂。过度复杂的决策树一般存在对于训练集 的过度适应，这种过度适应会导致决策树分类正确率的明显下降；而且过度复杂的决策树 的可理解性也很差，而决策树作为一种知识的表达方式，应该具有较高的可理解性。因此 决策树剪枝方法的出现极大地改善了决策树的性能。 1 9 8 6 年，t n i b l e t t 提出了叫做m i n i m u m e r r o rp r u n i n g 的剪枝方法【5 】；1 9 8 7 年， jm i n g e r s 提出了叫做c r i t i c a lv a l u ep r u n i n g 的剪枝方法【6 】；1 9 8 7 年，j r q u i n l a n 提出 了叫做r e d u c e de r r o rp r u n i n g 的剪枝方法【7 j 0 1 9 9 2 年，k k i r a 和l r e n d e l l 提出了r e l i e f 算法【2 3 】。r e l i e f 算法设计属性选取标准的 第3 页 国防科学技术大学研究生院学位论文 基本准则是：对于实例空间( 以数据的属性作为坐标所形成的空间成为实例空间，每一个 数据就称为实例空间中的一个实例) 中不同类的多个邻居实例而言，一个理想的属性应该 取不同的值；对于实例空间中同类的多个邻居实例而言，一个理想的属性应该取相同的值。 r e l i b f 算法的提出是决策树算法发展史中的一座里程碑，因为它通过考虑“邻居”实例而 把数据集中的局部信息引入到决策树算法中，局部信息的优势在于它能够在其它属性的背 景下评估每一个属性；而此前的决策树算法都只能单独地评估每一个属性，忽略了属性间 可能存在的关联。 1 9 9 2 年，q u i n l a n 把i d 3 算法改进为c 4 5 算法f 8 ，使它可以适用于增量式学习任务。i d 3 算法不能用于增量式学习，数据集中每增加一个新的数据，都要抛弃原来的决策树，重新 生成新的决策树。而c 4 5 算法则可用于增量式学习，随着数据量的增加动态地调整决策树。 增量式学习对于在线任务非常有意义。 1 9 9 4 年，i k o n o n e n k o 把r e l i e f 算法扩展为r e l i e f f 算法f 9 】，r e l e f f 算法克服了r e l i e f 只能处理两类问题的缺点，可以处理多类问题。 1 9 9 7 年，i ，k o n o n e n k o 和e i m e c 把r e l i e f 进一步扩展为r r e l i e f f 算法【，r r e l i e f f 不 但可以处理多类问题，而且可以处理连续类问题，即回归问题。 1 9 9 7 年，s j h o n g 提出了c m 算法【2 5 j 。c m 算法继承了r e l i e f 算法的核心观念，也以数据 集中的局部信息作为属性选取的标准。c m 算法设计属性选取标准的基本准则是：对于两个 不同类的实例，仅仅取值不同的属性对它们有区分作用。 1 9 9 7 年，g e o f f r e yi w e b b 对生成的决策树进行了嫁接( g r a f t i n g ) 处理j 。所谓嫁 接是剪枝的逆过程，是指在决策树构建完成之后，按照一定的策略适当的添加一些节点， 来提高决策树的分类正确率。 近几年，对于模糊决策树的研究得到了蓬勃的发展。模糊决策树的发展主要是为了克 服传统决策树的脆弱性问题，进一步的研究可以参考相关文献f 1 2 】【1 3 】。 1 2 2 决策树算法研究的发展趋势 通过仔细考察上述决策树算法研究的发展过程，可以发现决策树算法研究的发展呈现 出如下趋势： 1 决策树算法对属性的考察逐渐深入细致。在1 9 8 4 年a s s i s t a n t 算法出现以前， 决策树算法所采用的属性选取标准都是属性间相互独立的，即属性选取标准独立地评估每 一个属性。a s s f s t a n t 算法以及后来出现的c m 算法，它们的属性选取标准都是属性问 相互关联的，即属性选取标准是在其它属性的背景下评估每一个属性。属性选取标准的这 种改进有重要的意义：首先，属性间相互关联的属性选取标准有助于发现属性间潜在的依 赖关系。有许多问题，单一属性不能传递类的信息，需要把几个属性结合起来才能传递类 的信息。比如“异或运算”，当两个属性取值相同时，类的取值为】，当两个属性的取值不 同时，类的耿值为0 。此时，两个属性相互依赖共同决定类的状况。类似于这种属性问的 第4 页 国防科学技术大学研究生院学位论文 依赖关系，属性间相互独立的属性选取标准是无法发现的；其次，属性间相互关联的属性 选取标准可以避免多值偏向问题。大部分属性间相互独立的属性选取标准都存在多值偏向 问题，而属性问相互关联的属性选取标准则避免了此问题。本文将在第四章对决策树算法 的多值偏向问题进行详细的分析。 2 决策树算法对数据集的约束逐渐减少。首先，对数据集中属性的取值约束逐渐减 少。比如，在i d 3 算法中属性只能在有限集中取值，到a c l s 算法时属性可以在整数集中 取值，到a s s i s 吖心t 算法时属性可以在实数集中取值。对属性取值的约束减少就扩大了 决策树算法的应用范围；其次，数据集中的类别数目逐渐增加。比如，砌! l i e f 算法只能 处理两类问题，其扩展算法! l i e f f 算法就可以处理多类问题，到i 氓l i e f f 算法时就已 经可以处理连续类问题( 即回归问题) 了。类别数目的增加也同样扩大了决策树算法的应 用范围。 3 决策树算法的分类精度逐渐提高。1 9 8 4 年出现了决策树剪枝技术，决策树剪枝减 小了数据噪声对决策树的影响，极大地提高了决策树地分类精度；同时，嫁接技术正是基 于提高决策树的分类精度而提出的。 1 3 论文的主要内容及组织结构 论文的第一章介绍了决策树算法研究的意义以及研究的历史和现状；第二章和第三章 介绍了决策树算法的理论基础；第四章分析了现存的决策树算法普遍存在的多值偏向问 题；第五章和第六章提出了一种克服了多值偏向问题的决策树算法并把实现后的算法应用 到病人分类中；第七章对本文进行了总结并对未来的研究方向作了展望。 论文的具体组织结构如下： 第一章，绪论。阐述了决策树算法研究的意义、历史与现状。 第二章，数据挖掘理论。阐述了数据挖掘的定义、功能和数据挖掘算法的评估标准。 第三章，数据挖掘中的决策树算法。阐述了决策树算法的基本概念、要研究的问题以 及各种属眭选择策略。 第四章，决策树算法中的多值偏向问题分析。从实验和理论两个方面分析了决策树算 法的多值偏向问题。 第五章，基于关联度函数的决策树算法。提出了一种新的基于关联度函数的决策树算 法，分析了其多值偏向问题，并对算法的性能作出了评估。 第六章，关联度函数算法的应用。详细阐述了关联度函数算法实现中的数据结构和算 法流程，以及算法在病人分类中的应用。 第七章，总结与展望。对本文的内容进行了总结，并对今后的工作进行了展望。 第5 页 国防科学技术大学研究生院学位论文 第二章数据挖掘理论 2 1 引言 随着计算机硬件和软件的飞速发展，尤其是数据库技术与应用的日益普及，人们面临 着快速扩张的数据海洋，如何有效利用这一丰富数据海洋的宝藏为人类服务，业已成为广 大信息科技工作者所重点关注的焦点之一。与日趋成熟的数据管理技术和数据管理软件相 比，数据分析工具的功能，却无法有效地为决策者提供其决策所需的相关知识，从而形成 了一种独特的现象“丰富的数据，贫乏的知识”。为有效解决这一问题，自二十世纪8 0 年 代开始，数据挖掘技术逐步发展起来。 本章的主要目的是介绍数据挖掘的基本理论，主要包括数据挖掘的定义、功能、以及 数据挖掘结果的评估方法。 2 2 节给出了数据挖掘的定义；2 3 节介绍了数据挖掘的功能；2 4 节介绍了数据挖掘结 果的评估方法。 2 2 1 数据挖掘的含义 2 2 数据挖掘的定义 数据挖掘( d a t am i n i n g ，简称d m ) 1 7 ，简单地讲就是从大量数据中挖掘或抽取出知 识，数据挖掘的定义描述有若干版本，以下给出一个被普遍采用的定义描述： 数据挖掘，又称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yf 沁md a _ c a b a s e ，简称 k d d ) ，是一个从大量数据中抽取出未知的、有价值的模式或规律的复杂过程。数据挖掘 的过程描述如f i g u r e 2 1 所示。 如f i 趴r e 2 1 所示，整个知识挖掘( k d d ) 过程是由若干挖掘步骤组成，而数据挖掘仅 是其中的一个主要步骤。整个知识挖掘的主要步骤有： 数据清洗( d a t ac l e a n i n g ) ，其作用就是清除数据噪声和与挖掘主题明显无关的数 据； 数据集成( d a t a i n e t e g r a t i o n ) ，其作用就是将来自多数据源中的相关数据组合到一 起； 数据转换( d a t at r a i l s f o n n a l i o n ) ，其作用就是将数据转换为易于进行数据挖掘的 数据存储形式： 数据挖掘( d a t am i n i n g ) 它是知识挖掘的一个基本步骤，其作用就是利用智能方 法挖掘数据模式或规律； 第6 页 国防科学技术大学研究生院学位论文 模式评估( p a t t e me v a l u a t j o n ) ，其作用就是根据一定评估标准从挖掘结果筛选出 有意义的模式： 知识表示( 鼬l o w l e d b ep r e s e n t a t i o n ) ，其作用就是利用可视化技术和知识表达技术， 向用户展示所挖掘出的相关知识。 f i 舻r e 2 1 知识挖掘全过程示意描述 尽管数据挖掘仅仅是整个知识挖掘过程中的一个重要步骤，但由于目前工业界、媒体、 数据库研究领域中，“数据挖掘”一词已被广泛使用并被普遍接受，因此本文也广义地使 用“数据挖掘”一词来表示整个知识挖掘过程，即数据挖掘就是一个从数据库、数据仓库 或其它信息资源库的大量数据中发掘出有趣的知识。 2 ，2 2 数据挖掘示例 为了能够更为清楚地勾画出数据挖掘的基本轮廓，以下我们给出一个数据挖掘示例， 以帮助大家进一步地了解数据挖掘的核心工作。 如t a b l e 2 ，i 所示。它是一个关于劳动合同谈判的数据集合。表中的第一列是j 6 个属性， 来描述劳工的基本情况，其中最后一个属性( a c c e p k 山m t yo f c o n t r a c t ) 为劳工合同谈判结果， 其值域为f 接受、拒绝 。表中的第二列分别为1 6 个属性的取值类型。从第三列开始，表中 的每一列代表一个劳工情况。该数据挖掘任务就是根据所给的5 0 0 个劳工对谈判结果的接 受情况，挖掘出识别劳工接受谈判结果的分类知识，以便以后只需根据其它劳工情况就可 判断出某个劳工是否会接受谈判结果。 t a b l e 2 1 所示的是一个来源于实际问题的数据集，其中的“? ”表示该项数据空缺。这 里采用决策树算法进幸亍数据挖掘，从t a b l e 2 1 所示的数据中抽取出识别劳工接受谈判结果的 分类知识。所挖掘出的分类知识用决策树表示，如f i g u r e 2 - 2 所示。我们把这种决策树形式 的分类知识转换为规则的形式，其中决策树中的每条从根节点到叶节点的路径对应一条规 第7 页 国防科学技术大学研究生院学位论文 则，则部分规则表达如下： i fw a g ei n c r e a s ef i r s ty e a r 1 0 t h e na c c e 口t a b i l i t yo f c o n t r a c t = “接受”： t a b l e 2 ，1 劳工及谈判结果接受情况数据表描述 从上述的示例中，可以看出，k d d 就是利用机器学习的方法从数据库中提取有价值的 知识的过程，它是数据库技术和机器学习两个学科的交叉领域。数据库技术侧重于对数据 存储处理的高效率方法的研究，而机器学习则侧重于设计新的方法从数据中提取知识。 k d d 利用数据库技术对数据进行前端处理，而利用机器学习方法从处理后的数据中提取有 用的知识。 f i g u r e 2 _ 2 劳工合同谈判结果识别决策树 第8 页 国防科学技术大学研究生院学位论文 目前出现了很多基于数据仓库的o l a p ( o n l i n e a n a l y t i c a lp r o c e s s i n g ) 的产品，它可 以对数据进行多维分析，并进行数据的d r i l ld o “w 和r 。i iu p 等操作。那么同样作为数据分析 方法的数据挖掘与0 l a p 有何区别呢? o l a p 是由用户驱动的，般是由分析人员预先设定 一些假设，然后使用0 l a p 工具去帮助验证这些假设，它提供了可使分析人员很方便地进 行数据分析的手段：而数据挖掘则是通过对数据的分析来自动产生一些假设，并自动检验 这些假设的可靠性，最终获得知识，入们可以在这些知识的基础上更有效地进行决策。 这里我们通过一个例子说明两者的区别，在进行银行信用风险调查时，如果使用 o l a p ，分析人员必须首先设定一些假设条件，如高负债低收入的人有信用风险，分析人 员可以利用o l a p ，通过对有关数据进行分析来验证或推翻这个假设；如果使用数据挖掘， 则数据挖掘算法会自动找出对银行信用风险有影响的因素，而且还可能发现些按照常规 思维认为不可能的影响因素，如年龄、地域或者某些因素的组合。 2 3 数据挖掘的功能 利用数据挖掘技术可以帮助获得决策所需的多种知识。在许多情况下，用户并不知道 数据中存在着哪些有价值的知识，因此对于一个数据挖掘系统而言，它应该能够同时搜索 发现多种模式的知识，以满足用户的期望和实际需要。此外数据挖掘系统还应能够挖掘出 多种层次( 抽象水平) 的模式知识。数据挖掘系统还应容许用户指导挖掘搜索有价值的模 式知识。 数据挖掘的功能以及所能够挖掘出的知识类型描述如下。 2 3 1 概念，类描述 数据可以与类或者概念相关联。例如，假定存在一个叫做a l l e l e c t r o n i c s 的电子公司， 销售的商晶类包括计算机和打印机，顾客概念包括b i g s p e n d e r s 和b u d g e t s p e n d e 用汇总的、 简洁的、精确的方式描述每个类和概念可能是有用的。这种类或概念的描述称为类，概念描 述。这种描述可以通过下述方法的到：数据特征化，一般地汇总所研究类( 通常称为目 标类) 的数据；数据区分，将目标类与一个或者多个比较类进行比较。 数据特征化( d a t ac h a r a c t e r i z a t i o n ) 是目标类数据的一般特征或特征的汇总。通常，用户 指定类的数据通过数据库查询收集。例如，为研究上一年销售增加1 0 的软件产品的特征， 可以执行一个s q l 查询收集关于这些产品的数据。数据特征的输出可以用多种形式提供， 包括饼图、条图、曲线、多维数据立方体、多维表和规则形式。 例如，数据挖掘系统应该畿够产生一年之内在a l l e l e c t r o n i c s 花费1 o 元以上的顾客特 征汇总描述。得到的结果可能是顾客的一股轮廓，如年龄在4 0 5 0 、有工作、有很好的信 用等级。 粥9 页 国防科学技术大学研究生院学位论文 数据区分( d a t ad i s c r i m i n a i i o n ) 是将目标类对象的一般特征与对比类对象的一般特征比 较。目标类和对比类由用户指定，而对应的数据通过数据库查询检索。例如你可能将上一 年销售增加1 0 的软件产品与同一时期销售下降3 0 的那些产品进彳亍比较。区分描述如何 输出? 输出的形式类似于特征描述，但区分描述应包括比较度量，帮助区分目标类和对比 类。用规则表示的区分描述称为区分规则。 例如，数据挖掘系统应该能够比较两组a 1 l e l e c t r o n i c s 顾客，如定期购买计算机产品的 顾客和偶尔购买这种产品的顾客。得到的结果可能是一般的比较轮廓，如经常购买这种产 品的顾客8 0 在2 0 一4 0 岁之间，受过大学教育；而不经常购买这种产品的顾客6 0 或者太 老，或者太年轻，或者没有大学学位。 2 3 2 关联分析 关联分析用于发现关联规则，这些规则展示“属性值”对频繁地在给定数据集中一 起出现的条件。关联分析广泛用于购物篮和事务数据分析。 更形式化地讲，关联规则是形如x j y ，即形如4 爿。j 层 鼠的规则，其 中4 ( f 1 ，一，m ) ) 和曰，( - ， l ，聆) ) 都是“属性一值”对。关联规则z j 】，解释为“满足 x 中条件的数据库元组多半也满足y 中的条件”。 例如，给定a l l e l e c t r o n i c s 关系数据库，一个数据挖掘系统可能发现如下形式的关联规 则： n 班( x ，”2 0 2 9 “) f h c o m p ( ，”2 0 k 2 9 k ”) j6 砂s ( x ，”c d p j q ”r ”) s u p p o r t = 2 ，c o n n d e n c e = 6 0 其中x 是变量，代表顾客。该规则说，所研究的a l l e l e c 仕o n i c s 顾客2 ( 支持度) 在2 0 一2 9 岁， 年收入2 0 k 一2 9 k ，并且在a l l e l e c t r o n i c s 购买c d 机。这个年龄和收入组的顾客购买c d 机的 可能性有6 0 ( 置信度) 。 注意，这是一个以上属性之间的关联，所以称上面的关联规则为多维关联规则。 假定作为a 1 1 e l e c t r o n i c s 的市场部经理，你想知道在一个事务中，哪些商品经常被一块 购买。这种规则的一个例子是： c d 椭f 珊( r ，”卅p “r p r ”) j ”胁f 珊( r ，”j 咖邪) 【s u p p o 九= 1 ，c o n 丘d e n c e = 5 0 该规则说，如果事务t 包含“c o m p u t e r ”，则它也包含“s o f 【w a r e ”的可能性为5 0 ，并且所 有事务的1 包含二者。这个规则涉及单个重复的属性，所以称为单维关联规则。 2 3 3 分类和预测 分类的过程是这样的，它首先找出描述并区分数据类的模型，然后使用模型预测类别 未知的对象的类别。模型的导出基于对训练数据集( 即类别已知的数据对象) 的分析。 导出模型可以用多种形式表示，如分类规则、决策树、数学公式、神经网络等。决策 国防科学技术大学研究生院学位论文 树是一个类似于流程图的树结构，由节点和分支组成，每个非叶节点代表一个属性值上的 测试，每个分支代表测试的一个输出，每个叶节点代表一个类别。决策树可以很容易地转 换成分类规则。当用于分类时，神经网络由组类似于神经元的处理单元组成，单元之间 加权连接。 分类可以用来预测数据对象的类别，也可以用来预测数据对象的某些未知的属性值。 当被预测的是属性值而不是类别时，这种分类通常称之为预测。尽管预测可以涉及到属性 值预测和类别预测，但通常预测仅限于指值预测，并因此不同于分类。 在分类和预测之前可能需要进行相关分析，相关分析的作用是识别对于分类和预测无 关的属性，并排除这些属性。 例如，假定作为a l l e l e c t r o n i c s 的销售经理，你想根据销售活动的三种反应，即好的反 应、中等反应、没有反应，对商店的商品进行分类。你想根据商品的特征，即价格、品牌、 产地、类型，导出分类模型。导出的模型应该最大限度地区分每一个类，提供有组织的数 据集图像。如果结果用决策树的形式表示，决策树可能把价格看成最能区分三个类的因素， 在价格之后帮助进一步区分类对象的其它特性可能是品牌和产地。这样的决策树可以帮助 你理解哪些因素能够影响销售活动以及这些因素之间的相对重要性，并且可以帮助你设计 未来更有效的销售活动。 2 1 3 4 聚类分析 聚类分析与分类预测方法最主要的不同之处在于，后者构建分类预测模型所使用的数 据是已知类别归属的，属于有教师监督的学习方法；而聚类分析构建分类模型所使用的数 据是事先未确定类别归属的，属于无教师监督的学习方法。 f i g u r e 2 - 3 一个城市内顾客的二维图 聚类分析中，首先要给出数据对象之间的相似性度量，然后根据“各聚类内部数据对 象间的相似度最大化，而各聚类之间相似度最小化”的基本聚类分析原则，将数据对象划 国防科学技术大学研究生院学位论文 分为若干组。一个组中的数据对象间的相似度要比不同组中的数据对象间的相似度大。由 聚类分析所获得的每一个组，可以视为一个同类别归属的数据对象的集合，更进一步从这 些同类别数据集，又可以通过分类学习获得相应的分类预测模型。 例如，聚类分析可以在a l l e l e c t r o n i c s 公司的顾客数据上进行，以便识别顾客的同类子 群。f i g u r e 2 3 显示了一个城市内顾客的二维图，数据点的三个子群是显而易见的，每个子 群的聚类中心用“+ ”标记。 2 3 5 孤立点分析 一个数据库中的数据一般不可能都符合分类预测或聚类分析所获得的模型。那些不符 合由大多数数据对象所构成的模型的数据对象就被称为孤立点。许多数据挖掘方法在正式 进行数据挖掘之前，就将这些孤立点作为噪声或意外而排除在数据挖掘的分析处理范围之 外。但在一些场合，如各种商业欺诈行为的自动检测中，小概率事件( 数据) 往往比那些 经常发生的事件( 数据) 更有挖掘价值。对孤立点数据的分析处理通常就称为孤立点挖掘。 例如，孤立点分析可以用于发现信用卡欺骗。通过检测一个给定帐号，如果与正常的 付费相比，某次的付款数额特别大，就可以被认定为信用卡欺骗性使用。 2 3 6 演变分析 数据演变分析就是对随时间变化的数据对象的变化规律和趋势进行建模描述。这一建 模手段包括：概念描述、对比描述、关联分析、分类分析、时间相关数据分析( 这其中又 包括：时序数据分析、周期模式匹配，以及基于相似性的数据分析) 。 例如，假定你有纽约股票交易所过去几年的主要股票市场( 时间序列) 数据，并希望 投资于高科技工业公司的股票。股票交易数据的挖掘研究可以识别整个股票市场和特定公 司的股票演变规律。这种规律可以帮助预测股票市场价格的未来走向，帮助你对股票投资 作出决策。 2 4 数据挖掘结果的评估 一个数据挖掘系统在完成一个挖掘算法之后，常常会获得成千上万的模式或规则。关 联规则挖掘就是一个典型的例子，关联规则挖掘算法的执行结果，即使是对个规模较小 的数据库( 几万条交易事务记录) ，也会得到数千条关联规则。显然这数千条关联规则中， 只有一小部分是具有实际应用价值的。那么如何对数据挖掘所获得的结果进行有效的评 估，以便最终能够获得有实际应用价值的模式? 这就给数据挖掘提出了许多需要解决的问 题：“什么样的模式是有价值的? 一个数据挖掘算法能否产生所有有价值的模式? 一个数 据挖掘算法能否只产生有价值的模式? ” 对于第一问题，一个模式是有价值的，如果它易于被人理解；在一定程度上，对 国防科学技术大学研究生院学位论文 于新的数据或者测试数据是有效的：是潜在有用的；是新颖的。有价值的模式就是知 识。 存在着一些评价模式价值的客观标准，这些标准基于所挖掘出的模式的结构或者它们 的统计特征。例如，对于形如j ；y 的关联规则，一种客观评价标准就是规则的支持度 ( s u p p o r t ) 。规则的支持度表示满足相应关联规则的记录占记录总数的百分比。支持度是概 率p ( x u y ) ，其中u 】，表示同时包含x 和y 的记录。关联规则的另一种客观度量是置信 度( c o n 矗d e n c e ) 。置信度是条件概率p ( yz ) ，即在x 发生的条件下y 发生的概率。从数学上 讲，支持度和置信度的定义为： s 懈，口疗( x = y ) = p ( x u y ) c d 7 l ，池胛c g ( z = y ) = p ( 】，lx ) 尽管这些客观度量可以帮助识别有价值的模式，但是仅有这些还不够，还要结合反映 特定用户需要和兴趣的主观度量。例如，对于市场经理，描述频繁在a l l e l e c t r o n i c s 购物的 顾客特性的模式应当是有趣的：僵分析雇员