文档介绍：并行频繁项集挖掘综述并行频繁项集挖掘算法综述陈晓云赵娟(兰州人学信息科学与工程学院兰州730000)摘要:木文介绍了并行频繁项集挖掘算法的研究概况,对-些经典的并行频繁项集挖掘算法进行了分析和评价,在文章的最后对并行频繁项集挖掘进行了展望。关键字:并行化;频繁项集;数据挖掘;Abstract:Thispaperintroducestheparallelfrequentitemsetminingalgorithm,sometypicalparal1elfrequentitemsetminingalgoriLhmwereanalysedandevaluated・Attheendofthearticlesomefuturedirectionsinparallelfrequentitemsetminingwerediscussed・Keywords:para11e1;frequentitemset;datamining;1引言国内外许多的研究工作者都对频繁项集的挖掘表现出极人的兴趣,至今已经研究出许多频繁项集挖掘算法,其中最为经典的两个算法就是由R・・Han等人2000年提出的FP-Growth算法。频繁项集挖掘的算法大多都是基于这两种算法的原理,被分为类Apriori算法和类FP-Growth算法。由于数据挖掘在开始被提出吋就是血向海量数据的,庞人的搜索空间使得许多传统的数据挖掘算法的效率并不理想。高性能并行环境为数据挖掘的发展开辟了一•条新的路径,研究并行环境卞的数据挖掘并行算法成为了数据挖掘界的热点。频繁项集挖掘也不例外,经过这些年的研究,并行化的频繁项集挖掘算法已经取得了一•些成果。日前已有许多工作考致力于研究并行频繁项集挖掘算法,并已有一些成绩。,DataDistribution和CandidateDistributionMethods,-tree算法,分别是基于共享内存和分布式内存的类FP-Growth并行化频繁项集挖掘算法。2频繁项集挖掘的基木概念定义2-1(支持度与置信度)设I二{II,12,-,Im}是项的集合。设任务相关的数据库D是数据库事务的集合,其屮每个事务T是项的集合,TIo每一个事务有一个标识符,称作TID。设A是一个项集(itemset),也称模式(pattern),事物T包含A当且仅当ATo关联规则是形如AB的蕴含武,其小AI,BI,并且AB。规则AB在事务集D中成立,是由支持度(support)sup和置信度(confidence)conf来约束的。其中sup是D中事务包含AB的百分比,即P(AB),8吐是1)屮包含A的事务同吋也包含B的百分比。即P(B|A)o即support(AB)=P(AB)confidence(AB)=P(B|A)定义2-2(频繁k-项集)设I二{11,12,…,Im}为项的集合,其中Ij(j=l,2,-,m)表示—•个项。集合X被称为项集,如果XI。如果|X|=k,则X被称为k-项集。项集X的支持度是D中包含X的事务数占所有事务数的百分比,它是概率P(X),记为:sup(X)o给定事务数据库D和最小支持度阈值,如果sup(X),则项集X被称为频繁项集,如果|x|=k,则X被称为频繁k-项集。定义2-3(闭频繁项集和极人频繁项集)如果不存在真超项集Y使得Y与X在S屮有相同的支持度计数,则称项集X在数据集S小是闭合的。如果乂在“卩是闭合的和频繁的,则项集X是数据集S中的闭频繁项集。如果X是频繁的,并且不存在超项集Y使得XY并且Y在S屮是频繁的,则项集X是S屮的极人频繁项集。3并彳丁频繁项集挖掘算法频繁模式挖掘的搜索空间可以被模拟成类似格的结构,其小由模式的人小来决定它处于格小的哪一层,每一层又以某种顺序进行排列。模式格的维数决定了问题的指数级别[24]。比如,对于一个有着n个不同项的事务数据库,可能的模式就会有2n。也就是说,如果一个事务数据库有100个不同的项,搜索空间就达到21001030o巨人的搜索空间使得在人型数据库上的频繁模式的挖掘成为一个计算密集型问题。然而传统的频繁模式挖掘算法被单一处理器和有限的内存空间所限制,不适用于人型数据库。因此,利用高性能并行计算来改善现有频繁模武挖掘算法的瓶颈,使具适川于人规模数据库是非常必要的。,DataDistribution和CandidateDis