文档介绍：并行频繁项集挖掘算法综述
陈晓云赵娟
(兰州大学信息科学与工程学院兰州 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 引言
国内外许多的研究工作者都对频繁项集的挖掘表现出极大的兴趣,至今已经研究出许多频繁项集挖掘算法,-Growth算法。频繁项集挖掘的算法大多都是基于这两种算法的原理,被分为类Apriori算法和类FP-Growth算法。
由于数据挖掘在开始被提出时就是面向海量数据的,庞大的搜索空间使得许多传统的数据挖掘算法的效率并不理想。高性能并行环境为数据挖掘的发展开辟了一条新的路径,研究并行环境下的数据挖掘并行算法成为了数据挖掘界的热点。频繁项集挖掘也不例外,经过这些年的研究,并行化的频繁项集挖掘算法已经取得了一些成果。
目前已有许多工作者致力于研究并行频繁项集挖掘算法,并已有一些成绩。 Distribution,Data Distribution和Candidate Distribution Methods,2004年Osmar R. Zaiane等人提出的MLFPT算法和Javed和Khokhar等人提出的PFP-tree算法,分别是基于共享内存和分布式内存的类FP-Growth并行化频繁项集挖掘算法。
2 频繁项集挖掘的基本概念
定义2-1 (支持度与置信度)设I = {I1, I2,…,Im }是项的集合。设任务相关的数据库D是数据库事务的集合,其中每个事务T是项的集合,。每一个事务有一个标识符,称作TID。设A是一个项集(itemset),也称模式(pattern),事物T包含A当且仅当。关联规则是形如的蕴含式,其中,,并且。规则在事务集D中成立,是由支持度(support)sup和置信度(confidence)conf来约束的。其中sup是D中事务包含的百分比,即P(),conf是D中包含A的事务同时也包含B的百分比。即P()。即
support()= P()
confidence()= P()
定义2-2 (频繁k-项集)设I={I1,I2,…,Im}为项的集合,其中Ij(j=1,2,…,m)表示一个项