（模式识别与智能系统专业论文）分布式环境下约束性关联规则的挖掘算法研究与实现.pdf

摘要 随着分布式计算环境日益普遍，开发分布式数据挖掘算法变得日 益重要。在实际的挖掘过程中需要有效地利用约束条件来提高挖掘效 率。本文主要研究讨论在分布式环境下基于约束条件的分布式关联规 则的挖掘问题。 针对分布式数据库和项约束条件的特点，本文首先提出了基于 a p r i o r i 算法的d m a i c 算法和基于频繁模式树的d a m i c f p 算法。d 毗i c 算法可靠性高，通信协议简单，适用于对通信性能要求不高的分布式 数据库；d a m i c f p 算法执行效率高，通信性能好，适用于对通信性能 要求较高的多项目分布式数据库。对于多种规则约束条件( 反单调约 束、单调约束、简洁性约束、可转变的约束) ，本文在e c l a t 算法的 概念格理论和等价类划分方法基础上，提出了e c l a t a 、e c l a t m 、 e c l a t s 、e c l a t c a 等相应约束条件下的挖掘算法。算法采用自底向上 的搜索方法，在发现频繁项集的同时进行约束条件的检验。数据库的 扫描次数较少，无需对候选项集进行剪枝，占用内存较小。论文在基 于约束的e c l a t 类算法的基础上，结合抽样的方法，提出了一种分布 式挖掘多种规则约束的关联规则挖掘算法一d m c a s e 算法。算法在各 数据站点上对一个较小的样本采用基于约束的e c l a t 类算法挖掘局 部约束频繁项集，用归纳学习的方法归并所有局部约束频繁项集产生 全局约束频繁项集。以前缀树和位矩阵为数据结构保证了算法只需扫 描数据库1 次，通过完备性分析和实验证明算法兼顾了挖掘效率和精 度。 本文同时研究了项约束关联规则挖掘技术在生物信息学中的应 用。在f p g r o w t h 算法的基础上，提出了一种适合基因表达谱数据的 项约束关联规则挖掘算法i c f p 。对酵母基因表达谱数据处理的实验 结果表明：i c f p 算法适用于基因表达谱数据的关联规则挖掘，能够 大大提高挖掘的效率。 关键词数据挖掘，分布式数据挖掘，约束性关联规则 a b s t r a c t t t l er a p i dd e v e l o p m e n to fd i s t r i b u t e dc o m p u t i n ge n v i r o l l n l e n t s m a | sag r e a tp m c e s si nd i s t r i b u t e dd 角l 协m i n i n g 。u t i l i z ec o n s 灯a i n t sc a n i n c r e a s em i n i n ge m c i e n c yi nt 1 1 ep r o c e s so fa c t u a ld a 妇m i n i n g i nm i s p a p e r ，w ed i s c u s st h ep r o b l e mo fd i s n 。i b u t e dm i n i n g 鹤s o c i a t i o nm l e sw i t i l c o n s t m i m s ， f i r s t l y ，a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fd i s t r i b u t e dd a t a b a s e sa r i d i t e mc o n s t r a i m s ，t w oa l g 耐m m sf o rd i s t r i b u t e dm i n i n ga s s o c i a t i o nm l e s w i mi t e mc o n s t r a i 鹏c a l l e dd m a j ca n dd 伽c f pa r ed e v e l o p e d 确e d m a i ca l g o r i t h mi sb a s e do na p r i o r ia l g o r i t h ma n dd a m i c f pi sb a s e d o n f p g r o w t l la l g 耐t h m d m 趟ci s 锄a l g o r i 吐l i i lw i t hh i 曲r e l i a b i l 时a i l d s i m p l e c o m m u n i c a t i o n p r o t o c o l ， a n di ts u i t st l l e s y s t e m o fl o w c o m m u n i c a t i o nr e q u i r e m e n t d a m i c f pi sa n a l g o r i t h mw i t hh i 出 e m c i e n c ya n de x c e l l e n tc o m m u n i c a t i o nq u a l i 吼a n di ts u i 协m es y s t e mo f h i 曲 c o m m u n i c a t i o n r e q u i r e m e n t s e c o n d l y ， m u l t i - m l ec o i l s t r a i n t s ( a m i - m o n o t o n ec o n s 仃a i n t ，m o n o t o n ec o n s t r a i m ，s u c c i n c tc o n s n a i m ，a i l d c o n v e r t i b l e c o n s t r a i n t ) h a v eb e e ni n t e g r a t e d i n t 0t h e a l g o r i m m f o r a s s o c i a t i o nm l e sm i n i n gb a l s e do nv e r t i c a ld a t al a y o u tb yu t i l i z i n gt t l e l a _ c t i c e s t l l e o r ya n dm ed e c o m p o s i n gm e t h o do fe q u i v a l e n c ec l a s s e s s u 塌c i e m l y t h e i rr e s p e c t i v ea l g o r i t h m sb 船e do nt l l ee c l a ta i g o r i t i l ma r e a l s op r e s e n t e d ab o t t o m u ps e a r c hm e t h o di s p u tf o n v a r da n dt 1 1 e c o n s 慨n t sa r ec h e c k e da tm ep m c e s so fc a l c u l a t i n g 丘e q u e n ti t e m s e t s t h en e wa l g o r i t h f n ss c a nt h ed a t a b a s e 诧wt i m e sa n dh a v en 0n e e do f p m l l i n gc a l l d i d a t ei t e m s e t s 1 1 1 e ya l s oc 锄b es o l v e di nm e m o t h i r d l y a na i g o r i t i l i i lf o rd i s t r i b u t e dm i n i n ga s s o c i a t i o nr u l e sw i t l lm u l t i m l e c o n s 仃a i m sc a l l e dd m c a s ei sp r e s e m e du s i n gs 锄p l i n ga i l dc o n s 仃a i n e d e c i a t a l g o r i t l l m a te a c hd a t a b a s e s i t e s ，s 锄p l i n ga i g o r i t a n d c o n 鼬r a i n e d e c l a ta l g o r i t h ma r ei m p l e m e n t e d a n dm el o c a l 丘e q u e m i t e m s e t ss a t i s 分i n gc o n s t r a i n t sa r ed e v e l o p e d t h e ym e na r ec o m b i n e dt o g l o b a l 肫q u e r i ti t e m s e t st 1 1 a ts a t i s 母i n gc o n s t m i n t sb a s e do nl e a m i n g 劬m i n d u c t i o n t h e s t r u c t u r e so fp r e f i xt r e e 锄db i tm a t r i xe n s u r e 廿l a t d ，i c a s ea l g o r i t l l ms c a i l st h ew h o l ed a t a b a s co n l yo n c e c o m p l e t e n e s s 锄a l y s i sa n de x p 耐m e n t sp r o v et i l a td m c a s ec a ne n s u r es i m u l t a l l e o u s m i n i n ge 颤c i e n c y 锄dp r e c i s i o n a tm es a r i l et i m e ，m ea p p l i c a t i o no fa s s o c i a t i o nm l em i n i n gw i t h i t e mc o n s t r a i m st ob i o i n f o m l a t i c sa r er e s e a r c h e d a na i 譬o r i t h mb a s e d 帆 f p - g r o w t l lf o rm i n i n ga s s o c i a t i o nm l e sw i t hi t e mc o n s t r a i n t s 舶mg e n e e x p r e s s i o nd a t ac a l l e di c f pi sd e v e l o p e d r e s u i t s 行o mo u re x p e r i m e m s 丘d my e a s tg e n ee x p r e s s i o np r o f i l e ss h o wm a ti c f p 印p l i e st om i n i n g a s s o c i a t i o nr u l e so fg e n ee x p r e s s i o np r o f i l e s a n di tc a ni n c r e a s em i n i n g p e r f o 咖a i l c e t oa g r e a te x t e m ， 、 k e yw o r d sd a t am i n i n g ，d i s t r i b u t e dd a t am i n i n g ( d d m ) ，a s s o c i a t i o n i u l e sw i t hc o n s 仃a i n t s 原刨性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均己在在论文中作了明确的说明。 作者签名：盘垒! j 嗑日期：竺生年上月卫日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文； 学校可根据国家或湖南省有关部门规定送交学位论文。 作者繇蝉翩签名互赵嗍丛呲月毕日 硕士学位论文 第一章绪论 1 1 引言 第一章绪论 随着数据库技术和网络的迅速发展，数据库中存储的数据爆炸性的增长 如果能把隐藏在这些数据后面的重要信息从数据库中抽取出来，将会创造大量潜 在的利润，而这种从海量数据库中挖掘信息的技术，就称之为数据挖掘。在商业 应用里，它就表现为在大型数据库里面搜索有价值的商业信息。 数据挖掘是一门广义的交叉学科，它汇聚了不同领域的技术，其中包括数据 库、人工智能、数理统计、可视化、并行计算和机器学习等。通过数据挖掘，可 以从数据库中提取有趣的知识、规则和高层信息，并可以从不同角度观察和浏览。 发现的知识可以用于决策、过程控制、信息处理和查询处理等因此，数据挖掘 被信息产业界认为是数据库系统最重要的前沿之一，是信息产业最有前途的交叉 学科。 1 2 数据挖掘概述 数据挖掘技术是在八十年代末产生并迅速发展起来的新兴的研究领域。从数 据库中发现知识( 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 ，简称k d d ) 一词首次出现 在1 9 8 9 年举行的第十一届国际人工智能学术会议上。1 9 9 5 年，首届k d d d a t a m i n i n g 的国际性会议在加拿大的蒙特利尔召开。到目前为止，由美国人工智能 协会主办的k 叻国际研讨会已经召开了多次，规模由原来的专题讨论会发展到国 际学术大会，研究重点也逐渐从发现方法转向系统应用。1 9 9 7 年亚太地区在新 加坡组织了第一次规模较大的p a k d d 学术研讨会此外，数据库、人工智能、信 息处理、知识工程等其它领域的国际学术刊物也纷纷开辟了k d d 专题或专刊。 i e e e 的k n 0 w 1 e d g ea n dd a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技术 专刊。不仅如此，在i n t e r n e t 上还有不少k d d 电子出版物和论坛，人们可以免 费订阅和交流热点问题。从九十年代开始，我国的许多科研单位和院校都开始对 k 叻的基础理论和应用进行广泛的研究，也取得了一定的成果。 i 2 1 数据挖掘的定义 一般认为数据挖掘是k d d 中的一个很重要的步骤。从1 9 8 9 年至今，k 叻的 定义随着人们研究的不断深入也在不断地完善，目前比较公认的定义是f a y y a d 等给出的：k d d 是从数据集中识别出有效的、新颖的、潜在的、有用的以及最终 硕士学位论文 第一章绪论 可理解模式的高级处理过程。1 。k d d 的过程一般包括数据清理、数据集成、数据 选择、数据变换，数据挖掘、模式评估、知识表示。从广义的观点看，数据挖掘 是从存放在数据库、数据仓库或其它信息库中的大量数据中挖掘有趣知识的过 程。简单地说，数据挖掘是从大量数据中提取或挖掘知识“ 1 2 2 数据挖掘技术 最常用的数据挖掘技术有： 1 关联分析“( a s s o c i a t i o na n a l y s i s ) 关联分析用于发现关联规则，这些规则展示属性一值频繁地在给定数据集中 一起出现的条件。关联分析广泛用于购物篮或事务数据分析。详细的关联规则描 述见本文第2 章。 2 分类和预测“1 ( c l a s s i f i c a t i o na n dp r e d i c t i o n ) 分类是这样的过程，它找出描述并区分数据类或概念的模型( 或函数) ，以 便能够使用模型预测类标记未知的对象类。导出模型是基于对训练数据集( 即其 类标记己知的数据对象) 的分析。在某些应用中，人们可能希望预测某些空缺的 或不知道的数据值，而不是类标记。当被预测的值是数值数据时，通常称之为预 测。预测也包含基于可用数据的分布趋势识别。常用的分类和预测技术包括决策 树、简单贝叶斯和神经网络等。 3 聚类分析叫( c l u s t e r i n ga n a l y s is ) 与分类和预测不同，聚类分析数据对象，而不考虑已知的类标记对象根据 最大化类内的相似性、最小化类间的相似性的原则进行聚类或分组。即对象的簇 ( 聚类) 这样形成，使得在一个簇中的对象具有很高的相似性，而与其他簇中的 对象很不相似。所形成的每个簇可以看作一个对象类，由它导出规则。、 4 孤立点分析( o u t l i e ra n a l y s i s ) 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。这 些数据对象是孤立点。孤立点可以使用统计试验检测。它假定一个数据分布或概 念模型，并使用距离度量，到其他聚类的孤立点数据分析称作孤立点挖掘。 5 7 可视化“( v i s u a l i z a t i o n ) 即采用直观的图形方式来将信息模式、数据的关联或趋势呈现给决策者，决 策者可以通过可视化技术来交互分析数据关系。可视化技术主要包括数据，模型 和过程3 方面的可视化。 i 3 数据挖掘研究面临的问题 目前，数据挖掘技术的研究还很不成熟，还有许多问题需要解决。主要包括 2 硕士学位论文第一章绪论 以下几个方面： 1 提高挖掘算法的性能 由于数据库中存储的数据不断的呈指数级增长，因此所提供的数据挖掘算法 必须是有效的和可伸缩的。即对于大型数据库，数据挖掘算法的运行时间必须是 可预计的和可接受的。随着网络的迅速发展，分布式数据挖掘算法的开发也有待 加强。此外，有些数据挖掘过程的高花费导致了对增量数据挖掘算法的需要。这 就要求数据挖掘算法必须具有很高的性能和效率。 2 适合多种形式的输入数据 不仅可以处理数值型的结构化数据，还应该加强对各种非结构化的数据进行 挖掘。如文本、图形、数学公式、图象或w w w 资源等。另外，一些复杂的数据对 象、超文本和多媒体数据、空间数据、时间数据或事务数据等也需要进行特定的 挖掘操作。 3 增强用户交互和可视化 让用户真正参与到挖掘过程中，能够加强用户的指导作用，保证更有效的和 更有作用的挖掘。此外，增强挖掘系统的可视化，能够使挖掘的过程更好地被用 户理解，提高人机交互能力。目前的数据挖掘工具在这方面还做的不够。 4 加强其它领域的应用 目前的数据挖掘技术主要应用于数据库、人工智能和数理统计等领域。但由 于其具有卓越的大规模数据分析和处理能力，因此在其它领域也具有良好的研究 与应用前景。例如生物信息学领域。将数据挖掘技术扩展到一些能够充分发挥其 能力的应用领域将是今后发展的方向。 1 4 论文工作 目前国内外对于基于约束的分布式关联规则挖掘算法的研究还比较少，在作 者能够检索到的知名学术会议论文集和公开发表的刊物上，还未发现有针对这一 方向的研究成果。本文对基于项约束条件和多种规则约束条件的分布式环境下关 联规则的挖掘问题进行了研究和探讨。研究的主要内容如下： 1 针对分布式数据库和项约束条件的特点，研究基于项约束条件的分布式 关联规则的挖掘问题。 2 研究多种规则约束条件( 反单调约束、单调约束、简洁性约束、可转变 的约束) 整合到关联规则挖掘过程中的方法。 3 在抽样算法的基础上，研究基于多种规则约束条件的分布式关联规则的 挖掘问题。 4 将数据挖掘与生物信息学相结合，研究基于项约束的关联规则挖掘技术 硕士学位论文 第一章绪论 在生物信息学中的应用。最后对全文进行了总结，对今后的工作进行了展望。 有关以上工作的详细讨论将在本文第3 章到第6 章中给出。 1 5 论文组织 、 本文由以下章节组成： 第1 章是绪论，描述了数据挖掘的定义和常用的数据挖掘技术，并对数据挖 掘研究的主要问题进行了探讨 第2 章具体讨论了关联规则的概念和性质。并且对近年来关联规则挖掘问题 的发展情况进行了较全面的回顾。对现有的一些典型的、基于约束的、分布和并 行的关联规则挖掘算法进行了深入地介绍和讨论。 第3 章介绍了两种在分布式环境下挖掘约束性关联规则的有效算法：基于 p r i o r i 算法的d l a i c 算法和基于频繁模式树的d a m i c f p 算法。并进行了实例验 证和测试分析，指出了这两种算法各自的优缺点及适用条件。 第4 章介绍了基于多种规则约束条件的关联规则挖掘算法。充分利用了 e c l a t 算法的概念格理论和等价类划分方法，将多种规则约束条件( 反单调约束、 单调约束、简洁性约束、可转变的约束) 整合到关联规则的挖掘过程中，并给出 了e c l 8 t a 、e c l a t m 、e c l a t s 、e c l a t c a 等相应约束条件下的挖掘算法。 第5 章介绍了采用了抽样的方法，在基于约束的e c l a t 类算法( 例如e c l a t a 和e c l a t m ) 的基础上，提出了一种分布式挖掘多种规则约束关联规则的有效算 法一d m c a s e 算法。本算法在各数据站点上对一个较小的样本采用基于约束的 e c l a t 类算法挖掘局部约束频繁项集，采用归纳学习的方法归并所有局部约束频 繁项集产生全局约束频繁项集。只需1 次扫描数据库，挖掘效率较高 第6 章将数据挖掘与生物信息学相结合，研究基于项约束的关联规则挖掘技 术在生物信息学中的应用在f p g r o w t h 算法的基础上，提出了一种适合基因表 达谱数据的项约束关联规则挖掘算法i c f p 。该算法充分利用了f p - g r o w t h 算法 不产生候选项集和扫描数据库次数较少的特点，通过有效的数据预处理技术和数 据压缩技术，只挖掘出满足项约束条件的关联规则。 第7 章对全文进行了总结，并对今后的工作进行了展望。 4 硕士学位论文第二章关联规则描述 2 1 引言 第二章关联规则描述 关联规则挖掘是数据挖掘中的一个重要研究内容，用于发现给定数据集中项 之问的有趣联系。关联规则挖掘首先由a g r 鲫a 1 ，i m i e l i n s k i ，s w 砌i 提出。关 联规则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入其购物篮中 不同商品之间的联系，分析顾客的购买习惯。例如，在同一次去超级市场，如果 顾客购买牛奶，他也购买面包的可能性有多大? 其直观的意义是顾客在购买某些 商品的时候有多大倾向会购买另外一些商品。这些信息可以引导销售“。 2 ，2 关联规则的基本概念 设i = ( i 。i ：，i 是项的集合设任务相关的数据d b 是数据库事务的集 合。其中每个事务t 是项的集合，使得t i 。每一个事务有一个标识符，称作 t i d 。一个项目集合称为项集，在一个项集中项目的数量称为项集的长度，一个 长度为k 的项集称为k 一项集。设x 是一个项集，事务t 包含x 当且仅当x t 。 关联规则是形如x j y 的蕴含式，其中x c i ，y 亡i ，x n y = 0 。规则x j y 在事 务集船中成立，具有支持度s ，s 是d b 中事务包含x u y ( 即x 和y 二者) 的百 分比。规则x j y 在事务集d 中具有置信度c ，c 是d b 中包含x 的事务也包含y 的百分比。满足最小支持度阂值m i l s u p 的项集称为频繁项集。 挖掘关联规则就是在给定的交易集合中产生所有满足最小支持度阈值 ( m i n s u p ) 和最小置信度( m i n _ c o n f ) 的强规则。关联规则的挖掘是一个两步 的过程：找出所有频繁项集；由频繁项集产生强关联规则。第2 步相对来说比较 简单挖掘关联规则的总体性能由第1 步决定。 2 3 典型的关联规则挖掘算法简介 2 3 1 p r ；o r i 算法 a p r i o r i 算法嘲是一种最有影响的挖掘布尔关联规则频繁项集的方法。 a p r i o r i 使用一种称为逐层搜索的迭代方法，k 一项集用于探索( k + 1 ) 一项集。为 提高频繁项集逐层产生的效率，一种称为a p r i o r i 性质的重要性质用于压缩搜索 空间。 定义2 1a p r i o r i 性质脚：频繁项集的所有非空子集都必须也是频繁的 硕士学位论文第二章关联规则描述 1 使用候选项集找频繁项集 首先，在第l 层次计算所有大小为l 的单个项目的支持度计数。在第k 层次 产生大小为k 的侯选项集x ，前提是x 的所有子集都是频繁项集。在得到所有k 层的侯选项集的支持度计数以后，就可以产生( k + 1 ) 层的侯选项集，然后再计 算它们的支持度计数。重复以上过程直到不能产生新的侯选项集为止。层次算法 依据已知的频繁项集产生更大的侯选项集，保证了在已有信息的前提下，不考虑 那些不可能成为频繁项集的侯选项集，大大提高了计算效率但是，a p r i o r i 算 法存在两个缺陷：生成的候选项集数目将随频繁项集的长度而指数爆炸；需要重 复扫描数据库，频繁进行模式匹配。层次算法在每一层次都对数据库整个扫描一 遍，因此当最大的频繁项集的大小是k 时，需要扫描数据库k 或k + l 遍( 若还能 产生大小为k + 1 的候选项集，就需要第k + 1 遍扫描数据库) 。 a p r i o r i 算法产生频繁项集的步骤： ( 1 ) 收集所有的频繁卜项集： ( 2 ) 通过连接，用k 一项集的成员产生候选( k + 1 ) 一项目集。其中，k - 项集 的两个成员可以进行连接的条件为：两者有( k 一1 ) 个公共的项目； ( 3 ) 如果候选( k + 1 ) 一项集的成员x 的任何大小为k 的真子集不是频繁项集， 则将其从侯选( k + 1 ) 一项集中剔除( 应用了a p r i o r i 性质) ； ( 4 ) 扫描数据库，确定( k + 1 ) 一项集的所有成员的支持度计数，若大于给定 的支持度阈值，即为频繁项集成员； ( 5 ) 重复( 2 ) ( 4 ) ，直至再也不能产生候选项集为止。 2 。由频繁项集产生关联规则 一旦由数据库d b 中的事务找出频繁项集，由它们产生强关联规则是直截了 当的( 强关联规则满足最小支持度和最小置信度) 。对于置信度，可以用公式2 一l 计算，其中条件概率用项集支持度计数表示。 ， ，矿如，聊( 4 等b ) ；j p ( 一l b ) = 竺墼) 旦! = 善型辫 公式( 2 一1 ) s u p 即，l 一( _ 0 “蜱f l a ， 其中。s u p p o r t - c o u n t ( a u b ) 是包括项集a u b 的事务数，s u p p o r t c o u n t ( a ) 是包含项集a 的事务数。根据公式2 1 ，关联规则可以产生如下： ( 1 ) 对于每个频繁项集l ，产生1 的所有非空子集。 ( 2 ) 对于每个非空子集s ，如果竺墼翌i ! 旦兰竺黑m i k c d 矿，则输出规则 蛐pp d ，一柳f l 即 “s j ( 卜s ) ”。其中，m i n c o n f 是最小置信度阈值。 2 3 2a p ri o ri 算法的改进算法 由于a p r i o r i 算法存在候选项集的数目较大和需多次扫描数据库等缺陷，因 6 硕士学位论文 第二章关联规则描述 此不少学者提出了许多改进算法，其主要途径包括：减少候选项集的数目；尽可 能减少数据库的扫描次数；改进候选项集的计数方法。其中，有代表性的算法包 括d h p 算法嘲，p a t i t i o n 算法“1 和sa i 【i p l i n g 算法嘲等。 1 d h p 算法 与a p r i o r i 算法类似，d h p 算法也是从( k 1 ) 一频繁项集l 。产生k 一候选项集 c 。但它利用了前一轮中产生的哈希表来验证k 一项集的候选资格。只有那些可散 列到其值不小于最小支持度阂值的哈希表项的k 一项集才将其视为候选项集。这 样，可大大减少c 。的数目，特别是c ：。另外，d h p 算法不仅能修剪单个事务的大 小，还可以修剪整个事务数据库的大小，减少了i o 操作时间。这些特性使得 d h p 算法的效率比a p r i o r i 算法有明显提高。 2 p a t i t l 0 n 算法 p a t i t l 0 n 算法只需扫描2 次数据库。在第1 次扫描中，算法将数据库d b 中 的事务划分成n 个非重叠的部分。如果d b 中事务的最小支持度闽值为m i n s u p ， 则每个部分的最小支持度计数为m i n s u p ( 该部分中事务数) 。对每一部分， 找出该部分内的频繁项集。这些称为局部频繁项集( 1 0 c a lf r e q u e n ti t e m s e t ) 。 该部分将数据转换为垂直分布结构，使用t i d l i s t 相交得到项目集的计数和采 用a p r i o r i 算法来得到所有的局部频繁项集。局部频繁项集可能不是整个数据库 d b 的频繁项集。d b 中的任何频繁项集必须作为局部频繁项集至少出现在1 个部 分中。这样，所有的局部频繁项集作为d b 的候选项集。所有部分的频繁项集的 集合形成d b 的全局候选项集( 9 1 0 b a lf r e q u e n ti t e m s e t ) 。在第2 次扫描数据 库中，评估每个候选项集的实际支持度，以确定全局频繁项集。 3 sa r i l p l i n g 算法 。 s a l l l p l i n g 算法的主要思想是取一个比m i n s u p 还小的支持度阈值l o 吡s u p ， 在抽样数据s 上用层次算法求出支持度大于l o w - s u p 的所有项集的集合，记为s ( 假设s 是满足m i 吐s u p 的频繁项集的超集) ，并得出负边界b d ( s ) 扫描数据 库d b 的剩余部分，计算s u b d 一( s ) 在整个数据库d b 上的实际支持度。如果负边 界b d 一( s ) 中均是非频繁项集，则s 是频繁项集的超集，输出其中所有满足m i n j u p 的项集，否则报告出现错误。如果b d ( s ) 中存在某个频繁项集y ，则y 的超集也 可能足频繁的。解决的方法是将y 加到s 中( 即s = s u y ) ，再求出负边界b d ( s ) ， 再扫描数据库d b ，再验证，直到b d + ( s ) 中均为非频繁项集为止。这需要进行第2 次数据库扫描。 抽样方法是牺牲了一些精度来换取效率。当数据量比较大时，使用抽样方法 具有很高的效率，但不能保证挖掘出所有满足最小支持度阈值的频繁项集。如果 s 中实际包含了d b 中的所有频繁项集，只需扫描1 次陷。否则，还需做第2 次 7 硕士学位论文 第二章关联规则描述 扫描，以找出在第1 次扫描时遗漏的频繁项集。 2 3 3f p - g r o w t h 算法 h a n 等提出的f p - g r o w t h ( 频繁模式增长) 算法9 1 是一种不产生候选的挖掘 频繁项集方法，它通过逐步构造频繁模式树( f p - ”e e ) 来生成全部高频项集， 只需2 次扫描数据库，避免了高代价的候选项集产生；避免了a p r i o r i 类算法中 不可避免的会产生大量的候选项集问题；对于挖掘海量数据中的频繁项集， f p g r o w t h 算法都是有效的和可伸缩的，并且大约比a p r i o r i 算法快一个数量级。 f p - t r e e 是一个具有以下数据结构的树形结构：是一个以标号“n u l l ”为根、 以项目前缀子树为根节点的子节点以及频繁项目头表组成的结构；在项目前缀子 树里，每个节点由项目名字( i t e m n 踟e ) 、项目计数( c o u n t ) 及节点链( n o d e l i n k ) 3 个域组成。其中，项目名字表示该节点代表的项目，项目计数表示通过该结点 的路径数目，节点链用于链接下一个与之名字相同的节点：频繁项目头表由项目 名字( i t e l t r n a m e ) 和节点链头( h e a do fn o d e 一1 i n k ) 2 个域组成。其中，节点 链头指向在f p _ t r e e 里面具有与之名字相同的结点。 一 在以事务数据库d b 和最小支持度阈值m i n _ s u p 为输入条件的情况下， f p t r e e 的构造方法为：扫描1 次事务数据库d b ，导出频繁项( 1 一项集) 的集 合f 及其支持度计数。频繁项的集合按照支持度降序顺序排序，生成频繁项目列 表l ：产生f p t r e e 的根，用“n u l l ”标记；第二次扫描数据库，d b 中的每个事 务的项按l 中的次序排列，排过序的频繁项目列表标记为 p p ，p 是第1 个元 素，p 是剩余元素的列表；然后。调用i n s e n t r e e ( p p ，t ) 。其中，函数 i n s e 九一t r e e ( p fp ，t ) 的处理过程为：如果t 有子结点n ，且n i t e m n a i i l e = p i t e i i r n 鲫e ，则使n 计数加l ；否则，创建新结点n ，计数为1 ，其父结点为t ， 其n o d e 一1 i n k 指针链接到与其名称相同的下一个结点。如果p 非空，则递归调用 i n s e r t t r e e ( p f p ，t ) 。 由f p t r e e 的构造过程可知。d b 中的每个事务都映射到f p - t r e e 中的一条 路径，f p - t r e e 包含了有关频繁模式的所有信息。对于任意的频繁项目，都可从 项目头表的开始，沿n o d e l i n k 指针得到包含该频繁项目的所有频繁模式。 算法f p 一增长的挖掘过程是：首先扫描1 次f p t r e e ，由长度为l 的频繁模 式( 初始后缀模式) 开始，构造它的条件模式基( 一个“子数据库”，由f p t r e e 中与后缀模式一起出现的前缀路径集组成。用f p p a t t e r n fa 表示) 。然后，构 造它的( 条件) f p _ t r e e ，并递归地在该树上进行挖掘。详细的算法描述请参看 文献 9 。 硕士学位论文 第一二章关联规则描述 2 - 3 4e c i a t 算法 z a k i 提出的e c i a t 算法“町采用了垂直数据库结构、概念格划分和自底向上 的频繁集搜索方法。利用基于前缀的等价关系将概念格划分为较小的子概念格。 所谓垂直的t i d 列表数据库是指数据库中的每一条记录由一个项目及其所出现 过的所有事务记录的列表构成。这样使得任何一个频繁集的支持度都可以通过一 些t i d 一1 i s t 的交集运算求得。与a p r i o r i 算法相比，e c l a t 算法具有以下优点： 无需复杂的h a s h 数据结构，不必对整个数据库进行遍历：在生成候选项集后， 不需再进行剪枝；可以在内存中独立处理每一个子网格，数据库的扫描次数较少， 大大提高了关联规则挖掘的效率。与f p g r o w t h 算法相比，e c l a t 算法占用的内 存比较小。详细的算法描述请见本文4 2 2 。 此外，典型的关联规则挖掘算法还包括a p r i o r i t i d 算法“、a p r i o r i h y b r i d 算法幅l 、s e t m 算法o “和d i c 算法“2 1 等。 2 4 基于约束的关联规则挖掘算法 在实际的挖掘过程中，用户往往希望参与到挖掘的全过程中，以便对挖掘过 程进行指导和控制；用户所关心的通常只是关联规则的某个子集，而不是泛泛地 发现全部规则，这就需要有效地利用约束条件缩减数据库中事务的数量，提高挖 掘效率。由此也引出了基于约束的关联规则挖掘算法的研究。 在基于约束的挖掘中，挖掘在用户提供的各种约束的指导下进行。在数据挖 掘中常使用的几种约束”1 包括：知识类型约束：指定要挖掘的知识类型；数据约 束：指定与挖掘任务相关联的数据集；维层约束：指定数据库或数据仓库中所 用的数据维层；规贝口约束：指定对要挖掘的规则的具体约束。规则约束可以分 为5 类：反单调约束、单调约束、简洁性约束、可转变的约束和不可转变的约束； 兴趣性约束；指定规则兴趣度阈值或统计度量，如支持度和置信度。此外，项约 束的应用也比较广泛。本文主要研究基于项约束和5 种规则约束的分布式环境下 关联规则的挖掘问题。典型的基于约束的关联规则挖掘算法包括： 1 项约束关联规则挖掘算法 跏l t i p l e j o i n s ，r e o r d e r 和d i r e c t “3 是3 种不同的项约束关联规则挖掘算 法这三种算法均能够接受布尔表达式作为约束。在发现频繁项集的同时删除不 满足约束的频繁项集。m u l t i p l e j o i n s 算法的关键是生成个选择项集合s ，通 过s 可以减少算法的候选项集的数量。包含选择项s 的候选项集包括3 种存在形 式，并对应3 种不同的连接方法。r e o r d e r 算法是m u l t i p l e j o i n s 算法的一种简 化形式。只要根据s 的优先排序，用1 种连接方法就可以生成所有包含选择项的 9 硕士学位论文第一二章关联规则描述 候选项集d i r e c t 算法能够直接生成满足约束条件的候选项集，不需要根据约 束条件额外生成选择项集合s 。m u l t i p l e j o i n s 算法和r e o r d e r 算法的挖掘性能 相似，都需要根据约束条件额外生成选择项集合s ，并对相同的候选项集进行支 持度计数。r e o r d e r 算法在候选项集的剪枝步时执行速度要快于m u l t i p l e j o i n s 算法，尤其是当候选项集的数量较小时。d i r e c t 算法较m u l t i p l e j o i n s 算法和 r e o r d e r 算法而言，算法的实现过程比较简单，但生成的候选项集的数目较多， 挖掘效率较低。d i r e c t 算法适合解决低支持度和大数据集的约束关联规则挖掘 问题；m u l t i p l e j o i n s 算法和r e o r d e r 算法则适合解决具有高支持度和小数据集 的约束关联规则挖掘问题。 2 c a p 算法 n g ，l a k s h m a n a n ，h a n 和p a n “”根据反单调约束和简洁性约束的特点提出了 c a p 算法。c a p 算法在a p r i o r i 算法”1 的基础上实现了约束关联规则的挖掘算法 算法首先将反单调约束和简洁性约束组合成4 种情况：约束条件既是反单调约 束，又是简洁性约束，如m i n ( s ) v ；约束条件是简洁性约束，但不是反单调约 束，如m i n ( s ) v ；约束条件是反单调约束，但不是简洁性约束，如s u m ( s ) v ； 约束条件既不是反单调约束，也不是简洁性约束，如a v g ( s ) v 。c a p 算法针对 上述4 种不同类型的约束条件提出了不同的策略，能够产生完备的频繁项集。有 效地解决了约束关联规则的挖掘问题。但还存在一些不足之处，例如在第4 种情 况中，如何选择弱约束条件成为算法的一个不能解决的问题。 3 约束频繁模式增长 无论是c a p 算法，还是m u l t i p l e j o i n s 等项约束关联规则挖掘算法均属于 a p r i o r i 类算法，存在生成的候选频繁项集数目较大和需要重复扫描数据库等缺 陷。p e i 和h a n 提出了种基于f p g r o w t h 算法嘲的约束关联规则挖掘架构c f 争 约束频繁模式增长“毋( c o n s t r a i n e df r e q u e n tp a t t e r ng r o w t h ) ，能够将多种约 束( 包括反单调约束、单调约束、简洁性约束和可转交的约束) 整合到挖掘过程 中。文献“町中对可转变约束进行了详细的分析和分类，给出了前缀单调函数 ( p r e f i xm o n o t o n ef u n c t i o n ) 的概念和性质，在前缀条件数据库( p r o j e c t e d d a t a b a s e ) 的基础上，提出了反单调可转变约束、单调可转变约束和强可转变约 束对应的解决办法。约束频繁模式增长架构不仅适用于多种类型的约束关联规则 挖掘问题，还可以推广到其它一些用户感兴趣的模式挖掘。例如：用户所关心不 仅仅只有频繁项集，还对一些频繁项集的子序列模式比较感兴趣，这就引出了基 于约束的序列模式挖掘问题。文献“”在约束频繁模式增长理论的基础上，对多种 用户关心的模式挖掘问题进行了积极的探讨。 约束关联规则挖掘算法能够加强人对挖掘过程的导向与控制，提高挖掘性能 o 硕士学位论文 第二章关联规则描述 及效率。但是，现有的约束关联规则挖掘算法仍然有许多不完善的地方，存在一 些需要解决的问题，主要包括： 1 通用性和普遍性 目前，当约束条件为反单调的、单调的、简洁的和可转变的约束时，已有的 约束关联规则挖掘算法均能够有效解决。但对于不可转变的约束问题，研究的还 比较少此外，对于查询语言和具体的交互性数据挖掘系统的研究还有待加强， 只有将约束关联规则挖掘算法的理论与应用相结合，才能发挥更大的作用。 2 扩展性 已有的约束关联规则挖掘算法多是基于单个数据库的。随着数据库技术和计 算机网络的蓬勃发展，将约束关联规则挖掘扩展