陳興蜀 張帥 童浩 崔曉靖

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

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

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

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

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)個(gè)布爾矩陣，=(a(mk+1)j)1×n為一維矩陣且，記，若a(mk+1)j=，ε為最小支持度，則稱為A 的第k 個(gè)擴(kuò)展布爾矩陣(EBM)，^A 為擴(kuò)展向量.記Ti(iΩmk+1)和Ij(jΩn)分別為EBM的第i 個(gè)行向量和第j 個(gè)列向量，為了表述方便，Ti和Ij在關(guān)聯(lián)規(guī)則中分別代表事務(wù)名稱和項(xiàng)集名稱.

定義2 設(shè)Ii、Ij是擴(kuò)展布爾矩陣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 中元素的過濾，文中給出合取運(yùn)算符∧的定義.

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

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

1.2 FP-Growth 算法

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

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

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

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

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

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

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

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

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

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

圖1 項(xiàng)I3 的LocalFPTree Fig.1 LocalFPTree of item I3

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

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

輸出:Ik的TPTreek

生成Ik的頻繁模式集Lk;

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

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

創(chuàng)建根節(jié)點(diǎn)，以“null{}”標(biāo)記;

改進(jìn)的FP-Growth 算法描述如下:

初始化canpat{pattern:0};

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

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

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

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

2 BPFP 算法

2.1 MapReduce 并行計(jì)算模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

表1 實(shí)驗(yàn)配置Table 1 Configuration of experiment

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

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

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

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

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

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

圖6 BPFP 算法在不同實(shí)驗(yàn)條件下的加速比Fig.6 Speedup of BPFP algorithm under different experiment conditions

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

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

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

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

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

4 結(jié)論

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

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