（计算机软件与理论专业论文）基于多关系决策树算法的研究.pdf

哈尔滨理工大学工学硕士学位论文 基于多关系决策树算法的研究 摘要 多关系数据挖掘是近年来快速发展的重要的数据挖掘领域之一。高效 性和可扩展性一直是数据挖掘领域的重要研究课题。考虑多关系数据挖掘， 这个问题尤为重要。多关系数据挖掘任务的复杂性对算法的性能提出了更高 的要求。与传统的数据挖掘算法相比，多关系数据挖掘算法的搜索空间变得 更复杂，更大。对于多关系数据学习算法，提高算法效率的主要瓶颈在于假 设空间。针对以上问题，本文主要做了以下工作： 首先，本文对数据挖掘理论、关系数据挖掘理论进行了研究，尤其是多 关系数据挖掘的分类算法多关系决策树算法及多关系数据挖掘的最新技术 元组传播技术进行了深入的研究。 其次，本文提出了多关系决策树的改进算法。多关系决策树主要从两方 面进行改进：1 为了提高多关系决策树算法可扩展性，本文将虚拟连接元组 传播技术应用到改进的多关系决策树算法中；2 为了减少系统独自摸索的时 间、减少系统搜索有用属性的时间和提高用户的满意程度，本文提出了在用 户指导下完成分类任务的背景属性传递技术，并将该技术应用到改进的多关 系决策树中。 最后，本文对改进的多关系决策树算法进行了理论证明和实验验证。本 文的实验主要利用了p k d dc u p 9 9 中的l o a n 、a c c o u n t 、t r a n s a c t i o n 三个 关系，采用两种方法对一般多关系决策树算法和改进的对关系决策树算法进 行比较实验。第一种方法，固定三个关系的记录数不变，每个关系分别增加 属性个数进行实验，第二种方法，固定三个关系中的属性个数不变，改变关 系记录条数进行实验。 通过上面的实验结果，本文研究认为，当改进的多关系决策树在搜索数 据项未达到背景属性传递阀值时，改进多关系决策树算法的运行效率较低； 当改进的多关系决策树在搜索数据项达到背景属性传递阀值时，改进的多关 系决策树算法的效率相对很高且受属性个数增加( 或记录数增加) 影响较小。 关键词多关系数据挖掘；多关系决策树；元组标识传播；背景属性 哈尔滨理t 大学t 学硕十学位论文 r e s e a r c ho nm u l t i r e l a t i o n a ld e c i s i o nt r e e a l g o r i t h m a b s t r a c t m u l t i r e l a t i o n a ld a t am i n i n gi sa l li m p o r t a n ta n dr a p i dd e v e l o p m e n to fo n e o ft h ea r e a so fd a t am i n i n gi nr e c e n ty e a r s e f f i c i e n c ya n ds c a l a b i l i t yo fd a t a m i n i n gh a v eb e e na ni m p o r t a n tr e s e a r c ht o p i c c o n s i d e rm u l t i r e l a t i o n a l d a t a m i n i n g ，t h ei s s u ei sp a r t i c u l a r l yi m p o r t a n t t h ec o m p l e x i t yo fm u l t i - r e l a t i o n a l d a t am i n i n gp u tf o r w a r dt oh i g h e rr e q u i r e m e n t so np e r f o r m a n c eo ft h ea l g o r i t h m w i t ht h et r a d i t i o n a ld a t am i n i n ga l g o r i t h m ，t h es e a r c hs p a c eo fm u l t i - r e l a t i o n a l d a t am i n i n ga l g o r i t h mb e c o m e sm o r ec o m p l e xa n dm u c hb i g g e r f o rm u l t i r e l a t i o n a ld a t al e a r n i n ga l g o r i t h m ，t h em a i nb o t t l e n e c ko fi m p r o v i n ga l g o r i t h m e f f i c i e n c yi st h ea s s u m p t i o ns p a c e i nv i e wo ft h ea b o v ep r o b l e m s , t h i sp a p e rd o t h ef o l l o w i n gw o r k ： f i r s to fa l l ，t h i sp a p e rh a ss t u d i e do nd a t am i n i n gt h e o r y , m u l t i - r e l a t i o n a l d a t am i n i n gt h e o r y ，e s p e c i a l l yi th a ss t u d i e dd e e p l yo nm u l t i - r e l a t i o n a l c l a s s i f i c a t i o na l g o r i t h m s ，m u l t i - r e l a t i o n a ld e c i s i o nt r e ea n dl a t e s tt e c h n o l o g yo f m u l t i - r e l a t i o n a ld a t am i n i n g t u p l ei dp r o p o g a t i o n s e c o n d l y , t h i sp a p e rh a sp r o p o s e da ni m p r o v e da l g o r i t h mb a s e do nm u l t i - r e l a t i o n a ld e c i s i o nt r e e t h ei m p r o v e da l g o r i t h mb a s e do nm u l t i r e l a t i o n a l d e c i s i o nt r e eh a sb e e ni m p r o v e di nt w om a j o ra r e a s ：1i no r d e rt oi m p r o v e s c a l a b i l i t yo fm u l t i - r e l a t i o n a l d e c i s i o nt r e e a l g o r i t h m ，t u p l e i dp r o p o g a t i o n t e c h n o l o g i e so fv i r t u a lc o n n e c t i n gh a sb e e na p p l i e dt oi m p r o v e da l g o r i t h mb a s e d o nm u l t i - r e l a t i o n a ld e c i s i o nt r e e ；2i no r d e rt or e d u c et h et i m eo fs e a r c h i n gb y s y s t e ma l o n e ，r e d u c et i m eo ft h es y s t e ms e a r c h i n gu s e f u la t t r i b u t e a l o n ea n d i n c r e a s eu s e r ss a t i s f a c t i o n ，i th a sp r o p o s e dat e c h n o l o g yo ft h ed e l i v e r yo f b a c k g r o u n da t t r i b u t e so fc o m p l e t i n gt h et a s ko fc l a s s i f i c a t i o nu n d e rt h eu s e r s g u i d a n c e t h i st e c h n o l o g yh a sb e e na p p l i e dt oi m p r o v e da l g o r i t h mb a s e do nm u l t i r e l a t i o n a ld e c i s i o nt r e e - - 哈尔滨理工大学工学硕上学位论文 f i n a l l y , i nt h i sp a p e r , i th a sg a v et h et h e o r e t i c a lp r o o fa n dt h ee x p e r i m e n t p r o v i n go ft h ei m p r o v e da l g o r i t h mb a s e do nm u l t i r e l a t i o n a ld e c i s i o nt r e e t h i s p a p e rh a su s e dt h r e er e l a t i o n s ( l o a n ，a c c o u n t ，t r a n s a c t i o n ) o fp k d dc u p 9 9 ， a n dh a sd o n ec o m p a r e i n ge x p e r i m e n tw i t ht w om e t h o d sb e t w e e ni m p r o v e d a l g o r i t h mb a s e do nm u l t i r e l a t i o n a ld e c i s i o nt r e ea n dm u l t i r e l a t i o n a ld e c i s i o n t r e e t h ef i r s tm e t h o d si st h a tt h en u m b e ro fr e c o r d si nt h et h r e er e l a t i o n sr e m a i n u n c h a n g e d ，i td i dt h ee x p e r i m e n tw i t ht h en u m b e ro fp r o p e r t yi n c r e a s i n gi ne v e r y r e l a t i o n ；t h es e c o n dm e t h o d si st h a tt h en u m b e ro fp r o p e r t yi nt h et h r e er e l a t i o n s r e m a i nu n c h a n g e d ，i td i dt h ee x p e r i m e n tw i t ht h en u m b e ro fr e c o r d si n c r e a s i n gi n e v e r yr e l a t i o n t h r o u g ht h ea b o v ee x p e r i m e n t a lr e s u l t s ，t h i sp a p e rc o n s i d e rt h a t , w h e nt h e i m p r o v e da l g o r i t h mb a s e do nm u l t i r e l a t i o n a ld e c i s i o nt r e ed o e sn o tm e e tt h e t h r e s h o l do ft h eb a c k g r o u n do fp r o p e r t yt r a n s f e ri nt h es e a r c hd a t ai t e m ，t h e i m p r o v e da l g o r i t h mb a s e do nm u l t i r e l a t i o n a ld e c i s i o nt r e eh a sl o w e ro p e r a t i n g e f f i c i e n c y ；w h e nt h ei m p r o v e da l g o r i t h mb a s e do nm u l t i r e l a t i o n a ld e c i s i o nt r e e m e e t st h et h r e s h o l do ft h eb a c k g r o u n do fp r o p e r t yt r a n s f e ri nt h es e a r c hd a t ai t e m ， t h ei m p r o v e da l g o r i t h mb a s e do nm u l t i - r e l a t i o n a ld e c i s i o nt r e eh a sr e l a t i v e l y h i g h e ro p e r a t i n ge f f i c i e n c ya n di sl e s sa f f e c t e db yi n c r e a s i n gt h en u m b e ro f p r o p e r t y ( o ri n c r e a s i n gi nt h en u m b e ro fr e c o r d ) k e y w o r d sr e l a t i o n a ld a t am i m n g ，m u l t i r e l a t i o n a ld e c i s i o nt r e e ，t u p l ei d p r o p o g a t i o n ，b a c k g r o u n da t t r i b u t e i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于多关系决策树算法的研 究诊，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进行研 究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表 或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以 明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：床二广硷同期：2 印，年4 - 月8 h 哈尔滨理工大学硕士学位论文使用授权书 基于多关系决策树算法的研究系本人在哈尔滨理工大学攻读硕士学位 期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大学 所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨理 工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论文 和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影 印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密因。 ( 请在以上相应方框内打) 作者签名：泉于诠 导师签名：搁 日期：2 肋罗年拳月 罗日 日期：乒7 年驴月秒i t 哈尔滨理t 大学工学硕士学位论文 第1 章绪论 1 1 课题的来源及研究背景 课题的来源是黑龙江省自然科学基金资助项目，项目号：f 2 0 0 7 0 2 。 数据挖掘( d a t am i n i n g ) ，又称数据库中的知识发现幢( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ，k d d ) ，是指从大型数据库或数据仓库中提取隐含的、 未知的、非平凡的及有潜在应用价值信息的新领域，这些信息的表现形式为： 规则、概念、规律及模式等。它可帮助决策者分析历史数据及当前数据，并从 中发现隐藏的关系和模式，进而预测未来可能发生的行为。数据挖掘的过程也 叫知识发现的过程，它是- - f q 涉及到数据库、人工智能、数理统计、可视化、 并行计算等领域交叉性新兴学科。 数据挖掘和知识发现是在1 9 8 9 年8 月于美国底特律市召开的第十一届国际 联合人工智能学术会议上正式形成的。其他内容的专题会议也把数据挖掘和知 识发现列为议题之一，成为当前计算机科学界的一大热点。它将k d d 和d m 方面的研究推向了高潮，从此，“数据挖掘一词开始流行口1 。 在数据挖掘过程中，数据通常是不完美的。尽管大部分数据挖掘技术可以 忍受某种程度数据的不完美，但是注重理解和提高数据质量从而改进分析结果 质量h 1 。现实中的数据一般存在噪声、离群点、数据遗漏、不一致、重复、数 据有偏差，或者数据不代表所设想的现象或总体情况。通过数据处理技术可以 提高数据的质量，从而提高数据挖掘的精确度和效率。由于数据质量决定决策 质量，因此数据处理过程是数据挖据过程的重要步骤嗡引。 传统的数据挖掘中存在很多挖掘技术，但随着数据挖掘技术处理对象范围 的扩展，经典的学习方法存在一定的局限性：首先，命题逻辑的描述能力弱， 这包括对数据的描述和对发现知识的描述两个方面。其次，知识的获取并不都 是单纯地只从原始数据中获得。在人类获得知识过程中，常需或多或少地利用 已掌握地有关问题的背景知识。由于这些背景知识通常采用更具表达力的阶 逻辑盯一1 来描述，因此，现有的命题数据挖掘技术不便利用有关挖掘任务的背 景知识。最后，当前的数据挖掘算法多采用了单表假设，但是在实际应用中， 数据以多关系的形式组织。 哈尔滨理工大学工学硕士学位论文 虽然在理论上，多个关系表可以集成到一个单关系表中，但在实践中这一 方法存在许多问题。 l 计算泛关系的时空代价异常大。最终得到的泛关系中，存在大量冗余数 据。 2 在多对一关系形成的泛关系中，一个样例由多行组成，按照属性一值学 习方法的每一行代表一样例的假定，结果会出现语义偏差。对于实际自连接的 关系表难以确定其连接深度。 3 如果将样例的所有信息放入结果关系的单一元组中，则对于复杂数据 库，一方面会出现大量空值属性，另一方面，确定结果关系的全部属性非常困 难。 4 数据重复导致统计偏差。 5 属性值的学习效率非常低。 因此，机器学习与数据挖掘技术明确地需要考虑学习任务的关系表示方式 及其相关搜索机制。在机器学习领域，这类学习问题及其解决方法被称为关系 学习。在k d d 领域，这类挖掘方法的研究形成了关系数据挖掘。从历史的角度 看，关系数据挖掘是在关系学习发展的背景下产生发展起来的例。关系学习的 核心方法归纳逻辑程序设计( i n d u c t i v el o g i cp r o g r a m m i n g ，i l p 们) 。关系数据挖 掘( r e l a t i o n a ld a t am i n i n g ，r d m ) 的起源，可以追溯到2 0 世纪9 0 年代初的口研 究。从那时起，基于i l p 技术的思想并更新传统数据挖掘方法，大量的关系数 据挖掘算法和系统已经开发出来。 1 2 国内外研究情况综述 多关系数据挖掘是近年来快速发展的重要的数据挖掘领域，传统的数据挖 掘方法只能完成单一关系中的模式发现，多关系数据挖掘能够从复杂结构化数 据中发现涉及多个关系的复杂模式。 近年来多关系数据挖掘方面的主要成果u 1 1 2 1 有： 1 9 9 6 年s k r a m e r 提出了多关系挖掘算法s c a r t n 引，s c a r t 将分类树和 回归树这两种统计学的方法引入到多关系学习领域，它是命题学习方法c a r t 的拓展，能够直接从多关系数据表中发现知识且能方便地使用背景知识。s c a r t 系统构建了一棵树，这棵树的每一个节点包含一个文字( 原子文字) 或者 文字的合取，并为每个叶子节点赋予一个离散值或数据值。受c a r t 剪枝方法 的启发，s - c a r t 还在叶子节点中加入了线性回归模型以提高其性能。 哈尔滨理t 大学工学硕士学位论文 1 9 9 8 年hb l o c k e e l 提出多关系数据挖掘算法t i l d e n 钔更新了决策树归纳 方法c 4 5 ，归纳的多关系决策树与命题决策树在结构上是一致的，内部节点包 含测试，叶子节点包含有预测的类值。多关系决策树中，测试时逻辑查询。具 体地说，在一个内部节点发生的测试是一个存在量化的文字的合取式，该合取 式的文字是从根节点到该节点的路径上的所有节点出现的文字。 1 9 9 9 年k n o b b e 提出了使用i l p 技术的多关系数据挖掘框架n 5 1 且搜索空间 包括s q l 查询。 2 0 0 0 年n e v i l l 和j e n s e n 在关系数据挖掘的迭代方式下使用简单的命题贝 叶斯分类器n 引。这种方法可以通过规则使关系结构和目标当需要的时候保持单 调。 2 0 0 0 年p r e f f e r 了为使p r m s 适应累计学习提出将概率关系模型扩展到语 言。它不同于静态关系方法只获取数据库某一时刻的状态，而是建立一个分类 器，用它来预测未知情况。在给定关系解释集合上定义概率分布 。 2 0 0 1 年sw r o b e l 等人提出了使用最近邻居方法完成多关系数据挖掘任务 的最具代表性的系统r i b l 2 “引。r i b l 2 的优点是预测的准确性。在不需要显示 模型的情况下，它是一个很好的选择。缺点是关系距离测度的计算代价非常 大，同时它要求在预测过程中加载所有实例，若预测过程中要加载的样例数较 大时，系统开销会急剧增加。 2 0 0 1 年k r o g e l 和w r o b e l 提出了基于转换的i l p 的被称作r e l yo n a g g r e g a t i o n n 引，它可以处理不确定的关系。主要面向数据库虽大但结构简单的 商业领域。它另一个成功的应用就是2 0 0 2 年c h e n gj 等人将其应用到生物领 域啪1 。 2 0 0 4 年j i a n w e ih a n 等人提出的c r o s s m m e 乜1 1 是最近几年多关系分类方法 的研究成果中最具代表性。c r o s s m i n e 将i l p 技术和关系数据库系统融合在一 起，较好的提高了传统的i l p 方法的f o i l 效率。它通过d 传播技术提高效率。 i d 传播技术的核心思想是：数据库中各关系之间只进行一次连接操作，无需像 传统i l p 技术那样要执行多次连接，在连接同时也无需物化连接结果。 2 0 0 7 年霍峥等人对朴素贝叶斯分类算法进行拓展，提出了用户指导的关系 数据分类算法2 引。该算法提高了分类精度，并且能够直接支持关系数据库， 运行时间远远小于基于i l p 技术的关系数据分类算法。 图1 1 显示了传统的数据挖掘算法和关系数据挖掘算法之间的关系，下一 章将详细阐述。 哈尔滨理工大学t 学硕士学位论文 r e l a t i o n a ll e a r n i n ga l g o r i t h m s s i n g l et a b l e m u l t i p l et a b l e s p r o p o s i t i o n a l 彩弋卜 d tn bb n a rc r m u l t i - r e l a t i o n a ll e a r n i n g 弋 i l pf o b nm l m m p 貂ep 瓤p f o i li c l p l ps l pw a r m r 图1 1 传统的学习算法和关系学习算法的关系 f i g 1 一lr e l a t i o n s h i p sb e t w e e np r o p o s i t i o n a l a n dr e l a t i o n a ll e a r n i n ga l g o r i t h m s 主要的挖掘算法注释如下： ：p r o p o s i o n a l i z a t i o n - ( 命题化) d t ：d e c i s i o n t r e e n b ：n a r v eb a y e s b n ：b a y e s i a nn e t w o r k s a r ：a s s o c i a t i o nr u l 铬 c r ：c l a s s i f i c a t i o nr u l e s i l p ：i n d u c t i v el o g i cp r o g r a m m i n g f o b n ：f i r s to r d e rb a y e s i a nn e t w o r k s n m ：m u l t i r e l a t i o n a ld a t am i n i n g f o i l 乜耵： f i r s to r d e ri n d u c t i v el o g i c t i l d e ：t o p - d o w ni n d u c t i o no ff i r s t - o r d e r l o g i c a ld e c i s i o n t r e e s i c l ：i n d u c t i v ec l a s s i f i c a t i o nl o g i c p r m ：p r o b a b i l i s t i cr e l a t i o n a lm o d e l p l p ：p r o b a b i l i s t i cl o g i cp r o g r a m b l p ：b a y e s i a nl o g i cp r o g r a m s l p ：s t o c h a s t i cl o g i cp o r g r a m m 唾t ：m u l t i r e l a t i o n a ld e c i s i o nt r e e 1 3 本文的主要内容及结构安排 1 3 1 本文的主要内容 根据目前基于分类的关系数据挖掘的发展现状，一些经典的数据挖掘算法 已经应用到关系数据挖掘他5 1 里面，比如多关系分类，多关系关联规则等， 4 _ 哈尔滨理工大学工学硕士学位论文 但是多关系数据挖掘3 技术还不成熟，需要亟待解决的问题是效率，与传统数 据挖掘比较，多关系数据挖掘使用一阶谓词逻辑语言作为模式表示语言使得 m r d m 系统拥有庞大的空间，而且相关算法的计算代价也相当高，因此只有 尽力减少数据扫描次数并努力提高计算效率，m r d m 才能在实际中得到充分 的应用。 目前常见的提高m r d m 效率的方法有两个，即限制搜索空间大小( 通过 i d 传播技术) 和采用抽样方法。目前的这两种方法都存在着不足之处，利用d 传播技术限制搜索空间，搜索效率仍然很低，采用抽样的方法，挖掘的质量难 以保证。基于以上问题，本文利用多关系分类算法中的决策树完成以下工作： 1 本文对关系数据挖掘理论进行了深入的研究，尤其是多关系决策树分类 算法及多关系数据挖掘的最新技术元组传播技术。 2 提高多关系决策树算法的效率和可扩展性，减少假设空间是关键，因 此，本文提出了一种多关系决策树的改进算法，将虚拟连接元组传播技术应用 到多关系决策树算法之中，大大减少了建树过程中需要连接表的次数，减小搜 索空间，提高算法的执行速度。 3 由于用户是最了解应用需求和数据语义的群体，所以用户对分类的指导 会在很大程度上帮助系统完成分类任务，减少系统独自摸索的时间。为了减少 了系统搜索有用属性的时间，提高了用户的满意程度，本文提出了背景属性传 递技术，在用户指导下完成分类任务，提高了分类效率。本文对改进的多关系 决策树算法进行了理论证明和实验验证，结果表明本文提出的算法优于现有的 同类算法，实现了预期的研究目标。 多关系数据挖掘算法的效率的主要瓶颈在于搜索空问的大小，所以本文提 出了多关系决策树的改进算法，在较小的搜索空间利用决策树分类算法进行数 据挖掘。 1 3 2 本文的结构安排 本文主要在基于决策树的关系算法方面做了一些理论和实验的研究工 作。具体来说，主要结构安排如下： 第l 章，绪论部分，论述了关系数据挖掘产生背景，发展现状，并介绍了 本文的主要内容。 第2 章，数据挖掘基本理论及技术，主要介绍数据挖掘过程、当今数据挖 掘的主要方法与技术及几种主要的关系数据挖掘方法与技术。 哈尔滨理工大学工学硕士学位论文 第3 章，多关系决策树算法，主要介绍与多关系决策树算法相关的数据库 概念，多关系数据挖掘的框架及多关系决策树算法。 第4 章，改进的多关系决策树算法，提出多关系决策的改进算法，并对算 法进行了理论证明。 第5 章，对改进的多关系决策树算法进行实验验证。 最后对本文所做工作给以总结，指出还需要解决的问题和一些尚需进一步 研究的内容。 哈尔滨理工大学t 学硕士学位论文 第2 章数据挖掘基本理论及技术 2 1 数据挖掘概述 随着科技进步，特别是信息产业的发展，把我们带入了一个崭新的信息时 代。随着计算机的应用普及和数据库技术的不断发展，数据库管理系统应用领 域越来越广泛。最近十几年中，数据库中存储的数据量急剧增大。面对海量数 据库和大量繁多的信息，如何才能从中提取有价值的知识，进一步提高信息的 利用率，由此引发了一个新的研究方向1 ：基于数据库的知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b b a s e ) 及相应的数据挖掘理论和技术研究。 数据挖掘是一个反复迭代的过程m 1 ，它从大量的数据中搜寻有价值的、非 同寻常的新信息，是人和计算机合力的结果，它在人类描述问题和目标的知识 与计算机的搜索能力之间寻求平衡，以求得最好的结果。数据挖掘是一个利用 各种分析工具在海量数据中发现模型和数据间关系的过程，使用这些模式和关 系可以进行预测，它帮助决策者寻找数据间潜在的关联，发现被忽略的因素， 因而被认为是解决当今时代所面临的数据爆炸而信息贫乏问题的一种有效的方 法。数据挖掘通常也被称作数据库中的知识发现。精确的说，在k d d 中进行知 识学习的阶段称为数据挖掘，。 在实践中，数据挖掘的两个基本目标是预测和描述。预测涉及到使用数据 集中的一些变量或域来预测其他我们所关心变量的未知或未来的值；另一方 面，描述是找到描述可由人类解释的数据模式。因此，可以把数据挖掘活动分 成下述两类：预测性数据挖掘( 生成已知数据集所描述的系统模型) 和描述性数 据挖掘( 在可用数据集基础上生成新的非同寻常的信息) 。 2 2 数据挖掘的过程 数据挖掘是一个反复的过程，通常包含多个相互联系的步骤，并且随着应 用需求和数据基础的不同，数据挖掘处理的步骤可能也会有所不同。通常，数 据挖掘的基本步骤包括：问题定义、数据收集、数据预处理、建立模型、模式 评估和解释模型和得出结论。数据挖掘过程如图2 1 所示。 哈尔滨理工大学工学硕上学位论文 图2 1 数据挖掘过程 f i g 2 - 1t h ep r c m e s s i n go fd a t am i n g l 问题定义与主题分析数据挖掘首先必须分析应用领域，包括应用中的 各种知识和应用目标。问题定义即了解相关领域的有关情况，熟悉背景知识， 弄清用户要求。开始真正的数据挖掘之前最先也是最重要的就是了解用户的数 据和业务问题。精确定义所要解决的问题是数据挖掘成功的关键要素之一。要 想充分发挥数据挖掘的价值，必须对用户目标有一个清晰明确的定义，有效的 问题定义还应该包括一个对数据挖掘结果进行衡量的标准。 数据是数据挖掘工作成败的基础，因此，分析主题的任务包括对数据进行 进一步的理解，如确定数据挖掘所需要的具体数据，对数据进行描述，检查数 据质量等。数据挖掘要有一个明确的主题目标，该主题目标决定了此后数据挖 掘的各种操作。在数据挖掘过程中面对不同用户指定不同主题。主题是一个在 较高层次将数据归类的标准，每个主题对应一个宏观的分析领域，即将不同的 主题按照一定的标准集成，将原始数据结构进行从面向应用向面向主题转变。 2 数据的收集数据收集通常存在两种截然不同的可能m 1 。第一种是当数 据产生过程是在专家( 建模者) 的控制之下：这种方法被认为是“设计实验“。 第二种情况是专家不能影响数据产生过程时：这种方法被认为是“观察法”， 即数据随机产生，大多数数据挖掘中都被采用。 3 数据的预处理在观察设置，数据常常采集于已存在数据库、数据仓库 和数据集市中。数据预处理通常包括至少两个常见的任务： ( 1 ) 异常点的检测和去除。异常点是与众不同的数值，这些数值和大多数 观察值不一致。一般来讲，异常点是由测量误差、编码、记录差和自然的异常 哈尔滨理工大学工学硕士学位论文 值产生的，这种不具备代表性的样本严重影响模型的产生。对异常点处理有两 种处理方法：把检测并最终去除异常点作为预处理阶段的一部分和寻找不受异 常点影响的健壮性建模方法。 ( 2 ) 比例缩放、编码和选择特征。例如，一个取值范围为 o ，1 的特征和 一个取值范围为 1 0 0 ，1 0 0 0 1 的特征，它们在应用技术中的加权是不一样的， 对最终的数据挖掘结果的影响不尽相同。因此，推荐对它们进行比例缩放并使 它们加权相同以进行进一步的分析。 4 建立模型对历史数据建立一个预测模型，然后再用另外一些数据对这 个模型进行测试，这是数据挖掘的核心环节。建立模型是一个反复的过程，需 要仔细考察不同模型以判断那个模型对所需解决的问题最有用。 数据挖掘中的建模实际上就是利用已知的数据和知识建立一种模型，这种 模型可以有效的描述已知的数据和知识，希望该模型能有效地应用到未知数据 或相似的情况中。即建模把一些专业经验、一般规律或普遍情况抽象成一种分 析模型。一旦模型建好之后，就可以应用到那些情形相似而结果未知的判断 中。挖掘数据的过程就是按照人们设计的“模型”对数据进行处理、分析、预 测的过程，它是人的经验、分析过程在计算机中的实现。模型通过历史数据预 测未来，它的有效性的前提条件隐藏着三个假设：过去是将来的好的预测器； 数据是可利用的；数据包含我们想要的预测。 建立模型的最后一步是验证模型。在建立模型后，不直接利用这个模型作 出决策或采取行动之前先对模型测试和验证，是一种较好的方法。模型建立好 之后，必须评价其结果，解释其价值。模型的验证方式主要有：简单验证、交 叉验证和自举法验证。 5 模式评估由于数据挖掘得到的模式有可能没有实际意义或没有使用价 值，也有可能不能准确反映数据的真实意义，甚至是与事实相反的，因此对于 数据挖掘的结果需要进行评估，确定数据挖掘是否存在偏差，挖掘结果是否正 确，是否满足用户的要求。 评估的方法一种是直接使用原先建立的挖掘数据库中的数据进行检验，也 可以找新的测试数据对其进行检验，另一种方法是使用实际运行环境中的当前 数据进行检验。检验的目的就是对整个数据挖掘过程前面的步骤进行评估。 模式评估将发现的知识以用户能了解的方式呈现，根据需要对数据挖掘过程中 的某些处理阶段进行优化，直到满足用户要求。 6 解释模型和得出结论在大多数情况下，数据挖掘模型应该有助于决 策。因此，要对这种模型进行说明以使模型有用。一般来说，简单的模型容易 哈尔滨理工大学工学硕士学位论文 说明，但是其准确度就差一些。现代的数据挖掘方法寄望于使用高维度的模型 来获得高精度的结果。用特定的技术验证这些结果对这些模型进行及时说明被 看作是一项独立的任务。如果没有对问题进行有意义的明确的表述，那么在强 大的数据挖掘方法，最终得到的模型都是无效的。 2 3 数据挖掘的主要技术 数据挖掘技术口3 1 包括三个主要部分：算法和技术、数据、建模能力。下面 分别从进行数据挖掘和知识发现的各个不同的角度来介绍数据挖掘的主要方法 和技术。 l 决策树( d e c i s i o nt r e e ，d t ) 决策树m 1 是一种用于分类、聚类和预测的 预测型建模方法。它采用“分而治之 的方法将问题的搜索空间分为若干子 集。决策树是根和每个内部节点都被标记为一个问题的树。从每个节点引出的 弧代表与该节点相关联的问题的可能的答案。每个叶结点代表对问题解决方案 的预测。 构造决策树的方法采用的是至上向下的递归方式，如果训练例子集中的所 有例子都是同类的，就将其作为一个叶结点，结点内容为该类别的标记。否 则，根据某种策略确定一个测试属性，并按属性的各种取值把实例集合划分为 若干个子集合，使每个子集上的所有实例在该属性上具有相同的属性值。然后 再递归处理各个自己，直到得到满意的分类属性为止。d 3 、c 4 5 汹1 是著名的 决策树归纳算法。 构造一个好的决策树啪1 的关键在于恰当地选择属性。通常用信息增益度量 的方法为各种节点选择属性值，把具有最高信息增益的属性作为当前节点的测 试属性。决策树建立之后，由于噪声等原因导致很多树枝在训练数据中表现出 异常现象。典型的方法是用统计手段去掉可信度极小的树枝，加快分类，提高 决策树正确分类能力。一般通过两种途径对决策树进行剪枝1 。第一种是预剪 枝，指在构建决策树时就及时停止对某些树枝扩展。第二种就是后剪枝，指从 建立完决策树之后从整个决策树中减去节点及节点下属的树枝，主要用的是开 销复杂度剪枝算法。 一般而言，树的规模越小，它的测试能力越强。 2 聚类( c l u s t e r i n g ) 聚类是将物理或抽象的对象的集合分成多个组的过 程，聚类生成的组也被称为簇( c l u s t e r ) ，既是数据对象的集合。聚类就是让生 成的簇内部的任意两个对象之间具有较高的相似度，而属于不同簇的两个对象 哈尔滨理_ 丁大学t 学硕七学位论文 间具有较高的相异度。 从统计学观点看，聚类分析是对数据建模，从而简化数据的一种方法。作 为多元统计分析的主要分支之一，聚类分析主要集中在基于距离和基于相似度 的聚类方法。从机器学习的观点看，簇相当于隐藏模式，聚类是搜索簇的无监 督学习过程。从应用的角度看，聚类分析是数据挖掘的主要任务之一。数据挖 掘领域主要研究面向大型数据库、数据仓库的高效和实用的聚类分析算法。主 要的数据挖掘聚类方法有：划分的方法、层次的方法、基于密度的方法、基于 网格的方法、基于模型的方法等。 3 粗糙集( r o u g hs e t ) 粗糙集理论是一种研究不精确、不确定性知识的工 具，由波兰科学家z p a w l a k 在1 9 8 2 年首先提出。粗糙集理论旧1 是离散数据推理 的一种新方法。它通过引入不可分辨关系、等价类、上近似、下近似、属性约 简、分辨矩阵等概念考察知识表达中不同属性的重要性，来确定哪些属性是冗 余的，哪些属性是必不可少的。删除冗余属性进而简化知识表达空间，最终能 从数据中挖掘出规则。它的理论核心是基于知识源于对对象的分类这一思想， 通过分类找出属性间的关联规则。它可以不需要任何辅助信息，仅依据数据本 身提供的信息就能够在保留关键信息的前提下对数据进行化简并求得知识的最 小表达，从而建立决策规则，发现给定的数据集中隐含的知识。 4 关联规贝j ( a s s o c i a t i o nr u l e s ，a r ) 关联规则是指针对事物型数据库在无 指导学习系统中挖掘本地模式的最普通的模式，反映一个事物和其他事务之间 的相互依赖或相互关联。所谓关联规则是指数据集中支持度和信任度分别满足 给定阀值的规则。将其形式化定义如下： 设i - f ，i 2 ，) 是文字的集合，文字称为项。d 是事物的集合，每个 事物t 是项的集合，这里t c _ i 。相应的，将每一个事物唯一标识称为t i d 。，中 某些项集合墨若x 乃则称咆含丘关联规则形如x jl 这默c i ，y c 胼 胁y - - - o 。若果d 中揣的事物包僦同时包含y ，则称规则约束于事物集合 d 的信任度为c 。如果d 中s 的事物包含x ul 则s 是规贝怄j 】在d 中的支 持度。根据规则中所处理的值类型，关联规则可以分成布尔关联规则和量化关 联规则两种。根据关联规则集所涉及的不同抽象层次，关联规则可以分成多层 关联规则和单层关联规则。特别是对售货数据，如果对这些历史事物数据进行 分析，则可对顾客的购买行为提供极有价值信息。 基于关联规则最著名的算法是ra g r a w a l 等人提出的a p r i o r i 。a p r i o r i 算法 的核心思想是把发现关联规则的工作分为两步：第一步通过迭代检索出事务数 据库中所有频繁m 1 项集，即频繁项集的支持度不低于用户设定的阀值。第二步 哈尔滨理工大学工学硕士学位论文 从频繁项集中构造出满足用户最低信任度的规则。 5 模糊集模糊概念指没有明确外延。模糊概念无法用康托集合论来刻 画。1 9 6 5 年，美国计算机与控制论专家扎德提出了模糊集合论，用隶属程度来 描述差异的中间过渡，是一种用精确的数学语言对模糊性进行描述的方法。 模糊集表示的是某个元素属于某个集合的程度。模糊集的特征函数允许取 o 和l 之间的值，代表给定集合中元素的隶属度。如果删象( 一般用x 表示) 的 集合，那么肿的模糊翱可以定义为一组见公式( 2 1 ) 所示的有序对。 彳= 舷，州俐夕胙刀( 2 - 1 ) 其中，a 似称作模糊集a 的隶属函数( 简写为m f ) 。隶属函数将每个元素 映射n o 和l 之间的隶属级( 或者叫做隶属值) 。 模糊集和粗糙集都是对经典集合论的拓展，模糊集主要着眼于知识的模糊 性，而粗糙集着眼于知识的粗糙性，两者反映的知识粒度不同。模糊集理论已 经成为数据挖掘研究的有效工具。 6 人工神经网络