文档介绍：..页眉.. 页脚.. 并行频繁项集挖掘算法综述陈晓云赵娟(兰州大学信息科学与工程学院兰州 730000 ) 摘要: 本文介绍了并行频繁项集挖掘算法的研究概况, 对一些经典的并行频繁项集挖掘算法进行了分析和评价,在文章的最后对并行频繁项集挖掘进行了展望。关键字:并行化;频繁项集;数据挖掘; Abstract: This paper introduces the parallel frequent itemset mining algorithm, some typical parallel frequent itemset mining algorithm were analysed and evaluated. At the end of the article some future directions in parallel frequent itemset mining were discussed. Key words: parallel ; frequent itemset ; data mining; 1 引言国内外许多的研究工作者都对频繁项集的挖掘表现出极大的兴趣, 至今已经研究出许多频繁项集挖掘算法, 其中最为经典的两个算法就是由 和 于 1994 年提出的 Apriori 算法和 J. Han 等人 2000 年提出的 FP-Growth 算法。频繁项集挖掘的算法大多都是基于这两种算法的原理,被分为类 Apriori 算法和类 FP-Growth 算法。由于数据挖掘在开始被提出时就是面向海量数据的, 庞大的搜索空间使得许多传统的数据挖掘算法的效率并不理想。高性能并行环境为数据挖掘的发展开辟了一条新的路径, 研究并行环境下的数据挖掘并行算法成为了数据挖掘界的热点。频繁项集挖掘也不例外, 经过这些年的研究,并行化的频繁项集挖掘算法已经取得了一些成果。目前已有许多工作者致力于研究并行频繁项集挖掘算法, 并已有一些成绩。其中影响力比较大的包括 等人提出的类 Apriori 算法的并行算法 Count Distribution , Data Distribution 和 Candidate Distribution Methods , 2004 年 Osmar R. Zai ane 等人提出的 MLFP T 算法和 Javed 和 Khokhar 等人提出的 PFP-tree 算法, 分别是基于共享内存和分布式内存的类 FP-Growth 并行化频繁项集挖掘算法。 2 频繁项集挖掘的基本概念定义 2-1 ( 支持度与置信度)设I= {I 1,I 2,…,I m} 是项的集合。设任务相关的数据库 D 是数据库事务的集合,其中每个事务 T 是项的集合, T I ?。每一个事务有一个标识符,称作 TID 。设 A 是一个项集( itemset ) ,也称模式( pattern ) ,事物 T 包含 A 当且仅当 A T ?。关联规则是形如 A B ?的蕴含式,其中 A I ?, B I ?,并且 A B ? ??。规则 A B ?在事务集 D 中成立,是由支持度( support ) sup 和置信度( confidence ) conf 来约束的。其中 sup 是