1、并行頻繁項集挖掘算法綜述陳曉云 趙娟（蘭州大學信息科學與工程學院 蘭州 730000）摘要：本文介紹了并行頻繁項集挖掘算法的研究概況，對一些經典的并行頻繁項集挖掘算法進行了分析和評價，在文章的最后對并行頻繁項集挖掘進行了展望。關鍵字：并行化；頻繁項集；數據挖掘；Abstract: This paper introduces the parallel frequent itemset mining algorithm, some typical parallel frequent itemset mining algorithm were analysed and evaluated. At t

2、he end of the article some future directions in parallel frequent itemset mining were discussed.Key words: parallel; frequent itemset; data mining;1 引言國內外許多的研究工作者都對頻繁項集的挖掘表現出極大的興趣，至今已經研究出許多頻繁項集挖掘算法，其中最為經典的兩個算法就是由R.Agrawal和R.Srikant于1994年提出的Apriori算法和J.Han等人2000年提出的FP-Growth算法。頻繁項集挖掘的算法大多都是基于這兩種算法的原理

3、，被分為類Apriori算法和類FP-Growth算法。由于數據挖掘在開始被提出時就是面向海量數據的，龐大的搜索空間使得許多傳統的數據挖掘算法的效率并不理想。高性能并行環境為數據挖掘的發展開辟了一條新的路徑，研究并行環境下的數據挖掘并行算法成為了數據挖掘界的熱點。頻繁項集挖掘也不例外，經過這些年的研究，并行化的頻繁項集挖掘算法已經取得了一些成果。目前已有許多工作者致力于研究并行頻繁項集挖掘算法，并已有一些成績。其中影響力比較大的包括R.Agrawal等人提出的類Apriori算法的并行算法Count Distribution，Data Distribution和Candidate Distri

4、bution 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中成立，是由支持度（suppo

5、rt）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)表示一個項。集合被稱為項集，如果。如果|X|=k，則X被稱為k-項集。項集X的支持度是中包含X的事務數占所有事務數的百分比，它是概率P(X)，記為：sup(X)。給定事務數據庫和最小支持度閾值，如果，則項集X被稱為頻繁項集，如果|X|=k，則X被稱為頻繁k-項集。定義2-3 （閉頻繁

6、項集和極大頻繁項集）如果不存在真超項集Y使得Y與X在S中有相同的支持度計數，則稱項集X在數據集S中是閉合的。如果X在S中是閉合的和頻繁的，則項集X是數據集S中的閉頻繁項集。如果X是頻繁的，并且不存在超項集Y使得并且Y在S中是頻繁的，則項集X是S中的極大頻繁項集。3 并行頻繁項集挖掘算法頻繁模式挖掘的搜索空間可以被模擬成類似格的結構，其中由模式的大小來決定它處于格中的哪一層，每一層又以某種順序進行排列。模式格的維數決定了問題的指數級別24。比如，對于一個有著n個不同項的事務數據庫，可能的模式就會有2n。也就是說，如果一個事務數據庫有100個不同的項，搜索空間就達到21001030。巨大的搜索空間

7、使得在大型數據庫上的頻繁模式的挖掘成為一個計算密集型問題。然而傳統的頻繁模式挖掘算法被單一處理器和有限的內存空間所限制，不適用于大型數據庫。因此，利用高性能并行計算來改善現有頻繁模式挖掘算法的瓶頸，使其適用于大規模數據庫是非常必要的。R.Agrawal等人在Apriori算法的基礎上提出了并行算法Count Distribution，Data Distribution和Candidate Distribution Methods。2004年Osmar R. Zaiane等人提出的MLFPT算法和Javed和Khokhar等人提出的PFP-tree算法則是基于FP-Growth算法的并行頻繁項集

8、挖掘算法。下面將一一介紹這些經典算法。3.1 Count Distribution算法Count Distribution算法（以下簡稱CD算法）主要聚焦于最小化節點間的通訊。此算法使用了一種在其他空閑處理器上進行冗余的并行計算來避免節點間通訊的原則。CD算法的第一遍是特殊的。第一遍時，每個處理器Pi根據分配在本地數據分塊Di中的項動態地生成其本地候選項集。因此，不同的處理器的候選項計數可能是不同的，所以必須通過交換本地計數來確定總體的C1。對于所有的k>1遍，CD算法的具體步驟如下：1. 在第k-1遍的最后利用完全頻繁項集Lk-1，在每個處理器Pi生成完全候選集Ck。2. 處理器Pi掃

9、描一遍它的數據分塊Di并得到本地Ck的支持度計數。3. 處理器Pi與所有其他處理器交換本地Ck支持度計數來得到總的Ck支持度計數。這一步處理器之間被強迫進行同步。4. 每個處理器Pi從Ck得到Lk。5. 每個處理器Pi獨立地決定需要繼續下一次迭代還是結束。當所有處理器都有相同的Lk時迭代結束。在這個算法中，只有第3步是與傳統的Apriori算法有區別的。這一步的目的在于交換本地支持度計數來得到全局支持度計數。由于每個處理器上的候選項集Ck是相同的，實際上所要做的就是每個處理器將其本地計數按順序放入一個計數數組，然后執行一個并行的向量匯總。這個步驟消耗的時間僅為。3.2 Data Distrib

10、ution算法CD算法利用只交換支持度計數而不用交換數據元組這樣的大的數據結構來減少通訊開銷，但是它沒有有效的利用內存空間。Data Distribution算法（以下簡稱DD算法）則被設計用來在處理器數量增加的時候充分有效地利用系統內存空間。DD算法的第一遍迭代跟CD算法相同，對于所有的k>1遍，DD算法的具體步驟如下：1. 處理器Pi利用Lk-1產生Ck。僅僅保留項集中的1/N個項集來形成候選子集。究竟哪1/N個項集被保留是由處理器的編號來確定的。集合均是相交的，所有集合的并集就是總體的Ck。2. 處理器Pi利用本地數據頁和從其他處理器上接受到的數據頁來計算本地候選集的支持度計數。3

11、. 在掃描完數據時，每個Pi利用本地計算。然后，所有的集合做交集得到總體Lk。4. 處理器之間交換使得所有的處理器都獲得總體Lk來為下一步生成Ck+1做準備。這一步執行處理器的同步操作。獲得Lk的處理器獨立的決定繼續進行下一步還是結束迭代。此算法的第二步，處理器之間廣播它們的本地數據并接收其他處理器的數據，這是一個通訊量非常大的工作，因此，此算法僅適用于具有很快通訊速度的機器。3.3Candidate Distribution算法CaD算法綜合了DD和CD算法,以彌補它們各自的不足。CaD算法在前l步采用DD算法或CD算法;到第l步(其中l由啟發而定),為了減少各節點之間的數據依賴,算法對大項

12、集Ll-1進行分配,同時也對數據進行重新分配,使Pi能獨立于其他節點生成Cik(k>l,CikCjk= ,ij)。為了減少節點對候選集的依賴,CaD算法不等待從其他節點傳來完整的剪枝信息,它盡可能快地剪枝,而滯后到達的剪枝信息在下一次剪枝時使用。對于所有的k<1，采用DD算法或者CD算法。對于所有的k=1，CaD算法的具體步驟如下：1. N個處理器中的，是平衡的。我們討論怎么分割。記錄和在中的每一個頻繁項集，哪一個處理器被分配來處理這個頻繁項集。這個分割在每一個處理器上都是并行的。2. 處理器Pi生成，邏輯上僅僅使用分割來完成它。注意到Pi仍然接近完成，因此可以使用標準剪枝操作，在

13、這個過程中生成。3. Pi產生全局計數在中產生候選。同時數據庫被重新分配到。4. 當Pi處理完所有的本地數據以及從其他全部處理器接收的數據，它布置N-1異步接收緩沖來接收從所有其他處理器。這些需要剪枝，在產生候選項集的剪枝步。5. 處理器Pi利用計算，異步發送它到其他的N-1個處理器使用N-1異步發送。對于所有的k>1，CaD算法的具體步驟如下：1. 處理器Pi收集所有的頻繁項集發送給其他處理器。這些頻繁項集被用在產生候選項集的剪枝步，而不是添加步。從處理器j得到的項集，長度可以是k-1，或者小于k-1（比較慢的處理器）或者是大于k-1（比較快的處理器）。Pi保持跟蹤每個處理器pj產生最

14、大長度的頻繁項集。接收頻繁項集的緩沖區在處理完后重新后置處理。2. 處理器Pi利用本地來計算。Pi沒有從其他處理器收到，所以Pi在剪枝時應該注意。它需要區分一個項集（一個長度為k-1的候選項集的子集）并不存在于一個項集的任何，而是存在于一些。但是這個集合還沒有被Pi接收到。它這么做通過探索（重新分配發生在第l遍）使用在問題中長度為l-1的項集的前綴，發現處理器對它是可靠的，并且檢查是否被處理器接收。3. Pi通過DRi執行一遍并且計算。然后利用計算并且異步的傳播到每一個其他處理器使用N-1異步發送。3.4MLFPT算法由于類Apriori算法的兩個主要缺點，使得算法不能夠適用于海量數據庫。Za

15、ïane.O.R等人于2001年提出基于共享式內存的類FP-Growth的并行頻繁項集挖掘算法MLFPT。此算法對FP-Growth算法中的FP-Tree進行了并行化的改進。在整個執行過程中僅需掃描數據庫兩次，建立了一個特殊的數據結構叫做頻繁模式樹（Frequent Pattern Tree），之后在上面挖掘頻繁項集。由于一顆在并行節點上共享的樹結構勢必需要在葉子或節點甚至路徑上設置鎖機制，這樣就會導致嚴重的瓶頸。于是，MLFPT算法中采取了將FP-Tree分成塊到每個節點上，而保持結果樹是各節點上共享的來避免假負現象。建立這樣的樹大大減少了生成頻繁項集的開銷。這些樹上的頻繁項都是交

16、叉連接起來的（與FP-Tree中相同），并且總體上連接在一個全局頭表上。每塊樹森林（tree forest）被分配到各個處理節點上，分開后的FP-Tree在挖掘過程中被自下向上的順序快速遍歷。樹的位置降低了并行節點間由于錯誤的操作而覆蓋其他節點更新的可能性，同時使得死鎖的可能性最小化。基于共享式內存的并行頻繁項集不能夠適用于廣泛使用的集群系統，因此局限性比較大。3.5PFP-Tree算法Javed和Khokhar等人于2004年提出了分布式內存環境下的類FP-Growth并行頻繁項集挖掘算法PFP-Tree。算法中將整個數據庫分割成不重合的p塊，其中p是處理節點的數量。然后將各個數據塊分配給相

17、應的處理節點。PFP-tree算法的具體步驟如下：1. 各節點p掃描被分配的數據塊并且計算本地數據庫塊中的頻繁項的支持度。2. 所有處理節點做同步得到總體的頻繁項支持度計數。3. 各節點依據總的支持度來排序頻繁項，并刪除非頻繁項。4. 各節點第二次掃描本地數據庫塊并建立本地FP-tree。5. 頭表被分成p個互不相交的子集，每個處理節點為被分配到的項的集合并行挖掘頻繁模式。6. 由于第5步中的劃分是靜態的，每個處理節點必須通過其他的節點來確認本地樹上的信息。在第4步被分配到一個節點上的單頻繁前綴分支構成了挖掘步的完整信息。利用一次自底向上的掃描來進行確認信息。7. 第6步中確認的信息利用一個遞

18、歸的歸并樹結構在各節點上將需要進行次通訊。在每一次通訊的最后，一個節點需要解包收到的信息到本地的FP-tree樹上，然后為下一次歸并準備新的信息。8. 每個處理節點挖掘被分配的頻繁項集。由于PFP-tree需要各節點交換基于每個頻繁1-項集的條件模式基來得到本地所需的數據分塊，所以整個算法的通訊還是比較多的，降低了并行的效率。3.6 其他并行頻繁項集挖掘算法3.6.1 HPFP-Miner算法HPFP-Miner算法是2009年由IDM實驗室陳曉云、何艷珊，陳鵬飛等人提出來的一種分布式并行環境下的并行化的頻繁項集挖掘算法。該算法的主要貢獻有以下幾個方面：1 算法提出了兩個適用于并行環境的數據結

19、構HPFP-tree和HPFP-forest。HPFP-tree是一種類FP-tree，各節點上的HPFP-tree通過指針鏈接成為HPFP-forest。通過兩次數據庫掃描，將數據庫的頻繁項集信息壓縮到各節點上的HPFP-forest上。2 算法利用了一種主從模式的并行方法，利用一個主節點來掃描數據庫，然后將建樹信息分發到各分節點，各分節點通過被分配的建樹信息建立HPFP-tree和HPFP-forest。3 提出了并行挖掘頻繁項集的算法HPFP-Miner，挖掘階段不需要節點間通訊和同步，各節點只需要挖掘本地的HPFP-forest，然后通過一個共享文件指針將挖掘結果統一到一個共享文件中。

20、HPFP-Miner算法采用了一種主從模式的并行方法，由主節點掃描數據庫得到所有頻繁項的集合，之后主節點按算法中的順序，依次將建樹的信息發到各子節點。而在算法任務最集中的挖掘階段，則完全不需要節點間的通訊。由于不是平行模式，不需要將數據庫分塊，有效地避免了挖掘階段各節點間進行同步的通訊消耗。將節點間的通訊集中在建樹階段，而在最耗時的挖掘階段有效地避免了通訊，這樣就大大提高了算法的并行效率。3.6.2 MRPD算法 MRPD算法是2009年由合肥工業大學王丹陽等人提出來的一種有效的并行化頻繁項集的挖掘算法。該算法的步驟如下所示MRPD算法采用固定的l值和空閑節點申請計算任務的方式,克服了CaD算

21、法找不到合適的l值而引起的各節點間負載不平衡的缺點;也克服了當數據分布不夠均勻或者節點的運算能力相差很大的情況下,CD算法的同步代價非常大的缺點。MRPD算法采用較小的固定l值,并在l步后是一種異步算法, 降低了節點間的依賴。通過理論分析和實驗測試可知,MRPD算法是一種應用廣泛的有效算法。4 并行頻繁項集挖掘展望目前并行頻繁項集挖掘取得了很大的成績，但是在許多方面還有待進一步研究。1）負載平衡問題，一個好的負載平衡算法可以保證各節點間負載分配的平衡，從而降低發生過載的可能性，確保程序的可用性和系統的可靠性，同時能夠在一定程度上抵御負載峰值的沖擊。同時，好的負載平衡方法可以最小化系統的通信開銷

22、。2）內存開銷問題，在生成候選頻繁項集的時候盡可能一次性直接生成后面的步驟直接使用避免過多的臨時內存消耗。3）節點間通訊的問題，減少數據庫的掃描次數，減少候選項集的產生，采用主從模式或者分布式模式，減少節點計算中的同步通訊。參考文獻1 范明，孟曉峰.數據挖掘概念與技術第2版2王丹陽，田衛東，胡學剛.一種有效的并行頻繁項集挖掘算法.計算機應用研究.1001-3695(2008)11-3332-033王永恒，楊樹強，賈 焰.海量文本數據庫中的高效并行頻繁項集挖掘方法.計算機工程與科學.1007-130X(2007)09-0110-044 張大為，黃丹，嵇敏，謝福鼎.利用模式指導樹的并行頻繁項集挖據

23、方法.計算機工程與應用.1002-8331（2010）22-0147-045 王艷輝，吳斌，王柏.頻繁子圖挖掘算法綜述.計算機科學.2005 Vol.32 No.10.6 魯慧民，馮博琴，宋擒豹.頻繁子圖挖掘研究綜述.微電子學與計算機. 1000-7180（2009）03-0156-067 阮幼林，李慶華，劉干.分布環境中的并行頻繁模式挖掘算法.計算機工程與應用. 1002-8331（2005）25-0001-038 R. Agrawal, J. C. Shafer. Parallel Mining of Association Rules. IEEE Trans. Knowledge and Data Eng., 1996, 8(6): 962-969.9 Zaïane O R, El-Hajj M, Lu P. Fast Parallel Association Rule Mining without Candidacy Generation. In Proceedings of the 2001 IEEE international Conference on Data M