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