資源描述：
《并行頻繁項集挖掘綜述》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、并行頻繁項集挖掘算法綜述陳曉云趙娟（蘭州大學(xué)信息科學(xué)與工程學(xué)院蘭州730000）摘要：本文介紹了并行頻繁項集挖掘算法的研究概況，對一些經(jīng)典的并行頻繁項集挖掘算法進(jìn)行了分析和評價，在文章的最后對并行頻繁項集挖掘進(jìn)行了展望。關(guān)鍵字：并行化；頻繁項集；數(shù)據(jù)挖掘；Abstract:Thispaperintroducestheparallelfrequentitemsetminingalgorithm,sometypicalparallelfrequentitemsetminingalgorithmwerean
2、alysedandevaluated.Attheendofthearticlesomefuturedirectionsinparallelfrequentitemsetminingwerediscussed.Keywords:parallel;frequentitemset;datamining;1引言國內(nèi)外許多的研究工作者都對頻繁項集的挖掘表現(xiàn)出極大的興趣，至今已經(jīng)研究出許多頻繁項集挖掘算法，其中最為經(jīng)典的兩個算法就是由R.Agrawal和R.Srikant于1994年提出的Apriori算法和J.
3、Han等人2000年提出的FP-Growth算法。頻繁項集挖掘的算法大多都是基于這兩種算法的原理，被分為類Apriori算法和類FP-Growth算法。由于數(shù)據(jù)挖掘在開始被提出時就是面向海量數(shù)據(jù)的，龐大的搜索空間使得許多傳統(tǒng)的數(shù)據(jù)挖掘算法的效率并不理想。高性能并行環(huán)境為數(shù)據(jù)挖掘的發(fā)展開辟了一條新的路徑，研究并行環(huán)境下的數(shù)據(jù)挖掘并行算法成為了數(shù)據(jù)挖掘界的熱點。頻繁項集挖掘也不例外，經(jīng)過這些年的研究，并行化的頻繁項集挖掘算法已經(jīng)取得了一些成果。目前已有許多工作者致力于研究并行頻繁項集挖掘算法，并已有一些成
4、績。其中影響力比較大的包括R.Agrawal等人提出的類Apriori算法的并行算法CountDistribution，DataDistribution和CandidateDistributionMethods，2004年OsmarR.Zaiane等人提出的MLFPT算法和Javed和Khokhar等人提出的PFP-tree算法，分別是基于共享內(nèi)存和分布式內(nèi)存的類FP-Growth并行化頻繁項集挖掘算法。2頻繁項集挖掘的基本概念定義2-1（支持度與置信度）設(shè)I={I1,I2,…,Im}是項的集合。設(shè)任
5、務(wù)相關(guān)的數(shù)據(jù)庫D是數(shù)據(jù)庫事務(wù)的集合，其中每個事務(wù)T是項的集合，。每一個事務(wù)有一個標(biāo)識符，稱作TID。設(shè)A是一個項集（itemset），也稱模式（pattern），事物T包含A當(dāng)且僅當(dāng)。關(guān)聯(lián)規(guī)則是形如的蘊(yùn)含式，其中，，并且。規(guī)則在事務(wù)集D中成立，是由支持度（support）sup和置信度（confidence）conf來約束的。其中sup是D中事務(wù)包含的百分比，即P（），conf是D中包含A的事務(wù)同時也包含B的百分比。即P（）。即support（）=P（）confidence（）=P（）定義2-2（頻繁
6、k-項集）設(shè)I={I1,I2,…,Im}為項的集合，其中Ij(j=1,2,…,m)表示一個項。集合被稱為項集，如果。如果
7、X
8、=k，則X被稱為k-項集。項集X的支持度是中包含X的事務(wù)數(shù)占所有事務(wù)數(shù)的百分比，它是概率P(X)，記為：sup(X)。給定事務(wù)數(shù)據(jù)庫和最小支持度閾值，如果，則項集X被稱為頻繁項集，如果
9、X
10、=k，則X被稱為頻繁k-項集。定義2-3（閉頻繁項集和極大頻繁項集）如果不存在真超項集Y使得Y與X在S中有相同的支持度計數(shù)，則稱項集X在數(shù)據(jù)集S中是閉合的。如果X在S中是閉合的和頻繁的，則項
11、集X是數(shù)據(jù)集S中的閉頻繁項集。如果X是頻繁的，并且不存在超項集Y使得并且Y在S中是頻繁的，則項集X是S中的極大頻繁項集。3并行頻繁項集挖掘算法頻繁模式挖掘的搜索空間可以被模擬成類似格的結(jié)構(gòu)，其中由模式的大小來決定它處于格中的哪一層，每一層又以某種順序進(jìn)行排列。模式格的維數(shù)決定了問題的指數(shù)級別[24]。比如，對于一個有著n個不同項的事務(wù)數(shù)據(jù)庫，可能的模式就會有2n。也就是說，如果一個事務(wù)數(shù)據(jù)庫有100個不同的項，搜索空間就達(dá)到21001030。巨大的搜索空間使得在大型數(shù)據(jù)庫上的頻繁模式的挖掘成為一個計算
12、密集型問題。然而傳統(tǒng)的頻繁模式挖掘算法被單一處理器和有限的內(nèi)存空間所限制，不適用于大型數(shù)據(jù)庫。因此，利用高性能并行計算來改善現(xiàn)有頻繁模式挖掘算法的瓶頸，使其適用于大規(guī)模數(shù)據(jù)庫是非常必要的。R.Agrawal等人在Apriori算法的基礎(chǔ)上提出了并行算法CountDistribution，DataDistribution和CandidateDistributionMethods。2004年OsmarR.Zaiane等人提出的MLFPT算法和Javed和Kh
