基于布爾矩陣和MapReduce的FP-Growth 算法*

陳興蜀 張帥 童浩 崔曉靖

(四川大學(xué) 計算機學(xué)院，四川 成都 610065)

關(guān)聯(lián)規(guī)則挖掘(ARM)是數(shù)據(jù)挖掘領(lǐng)域中一個非常重要且具有挑戰(zhàn)性的研究課題.與其他數(shù)據(jù)挖掘算法相比，關(guān)聯(lián)規(guī)則挖掘具有挖掘效率高、準確性好、理解性強等優(yōu)點.通常，關(guān)聯(lián)規(guī)則挖掘和頻繁項集挖掘(FIM)密切相關(guān)，F(xiàn)IM 被認為是ARM 的先決條 件.ARM 常 用 的 算 法 有Apriori［1］、DHP［2-3］、DIC［4］、FP-Growth［5-6］等，在加速挖掘性能上，它們起著重要的作用.將這些算法應(yīng)用于FIM，已取得了許多成果.

近年來興起的云計算［7］以其超大規(guī)模、虛擬化、高可靠性、高擴展性等優(yōu)點為海量數(shù)據(jù)的處理帶來了新的解決方案.然而，目前針對云平臺下的FIM的研究仍然很少.Gunopulos 等［8］已經(jīng)證明:判斷一個事務(wù)數(shù)據(jù)集中是否存在至少包括t 個項、支持度為min_sup 的頻繁項集是非確定性多項式(NP)完全問題.面對海量數(shù)據(jù)，單機模式下頻繁項集挖掘算法常常顯得力不從心［9］，減少數(shù)據(jù)庫掃描次數(shù)及并行掃描是提高效率的有效方法之一.因此，對FIM的并行計算和分布式計算已成為必然.Jiang 等［10］在Apriori 算法的基礎(chǔ)上，應(yīng)用向量元、子規(guī)則、父規(guī)則提高了關(guān)聯(lián)規(guī)則的挖掘效率.Korczak 等［11］使用FP-Growth 算法挖掘客戶交易行為，與Apriori 算法相比更具優(yōu)勢，但它們并沒有實現(xiàn)真正意義上的并行計算.MapReduce［12］是一種簡潔抽象的并行計算模型，Apache 基金會在此基礎(chǔ)上實現(xiàn)了開源的并行平臺Hadoop，該平臺已在學(xué)術(shù)界和工業(yè)界得到了廣泛 的 應(yīng) 用.OPT-DIC［13］、MR-Apriori［14］、Apriori-like算法［15］與其他分布式Apriori 算法相比具有更好的性能和可伸縮性，但同步和通信等開銷較大.為此，Yu 等［16］在Hadoop 平臺上改進了Apriori 算法，盡管能處理一定的海量數(shù)據(jù)，但需要的時間并沒有線性地減少，同時需要生成候選集才能產(chǎn)生最終的頻繁集，并且該算法對事務(wù)數(shù)據(jù)的掃描次數(shù)也沒有減少.PFP 算法［17］在FP-Growth 算法的基礎(chǔ)上實現(xiàn)了并行化，按照項集劃分數(shù)據(jù)，但需要掃描兩次事務(wù)數(shù)據(jù)，在多個并行的節(jié)點上產(chǎn)生FP 樹，不能實現(xiàn)數(shù)據(jù)的實時處理.

文中針對大規(guī)模海量數(shù)據(jù)，在Hadoop 并行平臺上實現(xiàn)了基于布爾矩陣和MapReduce 的FP-Growth(BPFP)算法，并通過實驗驗證了該算法的有效性.

1 相關(guān)概念

1.1 布爾矩陣

記Ωn={1，2，…，n}.

定義1 設(shè)矩陣A=(aij)m×n，若滿足aij{0，1}，(i，j)= Ωm×Ωn，則稱A 為布爾矩陣.令為第k(k ≥1)個布爾矩陣，=(a(mk+1)j)1×n為一維矩陣且，記，若a(mk+1)j=，ε為最小支持度，則稱為A 的第k 個擴展布爾矩陣(EBM)，^A 為擴展向量.記Ti(iΩmk+1)和Ij(jΩn)分別為EBM的第i 個行向量和第j 個列向量，為了表述方便，Ti和Ij在關(guān)聯(lián)規(guī)則中分別代表事務(wù)名稱和項集名稱.

定義2 設(shè)Ii、Ij是擴展布爾矩陣A=(aij)m×n的列向量，構(gòu)造轉(zhuǎn)置元向量t= (1，1，…，1，0，則ωi=Ii·t 為Ii(關(guān)聯(lián)規(guī)則中)在A 中出現(xiàn)的總次數(shù);ωij= Ii·Ij- ami·amj，為(Ii，Ij)序列在A 中出現(xiàn)的總次數(shù).

考慮到EBM 中元素的過濾，文中給出合取運算符∧的定義.

定義3 設(shè)aij、akj為擴展布爾矩陣A=(aij)m×n的元素，i，kΩm，定義

EBM 用于代替事務(wù)數(shù)據(jù)庫，運算符∧用于過濾非頻繁項集.

1.2 FP-Growth 算法

設(shè)I= {I1，I2，…，Im}是項目集合，T= {T1，T2，…，Tn}是一個(數(shù)據(jù)庫)事務(wù)集合，事務(wù)Ti是項目的集合，Ti?I(iΩn).A(A ?I)的支持度sup(A)為T中包含A 的事務(wù)數(shù).如果sup(A)≥ε，則A 是頻繁項集.

FP-Growth 算法是一種FIM 算法，在挖掘頻繁項集過程中需要掃描兩次數(shù)據(jù)集:第1 次掃描是為了找出頻繁1-項集的集合F1和支持度，并將F1按支持度遞減的順序插入表頭項(記為L);第2 次掃描是利用頻繁1-項集過濾數(shù)據(jù)庫中的非頻繁項，同時生成FP 樹.將候選集壓縮到FP 樹上，可以大幅壓縮候選集的規(guī)模.FP-Growth 算法發(fā)現(xiàn)所有頻繁項集的過程如下:①構(gòu)造頻繁模式樹FP 樹;②在FP樹上調(diào)用挖掘算法挖掘所有頻繁項集.研究表明:對于挖掘長和短的頻繁模式，F(xiàn)P-Growth 算法均是有效和可規(guī)?；模⑶移溥\算速度大約比Apriori 算法快一個數(shù)量級.因此，并行的FP-Growth 算法具有更快的運算效率，這是合乎邏輯的.

為了建立FP 樹的路徑、模式與布爾矩陣、EBM之間的聯(lián)系，文中定義項的偏序關(guān)系“?”，以建立項與序號1∶1 的關(guān)系.

定義4 對于任意項Ii，IjI，Ii?Ij當且僅當Ii對應(yīng)的序號小于Ij對應(yīng)的序號.Ii的序號為Ii在EBM中對應(yīng)的列序號.

定義5 設(shè)Lk={I1，I2，…，Ik-1}，IiT (iΩk-1)，HTID是由表頭項的ID 組成的集合，如果LkHTID，則稱Lk為項Ik的頻繁模式集.

定義6 局部FP 樹(LocalFPTree)是滿足下列條件的一個樹結(jié)構(gòu):

(1)它由一個根節(jié)點(值為null)、項前綴子樹Tlocal和一個局部頻繁項頭表LHTable 組成.

(2)每個節(jié)點包括3 個域(item_name、count 和node_link)，item_name 由Ik及其頻繁模式集組成，count 為支持度計數(shù)，node_link 是指向Tlocal中下一個具有相同項目節(jié)點的指針(無節(jié)點可鏈時為空).

(3)LHTable 的表項包括頻繁項Ik的頻繁模式集Lk、支持度計數(shù)(Tlocal中的總支持度計數(shù))、節(jié)點鏈的頭指針(指向模式樹中具有Lk的第一個節(jié)點).

如果Ik是LocalFPTree 的葉子節(jié)點，則稱Local FPTree 為TPTreek或者Ik的局部頻繁樹.圖1 給出了項I3的LocalFPTree，它所生成的頻繁項集是{{I3I2:4}，{I3I1:4}，{I3I2I1:2}}.

圖1 項I3 的LocalFPTree Fig.1 LocalFPTree of item I3

TPTreek的構(gòu)造算法描述如下:

{輸入:Ik的條件模式基、F1和LHTable

輸出:Ik的TPTreek

生成Ik的頻繁模式集Lk;

∥根據(jù)定義4 排列項集

初始化LHTable，每項的支持度計數(shù)為0，node_link為null;

創(chuàng)建根節(jié)點，以“null{}”標記;

改進的FP-Growth 算法描述如下:

初始化canpat{pattern:0};

找出item 中所有的條件模式基構(gòu)成

定理1 頻繁模式的挖掘FP 樹和各LocalFPTree 是等價的.

證明 設(shè)IkHTID，其局部頻繁樹為TPTreek，由定義6 可知，TPTreek中每個節(jié)點的item_name 是由Ik及其條件頻繁模式集組成.因此，TPTreek產(chǎn)生的頻繁模式等同于FP 樹挖掘項Ik的頻繁模式;由HTID中的元素對應(yīng)的LocalFPTree 所挖掘的頻繁模式組成的集合就是FP 樹中挖掘頻繁樹的集合.故頻繁模式的挖掘FP 樹和各LocalFPTree 是等價的.證畢.

對于圖1 中的事務(wù)集，未改進的FP-Growth 算法需要遞歸掃描FP 樹9 次，而改進FP-Growth 算法只需要掃描FP 樹6 次，降低了搜索FP 樹的時間代價;另外，TPTreek為并行挖掘奠定了基礎(chǔ).

2 BPFP 算法

2.1 MapReduce 并行計算模型

Hadoop 是一個能夠?qū)Υ罅繑?shù)據(jù)分布式處理的軟件架構(gòu)，其核心組件是HDFS 和MapReduce.MapReduce是運行在大規(guī)模集群上的分布式數(shù)據(jù)處理模型，其處理過程主要分為兩個階段:Map 和Reduce.MapReduce 模型的定義如下［14］:

Map(k1，v1)→list(k2，v2)，

Reduce(k2，list(v2))→list(v2)，

2.2 BPFP 算法的實現(xiàn)及分析

BPFP 算法是針對PF-Growth 算法并基于EBM和MapReduce 而提出的.該算法采用MapReduce 并行計算模型進行并行計算，可以提高計算的效率;使用擴展布爾矩陣可以減少算法在計算過程中對事務(wù)數(shù)據(jù)的掃描次數(shù).給定一個事務(wù)數(shù)據(jù)集T 和最小支持度ε，BPFP 算法使用兩個MapReduce 來實現(xiàn)頻繁項集的挖掘，具體流程見圖2.

圖2 BPFP 算法流程圖Fig.2 Flowchart of BPFP algorithm

設(shè)有k 個節(jié)點，BPFP 算法步驟如下:

(1)構(gòu)建布爾矩陣.將事務(wù)數(shù)據(jù)集T(m 個事務(wù)n 個項)轉(zhuǎn)換為布爾矩陣A=(aij)m×n(BPFP 算法僅在此訪問事務(wù)數(shù)據(jù)集，從而減少開銷)，當相關(guān)的項存在時aij為1，否則為0.

(2)分片.將A 劃分為k 塊(A1，A2，…，Ak)，除了Ak外其他每個分塊的數(shù)據(jù)大小相等.Hadoop 為每個分塊構(gòu)建一個Map 任務(wù).

(3)并行計數(shù).在每個Map 任務(wù)中，程序掃描對應(yīng)的布爾矩陣Ai，利用MapReduce 并行計算每個項的支持度ε'.并行計數(shù)的空間和時間復(fù)雜度均為

(4)排序.對頻繁1-項集按其支持度降序排序生成F_list.由于F_list 一般很小，因此通常將其放在內(nèi)存中.此步驟一般可以在單機上進行操作，其空間復(fù)雜度為

(5)并行FP-Growth.在Map 階段，對每一個Ai(iΩk)生成對應(yīng)的EBM.同時對EBM 的每行進行頻繁1-項集提取、排序操作，然后構(gòu)造每個項的條件模式基;在Reduce 階段，對于每個長度為1 的頻繁項集，根據(jù)其條件模式基構(gòu)建局部FP 樹，并對該局部FP 樹進行挖掘，最后生成頻繁模式.

BPFP 算法中使用了EBM，當事務(wù)數(shù)據(jù)集更新后，它不需要對原有的事務(wù)數(shù)據(jù)進行掃描，只需要掃描更新后的數(shù)據(jù)集，再更新EBM，因此可以降低掃描空間，提高算法效率，同時也能實現(xiàn)數(shù)據(jù)的實時處理.并行計數(shù)的偽代碼如下:

并行FP-Growth 算法的偽代碼如下:

3 實驗結(jié)果與分析

在BPFP 算法中采用EBM，可以減少系統(tǒng)的存儲開銷，提高數(shù)據(jù)訪問的效率，特別是對于海量數(shù)據(jù).假設(shè)I 由100 個項組成，T 有5 000 萬個交易記錄，即使每個項都是頻繁的，在EBM 中每個元素占1 B，EBM 共占5000 MB，與原事務(wù)數(shù)據(jù)大小相比，存儲空間占有率也變小了.如果對EBM 進行壓縮，實際的存儲空間占有率只有原來的十分之幾甚至更少.當對EBM 進行分塊時，得到的每個分塊完全可以存入內(nèi)存，這樣保證了后續(xù)的挖掘不再掃描原始事務(wù)數(shù)據(jù)集，有效地提高了挖掘效率.

文中實驗平臺的基本配置見表1，1 個NameNode，5 個DataNodes，操作系統(tǒng)均為CentOS release 5.6(Final).每個DataNode 設(shè)置的mapper 的最大負載(mapred.tasktracker.map.tasks.maximum)為2，Reducer 的最大負載(mapred.tasktracker.reduce.tasks.maximum)也為2，Hadoop 的其他配置采用默認方式.文中采用的測試數(shù)據(jù)集為挖掘頻繁項集領(lǐng)域常用的測試數(shù)據(jù)集［18］，如表2 所示.對數(shù)據(jù)集Connect、Accidents 和Webdocs 分別進行實驗;對相同的數(shù)據(jù)集，選擇不同的ε進行實驗.

表1 實驗配置Table 1 Configuration of experiment

使用數(shù)據(jù)集Webdocs2 和最小支持度為10%進行實驗，P-Apriori 算法［12］(也使用了布爾矩陣)與BPFP 算法的性能(執(zhí)行時間t 與節(jié)點數(shù)p 的關(guān)系)見圖3.與P-Apriori 算法相比，BPFP 算法僅需要掃描一次布爾矩陣，并且不會因為快速增長的候選集而需要大量的時間和空間開銷，因此BPFP 算法的時間開銷優(yōu)于P-Apriori 算法.

表2 測試數(shù)據(jù)集Table 2 Test datasets

圖3 BPFP 與P-Apriori 算法的性能比較Fig.3 Comparison of performance between BPFP algorithm and P-Apriori algorithm

對于同一事務(wù)數(shù)據(jù)集，BPFP 算法的頻繁項數(shù)Nf與支持度ε的關(guān)系如圖4 所示，即符合Zipf 法則:支持度越小，頻繁項數(shù)越大.因此，在并行FPGrowth 階段需要的時間開銷較大(見圖5).文中通過加速比和加速率指標來評估BPFP 算法的性能.

圖4 支持度與頻繁項集數(shù)的關(guān)系Fig.4 Support versus number of frequent item sets

圖5 同一數(shù)據(jù)集在不同支持度下的執(zhí)行時間Fig.5 Execution time of the same dataset with different supports

圖6 BPFP 算法在不同實驗條件下的加速比Fig.6 Speedup of BPFP algorithm under different experiment conditions

定義7 加速比Sp=t1/tp，其中t1是在單個節(jié)點上的執(zhí)行時間，tp是在p(p ≥1)個節(jié)點上的執(zhí)行時間.

定義8 加速率ks用于描述加速比的變化趨勢.設(shè)(Dni，Si)表示Dni個節(jié)點所對應(yīng)的加速比序列，其中，Dni{Ωn- Ωm}，n＞m，(m，n］為描述ks變化的自定義域，則

基于表1 的實驗環(huán)境，使用表2 中的數(shù)據(jù)集，分別在5 個數(shù)據(jù)節(jié)點上和ε為10%、20%、30%的情況下進行實驗，結(jié)果如圖6 所示.從圖可知:當數(shù)據(jù)集較小時，各個節(jié)點用于計算的時間較小，隨著數(shù)據(jù)節(jié)點數(shù)的增加，用于節(jié)點通信的時間開銷所占的比重越來越明顯;對于數(shù)據(jù)較大的節(jié)點，計算時間較長，用于節(jié)點通信的開銷所占的比重相對較小，因此圖6(a)、6(b)中加速率ks的增長不太明顯，趨于0(如圖6(b)中ks在ε為10%、20%、30%時分別為0.0508、0.025 8、0.023 2)，而圖6(c)、6(d)中在數(shù)據(jù)節(jié)點數(shù)小于3 時，ks較大(如圖6(d)中ks在ε為10%、20%、30%時分別為0.3700、0.3200、0.2550)，隨著數(shù)據(jù)節(jié)點數(shù)的增加，ks趨于0.因此，在規(guī)模較小的數(shù)據(jù)集中，BPFP 算法的數(shù)據(jù)交換成本太大，很快就達到阿姆達爾定律的限制;對于規(guī)模較大的數(shù)據(jù)集，數(shù)據(jù)交換成本所占比重降低，加速比表現(xiàn)更優(yōu)，故BPFP 算法在規(guī)模較大的數(shù)據(jù)集上的性能更優(yōu).

使用數(shù)據(jù)集Webdocs2 和最小支持度為10%進行實驗，BPFP 與PFP 算法［9］的執(zhí)行時間如圖7 所示.從圖中可知，當數(shù)據(jù)節(jié)點數(shù)較小時，BPFP 算法需要在EBM 和事務(wù)數(shù)據(jù)間相互映射，因此所需要的時間開銷較PFP 算法大;隨著數(shù)據(jù)節(jié)點數(shù)的增加，BPFP算法使用EBM 對事務(wù)數(shù)據(jù)進行壓縮，從而減少了節(jié)點間的通信開銷，因此所需要的時間開銷較PFP 算法小.

圖7 BPFP 與PFP 算法的執(zhí)行時間比較Fig.7 Comparison of execution time between BPFP algorithm and PFP algorithm

4 結(jié)論

文中基于布爾矩陣和MapReduce 提出了改進的FP-Growth 算法(BPFP 算法).該算法將事務(wù)數(shù)據(jù)集轉(zhuǎn)化為布爾矩陣存儲，不僅減少了算法對事務(wù)數(shù)據(jù)集的掃描次數(shù)，而且降低了數(shù)據(jù)的存儲空間.非遞歸地構(gòu)建FP 樹和掃描FP 樹會產(chǎn)生頻繁項集，可減少條件模式基和FP 樹的規(guī)模，從而降低算法的時間和空間開銷.MapReduce 為BPFP 算法提供了并行化框架，在很大程度上提高了算法的挖掘效率，使算法具有很好的拓展性、容錯性.實驗結(jié)果表明，BPFP算法是有效、可行的，能較大地提高執(zhí)行效率，具有較好的加速比及加速率.

對于規(guī)模較小的數(shù)據(jù)集，由于節(jié)點的通信開銷所占比重較大，故BPFP 算法與單機(單節(jié)點)模式算法相比沒有太大的優(yōu)勢.今后將針對小文件小數(shù)據(jù)的關(guān)聯(lián)挖掘的并行化進行研究，改進BPFP 算法在處理小文件小數(shù)據(jù)時的不足，使之同樣適用于高效的并行化數(shù)據(jù)挖掘.

［1］Agrawal R，Srikant R.Fast algorithms for mining association rules ［C］∥Proceedings of the 20th VLDB Conference.San Francisco:Morgan Kaufmann Publishers Inc，1994:487-499.

［2］Park J，Chen M，Yu P.Using a hash-based method with transaction trimming for mining association rules ［J］.IEEE Transactions on Knowledge and Data Engineering，1997，9(5):813-825.

［3］Zel S A，Guvenir H A.An algorithm for mining association rules using perfect hashing and database pruning［C］∥Proceedings of the 10th Turkish Symposium on Artificial Intelligence and Neural Networks.Berlin:Springer-Verlag，2001:257-264.

［4］Brin S，Motwani R，Ullman J D，et al.Dynamic itemset counting and implication rules for market basket data［C］∥Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data.New York:ACM，1997:255-264.

［5］Han Jiawei，Pei Jian，Yin Yiwen.Mining frequent patterns without candidate generation ［C］∥Proceedings of the2000 ACM SIGMOD International Conference on Management of Data.Dallas:ACM，2000:1-12.

［6］Han Jiawei，Pei Jian，Yin Yiwen，et al.Ming frequent patterns without candidate generation:a frequent-pattern tree approach［J］.Data Mining and Knowledge Discovery，2004，8(1):53-87.

［7］Aaron Weiss.Computing in the clouds ［J］.netWorker，2007，11(4):16-25.

［8］Gunopulos D，Khardon R，Mannila H，et al.Discovering all most specific sentences［J］.ACM Transactions on Database Systems，2003，28(2):140-174.

［9］Yu Kun-Ming，Zhou Jiayi，Hong Tzung-Pei，et al.A loadbalanced distributed parallel mining algorithm［J］.Expert Systems with Applications，2010，37(3):2459-2464.

［10］Jiang Y，Wang J.An improved association rules algorithm based on frequent item sets［J］∥Procedia Engineering，2011，15:3335-3340.

［11］Korczak Jerzy，Skrzypczak Piotr.FP-growth in discovery of customer patterns［M］∥Data-Driven Process Discovery and Analysis:First International Symposium.Heidelberg:Springer-Verlag，2012:120-133.

［12］Dean Jeffrey，Ghemawat Sanjay.MapReduce:simplified data processing on large clusters［J］.Communications of the ACM，2008，51(1):107-113.

［13］Paranjape P，Deshpande U.OPT-DIC:an efficient algorithm for distributed association rule mining［C］∥Proceedings of the 2009 International Conference on Computer Engineering and Applications.Singapore:IACSIT Press，2011:450-455.

［14］Wu Gang，Zhang Huxing，Qiu Meikang，et al.A decentralized approach for mining event correlations in distributed system monitoring［J］.Journal of Parallel and Distributed Computing，2013，73(3):330-340.

［15］Aouad L M，Le-Khac N A，Kechadi T M.Performance study of distributed Apriori-like frequent itemsets mining［J］.Knowledge and Information Systems，2010，23(1):55-72.

［16］Yu Honglie，Wen Jun，Wang Hongmei，et al.An improved Apriori algorithm based on the boolean matrix and hadoop［J］.Procedia Engineering，2011，15:1827-1831.

［17］Li Haoyuan，Yi Wang，Zhang Ming，et al.PFP:parallel FP-growth for query recommendation［C］∥Proceedings of the 2008 ACM Conference on Recommender Systems.New York:ACM，2008:107-114.

［18］Frequent Itemset Mining Implementations Repository.Frequent itemset mining dataset repository:FIMI dataset［EB/OL］.［2013-04-20］.http:∥fimi.cs.helsinki.