文档介绍：挖掘关联规则的并行算法
SC02011028 苏媛媛
摘要: 挖掘关联规则是数据挖掘领域的一个重要问题。文中对挖掘关联规则问题进行了简单的回顾,对已提出的挖掘关联规则的并行算法进行了较全面的总结,对他们的性能进行了分析,并提出了三种新的挖掘关联规则的并行算法,对他们的性能作了简要分析,给出了优化策略。第一种:设计了一个效率较高的并行挖掘关联规则的算法 PMAR;并与其它相应算法进行了比较。实验证明,算法 PMAR是有效的。第二种:提出一种新的并行算法 NA,不管大项集的最大长度是多少,他只需 2次同步就能得到结果,当大项集的最大长度比较大时, NA会显示出更好的性能。第三种:介绍了一种改进的基于Apriori算法的挖掘关联规则的并行算法,并和以前提出的DD算法进行了比较。这种改进的算法IDD克服了以前提出的DD算法的缺点,消除了DD算法中的工作冗余。
关键字:并行算法关联规则大项集集群格
引言
数据挖掘(Data Mining)就是从大量的日常业务数据中发掘出有用的信息。关联规则的挖掘(ARM)是数据挖掘的一项重要的任务。其目的就是从事务数据库、关系数据库中发现项目集或属性之间的相关性,关联关系,因果关系。关联规则可描述如下:D是一个事务数据库,其中每一个事务 T由一些项目(Item)构成,并且都有一个唯一的标识(TID)。项目的集合简称项目集(item set),含有 k个项目的项目集称为 k_ 项目集。项目集 X的支持度(support)是指在事务数据库 D中包含项目集 X的事务占整个事务的比例,记为sup(X)。可信度(confidence)是指在事务数据库 D中,同时含项目集 X和 Y的事务与含项目集 X的事务的比,即 sup(X∪Y)/sup(X)。项目集中长度为 k的子集称为 k_ 子项目集。如果一个项目集不是任何其它项目集的子集则称此项目集为极大项目集。如果项目集的支持度大于用户指定的最小支持度(min_ sup)则称此项目集为频繁项目集(frequent item set)或大项集(large itemset)。关联规则可形式化表示为 X=>Y,它的含义是(X∪ Y)的支持度 sup(X∪ Y)大于用户指定的最小支持度 min_ sup,且可信度 conf大于用户指定的最小可信度 min_ conf。关联规则挖掘就是在事务数据库 D中找出满足用户指定的最小支持度 min_ sup和最小可信度 min_ conf的所有关联规则。挖掘任务可分为两个子问题:
1. 找出事务数据库中所有的大项集。
2. 从大项集中产生所有大于最小可信度的关联规则。相对来说,第二个子问题比较容易,目前大多数研究主要集中于第一个子问题。
关联规则描述虽然简单,但它的计算量是很大的。假设数据库含 m个项目,就有 2m个子集可能是频繁子集,可以证明要找出某一大项集是一个 NP问题。当 m较大时,要穷尽搜索每一个子集几乎是不可能的,另一方面,处理数据库中存储的大量记录要求繁重的磁盘 I/O操作。因此,随着数据库规模的不断增大,数据属性向高维发展,传统的顺序挖掘算法很难适应大规模、可扩展(scalability)的挖掘需要,发展高性能的并行算法是解决这一问题的关键。
相关工作
Apriori算法及其并行化
Apriori算法是由 Agrawal等人〔1〕提出的,算法思想主要依据支持度有“向下封闭”的特性。即,如果一个项目集是大项集,那么它的子集也是大项集。所以 k_ 大项集的候选项目集可通过合并(k-1)_ 大项集构成。
算法首先对数据库进行搜索,找出所有的频繁项目,即1_ 大项集。接着从 1_ 大项集中产生 2_ 大项集的候选集。然后进行第二次数据库搜索得出候选项目集的支持度,保留那些支持度大于 min_ sup的项目集,搜索结束时,得出 2_ 大项集。这个过程重复进行,每一次迭代,保留大项集用于生成下一次
迭代的候选集。直到找出所有的大项集。基于 Apriori、Agrawal和 Shafer在〔2〕中提出了三种并行算法:Count Distribution算法、Data Distribution算法和Candidate Distribute算法。这些算法的前提是处理器有专用内存和磁盘,而结构上没有任何共享。处理器用通信网络连接,靠消息传递进行通信。数据平均分配到每个处理器的专用磁盘上。
这些算法需要用到的符号意义如表 1。
· Count Distribution算法
Count Distribution是 Apriori的一个简单并行化算法。算法是通过分割数据库来完成并行化的。如果有 N个处理器节点,则各节点获得数据库的 1/N,然后分别在各数据库子集上完成类似于 Apriori的算法。
k