（计算机应用技术专业论文）基于mfptree的关联规则挖掘算法研究.pdf

基于m f p - t r e e 的关联规则挖掘算法研究 摘要 数据挖掘技术是近年来数据库和人工智能等领域研究的热点课题，它 引起了科学界和产业界的广泛关注。关联规则挖掘是数据挖掘的一个重要 研究分支，主要用于发现数据集中项之间的相关联系。信息技术的快速发 展使得众多行业和部门的数据量激增，而这些数据大多都是关系型数据 库，积极研究在关系数据库中挖掘关联规则的有效技术具有极为广阔的发 展前景。 基于f p - t r e e 的关联规则挖掘算法f p - g r o w t h 是当前挖掘频繁项目集算法 中应用最广，并且不需要候选集的一种挖掘关联规则的算法。但是， f p - o r o w t h 算法在挖掘大型关系数据库时占用内存大和运行速度慢甚至根 本无法构造基于内存的f p - t r e e 。针对这些不足，本文提出了一种新的关 联规则挖掘算法，即d m f p 算法，以解决大型数据库挖掘的需要。 本文所做的研究工作如下： ( 1 ) 对数据挖掘和关联规则挖掘技术发展现状进行了探讨。 ( 2 ) 对关联规则挖掘理论展开研究，讨论了一些传统的关联规则挖掘算 法及存在的问题。 ( 3 ) 在对f p g r o w t h 算法深入研究的基础上，提出一种改进的适合大型 数据库挖掘的关联规则挖掘算法d m f p 算法，并进行了实验验证和性能分 析。该算法减少了f p - t r e e 所占用的内存，实验表明该算法比f p g r o w t h 算法具有更好的性能。 ( 4 ) 结合实际，将d m f p 算法应用于一个个人情况调查表中，结果表明该 算法是可行性的。 关键词：数据挖掘；关联规则；m f p t r e e ；d m f p 算法 a s t u d yo f a s s o c i a t i o nr u l em i n i n g a l g o r i t h m b a s e do nm f pt r e e a b s t r a c t d mt e c h n i q u ei sah o tt o p i ci nd a t a b a s ea n da r t i f i c i a li n t e l l i g e n c er e s e a r c h e s ， b r i n g i n gi t s e l ft ot h ea t t e n t i o no ft h es c i e n c ec o m m u n i t ya n di n d u s t r i a lc o m m u n i t y r u l em i n i n ga l g o r i t h mi so n eo ft h ei m p o r t a n tb r a n c h e si nd a t am i n i n g ，m a i n l y a d o p t e dt od i s c o v e rt h ec o r r e l a t i o nc o n n e c t i o n sa m o n gd a t ac o n c e n t r a t o r s 。d a t a a m o u n ti n c r e a s e sd r a m a t i c a l l ya st h ef a s tg r o w t ho fi n f o r m a t i o nt e c h n o l o g ya n d m o s to ft h ed a t a b a s e sa r er e l a t i o n a l l i k ed a t ab a s e t h u s ，t h es t u d yo fe f f e c t i v e t e c h n i q u e sf o rr u l em i n i n ga l g o r i t h mi nr e l a t i o n a l l i k ed a t a b a s eh o l d sv a s tv i s t a s f p g r o w t h ，a na s s o c i a t i o nr u l em i n i n ga l g o r i t h mb a s e do nm f pt r e e ，d e m a n d i n g n oc a n d i d a t ei t e m s e t ，i st h em o s tu s e dm e t h o df o rm i n i n gf r e q u e n ti t e m s e t s o c c u p y i n gag r e a td e a lo fm e m o r y ，f p - g r o w t ha l g o r i t h mr u n ss l o w l ya n de v e nf a i l s t oc o n s t r u c tf p - t r e eb a s e do nm e m o r y t os o l v et h e s ep r o b l e m s ，t h i sp a p e r p r o p o s e san e wa s s o c i a t i o nr u l em i n i n ga l g o r i t h m ，d m f p ，t om e e tt h ed e m a n do f l d bm i n i n g t h ew o r k so ft h i sd i s s e r t a t i o na r ea sf o l l o w s ： ( 1 ) d i s c u s s e sp r e s e n tr e s e a r c h e so nd a t am i n i n ga n da s s o c i a t i o nr u l em i n i n g t e c h n i q u e s ( 2 )r e v i e w st r a d i t i o n a la s s o c i a t i o nr u l em i n i n ga l g o r i t h m sa n dt h e i rd e f e c t s a f t e rat h e o r e t i c a ls t u d yo ft h e o r i e so fa s s o c i a t i o nr u l em i n i n ga l g o r i t h m ( 3 ) p r o p o s ea ni m p r o v e da s s o c i a t i o nr u l em i n i n ga l g o r i t h mf i t f o rl d b m i n i n g ，d m f p ，w i t he x p e r i m e n tt e s ta n df u n c t i o n a la n a l y s i s d m f pr e d u c e st h e m e m o r yu s a g eo ff p t r e e ，a n de x p e r i m e n t ss h o wd m f pd e m o n s t r a t e sab e t t e r f u n c t i o nt h a nf p g r o w t h ( 4 ) c o m b i n i n gt oa c t u a la p p l i c a t i o n ，d m f pa l g o r i t h mi su s e dt oap e r s o n a l i n f o r m a t i o no nt h ei n v e s t i g a t i o nt a b l e t h e s ee x p e r i m e n t a lr e s u l t ss h o wf 矗a f d m f pa l g o r i t h mi se f f e c t i v e k e y w o r d s ：d a t am i n i n g ，a s s o c i a t i o nr u l e ，m f p t r e e ，d m f pa l g o r i t h m i i 插图清单 图2 1 数据挖掘过程4 图3 if p - 树生成过程示例2 8 图3 2由图3 一l ( c ) 中f p - t r e e 形成的条件模式基2 9 图3 3f p - t r e e 中的惟一前缀路径3 0 图4 1m f p - 树及路径组合3 3 图4 2 事务数据库d 生成的m f p - 树3 4 图4 3 数据库d 的数据链表组3 8 图4 4 头项为i1 的数据库d ”的生成3 8 图4 5 头项为i1 的数据库d ”生成的m f p - 树3 9 图4 6 数据重新组合后形成的新数据链表组3 9 图5 1f p - g r o w t h 与d m f p 算法执行时间比较4 8 v i 表格清单 表3 1某商店的销售事务数据库1 6 表3 2用于c l o s e 算法的事务数据库2 4 表3 3f c c l 所有的闭合与支持度2 4 表3 4所有非空2 一项集对应的闭合与支持度2 5 表3 5用于f p - g r o w t h 算法的示例数据库2 7 表4 1事务数据库d 3 2 表4 2用于d m f p 算法的事务数据库d 3 7 表4 3 重新得到的事务数据库d 3 7 表4 4 事务数据库d 上所得到的频繁项集( 最小支持度为3 0 ) 4 0 表4 5f p g r o w t h 与d m f p 算法在w e b d o c s ( 3 5 0 m ) 上测试结果4 0 表4 6f p - g r o w t h 与d m f p 算法在w e b d o c s ( 5 0 0 m ) 上测试结果4 1 表4 7f p - g r o w t h 与d m f p 算法在a c c i d e n t s ( 3 3 8 m ) 上测试结果4 1 表4 。8f p g r o w t h 与o m f p 算法在b i o t r a i n ( 6 6 4 m ) 上测试结果4 l 表5 1c e n s u s 实验数据库部分记录4 6 表5 2c e n s u s 实验数据库的属性及值域4 7 表5 3 部分关联规则4 8 v i i 独仓l j 性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得 佥魍王些太堂 或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示谢意。 学位论文作者签字：孑晕撞毒泽字日期：扣许l - 月1 5 - 日 学位论文版权使用授权书 本学位论文作者完全了解 金鱼曼王些盘堂 有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授 权 金墨王些太堂 可以将学位论文的全部或部分论文内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：碌浮破 签字日期：如嚼年f 月l ，日 工作单位：r 也、吖朝丈 通讯地址i 小1 。胡屯船杏怂 i l l 名：用结 签字日想柳加，归 电话：。一如7 声。 邮编：i 啊侈 致谢 本文是在我的导师周国祥教授的悉心指导下完成的。在课题的确定、课题 的研究及论文撰写等方面，周老师均给予了精心指导、热情鼓励和大力帮助。 周老师为人正直、治学严谨、诲人不倦的高贵品质使我受益匪浅、终生难忘。 在此论文完成之际，由衷地感谢我的导师周国祥教授，谨向周老师表示最诚挚 的敬意! 感谢计算机与信息学院所有给我们授课的老师，他们不仅给了我们知识， 而且他们对工作的认真态度和敬业精神给了我另外的教育，使我知道做一个真 正的为人师表者的标准。他们都是我的学习榜样。 感谢各位评审专家在百忙之中对论文进行仔细的评阅。 另外感谢我的家人，他们一直给我精神上的鼓励和生活上的关心，给了我 克服困难的信心和不断进取的动力。 感谢池州学院教务处的桂处长，感谢所有帮助过我的同事和朋友们。 i i i 作者：操漫成 2 0 0 8 年1 1 月 1 1 课题研究背景及意义 第一章绪论 近年来，以数据库和信息技术的发展为技术保障，以网络技术的迅速普及 为发展通道，以计算机硬件、数据收集设备和存储介质的大量供应为物质基础， 人们的数据收集能力得到了大幅的提高，社会各行业都存储了大量的有关生产、 管理和科研的各种信息，全球范围内数据存储量正急剧增加。然而与此形成鲜 明对比的是，人们对大规模数据的理解能力并没有得到有效的提高，仅仅依靠 传统的数据检索和统计分析等方法已远远不能满足需要，以致出现了“数据丰 富，但信息贫乏( d a t ar i c hb u ti n f o r m a t i o np o o r ) ” 1 ，2 的局面。于是，一 个新的挑战被提了出来：在这被之为信息爆炸的时代，信息过量几乎成为人人 需要面对的问题。为从海量的数据存储中抽取模式、找出数据变化的规律和数 据之间的相互关系，充分发掘数据的潜力，以指导决策和科学发现等各项工作， 人们对数据分析并使之转化为易于理解的知识的需求越来越迫切 3 。 数据挖掘( d a t am i n i n g ) 技术迎合了人们的需求，它是2 0 世纪9 0 年代初 期新崛起的一个活跃的研究领域。数据挖掘就是从大量的、不完全的、有噪声 的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、 但又是潜在有用的信息和知识的过程 5 。数据挖掘是一门汇集统计学、机器学 习、数据库、模式识别、知识获取、专家系统、数据可视化和高性能计算等多 种学科的新兴交叉学科 4 ，这个领域融合了多个不同学科领域的技术和成果， 使其方法表现出多种多样的形式。为自动和智能地把海量的数据转化为有用的 信息知识提供了有力的手段，给数据和知识之间的鸿沟架设了方便之桥 4 。数 据挖掘技术的应用领域十分广阔，它可以从关系数据库、数据仓库、文本和多 媒体数据库、事务数据库和互联网各种数据源上设法获取诸如分类模型、聚类 模型、回归模型、关联模型和时间序列模型等多种知识模型。可以说，有数据 积累的地方，就有数据挖掘技术的用武之地。 1 2 数据挖掘的研究现状 数据挖掘，又称为数据库中的知识发现( k n o w l e d g ed is c o v e r y in d a t a b a s e s ，k d d ) 8 2 ，k d d 这个术语首次出现在1 9 8 9 年举行的第十一届国际联 合人工智能学术会议上。1 9 9 3 年a g r a w a l r 等人首先提出了关联规则的问题 6 ， 并于1 9 9 4 年提出了挖掘关联规则的经典算法a p r i o r i 算法 7 ，这个算法奠定 了关联规则挖掘算法的基础，之后不少国内外学者、机构对关联规则挖掘进行 了大量的研究。关联规则挖掘的目的是在交易数据库中发现各项目之间的关联 关系。 著名的关联规则发现算法是a p r i o r i 算法，a p r i o r i 算法通过多次迭代找 出所有的频繁项目集。由于关联规则的数目可能相当大，人们在探索发现关联 规则的同时，对于提高挖掘过程的效率也做了不少的研究。常见的方法包括： 减少对于数据库的搜索次数；适当放松对精度的限制；当数据库经常变动时， 采用增量更新技术来防止对于整个数据库的重新挖掘；并行化数据挖掘，等等。 所以，为了改善算法的性能，涌现了大量对a p r io r i 改进的算法。如a g r a w a l 等人在v l d b 9 4 提出的快速算法 7 ，p a r k 次等人在s i g m o d 9 5 提出了利用d h p 算法 9 i 0 ，t o i v o n e n 提出基于采样的算法，a g r a w a l 等人提出了并行关联规 则挖掘算法，h a n 等人提出了分布式关联规则算法 11 、多层关联规则挖掘算 法 1 2 ，s r i k a n t 和a g r a w a l 提出了数值扩展的关联规则算法 1 3 3 ，l i u ，h s u 和m a 提出了利用关联规则进行分类的思想。还有一些研究采用了不同的数据结 构进行关联规则的挖掘。如a g r a w a i 等人提出了形象规则的发现算法 1 4 ； b r i g h a ma n d e r s o n 等人提出了对关联规则快速学习的方法 1 5 ：w a n g 等人给出 了基于兴趣度进行数值型关联规则合并的算法 1 6 ；a m i r ，f e l d m a n ，k a s h i 采 用t r e e 树进行关联规则挖掘 1 7 ；p a s q u i e r ，b a s t i d e 等人采用项目格进行关 联规则的挖掘 1 8 ；h u ，l u ，s h i 等人利用概念格进行关联规则的挖掘。b o r g e s 和l e v e n e 总结了关联规则的概念，提出了结构化有向图的概念，重新定义了置 信度和支持度的概念，给出了在超文本数据库中挖掘关联规则的两个算法 1 9 3 。 与国外相比，国内对数据挖掘研究稍晚，没有形成整体力量。所涉及的研 究领域较多，一般集中于算法的研究、数据挖掘的实际应用以及相关理论的研 究。如最大频繁项目集挖掘算法有：颜跃进、李舟军等提出的f p m f i 算法i s 6 ： 宋余庆、朱玉全等提出的d m f i a 算法 5 7 ；吉根林、杨明等提出的i d m f i a 算法 5 8 等。国内企业运用数据挖掘技术来协助企业活动的应用还处在起步阶段。 成功应用的案例还比较少，这对数据挖掘技术和工具的研究人员来说，我国市 场有着巨大的潜力。 1 3 课题研究内容安排 本文由六章组成，具体内容安排如下： 第一章，介绍课题的研究背景和意义、数据挖掘国内外研究现状。 第二章，是对数据挖掘技术的研究。首先对数据挖掘的概念、过程、功能、 进行了详细的叙述，然后具体分析了数据挖掘的支撑技术，并且介绍了数据挖 掘的发展趋势及面临的挑战。 第三章，在提出关联规则基本概念的基础上，对关联规则的种类进行了全 面的总结，对关联规则的经典挖掘算法及其基本思想进行了详细的分析和研究。 第四章，基于m f p - t r e e 算法，提出了一个新的改进的关联规则挖掘算法， 阐述了新算法的原理和实现方法，以及和f p g r o w t h 算法优缺点比较。 2 第五章，将d m f p 算法应用于一个个人情况调查表，进一步说明新算法的高 效性。 第六章，进行总结和展望，对整编论文进行总结，以及对后续的工作展望。 1 4 本章小结 本章是论文的绪论部分，介绍了课题研究的背景和意义、数据挖掘国内处 研究现状，说明了本文内容的组织结构。 第二章数据挖掘技术 数据挖掘是近年来信息技术领域兴起的一个重要研究领域。随着计算机硬 件和软件技术的发展，包含大量数据的信息系统已经无处不在。随着数据采集 技术的发展，数据量越来越大，属性也越来越多，如何从这些数据中获得有效 的知识正是数据挖掘所要解决的问题。 2 1 数据挖掘的概念 什么是数据挖掘( d a t am i n i n g ，简称d m ) ? 广为接受的定义是：数据挖 掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在 其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程 2 0 ，是数 据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，简称k d d ) 的核心。 知识发现被认为是数据库发现有价值信息( 如规则) 的整个过程，数据挖掘只 是数据库知识发现的一个步骤，但又是非常重要的一步，它用专门算法从数据 库中挖掘模式。这些模式蕴含了数据库中一组对象之间的特定关系，揭示出一 些有用的信息，可以为经营决策、信息管理、市场策划和金融预测等方面提供 依据。因此，数据挖掘是一门广义的交叉学科，它汇聚了不周领域的研究者， 尤其是数据库，人工智能、数理统计、可视化、并行计算等方面的学者和工程 技术人员 2 1 。人们注重的是数据挖掘算法理论和应用的研究，而并不严格区 分数据挖掘和数据库中知识发现。一般来说，在产业界和数据库领域界称为数 据挖掘，而在科研领域界称为k d d 。 2 2 数据挖掘过程 数据挖掘的过程 2 2 可粗略地分为：问题定义( t a s kd e f i n it i o n ) 、数据 准备( d a t ap r e p a t i o n ) 、数据挖掘( d a t am i n i n g ) 、结果评价( i n t e r p r e t a t i o n a n de v a l u a t i o ) ，如图2 1 所示： 图2 1 数据挖掘过程 l 、问题定义 数据挖掘是为了从大量的数据中发现有用的、令人感兴趣的信息，因此发 现何种知识就成为整个过程中第一个也是最重要的一个阶段。在问题定义的过 程中，数据挖掘人员必须和领域专家以及最终用户紧密协作，方面明确实际 4 工作对数据挖掘的要求；另一方面通过对各种学习算法的对比而确定可用的学 习算法。后续的学习算法的选择和数据集准备都是在此基础上进行的。 2 、数据准备 数据准备即数据预处理，是k d d 过程中一个重要步骤，通过预处理数据， 提高数据挖掘对象的质量，并最终达到提高数据挖掘所获模式知识质量的目的 2 3 2 4 。 数据准备又可分为四个步骤：数据清洗( d a t ac l e a n i n g ) 、数据集成( d a t a i n t e g r a ti o n ) 、数据变换( d a t at r a n s f o r m a t i o n ) 、数据消减( d a t ar e d u c ti o n ) 。 数据清洗过程包括：填补遗漏的数据值、平滑有噪声数据、识别或除去异 常值，以及解决不一致问题。 数据集成就是将来自多种数据源( 如e x c e l 数据、文本数据等) 中数据合 并到一起。在进行数据集成时特别要注意消除数据的冗余。 数据转换主要是对数据进行规格化操作。如把连续值数据转换为离散型数 据，以便于符号归纳，或是把离散型数据转换为连续型数据，以便于神经网络 计算。 数据消减的目的就是缩小所挖掘数据的规模，但不会影响或基本不影响最 终的挖掘结果。现有的数据消减包括：( 1 ) 数据聚全( d a t aa g g r e g a t i o n ) ( 2 ) 消减维数( d i m e n s i o nr e d u c tio n ) ，即从初始特征中找出真正有用的特征以减 少数据挖掘时要考虑的特征或变量个数( 3 ) 数据压缩( d a t ac o m p r e s s i o n ) ( 4 ) 数据块消减( n u m e r o s i t yr e d u c t i o n ) 。 3 、数据挖掘 数据挖掘阶段即是挖掘算法执行阶段。数据挖掘算法执行阶段首先根据对 问题的定义明确挖掘的任务或目的，如分类、聚类、关联规则发现或序列模式 发现等。确定挖掘任务后，就要决定使用什么样的算法。选择实现算法有两个 考虑因素：一是不同的数据有不同的特点，因此需要用与之相关的算法来挖掘； 二是用户或实际运行系统的要求。 4 、结果评价 数据挖掘阶段发现出来的模式，经过评估，可能存在冗余或无关的模式， 这时需要将其剔除；也有可能模式不满足用户要求，这时则需要整个发现过程 回退到前一阶段，如重新选取数据、采用新的数据变换方法、设定新的参数值， 甚至换一种算法等。另外，k d d 由于最终是面向人类用户的，因此可能要对发 现的模式进行可视化，或者把结果转换为用户易懂的另一种表示，如把分类决 策树转换为“i f t h e n ”规则。 2 3 数据挖掘的功能嵋副 数据挖掘大体上有两种功能，即预测验证功能和描述功能。前者指用数据 库的若干已知属性预测或验证其他未知属性值；后者指找到描述数据的可理解 模式。数据挖掘功能以及它们可以发现的模式类型介绍如下： 1 关联规则挖掘 关联知识( a s s o c i a t i o n ) 反映一个事件和其他事件之间的依赖或关联。关 联分析的目的就是找出数据库中隐藏的关联信息。关联可分为简单关联、时序 关联、因果关联、数量关联等。 2 分类和预测 分类( 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 is i o nt r e e ) 、贝叶斯分 类算法( b a y e s i a nc l a s s i f i e a t i o n ) 、后向传播算法( b a c kp r o p a g a t i o n ) ，k 一 最近邻近分类算法( k - n e a r e s tn e i g h b o rc l a s s i f i e r s ) 、基于案例的推理 ( c a s e b a s e dr e a s o n i n g ) 、遗传算法( g e n e t i ca l g o r i t h m s ) 、粗糙集算法( r o u g h s e ta l g o r i t h m s ) 、模糊集算法( f u z z ys e ta p p r o a c h e s ) 、神经网络( n e u r a l n e t w o r k s ) 等。第二步，使用数据模型进行分类。 预测一般认为是针对连续系统而言的，可以用概率统计中的回归统计技术 建模。许多问题可以用线性回归解决，并且更多的可以对变量进行变换，例得 非线性问题可以转化为线性问题进行处理。 分类和预测的区别是：用预测法预测分类标号( 离散值) 为分类，用预测法 预测连续值( 例如使用回归方法) 为预测。分类和预测具有广泛的应用，包括 信誉证实、医疗诊断、性能预测和选择购物等。 3 聚类 聚类( c l u s t e r i n g ) 也是一种常用的数据挖掘方法，是一种描述数据的工 具。聚类是将数据对象分组成为多个类或簇，在同一簇中的对象之间具有较高 的相似度，而不同簇中的对象差别较大。与分类和预测不同，聚类操作要划分 的类是事先未知的，类的形成是数据驱动的，属于一种无指导的学习方法。最 初的对聚类分析的研究主要是作为统计学的一个分支进行的，这些研究主要集 中在基于距离的聚类分析方面。主要的聚类算法可以划分为如下几类：划分方法 ( p a r t i t i o n i n gm e t h o d ) 、层次的方法 ( h i e r a r c h i c a lm e t h o d ) 、基于密度 的方法( d e n s i t y b a s e dm e t h o d ) 、基于网格的方法( g r i d - b a s e dm e t h o d ) 、基 于模型的方法( m o d e l - b a s e dm e t h o d ) 。聚类分析己经广泛地应用于许多方面， 包括模式识别，数据分析，图像处理，以及市场研究等。 6 2 4 数据挖掘的支撑技术 数据挖掘融合了人工智能、统计及数据库等多种学科的理论、方法和技术， 这些学科中的多种技术和方法都可以直接应用在数据挖掘的过程中。在数据挖 掘中主要用到以下一些技术和方法咖m 6 m ： l 决策树方法 决策树是模式识别中进行分类的一种有效方法，它可以帮助人们把一个复 杂的多类别分类问题转化为若干个简单的分类问题来解决，在形式上是一棵树， 它由中间结点、叶结点和分支组成。决策树的构造从根结点开始，选择合适的 属性把样本数据集合分割为若干子集，建立树的分支，在每个分支子集中，重 复建树的下层结点和分支的过程，直到条件满足为止。训练好的决策树用来预 测新样本的类别。 2 人工神经网络方法 人工神经网络是为了模拟生物大脑的结构和功能而构成的一种信息处理系 统。由大量的简单处理单元彼此按某种方式相互连接而成，依靠其状态对外部 的动态响应来处理信息。人工神经网络基于自学习数学模型，通过数据的编码 及神经元的迭代求解，完成复杂的模式抽取及趋势分析功能。在数据挖掘应用 中，当需要从复杂或不精确数据中导出概念和确定走向比较困难时，利用神经 网络技术就特别有效。经过训练后的神经网络就像具有某种专门知识的“专家”， 可以像人一样从经验中学习。 3 模糊集合方法 模糊集合理论的概念是由美国控制论专家扎德( z a d e h ) 首次提出的。模糊数 据挖掘是模糊集合理论( 模糊论) 在数据挖掘中的应用，可以协助发现一些不能 形成精确挖掘要求的规律。 4 基于事例的推理方法 基于事例的推理方法的主要思想是：当预测未来情况或进行决策时，系统寻 找与现有情况相类似的事例，并选择最佳的解决方案，这种方法能用于很多问 题的求解，并获得好的结果。 5 粗集方法 粗集理论又叫粗糙集理论，是一种处理模糊和不确定知识的数学工具，近 年来在数据挖掘领域引起了广泛的重视。这一方法在数据挖掘中具有重要作用， 它是常用于处理含糊性和不确定性问题，发现不准确数据或噪声数据内在的结 构联系，也可以用于特征归约和相关分析。粗糙集可以看成是含糊概念的一个 数学模式，其主要优点就是不需要任何关于数据的初始的或附加的信息。因此， 广泛应用于不确定、不完整的信息分类和信息获取。粗糙集理论和技术的出现， 大大地提高了数据挖掘和知识发现的效率。 6 可视化方法 7 可视化技术乜鲫是指基本网络化的视像传输、交互和提供多媒体视像服务的 技术，交互性、动态性和可操作性是可视化技术最鲜明的特点。 可视化分析技术拓宽了传统的图表功能，使用户对数据的剖析更清楚。例 如把数据库中的多维数据变成多种图形，这对揭示数据的状况、内在本质及规 律性起到了很强的作用。 2 5 数据挖掘发展趋势及面临的挑战 目前，数据挖掘的发展趋势主要有以下几个方向乜p 川：应用推广、挖掘算 法的效率和可伸缩性、时序数据的挖掘、数据挖掘语言的标准化、可视化数据 挖掘、发现模式的精炼、w e b 和各种复杂数据的挖掘、数据挖掘中的隐私保护 和数据安全。尽管数据挖掘经过一些年的研究和应用，在理论上和应用中都已 经取得了很大的成功，但数据挖掘仍面临许多问题和挑战。 1 源自于数据库本身，现实世界数据库中的数据是动态的且信息庞大，有 时数据是不完全的，存在噪声、不确定性、信息丢失、信息冗余、数据分布稀 疏等。 2 挖掘算法的效率和可伸缩性。对于大型数据库，数据挖掘算法的运行时 间必须是可预计的和可接受的，所以高效的数据挖掘算法将是一个重要的研究 方向。 3 各种不同的模型如何应用，其效果如何评价。不同的人对同样的数据进 行挖掘时可能产生不同的结果，甚至差异很大，这就涉及到可靠性的问题。 4 当数据能从不同角度及不同抽象层次查看时，严重地威胁了保护数据安 全及禁止侵犯隐私的目标。知识发现何时可能导致侵犯隐私以及为了保护敏感 信息而开发何种安全措施，这些工作都是非常重要的。 5 如何对挖掘到的知识进行有效的表示，使人们容易理解，比如如何对数 据进行可视化，推动人们主动地从中发现知识，可视化要求己经成为目前信息 处理系统的必不可少技术。 在近来的数据挖掘研究和开发中，一些挑战业已受到一定程度的关注，并 考虑到了种需求，而另一些仍处于研究阶段。然而，这些问题将继续刺激进一 步的研究和改进，数据挖掘给人类带来的经济效益也一定更加巨大。 2 6 本章小结 本章介绍了数据挖掘技术概念、数据挖掘过程，综述了数据挖掘功能及数 据挖掘支撑技术，最后对数据挖掘的发展趋势及面临的挑战进行了介绍。 8 第三章关联规则挖掘 关联规则挖掘口3 1 ( a s s o c i a t i o nr u l em i n i n g ) 发现大量数据中项集之间 有趣的关联或相关联系。关联规则的概念由a g r a w a l 、i m ie lin s k i 、s w a m i 提出， 是数据中一种简单但很实用的规则。关联规则挖掘是数据挖掘研究的一个重要 分支，关联规则是数据挖掘的众多知识类型中最为典型的一种。目前关联规则 挖掘问题己经引起了数据库、人工智能、统计学、信息检索、可视化及信息科 学等诸多领域的广大学者和研究机构的高度重视，取得了许多研究成果。关联 规则形式简洁、易于解释和理解并可以有效地捕捉数据间的重要关系，从大型 数据库中挖掘关联规则问题己成为数据挖掘中最成熟、最重要、最活跃的研究 内容3 引。 关联规则发现最初的形式是零售商的购物篮分析，购物篮分析是通过发现 顾客放入其货篮中的不同商品，即不同项之间的关联，这种关联的发现可以帮 助零售商制定营销策略。购物篮分析的典型应用是可以帮助经理设计不同的商 品布局。一种策略是：经常一块购买的商品可以摆放近一些，以便进一步刺激这 些商品一起销售。例如，如果顾客购买计算机的同时常也会购买一些财务管理 管理软件，那么如果将电脑硬件摆放得离电脑软件近一点，就可能有助于增加 两者的销售：另一种策略是：将电脑硬件和电脑软件分别摆放在商品的两端，这 就会促使顾客在购买这两种商品时走更多的路，从而达到诱发他们购买更多商 品的目的。比如：顾客在决定购买了一台昂贵电脑之后，在去购买相应的财务管 理软件的路上可能会看到安全系统软件，这时他就有可能购买这一类软件。 尽管关联规则挖掘起源于商业上对市场购物篮进行分析的问题，但随着研 究的不断深入，其基本模型在多角度得到了扩充。他们的工作包括对原有算法 进行优化，如引入随即采样、并行的思想、增加衡量标准、规则约减、改变存 储结构等，以提高算法挖掘规则的效率，对关联规则的应用进行推广，从最初 的商业指导到生活中的其他领域，如工程技术数据分析、宏观决策支持、财政、 教育、科研、医学等。 3 1 关联规则理论 3 1 1 关联规则基本概念 设i = i l ，1 2 ，i m 是所有项的集合，其中i k ( k = 1 ，2 ，m ) 称为项( i t e m ) 。 项的集合称为项集( i t e m s e t ) ，包含k 个项的项集称为k 一项集。一个事务 t ( t r a n s a c t i o n ) 是一个项集，它是i 的一个子集，每个事务均与一个惟一标识 符t i d 相联系。不同的事务一起组成了事务集d ，它构成了关联规则发现的事 务数据库( t r a n s a c t i o nd a t a b a s e ) 。如果项集x t ，则称事务t 支持( s u p p o r t ) 9 项集x ，也称事务t 包含项集x 。关联规则是如下形式的一种蕴含：x j y ，其 中xci ，yc t ，且xny = m 。 i 、支持度( s u r p p o r t ) 和置信度( c o n f id e n c e ) 规则x j y 在事务集d 中成立，具有支持度s ，其中s 是d 中事务包含xu y 的百分比。它是概率p ( xuy ) 。规则x y 事务集d 中具有置信度c ，如果d 中包含x 的事务同时也包含y 的百分比是c 。这是条件概率p ( yx ) 。即： s = s u r p p o r t ( xj y ) = p ( x uy ) ； c = c o n f i d e n c e ( x j y ) = p ( y fx ) ； 同时满足最小支持度阈值( m i n s u r p p o r t ) 和最小置信度阈值 ( m i n e o n f i d e n c e ) 的规则称为强规则。 关联规则可以分为两种：布尔型关联规则和多值属性关联规则，布尔型关 联规则可以看作是多值属性关联规则的基础和特例，本文仅对布尔型关联规则 进行研究，不过该方法同样适用于多值属性关联规则。支持度和置信度是描述 关联规则的两个重要概念，前者用于衡量关联规则在整个数据库中统计的重要 性，后者用于衡量关联规则的可信程度。一般来说，只有支持度和置信度均较 高的关联规则可能是用户感兴趣的、有价值的关联规则。 2 、支持计数( s u p p o r tc o u n t ) 即包含项集的事务数，也称项集的频率或计数。 3 、频繁项集( f r e q u e n ti t e m s e t ) 如果项集满足最小支持度，则称它为频繁项集。 4 、最大频繁项集( m a x i m u mf r e q u e n ti t e m s e t ) 即在频繁项集中挑选出所有不被其他元素包含的频繁项集。 5 、期望可信度( e x p e c t e dc o n f i d e n c e ) 设事务集d 中有e 的事务支持项集y ，e 称为关联规则x j y 的期望可信 度。期望可信度描述了在没有任何条件的影响时，项集y 在所有事务中出现的 概率。如果某天共有1 0 0 0 个顾客到商场购买物品，其中4 0 0 个顾客购买了面包， 则上述的关联规则的期望可信度就是4 0 。 6 、相关度( c o r r e l a t i o n ) 和确信度( c o n v i c t i o n ) 使用s u p p o r t c o n f i d e n c e 框架的关联规则挖掘对许多应用是有用的。然 而，s u p p o r t c o n f id e n c e 框架可能误导，事实上，当x 的出现并不蕴含y 的出 现时，识别出规则x j y 是有趣的；否则，项集x 和y 作为事件是依赖和相关 的。x 和y 的出现的相关性c o r r e l a t i o n 或称为兴趣度i n t e r e s t 定义为： i n t e r e s t ( x y ) = p ( xuy ) p ( x ) p ( y ) = i n t e r e s t ( yjx ) = p ( ylx ) p ( y ) = c o n f i d e n c e e x p e c t e d c o n f 定义确信度：c o n v i c ti o n ( x j y ) = p ( x ) p ( 1y ) p ( xu1y ) 置信度是对关联规则的准确度的衡量，支持度是对关联规则重要性的衡量。 l o 支持度说明了这条规则在所有事务中有多大的代表性，显然支持度越大，关联 规则越重要。有些关联规则置信度虽然很高，但支持度却很低，说明该关联规 则实用的机会很小，因此也不重要。 期望可信度描述了在物品集x 的作用下，物品集y 本身的支持度；作用度 描述了物品x 对物品y 的影响力的大小。作用度( 置信度与期望可信度的比值) 越大，说明物品y 受物品x 的影响也就越大。一般情况，有用的关联规则的作 用度都应该大于l ，只有关联规则的置信度大于期望可信度，才说明x 的出现 对y 的出现有促进作用，也说明了它们之间某种程度的相关性，如果作用度不 大于1 ，则此关联规则也就没有实际意义了。 7 、兴趣度度量 规则的支持度( s u p p o r t ) 和置信度( c o n f id e n c e ) 是两个规则兴趣度度量。 对任务相关的数据和要挖掘的知识类型( 如特征化，关联等) 的说明可以在幅 度减少产生规则的数量，但数据挖掘的过程仍然可能产生大量模式。通常，这 些模式中只有小部分是特定用户感兴趣的。 因此，用户需要进一步限制挖掘过程中产生的不感兴趣的模式数量，这可 以通过设定兴趣度度量来实现。兴趣度度量评估模式的简洁性( s i m p l i c i t y ) 、 确定性( c e r t a i n t y ) 、实用性( u t i 1i t y ) 和新颖性( n o v e l t y ) 。兴趣度的客观 度量基于模式的结构和统计。一般地，每种度量都有一个可以由用户控制的阈 值。不满足阈值的规则被认为是不感兴趣的，因而不作为知识向用户提供。 简洁性：模式兴趣度的一个重要因素是对于人的理解而言的模式的总体简 洁性。模式简洁性的客观度量可以看作模式结构的函数，用模式的二进位位数 或属性数、模式中出现的操作符来定义。规则长度是简洁性的度量。对于以判 定数表达的模式，简洁性可以是树叶或树节点个数的函数。 确定性：每个发现的模式都应有一个表示其有效性或“值得信赖 的度量。 对于形如x j y 的关联规则，置信度就是这样一种度量。 实用性：一个模式的潜在的有用性是定义其兴趣度的一个重要因素。它可 以用支持度来评估。关联模式的支持度是模式为真的任务相关的元组所占的百 分比。 新颖性：新颖的模式是那些提供新信息或提高给定模式集性能的模式。例 如，一个数据异常可以认为是新颖的，它不同于根据统计模型和用户所期望的 模式。检测新颖性的另一个策略是删除冗余模式。如果发现的规则被已在知识 库