（计算机软件与理论专业论文）关联规则挖掘的并行算法研究.pdf

关联规则挖掘的并行算法研究 摘要 从大型数据库中挖掘关联规则是数据挖掘中一个重要的课题。从挖掘要求 的时间和空间上看，传统的顺序算法已很难适应于现实中不断增大的数据库规 模。研究和发展高性能、可扩展的并行算法对解决这一问题就显得十分必要。 本文做了如下研究工作： 1 基于分布式存储的并行关联规则挖掘研究 本文在研究传统的挖掘频繁项集并行算法的基础上，提出了一种多次传送 重新分配数据的并行算法( m r p d ) ，并从理论上证明了算法的正确性。m r p d 算 法在第l 步时对数据库重新划分成若干组，并根据各节点的需要多次传送分组， 各节点获得完整分组后异步地计算频繁项集。所有节点计算完成后，得到全部 频繁项集。通过实验，将m r p d 算法与传统挖掘算法在不同数据分布情况下做 了比较。 2 基于共享存储的并行关联规则挖掘的研究 本文在关联规则串行挖掘算法a p r i o r i 的基础上，针对s m p 系统设计了两 种不同并行粒度的挖掘算法，基于h a s h 表的h a 1 算法和基于局部数据库的 h a 2 算法，初步解决了分布式存储系统算法中通信开销过大、并行度低等问题。 通过实验对这两种算法与传统挖掘算法的性能进行了比较。 关键词：关联规则；并行算法；数据挖掘 2 r e s e a r c ho np a r a l l e la l g o r i t h m sf o rm i n i n g a s s o c i a t i o nr u l e s a b s t r a c t m i n i n ga s s o c i a t i o nr u l e sf r o ml a r g ed a t a b a s e si sa ni m p o r t a n tp r o b l e mi nd a t a m i n i n g i tb e c o m e sn e a r l yi m p o s s i b l et op r o c e s sl a r g ed a t a b a s e so n as i n g l e s e q u e n t i a lm a c h i n e ，f o rb o t ht i m ea n ds p a c er e a s o n s i ti su r g e n tt od e v e l o pp a r a l l e l a l g o r i t h mf o rt h i sp r o b l e m i nt h i sd i s s e r t a t i o n ，a l g o r i t h m sf o rm i n i n ga s s o c i a t i o n r u l e sa r es t u d i e do nt w ot y p e so fp a r a l l e lc o m p u t e ra r c h i t e c t u r e t h ec o n t e n to ft h e d i s s e r t a t i o ni sa sf o l l o w s ： 1 r e s e a r c hf o rm i n i n ga s s o c i a t i o nr u l e so nd i s t r i b u t e ds t o r a g es y s t e m a i m i n ga ts o l v i n gt h ep r o b l e m si nt r a d i t i o n a lp a r a l l e lm e t h o d s ，m r p d ，a p a r a l l e la l g o r i t h mw i t hm u l t i - t r a n s m i t t i n gr e d i s t r i b u t e dd a t a ，i sp r o p o s e da n di t s c o r r e c t n e s si sp r o v e di nt h e o r y i nm r p d ，d a t ai sr e d i s t r i b u t e di n t os o m eg r o u p sa t s t e p1 ，a n da 1 1t h eg r o u p sa r em u l t i - t r a n s m i t t e da c c o r d i n gt ot h er e q u e s to fc o m p u t e r n o d e s e a c hn o d ew i l lc o m p u t ef r e q u e n ti t e m s e t sa s y n c h r o n o u s l ya f t e rh a v i n g r e c e i v e do n ef u l lg r o u p ，a n df i n a l l y ，a l lf r e q u e n ti t e m s e t sa r ec o l l e c t e d t h r o u g h e x p e r i m e n t ，t h ea l g o r i t h mi sc o m p a r e dt ot r a d i t i o n a la l g o r i t h m si nd i f f e r e n t c o n d i t i o n so fd a t ad i s t r i b u t i o n 2 r e s e a r c hf o rm i n i n ga s s o c i a t i o nr u l e so ns h a r e ds t o r a g es y s t e m i nt h i sd i s s e r t a t i o n ，o nt h eb a s i so ft h er e s e a r c ho ft h ea p r i o r ia l g o r i t h m ，t w o p a r a l l e la l g o r i t h m sr u n n i n go ns m pm a c h i n e ，h a - 1a l g o r i t h mb a s e do nh a s h t a b l e a n dh a 一2a l g o r i t h mb a s e do nl o c a ld a t a b a s e ，a r cp r o p o s e da n da r ec o m p a r e dt o t r a d i t i o n a la l g o r i t h m sf o rt h e i rp e r f o r m a n c e s o m ed r a w b a c k si np a r a l l e lm i n i n g a l g o r i t h m so nd i s t r i b u t e ds t o r a g es y s t e m ，s u c ha so v e r l o a do fd a t at r a n s p o r t a t i o n a n dl o wp a r a l l e ld e g r e e ，a r ee l e m e n t a r i l yo v e r c o m e d k e yw o r d s ：a s s o c i a t i o nr u l e s ；p a r a l l e la l g o r i t h m ；d a t am i n i n g 3 插图清单 图2 1五类并行计算机体系结构1 8 图3 1 测试2 的结果3 5 图3 。2 测试3 的结果3 6 图3 3时间比例图3 6 图4 1事务数据库举例4 0 图4 2 频繁项目集表举例4 0 图4 3h a 1 算法的流程图4 2 图4 4 求事务k 项组合函数4 4 图4 5h a 2 算法的流程图4 5 图4 6 测试5 的结果4 6 表格清单 表l 测试数据集特征3 4 表2 不同数据下的测试3 4 表3 不同特征实验数据的运行结果4 6 4 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金胆工些太堂 或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 学位论文版权使用授权书 本学位论文作者完全了解金壁王些盔堂有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权金壁兰些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索。可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在鳃密后适用本授权书) 学位论文作者签名：王飘阳 导师签名： 签字日期：2 0 d 年莎月f 1 日 签字日期6 k 豸年占月 f 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 致谢 值此论文完成之际，我谨向我的导师田卫东副教授表示真挚的谢意! 在三 年的硕士研究生学习中，自始至终都得到了田老师悉心的指导，所取得的点滴 进步，无不浸透着田老师的心血。田老师严谨的治学态度，踏实的工作作风都 是我学习的榜样，不仅在学术上，在做人、处事的原则上，田老师更是给我指 明了前进的方向。田老师知识渊博，治学严谨，对问题有敏锐的洞察力，我的 硕士论文中本身就倾注了田老师大量的心血。没有他的指导和帮助，没有他对 我论文反复修改和精心提炼，我是不可能顺利完成我的毕业论文的。 同时在这里，我要十分感谢计算机与信息学院的胡学钢教授，在我攻读硕 士期间，他给了我大量的指导、关怀和帮助，并提出了许多宝贵的意见，令我 在成长的路上受益匪浅。 除此之外，我还要感谢吴共庆老师、张玉红老师、张晶老师等，与他们一 起对数据挖掘的课题进行讨论，集思广益，对我论文的构思有很大的帮助：感 谢合肥工业大学人工智能与数据挖掘研究室每个成员对我的关怀和帮助，没有 这个团结、上进的集体就没有我今天的成绩。 还要特别感谢合肥工业大学可视化与协同计算研究室( v c c ) 提供了并行 计算环境，并给予了大量的相关资料。感谢卫兴武同学的热情接待和耐心解答 并行实验环境方面的问题。 感谢计算机与信息学院的王浩教授、曹航老师、徐静老师、王新生老师为 我所付出的辛勤工作! 最后，我要衷心的感谢我的家人，是他们几十年来一直默默地给与我无尽 的关怀和帮助。这种支持不但使我能够顺利地完成学业，也将激励着我在今后 的日子里不断的前进。 4 作者：王丹阳 2 0 0 8 年6 月 第一章绪论 1 1 本文的研究背景和意义 ( 1 ) 数据库技术的发展与数据挖掘的提出 数据库的应用已经进入了成熟的阶段，尤其在1 9 7 0 年e d g a rc o d d 提出了 关系数据库模型以来，数据库的应用迅速渗透到了社会数据处理的各个层面。 在商业领域数据库保存了各个公司多年积累的用户信息，交易纪录以及生产数 据；在科学研究领域保存了大量的实验数据，观测数据和调查数据，这其中都 蕴含了大量的人们还没有发现的信息和知识。尤其是上个世纪末以来i n t e r n e t 全球互联网的迅猛发展，使得各种数据急剧增长，人类进入“信息爆炸 时代 大量无用信息湮没了有价值的信息，人们要找到自己所需的信息所花费的 时间越来越长。如何高效利用数据成了一个急待解决的问题。 数据挖掘( 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 s ，k d d ) ，是自动的或方便的模式提取，这些模式代表隐 藏在大型数据库、数据仓库或其他大量信息中的知识【1 1 。数据挖掘的目标是从 海量的数据中抽取出模式，找出数据变化的规律和数据之间的相互依存关系， 使人们能够从宏观的高层次的角度来审视数据，充分发掘数据的潜力，指导人 们的行为，为决策和科学发现提供有力的支持。 “数据库中的知识发现”即k d d 是在1 9 8 9 年8 月于美国底特律市召开的第 一届k d d 国际学术会议上正式形成的【2 】。国际k d d 学术会议起初每两年召开 一次，1 9 9 3 年后每年召开一次。 19 9 5 年，在加拿大召开了第一届知识发现和数据挖掘国际学术会议【3 】。由 于数据库中的数据被形象地喻为矿床，因此数据挖掘一词很快流传开来。1 9 9 5 年以来，国外在数据挖掘和知识发现方面的论文非常多，已形成了热门研究方 向。随着国外知识发现的兴起，我国也很快跟上了国际步伐，对算法的研究和 分析，以及在不同领域中的应用均取得了不错的成果。 ( 2 ) 并行计算机系统的发展 计算机的出现对世界的经济发展和人们的生活都产生了巨大影响。而生产 力的持续增长以及各种应用领域对高性能、低价格计算能力的要求，也极大地 推动了计算机本身的发展。并行计算技术就是在这个过程中得以产生并不断发 展的。 传统上，科学与工程计算领域对并行计算能力的要求总是永无止境的。作 为三大科学研究手段之一的高性能计算机，其发展的根本动力来自于各类科学 技术对计算机性能永无止境的需求和生产的实际需要。1 9 9 2 年，美国高性能计 算和通信计划( h i g hp e r f o r m a n c ec o m p u t i n ga n dc o m m u n i c a t i o n ，h p c c ) 提出 了科学与工程计算领域里具有深远影响的一些重大挑战性课题，其中包括中长 期天气预报、湍流分析、海洋环流建模、空气动力学、三维等离子体研究、 药物分子结构设计、全球气候变化、结构生物学、图像理解等诸多方面1 4 j 。所 有这些课题全都具有极大的计算量，因而无一不对计算机的性能提出了非常高 的要求。同时，这些问题又都非常适合于进行并行计算，因此，这种需求也正 是推动并行计算机体系结构不断发展演进的原动力。在19 9 6 年的“s u p e r c o m p u t i n g 9 6 ”大会上，美国政府h p c c 计划全国协调委员会主席j o h nt o o l e 在题为“危机、创新与机会：h p c c 将向何处去 的报告中对此做了很好的说 明。他指出，高性能计算与通信对美国的国家安全及保持美国在未来的优势至 关重要。美国政府将在高端计算机与通信、大规模网络、高可信系统等5 个方 面制定1 0 1 5 年的长期计划，保持长期持续性投资。 随着计算机技术、网络技术的迅速发展及其对经济与生活影响的日益深入， 新的应用、新的需求也不断地涌现了出来。h p c c 所列举的科学计算需要的是 具有超级计算能力的大型计算机系统，甚至巨型计算机系统，但这个领域毕竟 位于金字塔的顶端，市场空间有限。而在商业领域，随着信息化进程的不断深 入，大型数据库系统得到了广泛的应用，网络信息服务业以惊人的速度扩展， 电子商务也在日益普及。这些新的领域对计算能力的需求虽然不及科学计算， 但是它们也需要大规模的数据存储系统以及大规模的计算能力，并且天生就具 有很好的并行性。因此，它们也从市场的角度对并行计算提出了新的要求。 另一方面，并行计算机体系结构的发展又和处理器、存储器以及网络互连 技术的发展密不可分。由于受到当时技术水平的限制，早期的计算机都只是单 机系统。随着计算机的基本元件从电子管发展到晶体管，计算机的体积大大地 缩小了，从而在6 0 年代初出现了最早的采用并行体系结构的计算机。此后，集 成电路、大规模集成电路以及超大规模集成电路相继出现，而并行计算机的体 系结构则随之不断发展，性能也得到了极大的提高。商品化微处理器和p c 工 业有如一对孪生兄弟，自8 0 年代中期以来，两者都得到了迅猛的发展。微处理 器的性能不断提高，价格也不断下降。在越来越多的并行计算机系统也开始采 用这种具有极高性能价格比的处理单元以后，超级并行计算机就进入了一个新 的时代。到了9 0 年代，即使是在p c 服务器领域，也出现了大量相对比较廉价 的多处理机系统，并行计算的应用达到了前所未有的广度和深度。 ( 3 ) 数据挖掘中遇到的问题 数据挖掘问题中所涉及到的数据集的规模一般较大并具有多维的特性，这 样使得解决该类问题的理想办法是在多处理机上采用并行的方式，其主要原因 是单处理机的c p u 和内存资源都非常有限。尽管对传统算法进行了许多改进工 作，但大规模和多维问题所需的单纯计算工作在单处理机上的运行时间仍然太 长。因此，设计高效的并行算法来完成该任务就变得尤为重要。开发并行算法 2 的另一个原因是许多事务数据库来源于分布式数据库或者这些数据分布于不同 的站点【5 1 ，而将它们搬到同一站点或同一计算机中以便于使用串行挖掘关联规 则的算法所带来的开销是巨大的。所以，开发并行和分布式数据挖掘算法是十 分必要的【6 1 ，这些并行算法将数据划分成各部分，这些部分可以并行处理，然 后合并各部分的结果。 关联规则是r a g r a w a l 等人在1 9 9 3 年首先提出的【7 】，关联规则挖掘是数据 挖掘的重要功能。关联规则是寻找在同一个事件中出现的不同项的相关性，即 找出事件中频繁发生的项或属性的所有子集，以及它们之间应用相互关联性h j 。 关联规则最早用于发现顾客交易数据库中不同商品间的联系，后来诸多的研究 人员对关联规则的挖掘问题进行了大量的拓展和研究。他们的工作包括对原有 算法的优化，如引入并行的思想提高算法的效率，对关联规则的应用进行扩展。 关联规则挖掘的特点是计算量很大且i o 操作繁重，而且许多关联规则的 实际应用涉及到海量数据。在这种情况下，即使对算法进行了优化，在单处理 机上使用串行算法进行挖掘所需要的时间可能也是无法接受的。其主要原因在 于单处理器本身受到内存和i o 带宽的限制。因此，随着数据库规模的不断增 大，数据属性向高维发展，传统的顺序挖掘算法很难适应大规模、可扩展 ( s c a l a b i l i t y ) 的挖掘需要，发展高性能的并行算法是解决这一问题的关键。 1 2k d d 与数据挖掘 1 2 1k d d 过程 k d d 过程包括许多步骤，数据挖掘只是其中的一个步骤【9 1 。k d d 运用数 据挖掘的方法列举得到的模式，并且评估数据挖掘的产品。事实上，k d d 的总 体过程包括了对挖掘出来的模式评估和的可能的解释，并据此决定哪一个模式 可视为新知识。它交互、可重复，且包括许多步骤。k d d 知识发现过程包括数 据清理、数据集成、数据变换、模式评估和知识表示【1 0 l 。 k d d 基本步骤如下： 第一步是对应用领域和相关先验知识的理解以及从客户的角度确定k d d 过程的目标。 第二步是创建目标数据集：选择一个数据集，或者从将要进行操作的变量 或数据样本中选一个子集。 第三步是数据清理和预处理。基本操作包括去除噪声，收集必要的信息来 建模解决噪声，决定如何处理丢失的数据域，并且说明时序信息和已知的变化。 第四步是数据约简：基于任务目标找寻有用的特征来体现数据。 第五步是基于k d d 的目标选择特定的数据挖掘方法。比如分类、综合、 回归、聚类等等。 第六步是探查分析和模型及假设选择：选择数据挖掘算法和方法去搜寻数 3 据模式。这一过程包括决定哪一种模型和参数合适，并且基于k d d 整体标准 配备一种数据挖掘算法。 第七步是数据挖掘：搜寻有趣的模式，包括分类规则、树、回归和聚类等 等。通过正确地执行前面的步骤，用户能显著地辅助数据挖掘方法。 第八步是解释挖掘出的模式，有可能会回到1 到7 的任何步骤。 第九步是将挖掘出的知识直接应用于另一个系统，或者做出文档，提交给 感兴趣的部门。该过程也包括用之前已经确定的知识检查、解决潜在的冲突。 这只是一种步骤的划分方法，有些专家则倾向于合并某几步【1 1 1 。基于这种 划分方法，k d d 大部分前面的工作集中在第七步，即数据挖掘。然而，其它步 骤对于将k d d 成功用于实践同样重要。比如数据选择和数据预处理对于整个 知识发现过程有着很重要的作用，同时又是最费时的步骤。完全自动的系统不 能达到最终的目标，由于大多数的数据不是由数据仓库提供或者说仅仅零散地 存放在数据库中，作为日常的商业处理，如支出，入账等等，直接对这样的数 据操作，会导致生成适用性很低的模式或知识发现的失败。所以成功的知识发 现过程是需要相关的领域专家，数据专家和用户所关心的目标来辅助的。 1 2 1k d d 的任务 k d d 的任务主要有两类：预测和描述。预测指的是预测未知的感兴趣的变 量或发现某些实例未来的行为模式：描述是指寻找可以理解的描述数据的好的 模式。预测和描述之间的分界不明显( 某些预测模型可用于描述，在某种程度 上是可理解的) ，但理解两者的不同对理解整个发现目标是有用的。特定问题的 数据挖掘的预测和描述是相当重要的。预测和描述可以通过下列方法实现： ( 1 ) 分类( c l a s s i f i c a t i o n ) ：分类是数挖掘中的重要研究分支。分类的含义 就是指从一组已知的、已经具有类别的训练数据中，提取出一个分类模型( 分 类器) ，然后把该分类模型( 分类器) 应用于数据库中的那些有待进行类别判断 的数据上，从而实现对它们的分类。如今分类问题被广泛应用于银行信贷，疾 病诊断等多个领域。目前常用的分类模型( 分类器) 主要有决策树，神经网络， 统计方法，遗传算法等。其中决策树是应用最广泛的方法之一，而这要归功于 其准确率高和计算量相对小的特点。 ( 2 ) 聚类( c l u s t e r i n g ) ：聚类简单的说就是“物以类聚”，即对一系列未分 类客体依据客体属性集进行类别的识别，按照其相似性分成若干类别聚类的目 的是使属于同一类别的个体之间的距离尽可能的小而不同类别的个体间的距离 尽可能的大，即聚类应该使类内个体间的相似性最大，而类别间的相似性最小。 聚类和分类最大的区别在于，分类是在已知“标记”的前提下，对未知对象划分 类别，而聚类则是根据现有“无标记”对象的特性，对它们进行划分，然后再“贴 上标记”。 4 ( 3 ) 关联规则( a s s o c i a t i o nr u l e s ) ：关联规则是指数据对象之间的相互依赖 关系，而发现关联规则的任务就是从数据库中发现那些确信度和支持度都大于 给定值的强规则。关联规则的发现，目前已经从单一概念层次发展到多个概念 层次上的发现。在概念层次上的不断深入，使发现的关联规则能提供更具体的 信息，这实际上是逐步深化发现知识的过程。关联规则挖掘的研究在最近几年 一直是数据挖掘界中异常热门的课题之一。 ( 4 ) 序列模式( s e q u e n t i a lp a t t e r n s ) ：序列模式是指在多个数据序列中发现 共同的行为模式。序列模式挖掘算法的框架与之前提到的关联规则挖掘十分相 似。在序列模式挖掘算法的过程中，包括了候选频繁序列的生成和在事件序列 中识别候选序列两个过程，而这两个过程组成了一步迭代。序列模式挖掘算法 就是这样不断地多次迭代，直到不能再产生频繁情节为止。例如，对序列数据 库中的某顾客，序列模式就是指能在该数据库中寻找到的所有的最长频繁序列。 ( 5 ) 偏离发现( d e v i a t i o nm i n i n g ) ：是指数据库中客体与常规或期望模式 的偏离发现或评估。客体的期望行为通常由用户给定或根据假设( 如平均、线 性增长) 计算得知。例如网络中的服务器上发现某些站点访问方式在某段时间 内其行为不同于大多数其它站点的一种特殊情况。 1 3 相关研究工作 随着数据挖掘研究领域的拓展，关联规则挖掘的研究日益受到人们的关注。 与本文相关的研究主要包括以下三个方面。 1 3 1 串行关联规则挖掘算法 ( 1 ) a p r i o r i 算法及改进算法 a p r i o r i 算法【l2 j 是由a g r a w a l 在1 9 9 4 年提出的一种最有影响的挖掘关联规 则挖掘算法，是一种宽度优先搜索算法。它使用一种称作逐层搜索的迭代方法 产生频繁项集，利用“频繁项集的所有非空子集都必须也是频繁的 这条性质 对候选项集删减。算法首先扫描一遍数据库计算各个1 项集的支持度，从而得 到频繁1 项集l l ；然后采用迭代的方式，逐步找出频繁2 项集，3 项集， 直至不再产生新的频繁项集为止。在计算频繁k 项集l k ( k _ 2 ，3l e e ) 时，先通过 l k 1 自连接产生候选集c k ，利用一定的剪枝策略缩减c k ；再通过扫描数据库来 计算候选集的出现频率，消除非频繁项，从而得到l k 。 a p r i o r i 算法能够有效地产生所有关联规则，但在效率上存在一些问题： 数据库扫描次数太多，扫描数据库的次数等于最大频繁模式的长度。产生的 候选项集过大，虽然采取了一定的剪枝策略，但候选项集仍然较大。候选项 集的计数需要花费大量的时间。 对于a p r i o r i 算法存在的问题，人们提出来了许多改进算法。主要有：采用 哈希技术改进候选集生成过程的d h p ( d i r e e th a s h i n ga n dp r u n i n g ) 算、法t ”1 ；采用 分而治之的思想来解决内存不足问题的分块挖掘算法( p a r t i t i o n ) t 1 4 】；抽样算法 ( s a m p l i n g ) 1 5 1 ；动态项集计数算法d i c ( d y n a m i ei t e m s e tc o u n t i n g ) 1 6 】等。 ( 2 ) e c l a t 算法、d i f f s e t 算法和v i p e r 算法 这三种算法都使用了深度优先搜索策略，数据库中的数据采用了纵向 ( v e r t i c a l ) 表示法。原来的横向( h o r i z o n t a l ) 表示法是用一个事务中的项集来表示 数据，纵向表示法则是用包含某一项的事务集( r i d s ) 来表示。如：项a 在t 1 ，t 2 ， t 3 中出现，s u p ( a ) = 3 ；项b 在t 2 ，t 3 ，t 4 中出现，s u p ( b ) = 3 ；则项集a b 在t 2 ， t 3 中出现，s u p ( a b ) = 2 。 e c l a t 算法l l7 j 利用数据库的纵向表示，通过集合之间的交运算求频繁项集。 每个项对应一个t i d s e t ，组成一个t i d l i s t ，在求频繁项集时只需将两个t i d s e t 相 交，这样可以在判断是否为频繁项集的同时，又去掉不必要的项；将搜索空间 分成格，或更小的子格，就不必同时存储所有频繁项集的t i d s e t ，从而避免内存 溢出的可能。 d i f f s e t t l 8 】是z a k i 等人提出的一种对数据的纵向表示法。与e c l a t 算法不同， d i f f s e t 算法只保存候选模式与产生的频繁模式在事务集( t i d s ) 上的差集，这样可 以减少大量的存储空间；特别是对数据密集的情形，效果更为明显。d i f f s e t 算 法改善了e c l a t 算法当数据库稠密时，求交集会导致大量的冗余而浪费了很多 空间的缺点。 v i p e r ( v e r t i c a li t e m s e tp a r t i t i o n i n gf o re f f i c i e n tr u l e e x t r a e t i o n ) 算法【1 9 1 采 用了位向量来表示数据，并采用了许多方法对位向量生成、数据的交运算、计 数及存储等进行优化。v i p e r 算法改善了e c l a t 算法当数据库稀疏时，用数据 库垂直t i d s e t 表示占用较大的空间的缺点。 ( 3 ) f p g r o w t h 算法及改进算法 这一类算法也是深度优先搜索算法，采用树的结构压缩数据库。 j i a w e ih a n 在2 0 0 0 年提出了称作频繁模式增长或简称f p 增长的方法【2 0 1 。 算法采用分而治之的策略，在经过第一遍扫描之后，把数据库中的项集压缩进 一棵频繁模式树( f f t r e e ) ，同时依然保留其中的关联信息，随后再将f p t r e e 分化成一些条件库，每个库和一个长度为1 的频繁项集相关，然后再对这些条 件库分别进行挖掘。该算法只需扫描数据库两次，且不需要产生候选项集，有 效减少了i o 时间以及产生和测试候选项集需要耗费的时间。但是当数据库很 稀疏时，可以共享前缀的事务很少，几乎每条事务都要创建一个分支，所需内 存就会很大，递归地产生条件模式树和条件模式基，既耗费时间又耗费空间。 国内学者范明等1 2 i j 对f p g r o w t h 算法做了改进。他们认为f p g r o w t h 由于 需要不断地递归生成条件f p 树，影响了该算法的效率。因此他们提出了在f p 树挖掘中，不生成条件f p 树的频繁模式挖掘算法。该算法在挖掘时，直接利 6 用原f p 树的约束子树来进行挖掘。另外，该算法还减少了每一个结点域的个 数，只保留指向父结点的指针。 g r a h n e 等人【2 2 】也对f p g r o w t h 算法做了改进。由于在f p g r o w t h 算法中， 8 0 的时间用在了f p 树的遍历上，建立每棵条件f p 树需要遍历f p 树两次， 如果能减少遍历的时间则可以提高算法的效率。因此他们利用数组来存储条件 模式库的计数数据，在建立条件f p 树的同时计算以各个项为后缀的条件模式 库的计数数组值。从而对于每棵条件f p - 树的建立，只需对f p 树遍历一次。 ( 4 ) t r e e p r o j e c t i o n 算法和o p p o r t u n e p r o je c t 算法 这两种算法都是宽度搜索与深度搜索相结合的挖掘算法。 t r e e p r o j e c t i o n 算法【2 3 】采用字典树( l e x i c o g r a p h i ct r e e ) 作为数据存储框架， 并将数据库中的事务投影到树中。t r e e p r o j e c t i o n 算法主要采用了广度优先的策 略来建立树，并与深度优先的策略相结合进行事务投影和计数。在频繁项集的 计算过程中，还利用矩阵进行频度计算。 国内学者刘君强等人提出的o p p o r t u n e p r o j e c t 算法【2 4 】，根据局部数据集的 特性动态地决定对数据库采用基于树的虚拟投影或者基于数组的非过滤投影， 从而较好地解决了提高效率与节省空间的矛盾。该算法主要采用深度优先的搜 索方法，但必要的时候也会先用宽度优先方法建立树的最上几层。 1 3 2 基于分布式系统的并行挖掘算法 ( 1 ) c d 算法、d d 算法和c a d 算法 a g r a w a l 等给出了关联规则挖掘的三种并行算法【2 5 1 ，它们对候选集频度计 算采用了不同策略，一是计数分布c d ( c o u n td i s t r i b u t i o n ) 算法，二是数据分布 d d ( d a t ad i s t r i b u t i o n ) 算法，三是候选集分布c a d ( c a n d i d a t ed i s t r i b u t i o n ) 算 法。在c d 算法中，每个节点都要在本地数据库中对所有候选项集计数，然后 交换计数信息，得到全局计数。在d d 算法中，每个节点分别计算互不相交的 候选项集，各个节点之间需将各自处理的分区的数据传送给其它所有节点。c a d 算法在每一轮的计算中，通过把数据和候选集都划分到每一个节点，使每一个 节点都能独立地进行计算。这三种算法各有利弊，c d 算法交换的数据量较少， 但内存的利用率不高；d d 算法的内存利用率较好，但处理器之间需要交换大 量的数据；c a d 算法实现了异步计算，但需要对数据库进行重新分配。 ( 2 ) i d d 算法和h d 算法 i d d ( i n t e l l i g e n td a t ad i s t r i b u t i o n ) 算法【2 6 】是改进的d d 算法。i d d 算法根据 集合的首项来分割候选集，因此每个处理器只需处理事务中那些以相应项为起 始的子集，从而减少了d d 算法中的冗余计算，另外i d d 还采用了环结构来降 低通信负载。但是，对哈希树的静态划分导致了负载不平衡，这在处理器数量 较多时是很严重的问题。h d ( h y b r i dd i s t r i b u t i o n ) 算法【2 6 】将c o u n td i s t r i b u t i o n 7 和i d d 相结合，通过动态地将处理器分组，再根据分组将候选集划分以达到负 载平衡。这样就很好地解决了i d d 算法的问题。 ( 3 ) f d m 算法和d d d m 算法 为了减少分区间的通讯量，d w c h e u n g 在1 9 9 6 年对c d 算法进行了改进， 提出了f d m 算法【2 7 1 。f d m 算法在每个分区运行a p r i o r i 算法，找出局部大项 集，然后在每个节点全局大项集之间进行支持度合计数交换，每一次扫描后节 点间的通讯量为0 ( n ) 。f d m 算法是在一种无共享资源的环境下设计的，即各个 节点之间形成一个网状拓扑结构的网络环境【2 9 1 。s c h u s t e r 等人提出的d d d m 算 法1 2 8 】是一种改进的f d m 算法。该算法在f d m 算法的基础上使每次迭代的通信 开销降的更低，且不依赖于站点数。 ( 4 ) s d a m 算法 国内的黄贤英等在f d m 算法的基础上提出了一种基于星型网络的分布式 关联规则挖掘算法s d a m ( s t a r b a s e dd i s t r i b u t e da s s o c i a t i o nr u l e sm i n i n g a l g r i t h m ) p0 。s d a m 算法同f d m 的区别在于，发现一个节点中局部大项集并 不是发往各个节点，而是同中心节点进行信息交换。算法在各节点点利用局部 剪枝技术，而在中心节点利用全局剪枝技术。从网络的建设成本以及网络的管 理和维护方面与f d m 系统采用的网状结构相比较，s d a m 具有成本低且易于 管理的优点。 ( 5 ) d m a 算法 d m a ( d i s t r i b u t em i n ga s s o c i a t i o n ) 3 1 】，顾名思义该算法是针对分布式数据 环境设计的，与c d 算法一样，要在各节点中保存全体候选项集。d m a 算法充 分利用了分布式数据环境的数据分布特点( 数据局部性) ，大大消减了候选集数 量，但它要求各计算机间同步次数较多。 ( 6 ) p d m 算法 基于d h p 的思想，p a r k 等人提出了p d m ( p a r a l l e ld a t am i n i n g ) 算、法t 3 2 】。p d m 算法类似于c d 算法，所有节点含有相同的杂凑表和候选集，每一个节点通过 交换候选集的支持度计数来计算全局的频繁项集。p d m 算法实现了杂凑表构成 的并行，还应用了候选集分布剪枝和全局剪枝技术来减少每次迭代中候选集的 数量。 ( 7 ) d s a m p l i n g 算法 d s a m p l i n g 算法【3 3 】是并行的s a m p l i n g 算法，它是针对完全不共享的机群 ( c l u s t e r ) 系统设计的。该算法只需扫描数据库一次，优于此前发表的其他算法。 该算法不仅通过将数据库分到多台机器而减少了一次扫描的磁盘i o 时间，而 且通过组合内存线性地增加了样本的数目。该算法具有很好的可扩展性，但是 产生的结果不精确是它的最大缺点。 ( 8 ) d a s m 算法 d a s m ( d i s t r i b u t e da s s o c i a t i o nr u l em i n i n gw i t hs a m p l i n ga n dm e t a - l e a r n i n g ) 算法【3 4 】结合抽样技术和元学习策略，是一种不共享内存的分布式关联规则挖掘 算法。首先，各站点根据用户给定的误差值和概率值计算样本大小，并对本地 数据库进行随机抽样得到样本集，然后在每个样本集上应用动态项集计数技术 进行计数，得到局部的估计频繁项；然后将这些估计频繁项作为元知识，利用 分组并行计数的学习策略对它们进行学习，得到全局频繁项集。并且通过引入 相似度的概念，提高了挖掘的精确度。d a s m 算法具有较高的挖掘效率和较低 的通信量，适用于对效率要求较高的应用领域。 ( 9 ) f m a g f 算法 国内学者杨明等提出的f m a g f ( f a s tm i n i n go fg l o b a lf r e q u e n ti t e m s e t s ) 算法1 3 5 是基于f p g r o w t h 的并行挖掘算法。该算法思想为：各节点通过全局频 繁1 项集建立本地的f p t r e e ，再挖掘各节点的f p t r e e 获得全局频繁项集。 f m a g f 算法采用传送条件频繁模式树或条件模式基来挖掘全局频繁项目集， 减小了网络通信量，提高了全局频繁项目集挖掘效率。 ( 1 0 ) i n v e r t e dm a t r i x 算法 e i h a j j 等人提出了一种基于反转矩阵( i n v e r t e dm a t r i x ) 的算法【3 6 1 ，该算 法首先将数据库映射为一个基于磁盘的反转矩阵，以避免对数据库的多次扫描。 然后针对反转矩阵赋予每个并行节点的频繁项，建立c o f i ( c o o c c u r r e n c e f r e q u e n ti t e m ) 树，利用c o f i 树挖掘频繁项目集。算法简单而非递归的挖掘过 程减少了对内存的占用，并且在产生全局模式时无须各节点之间的通信。 1 3 3 基于共享存储系统的并行挖掘算法 ( 1 ) c c p d 算法 z a k i 等提出的c c p d ( c o m m o nc a n d i d a t ep a r t i t i o nd a t a b a s e ) 算法【3 7 】是在 共享内存的系统上实现的。c c p d 算法能够并行产生候选项集，并把候选集存 储在同一个哈希树中，所有处理机共享一棵哈希树。每个处理机扫描自己的数 据库逻辑划分，计算共享哈希树中的候选项集的支持度。无需为了产生全局支 持度而进行归纳操作。该算法采用锁机制来实现杂凑树生成过程的并行。 ( 2 ) a p m 算法 c h e u n g 等提出的a p m ( a s y n c h r o n o u sp a r a l l e lm i n i n g ) 算法p 8 】是基于的 d i c 并行算法，对数据扭曲非常敏感，并且认为数据是同构的。在a p m 算法 中，采用全局修剪技术来减小候选2 项集的大小，这在存在大的数据扭曲的时 候非常有效。在第一次循环中，数据库被逻辑划分为大小相等的块，对每个分 块执行局部支持计数，然后对它们进行群集，用以生成候选2 项集。接下来， 数据库被划分为同构的分块，每个处理器在局部分块上独立地执行d i c 算法。 ( 3 ) m l f p t 算法 9 m l f p t ( m u l t i p l el o c a lf r e q u e n tp a t t e r nt r e e ) 算法p 别是基于f p g r o w t h 的并 行挖掘算法，它是在共享内存的有6 4 个处理器的s g i 系统上实现的。m l f p t 算法只需对数据库进行两次扫描，避免了生成大量候选集的问题，而且通过在 挖掘过程的不同阶段采用不同的划分策略实现最佳的负载平衡。在频繁模式树 ( f p t r e e ) 生成阶段，数据库被划分为大小均等的分块，每个节点生成一个局部 频繁模式树( 1 0 c a lf p t r e e ) 。在挖掘阶段，所有节点共享这些局部频繁模式树， 并生成相应的频繁1 项集的条件库，很大程度上减少了资源竞争的现象。 1 4 本文工作概述 目前，应用广泛的两大类并行计算机体系结构是以工作站机群( c o w ，也 称c l u s t e r ) 为代表的分布式存储系统和以对称多处理机( s m p ) 为代表的共享 存储系统。本文对并行关联规则挖掘算法的研究就是在这两类并行计算机体系 结构下进行的。 基于分布式存储系统的研究工作：本文对传统的挖掘频繁项集的并行算法 进行了研究和探讨，分析了传统并行算法的优劣。对传统的c a d 算法进行了改 进，设计了一种多次传送重新分配数据的并行算法( m r p d ) 。通过理论证明了