一種有效的并行頻繁子圖挖掘算法

1、一種有效的并行頻繁子圖挖掘算法陳曉云 趙娟 陳鵬飛 邢喬金 劉國華（蘭州大學(xué)信息科學(xué)與工程學(xué)院 蘭州 730000）摘要：在分析并行頻繁項(xiàng)集挖掘算法的基礎(chǔ)上，提出了一種有效的并行頻繁子圖挖掘算法，該并行算法采用主從節(jié)點(diǎn)處理模式，將主節(jié)點(diǎn)處理后生成的頻繁子樹集放到從節(jié)點(diǎn)上并行的生成頻繁子圖。通過實(shí)驗(yàn)驗(yàn)證了算法的可行性和有效性。關(guān)鍵字：并行化；頻繁項(xiàng)集；頻繁子圖；Abstract：Based on the analysis of the parallel frequent itemset mining algorithm, a kind of effective parallel algorith

2、m for mining frequent subgraph is introduced in this paper. The parallel algorithm adopts a master-slave node processing mode，put the frequent subtree sets which generated by the master node on the slave node which parallel generate frequent subgraph.The results of the experiments show that our algo

3、rithm has good effectiveness and feasibility.Key words: parallel; frequent itemset; frequent subgraph1. 引言：頻繁子圖挖掘與其他比較成熟的頻繁模式挖掘相比，圖結(jié)構(gòu)數(shù)據(jù)所包含的信息比一般的數(shù)據(jù)類型的數(shù)據(jù)量更大,其數(shù)據(jù)結(jié)構(gòu)比線性表和樹更為復(fù)雜。在圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系是任意的，任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。盡管其結(jié)構(gòu)很復(fù)雜，但是由于基于圖的應(yīng)用越來越廣泛，其已經(jīng)滲入到諸如語言學(xué)、邏輯學(xué)、物理、化學(xué)、計(jì)算機(jī)科學(xué)及數(shù)學(xué)的這些分支學(xué)科中。如通過對(duì)已有的生物分子結(jié)構(gòu)與未知的生物結(jié)構(gòu)的研究，來確定未

4、知生物分子與已知生物分子之間的聯(lián)系與區(qū)別。例如在PTE(predictive toxicology evaluation challenge)項(xiàng)目中找到頻繁出現(xiàn)的而且與已有的有毒物質(zhì)具有相同子結(jié)構(gòu)的物質(zhì)，這樣就可以發(fā)現(xiàn)新的對(duì)人體有害的物質(zhì)。因此，對(duì)基于圖的頻繁子圖挖掘的算法研究是非常必要的，而且具有很好的實(shí)際應(yīng)用價(jià)值。在通常情況下，由于沒有任何先驗(yàn)知識(shí)做參考，頻繁子圖的挖掘工作量會(huì)很大。對(duì)于海量數(shù)據(jù)的挖掘任務(wù)來講，現(xiàn)有的頻繁子圖挖掘算法速度比較慢，而且效率不高，因此沒有得到廣泛的應(yīng)用。所以研究出一個(gè)算法效率高，執(zhí)行速度快的頻繁子圖挖掘算法是目前一個(gè)非常熱門的話題。 本文在分析以往的并行頻繁項(xiàng)集

5、挖掘算法的基礎(chǔ)上，提出了一種并行頻繁子圖發(fā)掘算法PG-Miner。該挖掘算法采用主從模式，將整個(gè)過程分為兩部分，第一部分由主處理節(jié)點(diǎn)來生成頻繁子樹集，然后將生成的子樹集分發(fā)到其他從處理節(jié)點(diǎn)。第二部分將頻繁子圖邊擴(kuò)展及同構(gòu)判斷這部分頻繁子圖挖掘算法中時(shí)間復(fù)雜度最高的部分并行處理。文章在最后通過實(shí)驗(yàn)驗(yàn)證了本算法的有效性和可行性。2. 并行頻繁項(xiàng)集挖掘綜述頻繁模式挖掘的搜索空間可以被模擬成類似格的結(jié)構(gòu)，其中由模式的大小來決定它處于格中的哪一層，每一層又以某種順序進(jìn)行排列。模式格的維數(shù)決定了問題的指數(shù)級(jí)別。例如，對(duì)于一個(gè)有著n個(gè)不同項(xiàng)的事務(wù)數(shù)據(jù)庫，可能的模式就會(huì)有2n。也就是說，如果一個(gè)事務(wù)數(shù)據(jù)庫有1

6、00個(gè)不同的項(xiàng)，搜索空間就達(dá)到21001030。巨大的搜索空間使得在大型數(shù)據(jù)庫上的頻繁模式的挖掘成為一個(gè)計(jì)算密集型問題。然而傳統(tǒng)的頻繁模式挖掘算法被單一處理器和有限的內(nèi)存空間所限制，不適用于大型數(shù)據(jù)庫。因此，利用高性能并行計(jì)算來改善現(xiàn)有頻繁模式挖掘算法的瓶頸，使其適用于大規(guī)模數(shù)據(jù)庫是非常必要的。在FP-Growth算法的基礎(chǔ)上，2001年Osmar R. Zaiane等人提出了并行頻繁項(xiàng)集挖掘算法MLFPT， 2004年Javed和Khokhar等人提出了并行頻繁項(xiàng)集挖掘算法PFP-tree。2.1 MLFPT算法Zaane.O.R等人于2001年提出基于共享式內(nèi)存的類FP-Growth的并行

7、頻繁項(xiàng)集挖掘算法MLFPT。此算法對(duì)FP-Growth算法中的FP-Tree進(jìn)行了并行化的改進(jìn)。在整個(gè)執(zhí)行過程中僅需掃描數(shù)據(jù)庫兩次，建立了一個(gè)特殊的數(shù)據(jù)結(jié)構(gòu)叫做頻繁模式樹（Frequent Pattern Tree），之后在上面挖掘頻繁項(xiàng)集。由于一顆在并行節(jié)點(diǎn)上共享的樹結(jié)構(gòu)勢必需要在葉子或節(jié)點(diǎn)甚至路徑上設(shè)置鎖機(jī)制，這樣就會(huì)導(dǎo)致嚴(yán)重的瓶頸。于是，MLFPT算法中采取了將FP-Tree分成塊到每個(gè)節(jié)點(diǎn)上，而保持結(jié)果樹是各節(jié)點(diǎn)上共享的來避免假負(fù)現(xiàn)象。建立這樣的樹大大減少了生成頻繁項(xiàng)集的開銷。這些樹上的頻繁項(xiàng)都是交叉連接起來的（與FP-Tree中相同），并且總體上連接在一個(gè)全局頭表上。每塊樹森林（tr

8、ee forest）被分配到各個(gè)處理節(jié)點(diǎn)上，分開后的FP-Tree在挖掘過程中被自下向上的順序快速遍歷。樹的位置降低了并行節(jié)點(diǎn)間由于錯(cuò)誤的操作而覆蓋其他節(jié)點(diǎn)更新的可能性，同時(shí)使得死鎖的可能性最小化。但是基于共享式內(nèi)存的并行頻繁項(xiàng)集不能夠適用于廣泛使用的集群系統(tǒng)，因此局限性比較大。2.2 PFP-tree算法Javed和Khokhar等人于2004年提出了分布式內(nèi)存環(huán)境下的類FP-Growth并行頻繁項(xiàng)集挖掘算法PFP-Tree。算法中將整個(gè)數(shù)據(jù)庫分割成不重合的p塊，其中p是處理節(jié)點(diǎn)的數(shù)量。然后將各個(gè)數(shù)據(jù)塊分配給相應(yīng)的處理節(jié)點(diǎn)。PFP-tree算法的具體步驟如下：1 各節(jié)點(diǎn)p掃描被分配的數(shù)據(jù)塊并

9、且計(jì)算本地?cái)?shù)據(jù)庫塊中的頻繁項(xiàng)的支持度。2 所有處理節(jié)點(diǎn)做同步得到總體的頻繁項(xiàng)支持度計(jì)數(shù)。3 各節(jié)點(diǎn)依據(jù)總的支持度來排序頻繁項(xiàng)，并刪除非頻繁項(xiàng)。4 各節(jié)點(diǎn)第二次掃描本地?cái)?shù)據(jù)庫塊并建立本地FP-tree。5 頭表被分成p個(gè)互不相交的子集，每個(gè)處理節(jié)點(diǎn)為被分配到的項(xiàng)的集合并行挖掘頻繁模式。6 由于第5步中的劃分是靜態(tài)的，每個(gè)處理節(jié)點(diǎn)必須通過其他的節(jié)點(diǎn)來確認(rèn)本地樹上的信息。在第4步被分配到一個(gè)節(jié)點(diǎn)上的單頻繁前綴分支構(gòu)成了挖掘步的完整信息。利用一次自底向上的掃描來進(jìn)行確認(rèn)信息。7 第6步中確認(rèn)的信息利用一個(gè)遞歸的歸并樹結(jié)構(gòu)在各節(jié)點(diǎn)上將需要進(jìn)行次通訊。在每一次通訊的最后，一個(gè)節(jié)點(diǎn)需要解包收到的信息到本地的

10、FP-tree樹上，然后為下一次歸并準(zhǔn)備新的信息。8 每個(gè)處理節(jié)點(diǎn)挖掘被分配的頻繁項(xiàng)集。由于PFP-tree需要各節(jié)點(diǎn)交換基于每個(gè)頻繁1-項(xiàng)集的條件模式基來得到本地所需的數(shù)據(jù)分塊，所以整個(gè)算法的通訊還是比較多的，降低了并行的效率。3. 并行頻繁子圖挖掘算法PG-Miner為了提高并行效率并且減少算法的通訊量，我們提出了一個(gè)頻繁子圖挖掘算法，該挖掘算法采用主從模式，將整個(gè)過程分為兩部分，第一部分由主處理節(jié)點(diǎn)來生成頻繁子樹集，然后將生成的子樹集分發(fā)到其他從處理節(jié)點(diǎn)。第二部分將頻繁子圖邊擴(kuò)展及同構(gòu)判斷這部分頻繁子圖挖掘算法中時(shí)間復(fù)雜度最高的部分并行處理。3.1 主節(jié)點(diǎn)頻繁子樹挖掘算法FTGenFTG

11、en(frequent subtree generation)算法第一步判斷要擴(kuò)展的頻繁子樹是否為最小DFS 編碼，來避免對(duì)重復(fù)生成的子樹做進(jìn)一步擴(kuò)展。第二步通過對(duì)頻繁邊集中的每條邊進(jìn)行擴(kuò)展判斷。第三步將已提取的邊從邊集中去掉，減小需要擴(kuò)展的邊集，第四步判斷當(dāng)前提取的邊是否為樹邊ee，如果是，將其加入到DFS編碼最小的頻繁子樹t中。第五步判斷在頻繁子樹T中是否存在t的同構(gòu)子樹。如果不存在，將t加入到結(jié)果集T中。第六步對(duì)擴(kuò)展后的t執(zhí)行FTGen算法以得到全部頻繁子樹。FTGen 的挖掘結(jié)果是圖集GS中出現(xiàn)的頻繁子樹，儲(chǔ)存在集合T中。頻繁子樹將被用于進(jìn)一步對(duì)邊擴(kuò)展以形成圖，同時(shí)，頻繁子樹作為圖的一

12、種，是最終挖掘結(jié)果的子集。算法偽代碼如Algorithm 3-1所示：3.2 從節(jié)點(diǎn)子圖拓展挖掘算法PFGGen算法PFGGen在FTGen算法的基礎(chǔ)上做進(jìn)一步挖掘，主要是從頻繁子樹向頻繁子圖的擴(kuò)展過程。第一步由于FTGen本身生成的頻繁子樹也是最終結(jié)果的一部分，故需要將其也加入到結(jié)果集中。第二步將T中的頻繁子樹按降序DFS編碼排序，并且對(duì)T中每顆子樹做擴(kuò)展成圖的處理。第三步先將當(dāng)前需要擴(kuò)展的子樹初始化到圖g，然后對(duì)頻繁邊集中的每條邊ee做擴(kuò)展處理，將已提取要擴(kuò)展的邊從邊集中去掉。第四步判斷當(dāng)前邊是否可擴(kuò)展，如果當(dāng)前邊可以擴(kuò)展，擴(kuò)展這條邊。第五步判斷擴(kuò)展后的圖是否滿足最小DFS編碼的要求，避免

13、重復(fù)操作。第六步判斷擴(kuò)展的圖在結(jié)果集中是否存在同構(gòu)子圖，如果不存在，將擴(kuò)展的子圖加入到結(jié)果集。算法偽代碼如Algorithm 3-2所示：3.3 PG-Miner算法PG-Miner算法第一步初始化MPI并行環(huán)境并且計(jì)算用于此次并行計(jì)算的所有節(jié)點(diǎn)。第二步判斷是否為主節(jié)點(diǎn)，掃描圖集并找到圖集GS中所有頻繁邊，并刪除圖集中所有非頻繁邊，將所有頻繁邊集按DFS編碼和支持度降序排列，初始化擴(kuò)展子樹t。第三步調(diào)用FTGen算法，獲得頻繁子樹集。第四步調(diào)用PFGGen算法，擴(kuò)展頻繁子樹到頻繁子圖。第五步結(jié)束MPI。PG-Miner算法偽代碼如Algorithm 3-3所示：4. 實(shí)驗(yàn)結(jié)果與分析實(shí)驗(yàn)環(huán)境：由

14、 5臺(tái)2.8 GHz Intel Core CPU，2GB內(nèi)存的PC機(jī)搭建MPI環(huán)境，機(jī)子之間的通信采用千兆路由器實(shí)現(xiàn)，操作系統(tǒng)為內(nèi)核2.6.31-14的Ubuntu Karmic Koala ( Ubuntu 9.10 )。所有程序均用GCC3.4.3和MPI庫mpich2-1.0.7編譯實(shí)現(xiàn)。在實(shí)驗(yàn)中，我們分別選取真實(shí)數(shù)據(jù)和仿真數(shù)據(jù)來與gSpan，F(xiàn)FSM作比較，gSpan和FFSM都是在單臺(tái)機(jī)子運(yùn)行，我們的算法啟動(dòng)4個(gè)從節(jié)點(diǎn)來計(jì)算。數(shù)據(jù)可從以下網(wǎng)址獲得：/docs/aids/aids_data.html。圖4-1，4-2，4-3給出了在不同數(shù)據(jù)集

15、上gSpan，F(xiàn)FSM，PG-Miner的運(yùn)行結(jié)果圖4-1 CA數(shù)據(jù)集圖4-2 CM數(shù)據(jù)集圖4-3 CI數(shù)據(jù)集仿真數(shù)據(jù)我們采用文獻(xiàn)16Kuramochi和Karypis提供的工具產(chǎn)生的數(shù)據(jù)集。我們選取了兩個(gè)參數(shù)集來測試我們的結(jié)果，第一個(gè)設(shè)置N=10(N代表可能的節(jié)點(diǎn)標(biāo)識(shí)數(shù))，T=40(T代表每個(gè)圖的平均邊數(shù))，D=10000(D代表生成圖的數(shù)量)，I=7(I代表可能生成的頻繁子圖的平均大小)；另一個(gè)數(shù)據(jù)集設(shè)置T=40，N=5，D=10000，I=7。圖4-4，4-5在不同數(shù)據(jù)集上gSpan，F(xiàn)FSM，PG-Miner的運(yùn)行結(jié)果圖4-4 N10I7T40數(shù)據(jù)集圖4-5 N5I7T40數(shù)據(jù)集在下面

16、，我們將PG-Miner在從節(jié)點(diǎn)個(gè)數(shù)為2和從節(jié)點(diǎn)為4時(shí)在CA上的運(yùn)行結(jié)果也展示出來，用來分析我們的算法在處理節(jié)點(diǎn)擴(kuò)展時(shí)的可擴(kuò)展性，圖4-6給出了運(yùn)行結(jié)果。圖4-6 CA數(shù)據(jù)集圖4-1到4-3為了能更加清晰的列出結(jié)果，我們采用了對(duì)數(shù)值。在這幾個(gè)真實(shí)數(shù)據(jù)集上，我們比較了從支持度3%到9%，在圖上我們可以看到，在支持度很小時(shí)，PG-Miner算法的運(yùn)行時(shí)間僅是FFSM的1/4多一點(diǎn)，這說明PG-Miner運(yùn)行效率提高了接近n(處理節(jié)點(diǎn)數(shù))倍。但當(dāng)支持度增加時(shí)，PG-Miner算法的運(yùn)行時(shí)間在4s左右，甚至出現(xiàn)高于FFSM的情況，這說明此時(shí)，MPI環(huán)境的啟動(dòng)開銷和通信開銷已經(jīng)成為程序運(yùn)行的主要時(shí)間，在

17、這種情況下，并不適合PG-Miner算法。圖4-4和4-5是在模擬數(shù)據(jù)集上得到的運(yùn)行結(jié)果，我們比較了支持度從1%到6%，由結(jié)果可以得到與真實(shí)結(jié)果集上相同的結(jié)論。圖4-6在CA數(shù)據(jù)集上處理節(jié)點(diǎn)分別為2和4時(shí)，我們比較了支持度從1%到6%的運(yùn)行結(jié)果，從運(yùn)行結(jié)果可以看出，PG-Miner具有很好的可擴(kuò)展性。5. 結(jié)論本文在研究以往并行頻繁項(xiàng)集挖掘算法的基礎(chǔ)，提出了并行頻繁子圖挖掘算法PG-Miner。該算法成功的將頻繁子圖挖掘算法中時(shí)間復(fù)雜度最高的子圖同構(gòu)判斷過程分發(fā)到多臺(tái)處理器上并行處理，使得算法的執(zhí)行時(shí)間隨處理節(jié)點(diǎn)的線性增加而線性減少。并且在不同的真實(shí)和模擬數(shù)據(jù)集上驗(yàn)證了算法的可行性。另外算法在

18、并行化方面，如何提高并行粒度，使得各處理節(jié)點(diǎn)負(fù)載更加均衡以及如何減少子圖同構(gòu)的判斷是我們下一步的研究方向。文獻(xiàn)：1 范明，孟曉峰.數(shù)據(jù)挖掘概念與技術(shù)第2版2 王丹陽，田衛(wèi)東，胡學(xué)剛.一種有效的并行頻繁項(xiàng)集挖掘算法.計(jì)算機(jī)應(yīng)用研究.1001-3695(2008)11-3332-03 3 王永恒，楊樹強(qiáng)，賈 焰.海量文本數(shù)據(jù)庫中的高效并行頻繁項(xiàng)集挖掘方法.計(jì)算機(jī)工程與科學(xué).1007-130X(2007)09-0110-044 張大為，黃丹，嵇敏，謝福鼎.利用模式指導(dǎo)樹的并行頻繁項(xiàng)集挖據(jù)方法.計(jì)算機(jī)工程與應(yīng)用.1002-8331（2010）22-0147-045 Fiedler, M. and Bo

19、rgelt, C.: 2007, Support computation for mining frequent subgraphs in a single graph, in P. Frasconi, K. Kersting and K. Tsuda (eds), MLG.6 X. Yan and J. Han, “gSpan: Graph-Based Substructure Pattern Mining,” Proc. 2002 Intl Conf. Data Mining (ICDM 02), pp. 721- 724, Dec. 2002.7 Wu, J. and Chen, L.:

20、 Mining Frequent Subgraph by Incidence Matrix Normalization. Journal of Computers 3(10)(2008) 109115.8 C. Wang and S. Parthasarathy. Parallel algorithms for mining frequent structural motifs in scientific data. In Proceedings of the ACM International Conference on Supercomputing (ICS), 2004.9 T. Mei

21、nl, I. Fischer, and M. Philippsen. Parallel mining for frequent fragments on a shared-memory multiprocessor -results and java-obstacles-. In M. Bauer, A. Kroner, and B. Brandherm, editors, LWA 2005 - Beitrage zur GI-Workshopwoche Lernen, Wissensentdeckung, Adaptivitat, pages 196201, 2005.10 M. Kuramochi and G. Karypis. Frequent subgraph discovery. In Proceedings of the Internation Conference on Data Mining (ICDM), pages 31