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