劉衛(wèi)明，張 弛，毛伊敏

江西理工大學(xué) 信息工程學(xué)院，江西 贛州341000

隨著信息技術(shù)的快速發(fā)展，大數(shù)據(jù)在互聯(lián)網(wǎng)、社交網(wǎng)絡(luò)以及物聯(lián)網(wǎng)等領(lǐng)域得到了廣泛的應(yīng)用。大數(shù)據(jù)的出現(xiàn)對(duì)工業(yè)、醫(yī)療以及政府機(jī)構(gòu)在內(nèi)的許多社會(huì)主體具有重要意義。如何快速并準(zhǔn)確地從這些海量數(shù)據(jù)中挖掘出有價(jià)值的信息和知識(shí)已經(jīng)成為當(dāng)今社會(huì)迫切需要解決的問(wèn)題之一。

數(shù)據(jù)挖掘又稱為知識(shí)發(fā)現(xiàn)（knowledge discover in database，KDD)，其目的在于發(fā)現(xiàn)大量數(shù)據(jù)中有價(jià)值的信息。常見(jiàn)的數(shù)據(jù)挖掘任務(wù)有分類、聚類、關(guān)聯(lián)規(guī)則等。其中關(guān)聯(lián)規(guī)則分析是其重要的研究方向之一。通過(guò)對(duì)關(guān)聯(lián)規(guī)則挖掘算法的研究能夠在海量數(shù)據(jù)中找出有價(jià)值的規(guī)則，這些規(guī)則對(duì)企業(yè)管理上的決策具有巨大幫助。傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法主要分為三類：（1）產(chǎn)生-測(cè)試方法，此類算法先通過(guò)迭代產(chǎn)生候選項(xiàng)集并分別計(jì)數(shù)，然后根據(jù)最小支持度閾值統(tǒng)計(jì)得到頻繁項(xiàng)集，典型算法是Agrawal 等人提出的Apriori 算法；（2）模式增長(zhǎng)方法，此類算法在挖掘過(guò)程中不會(huì)產(chǎn)生候選項(xiàng)集，而是將所有的頻繁項(xiàng)壓縮成一種樹結(jié)構(gòu)，通過(guò)對(duì)樹的直接遍歷挖掘頻繁項(xiàng)集，典型算法有FP-Growth、LP-tree等算法；（3）垂直格式方法，此類算法主要是將水平數(shù)據(jù)集轉(zhuǎn)換成垂直格式，通過(guò)交運(yùn)算來(lái)得到頻繁項(xiàng)集，典型算法為Eclat 算法。大數(shù)據(jù)環(huán)境下，隨著數(shù)據(jù)量的不斷增加，運(yùn)行時(shí)間和內(nèi)存使用量成為傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘算法的重要瓶頸，單純通過(guò)提升計(jì)算機(jī)硬件水平已經(jīng)不能滿足人們對(duì)大數(shù)據(jù)分析與處理的需求。此時(shí)并行化的計(jì)算思想變得尤為重要，通過(guò)改進(jìn)傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法，并與分布式計(jì)算模型相結(jié)合成為當(dāng)前研究的主要方向。

近年來(lái)，Google 開(kāi)發(fā)的MapReduce 并行編程模型由于其操作簡(jiǎn)單、自動(dòng)容錯(cuò)、負(fù)載均衡、擴(kuò)展性強(qiáng)等優(yōu)點(diǎn)深受廣大學(xué)者和企業(yè)的青睞。同時(shí)Hadoop作為一種廣泛使用的MapReduce 開(kāi)源框架，不僅實(shí)現(xiàn)了對(duì)MapReduce 的動(dòng)態(tài)調(diào)用，而且在很大程度上促進(jìn)了MapReduce的應(yīng)用開(kāi)發(fā)。目前許多基于Map-Reduce 計(jì)算模型的關(guān)聯(lián)規(guī)則挖掘算法已成功應(yīng)用到大數(shù)據(jù)的分析與處理領(lǐng)域中。文獻(xiàn)[9-11]采用Apriori 算法多次迭代的思想，在每次迭代過(guò)程中啟用一個(gè)MapReduce 任務(wù)，實(shí)現(xiàn)了Apriori 算法在大數(shù)據(jù)領(lǐng)域的應(yīng)用。然而此類算法在挖掘頻繁項(xiàng)集時(shí)不僅需要多次掃描事務(wù)數(shù)據(jù)集而且會(huì)生成大量候選項(xiàng)集，極大降低了并行算法的挖掘效率。鑒于并行Apriori算法的固有缺陷，文獻(xiàn)[12-16]通過(guò)將MapReduce 計(jì)算模型與FP-Growth 算法相結(jié)合提出了并行的FPGrowth 算法。與并行Apriori 算法不同，此類算法在挖掘過(guò)程中不產(chǎn)生大量的候選項(xiàng)集，并且只需要掃描兩次事務(wù)數(shù)據(jù)集，在每個(gè)計(jì)算節(jié)點(diǎn)上構(gòu)建局部FPTree 樹，通過(guò)對(duì)局部FP-Tree 樹的遍歷得到局部頻繁項(xiàng)集，然后將其合并得到全局頻繁項(xiàng)集。在挖掘頻繁項(xiàng)集的過(guò)程中，各節(jié)點(diǎn)之間計(jì)算獨(dú)立，既不需要相互等待也不需要交換數(shù)據(jù)，極大提高了并行頻繁項(xiàng)集挖掘算法的效率。然而并行FP-Growth 算法在挖掘過(guò)程中需要消耗大量的計(jì)算資源來(lái)遞歸構(gòu)建頻繁項(xiàng)的FP-Tree 樹，且大數(shù)據(jù)環(huán)境下各節(jié)點(diǎn)所構(gòu)造的局部FP-Tree 樹的規(guī)模十分巨大，對(duì)于這些FP-Tree 樹的存儲(chǔ)需要消耗大量的內(nèi)存。考慮到并行Apriori 算法與并行FP-Growth 算法的不足，文獻(xiàn)[17-19]提出了并行Eclat 算法，此類算法雖然計(jì)算簡(jiǎn)單，在一定程度上克服了從海量事務(wù)數(shù)據(jù)集中挖掘頻繁項(xiàng)集時(shí)存在計(jì)算能力不足的問(wèn)題，但并行的Eclat 算法需要將水平數(shù)據(jù)集轉(zhuǎn)化為垂直數(shù)據(jù)集作為輸入數(shù)據(jù)，然后采用類Apriori 方法迭代挖掘頻繁項(xiàng)集，這在大數(shù)據(jù)環(huán)境下是無(wú)法實(shí)現(xiàn)的。

為了充分利用不同算法各自的優(yōu)點(diǎn)，減少并行計(jì)算中單個(gè)節(jié)點(diǎn)的內(nèi)存需求量與節(jié)點(diǎn)之間的通信量，Liao 等人提出了一種將dist-Eclat與傳統(tǒng)FPGrowth算法相結(jié)合的混合算法——MRPrePost 算法。該算法主要分為三個(gè)階段：首先通過(guò)調(diào)用一次MapReduce 任務(wù)得到頻繁1 項(xiàng)集F-list；然后構(gòu)造Flist 所對(duì)應(yīng)的PPC-Tree 樹，并對(duì)PPC-Tree 樹進(jìn)行先序和后序遍歷產(chǎn)生頻繁項(xiàng)的N-list；最后對(duì)F-list 進(jìn)行分組，并分布在多個(gè)計(jì)算節(jié)點(diǎn)上進(jìn)行頻繁項(xiàng)集的挖掘。相較于其他單一的并行頻繁項(xiàng)集挖掘算法，該算法既能對(duì)原始數(shù)據(jù)集進(jìn)行無(wú)損壓縮，又可以快速計(jì)算項(xiàng)集的支持度。此外，該算法將對(duì)樹的挖掘過(guò)程轉(zhuǎn)化成與垂直格式交運(yùn)算類似的N-list 合并過(guò)程，并且該過(guò)程不需要將PPC-Tree 樹保存在內(nèi)存中，極大減少了算法的計(jì)算時(shí)間和內(nèi)存使用量。然而該算法仍存在幾個(gè)明顯不足：（1）在F-list 分組階段，該算法未能充分考慮到集群負(fù)載均衡對(duì)算法性能的影響，容易造成數(shù)據(jù)劃分中計(jì)算節(jié)點(diǎn)負(fù)載不均衡的問(wèn)題；（2）在合并兩個(gè)頻繁項(xiàng)集的N-list 結(jié)構(gòu)時(shí)不僅要逐一比較兩者中的每一項(xiàng)，而且需要將初步獲得的N-list 結(jié)構(gòu)中(先序，后序)序列相同的PP-code 合并，極大地降低了N-list 的合并效率；（3）在并行挖掘頻繁項(xiàng)集階段，該算法是通過(guò)合并任意兩個(gè)-項(xiàng)集的N-list 結(jié)構(gòu)來(lái)生成（+1）-項(xiàng)集，會(huì)產(chǎn)生大量的冗余搜索。針對(duì)上述問(wèn)題，本文提出了一種基于N-list 結(jié)構(gòu)的混合并行頻繁項(xiàng)集挖掘算法（hybrid parallel frequent itemset mining algorithm based on N-list，HPFIMBN）。首先，該算法充分考慮到集群負(fù)載對(duì)并行算法挖掘效率的影響，設(shè)計(jì)負(fù)載估計(jì)函數(shù)（load estimation function，LE）用于計(jì)算出頻繁1 項(xiàng)集中每項(xiàng)的負(fù)載量，并提出基于貪心策略的分組方法（grouping method based on greedy strategy，GM-GS），將F-list 中的每一項(xiàng)根據(jù)其負(fù)載量進(jìn)行均勻分組，既解決了數(shù)據(jù)劃分中計(jì)算節(jié)點(diǎn)負(fù)載不均衡的問(wèn)題，又降低了集群中各節(jié)點(diǎn)上子PPC-Tree 樹的規(guī)模。其次，提出預(yù)先放棄策略（early abandon strategy，EAS），該策略不僅能避免兩個(gè)N-list 結(jié)構(gòu)在合并過(guò)程中的無(wú)效計(jì)算，而且不需要遍歷初始N-list 結(jié)構(gòu)就能得到最終的Nlist，極大地提高了N-list 結(jié)構(gòu)的合并效率。最后，該算法采用集合枚舉樹作為搜索空間，并提出超集等價(jià)剪枝策略（superset equivalent strategy，SES），來(lái)避免挖掘過(guò)程中的冗余搜索，生成最終的挖掘結(jié)果。實(shí)驗(yàn)結(jié)果表明，該算法在大數(shù)據(jù)環(huán)境下進(jìn)行頻繁項(xiàng)集挖掘具有較好的效果。

1 相關(guān)概念介紹

（PPC-Tree 樹）PPC-Tree 樹是一種樹形數(shù)據(jù)結(jié)構(gòu)，樹中的每個(gè)節(jié)點(diǎn)均由以下五部分組成：

item-name：節(jié)點(diǎn)名稱

count：節(jié)點(diǎn)計(jì)數(shù)

pre-order：先序編碼

post-order：后序編碼

children-list：子節(jié)點(diǎn)列表

（PP-code 編碼）PP-code 編碼又被稱為先序后序編碼，由pre-order、post-order 和count 三部分組成。對(duì)于PPC-Tree 樹中的任意節(jié)點(diǎn)，稱(.-,.-,.)為該節(jié)點(diǎn)的PP-code編碼。

（祖先孩子關(guān)系）給定PPC-Tree 樹中任意兩節(jié)點(diǎn)和(≠)的PP-code，若滿足以下關(guān)系：

則稱節(jié)點(diǎn)是節(jié)點(diǎn)的祖先節(jié)點(diǎn)，為的孩子節(jié)點(diǎn)。

（頻繁1 項(xiàng)集的N-list）在PPC-Tree 樹中，代表相同項(xiàng)的所有PP-code 編碼按照先序遍歷升序連接生成的序列，被稱為頻繁1 項(xiàng)集的N-list。

（“ ?”關(guān)系）給定頻繁1 項(xiàng)集中的任意兩項(xiàng)和，若的支持度大于的支持度，則表示為?。

（-項(xiàng)集N-list）給定任意兩個(gè)具有相同前綴的頻繁(-1)-項(xiàng)集和，其對(duì)應(yīng)的N-list結(jié)構(gòu)分別表示為：

則-項(xiàng)集的N-list 定義如下：

（1）對(duì)于任意(,,)∈-() (1 ≤≤)，(,,)∈-()(1 ≤≤)，若滿足條件<，>，則將(,,)加入到的N-list 中，得到初始的N-list。

（2）遍歷的N-list，將pre-order 和post-order相同的PP-code 進(jìn)行合并，得到最終的N-list。

（頻繁項(xiàng)集的支持度）給定項(xiàng)集，其N-list 為(,,),(,,),…,(x,y,z)，則項(xiàng)的支持度為++…+z。

2 HP-FIMBN 算法

HP-FIMBN 算法主要包括獲取頻繁1 項(xiàng)集、頻繁1 項(xiàng)集分組和并行挖掘頻繁項(xiàng)集3 個(gè)階段。（1）在獲取頻繁1 項(xiàng)集階段，啟用一次MapReduce 任務(wù)，采用類似World Count 方法并行獲取頻繁1 項(xiàng)集F-list。（2）在頻繁1 項(xiàng)集分組階段，為了避免數(shù)據(jù)劃分中出現(xiàn)計(jì)算節(jié)點(diǎn)負(fù)載不均衡的問(wèn)題，提出GM-GS 分組方法，該方法先通過(guò)負(fù)載估計(jì)函數(shù)LE 計(jì)算出頻繁1 項(xiàng)集中每一項(xiàng)的負(fù)載量，然后根據(jù)貪心思想將F-list 進(jìn)行均勻分組，生成分組列表G-list。（3）在并行挖掘頻繁項(xiàng)集階段，主要包括并行挖掘頻繁項(xiàng)集的Map 階段和Reduce 階段。在Map 階段主要是根據(jù)前兩個(gè)階段生成的F-list 列表和G-list 列表構(gòu)造出映射路徑。在Reduce 階段首先調(diào)用函數(shù)在各個(gè)計(jì)算節(jié)點(diǎn)上生成子PPC-Tree 樹。然后通過(guò)遍歷本地PPC-Tree 樹，在各個(gè)節(jié)點(diǎn)上生成局部2-項(xiàng)集的N-list結(jié)構(gòu)。在此過(guò)程中為了加快完成N-list 結(jié)構(gòu)的合并任務(wù)，提出預(yù)先放棄策略EAS，來(lái)減少合并過(guò)程中的無(wú)效計(jì)算。最后在挖掘頻繁-項(xiàng)集(>2)的過(guò)程中采用集合枚舉樹作為搜索空間，并提出SES 策略，來(lái)避免挖掘過(guò)程中的重復(fù)搜索，生成最終的挖掘結(jié)果。

2.1 獲取頻繁1 項(xiàng)集

對(duì)于數(shù)據(jù)集DB，其頻繁1 項(xiàng)集的生成過(guò)程主要包括Split、Map、Combine 和Reduce 四個(gè)階段。（1）在Split階段：使用Hadoop 默認(rèn)的文件塊策略，將原始數(shù)據(jù)集劃分成大小相同的文件塊Block，并保存在分布式文件系統(tǒng)（hadoop distributed file system，HDFS）中。（2）在Map 階段：每個(gè)Mapper 節(jié)點(diǎn)調(diào)用Map()函數(shù)對(duì)輸入文件塊Block 進(jìn)行一次映射，以鍵值對(duì)<=,=1>的形式統(tǒng)計(jì)出相應(yīng)節(jié)點(diǎn)中各項(xiàng)出現(xiàn)的次數(shù)；同時(shí)為了降低集群通信，經(jīng)過(guò)Mapper 節(jié)點(diǎn)處理后的數(shù)據(jù)不會(huì)立刻發(fā)送給Reduce 節(jié)點(diǎn)，而是先進(jìn)行本地結(jié)合。（3）在Combine 階段：將本地值相同的鍵值對(duì)進(jìn)行初步合并，然后再以新的鍵值對(duì)作為下一階段的輸入數(shù)據(jù)傳送到Reduce任務(wù)中。（4）在Reduce 階段：需要將輸入的鍵值對(duì)進(jìn)行再次合并，得到每個(gè)數(shù)據(jù)項(xiàng)在整個(gè)數(shù)據(jù)集中的支持度，最后根據(jù)最小支持度閾值_篩選出頻繁1 項(xiàng)集F-list。

為了更清楚地說(shuō)明頻繁1 項(xiàng)集的獲取步驟，本文給出事例，假設(shè)事務(wù)數(shù)據(jù)集DB 如表1 所示(_=2)，表2 是針對(duì)DB 運(yùn)行頻繁1 項(xiàng)集獲取步驟之后得到的F-list。

表1 事務(wù)數(shù)據(jù)集DBTable 1 Transaction database-DB

表2 頻繁1 項(xiàng)集獲取過(guò)程Table 2 Process of getting F-list

最終根據(jù)支持度降序排序生成的F-list 序列為{:5;:5;:4;:3;:3}。

2.2 頻繁1 項(xiàng)集分組

大數(shù)據(jù)環(huán)境下，經(jīng)過(guò)第一階段獲得的頻繁1 項(xiàng)集F-list 的規(guī)模非常大，導(dǎo)致無(wú)法在有限的內(nèi)存空間中構(gòu)造PPC-Tree 樹。為解決此問(wèn)題，提出了一種基于貪心策略的分組方法GM-GS。該方法的主要思想是先求取所有頻繁1 項(xiàng)集對(duì)于分組數(shù)量的負(fù)載均值，然后為每組分配一個(gè)接近負(fù)載均值的負(fù)載量，從而達(dá)到整體的負(fù)載均衡。采用GM-GS 分組方法將F-list進(jìn)行分組時(shí)，其關(guān)鍵在于計(jì)算頻繁1 項(xiàng)集中每一項(xiàng)的負(fù)載量，即頻繁1 項(xiàng)集中每項(xiàng)所對(duì)應(yīng)的N-list 結(jié)構(gòu)長(zhǎng)度。然而N-list 中的元素與PPC-Tree 樹中的節(jié)點(diǎn)一一對(duì)應(yīng)，在沒(méi)有構(gòu)造PPC-Tree 樹之前無(wú)法準(zhǔn)確計(jì)算出每一項(xiàng)的負(fù)載量。為了解決該問(wèn)題，在GMGS 方法中通過(guò)負(fù)載估計(jì)函數(shù)來(lái)預(yù)測(cè)頻繁項(xiàng)的N-list長(zhǎng)度。

（負(fù)載估計(jì)函數(shù)LE）若頻繁項(xiàng)的支持度是，在F-list 中的位置為，則其負(fù)載估計(jì)函數(shù)如下所示：

證明 對(duì)于頻繁項(xiàng)來(lái)說(shuō)，其N-list 的長(zhǎng)度表示該項(xiàng)在PPC-Tree 樹中的節(jié)點(diǎn)個(gè)數(shù)，顯然對(duì)于每一項(xiàng)來(lái)說(shuō)，節(jié)點(diǎn)數(shù)的最大值為該項(xiàng)的支持度。此外在構(gòu)造PPC-Tree 樹時(shí)，樹中每一項(xiàng)的節(jié)點(diǎn)數(shù)與其在Flist 中的位置有關(guān)。對(duì)于頻繁項(xiàng)來(lái)說(shuō)，假設(shè)其在F-list中的位置為，則最壞情況是排在之前的-1 項(xiàng)中任意項(xiàng)組合在PPC-Tree 中都有對(duì)應(yīng)的路徑，且該路徑包含項(xiàng)，在此情況下的路徑最多有2條。因此頻繁1 項(xiàng)集中的每一項(xiàng)的N-list長(zhǎng)度不超過(guò)該項(xiàng)支持度與2之間的最小值。

采用GM-GS 方法將頻繁1 項(xiàng)集F-list 劃分為組的分組思想如下：首先根據(jù)式（3）計(jì)算出頻繁1 項(xiàng)集F-list 中每一項(xiàng)的負(fù)載量，按照負(fù)載量從大到小排序生成L-list；然后計(jì)算出所有項(xiàng)對(duì)于分組數(shù)量的負(fù)載均值，將每個(gè)負(fù)載量大于均值的項(xiàng)分配到負(fù)載為0 的組中，并刪除該項(xiàng)在L-list 中的信息；最后逆序遍歷L-list 剩余的項(xiàng)，若與當(dāng)前組的負(fù)載量_滿足式（4），則將項(xiàng)添加到當(dāng)前組中，更新當(dāng)前組的負(fù)載總量并從L-list 中刪除，若不滿足式（4），則將項(xiàng)item 添加到下一組，更新分組信息。在分組完畢后，將得到的分組列表G-list 存儲(chǔ)到分布式文件系統(tǒng)HDFS 中，使得集群中任意節(jié)點(diǎn)都能訪問(wèn)。

GM-GS 分組方法的形式化如算法1 所示。

GM-GS 分組策略

以表2 中的原始數(shù)據(jù)為例，若采用GM-GS 分組方法和未采用該方法分別將F-list 分為兩組，其結(jié)果如表3、表4 所示。

表3 未采用GM-GS 方法對(duì)F-list分組Table 3 Without using GM-GS to group F-list

表4 采用GM-GS 方法對(duì)F-list分組Table 4 Using GM-GS to group F-list

2.3 并行挖掘頻繁項(xiàng)集

采用GM-GS 分組方法對(duì)F-list 進(jìn)行分組是為了將原始數(shù)據(jù)集中的事務(wù)進(jìn)行重新劃分，并把劃分后的事務(wù)數(shù)據(jù)集根據(jù)分組列表G-list 映射到集群中各個(gè)計(jì)算節(jié)點(diǎn)上，同時(shí)在各個(gè)節(jié)點(diǎn)上構(gòu)建滿足內(nèi)存要求的子PPC-Tree 樹，從而進(jìn)一步完成頻繁項(xiàng)集的挖掘任務(wù)。在此過(guò)程中主要包括Map 階段和Reduce 階段。（1）在Map 階段：首先根據(jù)頻繁1 項(xiàng)集F-list 和分組列表G-list 構(gòu)建哈希表，然后結(jié)合哈希表將原始事務(wù)集映射到集群中不同的計(jì)算節(jié)點(diǎn)上，生成映射路徑。（2）在Reduce 階段：集群各節(jié)點(diǎn)首先調(diào)用_()函數(shù)生成子PPC-Tree 樹。然后通過(guò)對(duì)本地PPC-Tree 樹的遍歷生成局部2-項(xiàng)集的N-list 結(jié)構(gòu)，其中在N-list 合并過(guò)程中，為了加快完成N-list 合并任務(wù)，避免合并過(guò)程中的無(wú)效計(jì)算，提出一種預(yù)先放棄策略EAS。該策略可以通過(guò)比較項(xiàng)集支持度與最小支持度閾值的關(guān)系來(lái)預(yù)先判定是否為頻繁項(xiàng)集。最后在挖掘頻繁-項(xiàng)集(>2)的過(guò)程中采用集合枚舉樹作為搜索空間，并提出SES 策略，來(lái)避免挖掘過(guò)程中的冗余搜索，生成最終的挖掘結(jié)果。

在并行挖掘頻繁項(xiàng)集的Map 階段，其主要任務(wù)是將原始事務(wù)集根據(jù)哈希表映射到集群中不同的計(jì)算節(jié)點(diǎn)上，具體過(guò)程為：首先，從分布式文件系統(tǒng)HDFS 中讀取全局頻繁1 項(xiàng)集F-list 和分組列表G-list，并將G-list 每組所包含的項(xiàng)作為，組號(hào)作為構(gòu)建HTable。然后，依次讀取每一條記錄，逆序遍歷該記錄中的項(xiàng)，根據(jù)之前獲得的HTable，確定其組號(hào)，并以為，排在項(xiàng)之前所有項(xiàng)為組成鍵值對(duì)。與此同時(shí)，為了避免同一條記錄多次映射到同一節(jié)點(diǎn)，刪除HTable 中等于的所有鍵值對(duì)。若在映射時(shí)找不到對(duì)應(yīng)的組號(hào)，則讀取前一項(xiàng)執(zhí)行相同的操作，直到該記錄遍歷完畢。最后，將所得的結(jié)果作為Reduce 階段的輸入傳送給Reduce函數(shù)。該操作過(guò)程偽代碼如算法2所示。

并行挖掘頻繁項(xiàng)集的Map 階段

輸入：原始數(shù)據(jù)集data，頻繁1項(xiàng)集F-list，分組列表G-list。

輸出：映射路徑<=,=>。

以表2 中的原始數(shù)據(jù)為例，若采用GM-GS 方法，經(jīng)過(guò)Map 階段處理后，分配到Reduce 階段的各組數(shù)據(jù)如表5 所示；若未采用GM-GS 方法，分配到Reduce階段的各組數(shù)據(jù)如表6 所示。

表5 采用GM-GS 方法后分配到Reduce階段的各組數(shù)據(jù)Table 5 Each group data allocated to Reduce stage by using GM-GS method

表6 未采用GM-GS 方法后分配到Reduce階段的各組數(shù)據(jù)Table 6 Each group data allocated to Reduce stage without using GM-GS method

在Reduce 階段，首先調(diào)用_()函數(shù)在集群各節(jié)點(diǎn)生成子PPC-Tree 樹，并對(duì)PPC-Tree 樹進(jìn)行先序、后序遍歷生成2-項(xiàng)集的N-list 結(jié)構(gòu)；然后提出EAS 策略來(lái)加快完成兩個(gè)頻繁項(xiàng)集N-list 結(jié)構(gòu)的合并過(guò)程，最后采用集合枚舉樹作為搜索空間，同時(shí)提出SES 策略來(lái)避免挖掘過(guò)程中的冗余搜索，生成最終的挖掘結(jié)果。

在并行挖掘頻繁項(xiàng)集的過(guò)程中最主要的一步是通過(guò)合并兩個(gè)頻繁-項(xiàng)集的N-list 結(jié)構(gòu)生成頻繁(+1)-項(xiàng)集，如何降低合并過(guò)程的運(yùn)行時(shí)間是該算法的關(guān)鍵所在。為此本文提出了一種預(yù)先放棄策略EAS，該策略不僅能減少兩個(gè)頻繁項(xiàng)集N-list 結(jié)構(gòu)在合并過(guò)程中的無(wú)效計(jì)算，而且不需要遍歷初始N-list結(jié)構(gòu)就能得到最終的N-list，極大提高了N-list結(jié)構(gòu)的合并效率。

給定任意兩個(gè)頻繁-項(xiàng)集，其N-list 分別表示為-和-，長(zhǎng)度為和，具體形式如下：

采用EAS 策略合并-和-的具體過(guò)程如下：

首先根據(jù)性質(zhì)2 分別計(jì)算出-和-的支持度、，并將、求和得到兩個(gè)N-list結(jié)構(gòu)的總支持度；然后對(duì)于任意一個(gè)PP-code C，若不滿足定義5，則用總支持度減去C.來(lái)更新總支持度，其中如果總支持度小于最小支持度閾值則認(rèn)為當(dāng)前所比較的項(xiàng)集是非頻繁的，提前結(jié)束比較過(guò)程。EAS 策略偽代碼如下：

EAS 策略

輸入：-,-，最小支持度_。

輸出：合并結(jié)果-。

為了說(shuō)明EAS 策略能夠提高N-list 結(jié)構(gòu)的合并效率，以表2 中的原始數(shù)據(jù)為例構(gòu)建PPC-Tree 樹，如圖1 所示，并根據(jù)定義3 可知節(jié)點(diǎn)與節(jié)點(diǎn)的Nlist 結(jié)構(gòu)分別為{(4,10,5)}，{(5,3,1),(7,6,3)}。若采用MRPrePost 算法中的合并策略將頻繁項(xiàng)、合并為2 項(xiàng)集需要4 步（表7 第2 列），尤其是在第3 步時(shí)需要遍歷初始N-list 結(jié)構(gòu)，將PP-code 相同的元素進(jìn)行合并得到最終的N-list 結(jié)構(gòu)；然而，采用EAS 合并策略只需要3 步，并且不需要遍歷初始N-list 結(jié)構(gòu)即可獲得最后結(jié)果（表7 第3 列）。對(duì)于任意的兩個(gè)頻繁(-1)-項(xiàng)集和，其N-list 結(jié)構(gòu)長(zhǎng)度分別為和，合并后的初始N-list 長(zhǎng)度為，對(duì)于MRPrePost 算法來(lái)說(shuō)其時(shí)間復(fù)雜度為(++)，而采用預(yù)先放棄策略其時(shí)間復(fù)雜度為(+)。

圖1 PPC-Tree樹Fig.1 PPC-Tree

表7 兩種N-list結(jié)構(gòu)合并方法對(duì)比Table 7 Comparison of two methods for merging N-list

由于在MRPrePost 算法中主要采用類Apriori 的方法來(lái)挖掘頻繁項(xiàng)集，這會(huì)導(dǎo)致在挖掘過(guò)程中出現(xiàn)大量的冗余搜索。為了優(yōu)化算法的挖掘效率，本文在挖掘頻繁項(xiàng)集時(shí)采用集合枚舉樹作為搜索空間，并且提出了一種超集等價(jià)策略SES 來(lái)避免挖掘過(guò)程中的冗余搜索，并生成最終的挖掘結(jié)果。

給定一組項(xiàng)集={,,…,i}，其中??…?i，則集合枚舉樹的構(gòu)造過(guò)程如下：（1）創(chuàng)建根節(jié)點(diǎn)；（2）依次取出項(xiàng)集中的每一項(xiàng)i(1 ≤≤)作為根節(jié)點(diǎn)的孩子節(jié)點(diǎn)；（3）樹中每個(gè)節(jié)點(diǎn)需要與F-list左側(cè)的每個(gè)節(jié)點(diǎn)分別做交集，從而生成該節(jié)點(diǎn)的孩子節(jié)點(diǎn)；（4）重復(fù)過(guò)程3 直到產(chǎn)生所有的葉子節(jié)點(diǎn)。以2.1節(jié)得到的F-list為例，構(gòu)造的集合枚舉樹如圖2 所示。

（超集等價(jià)策略）給定項(xiàng)集和項(xiàng)，如果的支持度()等于?{}的支持度(?{})，那么對(duì)于任何項(xiàng)集(?=?∧?)滿足以下關(guān)系：

對(duì)于項(xiàng)集，其支持度等于?{}的支持度，這說(shuō)明任何包含的事務(wù)也包含項(xiàng)，給定一個(gè)事務(wù)，若中包含項(xiàng)集?，則必包含項(xiàng)集和項(xiàng)集，根據(jù)前面知識(shí)可以推出事務(wù)也一定包含項(xiàng)，也就是說(shuō)?的支持度等于??{}。

圖2 集合枚舉樹Fig.2 Set-enumeration tree

圖3 剪枝后的集合枚舉樹Fig.3 Set-enumeration tree after pruning

并行挖掘頻繁項(xiàng)集的Reduce過(guò)程

輸入：映射路徑，最小支持度_，頻繁1 項(xiàng)集。

輸出：頻繁項(xiàng)集。

以Map 階段輸出的分組數(shù)據(jù)為例，并行挖掘頻繁項(xiàng)集的Reduce階段主要分為以下幾步：

（1）通過(guò)調(diào)用insert_tree()函數(shù)在各計(jì)算節(jié)點(diǎn)上構(gòu)建PPC-Tree 子樹。在此過(guò)程中為了說(shuō)明GM-GS對(duì)降低PPC-Tree子樹規(guī)模起到的作用，以表5、表6中的兩組數(shù)據(jù)分別構(gòu)建PPC-Tree 子樹，如圖4 所示。可以看出采用GM-GS 分組方法后各計(jì)算節(jié)點(diǎn)上PPCTree子樹的規(guī)模大致相同，而未采用GM-GS分組方法導(dǎo)致計(jì)算節(jié)點(diǎn)上PPC-Tree子樹的規(guī)模相差較大。

圖4 PPC-Tree子樹對(duì)比Fig.4 Comparison of PPC-Tree

（2）各個(gè)計(jì)算節(jié)點(diǎn)對(duì)PPC-Tree 子樹進(jìn)行先序后序遍歷，生成所有頻繁1 項(xiàng)集的N-list，如表8 所示。在此過(guò)程中，相較于MRPrePost 算法，本文采用了GM-GS 分組方法使得每個(gè)節(jié)點(diǎn)上的PPC-Tree 子樹規(guī)模大致相同，對(duì)樹遍歷所需時(shí)間相差不大，不僅有效解決了各計(jì)算節(jié)點(diǎn)負(fù)載不均衡問(wèn)題，而且也大大提高了算法的挖掘效率。

表8 各組各節(jié)點(diǎn)的N-list序列Table 8 N-list sequence of each node in each group

（3）并行化算法只需要找出以每個(gè)組中各項(xiàng)為后綴的所有頻繁項(xiàng)集，所有組的頻繁項(xiàng)集構(gòu)成整個(gè)挖掘過(guò)程的最終結(jié)果。對(duì)于第二組的兩個(gè)頻繁項(xiàng)、，采用EAS 策略分別找出所有以、為后綴的頻繁2 項(xiàng)集。對(duì)于項(xiàng)需要合并、和、的N-list得到2 項(xiàng)集、，其N-list分別為(3,7,5)和(5,6,3)；同樣對(duì)于項(xiàng)分別合并、，、和、的N-list得到2 項(xiàng)集、、，其N-list 分別為(3,7,2)、{(1,1,1),(5,6,2)}和(6,4,1)，根據(jù)最小支持度min_sup 可知以為后綴的全部頻繁2 項(xiàng)集是,，因此第二組輸出的頻繁2項(xiàng)集有、、和。同樣的對(duì)第一組采用相同的方法最終得到的頻繁2 項(xiàng)集為、、、。

此外在挖掘頻繁-項(xiàng)集的過(guò)程中為了避免重復(fù)搜索，在每個(gè)計(jì)算節(jié)點(diǎn)中構(gòu)造本地集合枚舉樹作為搜索空間（如圖5 所示），并采用超集等價(jià)策略挖掘頻繁項(xiàng)集，其結(jié)果如表9 所示。

圖5 不同節(jié)點(diǎn)上的本地集合枚舉樹Fig.5 Local set-enumeration tree on different nodes

表9 所有頻繁項(xiàng)集Table 9 All frequent itemsets

2.4 HP-FIMBN 算法步驟

HP-FIMBN 算法的具體實(shí)現(xiàn)步驟如下：

通過(guò)Hadoop 默認(rèn)的文件塊策略，將原始數(shù)據(jù)集劃分成大小相同的文件塊Block。

對(duì)于每一個(gè)文件塊調(diào)用頻繁1 項(xiàng)集F-list的生成過(guò)程，獲得全局頻繁1 項(xiàng)集，并將結(jié)果存入分布式文件系統(tǒng)HDFS 中。

調(diào)用GM-GS 分組方法將F-list 中的每一項(xiàng)進(jìn)行分組，生成分組列表G-list，并將分組列表存儲(chǔ)到HDFS 中。

啟動(dòng)新的MapReduce 任務(wù)，在Map 階段調(diào)用算法2 將原始數(shù)據(jù)集分別映射到各個(gè)計(jì)算節(jié)點(diǎn)上生成映射路徑，并在Reduce 階段調(diào)用算法4 來(lái)挖掘全局頻繁項(xiàng)集。

2.5 算法的復(fù)雜度分析

HP-FIMBN 算法主要包括3 個(gè)階段：獲取頻繁1項(xiàng)集、頻繁1 項(xiàng)集分組和并行挖掘頻繁項(xiàng)集。因此該算法的時(shí)間復(fù)雜度主要由三部分組成，分別記為、和。

在獲取頻繁1 項(xiàng)集的Map 階段，每個(gè)計(jì)算節(jié)點(diǎn)需要遍歷每條記錄中的每一項(xiàng)，假設(shè)每個(gè)節(jié)點(diǎn)上的記錄數(shù)目為，記錄的平均長(zhǎng)度為，則該階段的時(shí)間復(fù)雜度為：

在獲取頻繁1 項(xiàng)集的Reduce 階段，需要將Map階段輸出的key 值相同的鍵值對(duì)進(jìn)行合并，假設(shè)每個(gè)節(jié)點(diǎn)經(jīng)過(guò)Map 階段輸出的鍵值對(duì)個(gè)數(shù)為N，Mapper節(jié)點(diǎn)個(gè)數(shù)為，則該階段的時(shí)間復(fù)雜度為：

因此挖掘頻繁1 項(xiàng)集的時(shí)間復(fù)雜度為：

在頻繁1 項(xiàng)集分組階段主要采用GM-GS 策略將F-list 中的每一項(xiàng)進(jìn)行分組，采用單機(jī)即可完成。假設(shè)F-list長(zhǎng)度為，分組數(shù)為，則其時(shí)間復(fù)雜度為：

在并行挖掘頻繁項(xiàng)集過(guò)程中，其時(shí)間復(fù)雜度主要取決于將任意兩個(gè)具有相同前綴的頻繁(-1)-項(xiàng)集和的N-list 結(jié)構(gòu)合并生成-項(xiàng)集的Nlist 結(jié)構(gòu)。假設(shè)頻繁1 項(xiàng)集-={,,…,I}，以項(xiàng)I結(jié)尾的頻繁(-1)-項(xiàng)集的N-list 結(jié)構(gòu)長(zhǎng)度為L，則采用預(yù)先放棄策略的時(shí)間復(fù)雜度為：

對(duì)于HP-FIMBN 算法來(lái)說(shuō)其時(shí)間復(fù)雜度為：

在MRPrePost 算法中前兩個(gè)階段的時(shí)間復(fù)雜度與HP-FIMBN算法基本相同，而在合并兩個(gè)頻繁(-1)-項(xiàng)集的N-list 結(jié)構(gòu)時(shí)，需要遍歷初始N-list 結(jié)構(gòu)，將PP-code相同的元素進(jìn)行合并得到最終的N-list結(jié)構(gòu)，假設(shè)-項(xiàng)集的初始N-list 結(jié)構(gòu)平均長(zhǎng)度為，其時(shí)間復(fù)雜度為：

大數(shù)據(jù)環(huán)境下，、相較于的值過(guò)小可以忽略不計(jì)，而且通常情況下-項(xiàng)集的初始N-list 結(jié)構(gòu)較長(zhǎng)，對(duì)其遍歷以及合并需要消耗較多時(shí)間。因此可以得出，HP-FIMBN 算法的時(shí)間復(fù)雜度遠(yuǎn)低于MRPrePost算法。

HP-FIMBN 算法的空間復(fù)雜度是存儲(chǔ)頻繁項(xiàng)集及其N-list 結(jié)構(gòu)和集合枚舉樹所占的內(nèi)存總和。采用GM-GS 分組方法使得每個(gè)計(jì)算節(jié)點(diǎn)的任務(wù)量大致相同，每個(gè)子節(jié)點(diǎn)的PPC-Tree 規(guī)模接近，從而使得頻繁項(xiàng)集的N-list 結(jié)構(gòu)規(guī)模總體相差不大。假設(shè)每個(gè)節(jié)點(diǎn)平均有g個(gè)頻繁-項(xiàng)集，每個(gè)頻繁-項(xiàng)集占（單位為字節(jié)：B），頻繁-項(xiàng)集的N-list 長(zhǎng)度均值為L，頻繁-項(xiàng)集的每個(gè)N-list 結(jié)構(gòu)占（單位為字節(jié)：B）。則存儲(chǔ)頻繁項(xiàng)集N-list 結(jié)構(gòu)的空間復(fù)雜度為(∑g×(+×L))(1 ≤≤)，而集合枚舉樹的存儲(chǔ)只與頻繁1 項(xiàng)集的長(zhǎng)度有關(guān)，其空間復(fù)雜度為(×L!)。則HP-FIMBN 算法的空間復(fù)雜度為：

MRPrePost 算法的空間復(fù)雜度主要是頻繁項(xiàng)集及其N-list 結(jié)構(gòu)存儲(chǔ)所占的內(nèi)存。然而該算法采用Hash 映射的分組方法，極易造成計(jì)算節(jié)點(diǎn)之間負(fù)載不均衡的問(wèn)題。而在算法復(fù)雜度分析中采用最差情況，假設(shè)集群節(jié)點(diǎn)最多有個(gè)頻繁-項(xiàng)集。則MRPrePost算法的空間復(fù)雜度為：

在大數(shù)據(jù)環(huán)境下，頻繁項(xiàng)集及其N-list 結(jié)構(gòu)存儲(chǔ)所占的內(nèi)存遠(yuǎn)遠(yuǎn)大于集合枚舉樹存儲(chǔ)所需內(nèi)存，往往可以忽略。因此可知本文算法的空間復(fù)雜度小于MRPrePost算法。

3 實(shí)驗(yàn)結(jié)果及比較

3.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證HP-FIMBN 算法的挖掘性能，本文設(shè)計(jì)了相關(guān)實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境包括4 個(gè)計(jì)算節(jié)點(diǎn)，其中1個(gè)Master 節(jié)點(diǎn)，3 個(gè)Slaver 節(jié)點(diǎn)。所有節(jié)點(diǎn)的CPU 均為AMD Ryzen 7，每個(gè)CPU 都擁有8 個(gè)處理單元，其內(nèi)存均為16 GB。實(shí)驗(yàn)環(huán)境中的4 個(gè)節(jié)點(diǎn)處于同一個(gè)局域網(wǎng)中，通過(guò)200 Mb/s 以太網(wǎng)相連。軟件方面，每個(gè)節(jié)點(diǎn)安裝的Hadoop 版本為2.7.4，JDK 版本為1.8.0，操作系統(tǒng)為Ubuntu 16.04。各個(gè)節(jié)點(diǎn)的具體配置如表10 所示。

表10 實(shí)驗(yàn)環(huán)境中各節(jié)點(diǎn)的基本配置Table 10 Basic configuration of nodes in experimental environment

3.2 實(shí)驗(yàn)數(shù)據(jù)

HP-FIMBN 算法使用4 個(gè)真實(shí)數(shù)據(jù)集，分別為webdocs、kosarak、Susy 和accident。其中webdocs 數(shù)據(jù)集是由意大利科學(xué)家Claudio Lucchese 等人通過(guò)網(wǎng)絡(luò)爬蟲抓取的Web 文檔數(shù)據(jù),該數(shù)據(jù)集包含1 692 082條數(shù)據(jù)，共有5 267 656 項(xiàng)，具有數(shù)據(jù)量多、記錄長(zhǎng)度長(zhǎng)、項(xiàng)數(shù)多等特點(diǎn)；kosarak 數(shù)據(jù)集記錄了匈牙利一家大型新聞網(wǎng)站點(diǎn)擊流數(shù)據(jù)，該數(shù)據(jù)集包括990 002 條數(shù)據(jù)，共有41 270 項(xiàng)，具有數(shù)據(jù)量少、項(xiàng)數(shù)較多、數(shù)據(jù)離散等特點(diǎn)；Susy 數(shù)據(jù)集包含5 000 000 條實(shí)例，共有190 項(xiàng)，具有數(shù)據(jù)量多，記錄長(zhǎng)度均勻、項(xiàng)數(shù)少等特點(diǎn)；accident 數(shù)據(jù)集是美國(guó)近些年發(fā)生的交通事故數(shù)據(jù)，該數(shù)據(jù)集包含340 183 條數(shù)據(jù)，共有468 項(xiàng)，具有數(shù)據(jù)量少、記錄長(zhǎng)度均勻、項(xiàng)數(shù)少等特點(diǎn)。以上數(shù)據(jù)集均可以在數(shù)據(jù)挖掘網(wǎng)站下載（http://fimi.ua.ac.be/data/），其具體信息如表11 所示。

表11 實(shí)驗(yàn)數(shù)據(jù)集Table 11 Experimental data sets

3.3 評(píng)價(jià)指標(biāo)

大數(shù)據(jù)環(huán)境下，為驗(yàn)證并行算法的挖掘性能，通常采用加速比作為衡量指標(biāo)。加速比是指在并行計(jì)算下，降低運(yùn)行時(shí)間從而獲得的性能提升，其定義為：

其中，表示算法在單個(gè)節(jié)點(diǎn)上的運(yùn)行時(shí)間，T表示并行計(jì)算時(shí)的運(yùn)行時(shí)間，S越大，則表示并行計(jì)算所耗費(fèi)的相對(duì)時(shí)間較少，集群效率得到提升。

3.4 HP-FIMBN 算法可行性分析

為驗(yàn)證HP-FIMBN 算法在大數(shù)據(jù)集下挖掘頻繁項(xiàng)集的可行性，采用算法的加速比來(lái)進(jìn)行衡量。本文選取最小支持度閾值為1 000、5 000、20 000 和100 000，并在每一支持度下分別將HP-FIMBN 算法應(yīng)用于上述4 個(gè)實(shí)驗(yàn)數(shù)據(jù)集上。在每一數(shù)據(jù)集上獨(dú)立運(yùn)行10 次，取10 次結(jié)果的均值。通過(guò)對(duì)算法加速比的比較，實(shí)現(xiàn)對(duì)HP-FIMBN 算法性能的綜合評(píng)估。其實(shí)驗(yàn)結(jié)果如圖6 所示。

從圖6 中可以看出，隨著支持度的不斷增加，HPFIMBN 算法在處理webdocs、Susy 兩個(gè)規(guī)模較大的數(shù)據(jù)集時(shí)具有較高的加速比。而在處理kosarak、accident這樣小數(shù)據(jù)集時(shí)，隨著節(jié)點(diǎn)數(shù)量增加，加速比的增加趨勢(shì)并不明顯，甚至當(dāng)支持度為100 000 時(shí)，隨著節(jié)點(diǎn)數(shù)量的增加，加速比呈現(xiàn)下降趨勢(shì)且小于1。這是由于在數(shù)據(jù)集規(guī)模較小時(shí)，數(shù)據(jù)量遠(yuǎn)小于集群所能處理的數(shù)據(jù)量，將原始事務(wù)集根據(jù)分組列表G-list 劃分到不同的計(jì)算節(jié)點(diǎn)中反而增加了各個(gè)節(jié)點(diǎn)的時(shí)間開(kāi)銷，算法性能易陷入瓶頸。而在處理數(shù)據(jù)規(guī)模較大的webdocs 和Susy數(shù)據(jù)集時(shí)，隨著節(jié)點(diǎn)個(gè)數(shù)增加，加速比呈線性增長(zhǎng)趨勢(shì)，甚至當(dāng)支持度為1 000 時(shí)，算法在4 個(gè)節(jié)點(diǎn)下的加速比分別為3.73 和3.16，比在1 個(gè)節(jié)點(diǎn)下分別提升了2.73 和2.16，這是由于在大規(guī)模數(shù)據(jù)集下，算法能夠并行挖掘局部頻繁項(xiàng)集和合并頻繁項(xiàng)集的優(yōu)點(diǎn)被逐漸放大，算法的挖掘性能得到極大提高。同時(shí)這也表明HP-FIMBN算法適用于大數(shù)據(jù)集的處理，且具有較強(qiáng)的擴(kuò)展性。

圖6 算法在不同節(jié)點(diǎn)下的加速比Fig.6 Acceleration rate of algorithm on different computing nodes

為了分析并行挖掘頻繁項(xiàng)集過(guò)程中均勻分組的必要性，本文選取最小支持度閾值為5 000 和100 000，在上述4 個(gè)實(shí)驗(yàn)數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)。該實(shí)驗(yàn)比較了均勻分組和未均勻分組情況下算法運(yùn)行時(shí)間分布情況，從而實(shí)現(xiàn)對(duì)GM-GS 策略的綜合評(píng)估。其實(shí)驗(yàn)結(jié)果如圖7 所示。

從圖7 中可以看出，隨著支持度的增加，采用GM-GS 策略在處理webdocs、Susy 兩個(gè)規(guī)模較大的數(shù)據(jù)集時(shí)運(yùn)行時(shí)間有較大減小，而在處理kosarak、accident 這樣的小數(shù)據(jù)集時(shí)提升效果不太明顯，這主要是由于小規(guī)模數(shù)據(jù)集使得在各個(gè)計(jì)算節(jié)點(diǎn)中構(gòu)造的子PPC-Tree 樹規(guī)模急劇減小，對(duì)于PPC-Tree 樹的遍歷所需時(shí)間相差不大。而在webdocs、Susy 等大數(shù)據(jù)集下，若未采用GM-GS 策略極易導(dǎo)致數(shù)據(jù)分組不均衡，各計(jì)算節(jié)點(diǎn)之間構(gòu)造的子PPC-Tree 樹規(guī)模以及遍歷樹所需要的時(shí)間相差較大。由此看出在并行挖掘頻繁項(xiàng)集過(guò)程中GM-GS 策略是必要的。

圖7 有無(wú)GM-GS 策略時(shí)算法運(yùn)行時(shí)間的比較Fig.7 Comparison of algorithm running time with or without GM-GS strategy

3.5 HP-FIMBN 算法性能比較

為驗(yàn)證HP-FIMBN 算法的挖掘效果，本文在上述實(shí)驗(yàn)數(shù)據(jù)下進(jìn)行了對(duì)比實(shí)驗(yàn)，根據(jù)算法的運(yùn)行時(shí)間和內(nèi)存使用量，分別與MRPrePost算法、LBPFP算法和MREclat算法進(jìn)行性能比較。

在運(yùn)行HP-FIMBN、MRPrePost 和LBPFP 算法時(shí)需要根據(jù)每個(gè)數(shù)據(jù)集的F-list 規(guī)模設(shè)置分組數(shù)，表12 給出四種數(shù)據(jù)集在不同支持度下F-list 數(shù)目的具體情況。根據(jù)F-list 以及數(shù)據(jù)集大小，對(duì)于Susy 數(shù)據(jù)集設(shè)置分組數(shù)為50 組，kosarak 和accident 數(shù)據(jù)集設(shè)置分組數(shù)為100組，webdocs 數(shù)據(jù)集設(shè)置分組數(shù)為1 000 組，實(shí)驗(yàn)結(jié)果如圖8 所示。

表12 不同支持度下四種數(shù)據(jù)集的F-list規(guī)模Table 12 F-list size of four data sets with different support degrees

從圖8 中可以看出，相較于LBPFP 和MREclat 算法，HP-FIMBN 算法在每個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間均有所下降。其中在kosarak 數(shù)據(jù)集上的運(yùn)行時(shí)間降低幅度最大，分別降低了50.8%和69.74%；在webdocs數(shù)據(jù)集上降低的幅度最小，但也分別降低了20.06%和30.83%。這是由于HP-FIMBN 算法在并行挖掘頻繁項(xiàng)集的過(guò)程中，將傳統(tǒng)復(fù)雜的樹遍歷和迭代操作轉(zhuǎn)化為簡(jiǎn)單的N-list 結(jié)構(gòu)合并操作，極大降低了算法的運(yùn)行時(shí)間。相反，在挖掘頻繁項(xiàng)集時(shí)，MREclat 算法需要將水平數(shù)據(jù)集轉(zhuǎn)成垂直數(shù)據(jù)集，然后采用類Apriori方法，通過(guò)對(duì)兩個(gè)(-1)-項(xiàng)集的tid-list求交集來(lái)挖掘頻繁-項(xiàng)集，該過(guò)程需要消耗大量的時(shí)間；同樣，對(duì)于LBPFP 算法來(lái)說(shuō)，在挖掘頻繁項(xiàng)集時(shí)需要遞歸構(gòu)建頻繁項(xiàng)的FP-Tree，需要大量的計(jì)算資源。此外，可以發(fā)現(xiàn)HP-FIMBN 算法比最優(yōu)的MRPrePost算法的挖掘效果都好，尤其在Susy 數(shù)據(jù)集上，HPFIMBN 算法的執(zhí)行時(shí)間比MRPrePost 算法降低了19.97%。這主要是因?yàn)镠P-FIMBN 算法采用GM-GS分組方法均勻地將頻繁1 項(xiàng)集分配到各個(gè)節(jié)點(diǎn)中，在確保集群負(fù)載均衡的前提下降低了集群中子PPCTree 樹的規(guī)模，由此減少先序、后序遍歷PPC-Tree 樹所需要的時(shí)間，加快生成本地2-項(xiàng)集的N-list結(jié)構(gòu)；同時(shí)該算法在合并兩個(gè)(-1)-項(xiàng)集的N-list 結(jié)構(gòu)時(shí)，使用預(yù)先放棄策略可以提前得知該項(xiàng)集是否屬于頻繁項(xiàng)集，避免了合并過(guò)程中的無(wú)效計(jì)算，不僅提高了Nlist 結(jié)構(gòu)的合并效率，而且極大降低了算法的運(yùn)行時(shí)間。

圖8 四種算法在不同數(shù)據(jù)集上的運(yùn)行時(shí)間比較Fig.8 Comparison of running time of four algorithms on different data sets

然而從圖8（b）、（d）中可以看出，在小規(guī)模數(shù)據(jù)集kosarak 和accident 上，相較于MRPrePost 算法，本文算法的實(shí)驗(yàn)提升不夠顯著。其中，一方面是由于小規(guī)模數(shù)據(jù)集的運(yùn)算量不足以填充分布式集群；另一方面由于數(shù)據(jù)量較少，使得在各個(gè)計(jì)算節(jié)點(diǎn)中構(gòu)造的PPC-Tree 子樹規(guī)模急劇減小，導(dǎo)致-項(xiàng)集的Nlist 結(jié)構(gòu)長(zhǎng)度大幅降低，從而降低了預(yù)先放棄策略在合并兩個(gè)N-list結(jié)構(gòu)時(shí)所起到的作用。

由于LBPFP、MRPrePost 和HP-FIMBN 算法都對(duì)原始數(shù)據(jù)集進(jìn)行了無(wú)損壓縮，本文除了考察運(yùn)行時(shí)間外，還統(tǒng)計(jì)了支持度為5 000、20 000 和100 000 下上述算法在集群中各個(gè)節(jié)點(diǎn)消耗的平均內(nèi)存大小，實(shí)驗(yàn)結(jié)果如圖9 所示。

圖9 不同算法在不同數(shù)據(jù)集上的內(nèi)存使用量對(duì)比Fig.9 Comparison of memory usage of different algorithms on different data sets

從圖9 可以看出，在4 個(gè)數(shù)據(jù)集上，HP-FIMBN 算法和MRPrePost 算法所使用的內(nèi)存空間明顯小于LBPFP 算法，這是由于HP-FIMBN 算法和MRPrePost算法在挖掘頻繁項(xiàng)集時(shí)只需根據(jù)PPC-Tree 樹生成頻繁1-項(xiàng)集的N-list 結(jié)構(gòu)，之后將PPC-Tree 樹從內(nèi)存中刪除；而對(duì)于LBPFP 算法來(lái)說(shuō)需要遞歸地構(gòu)建條件模式子樹，并且所有的條件子樹都保留在內(nèi)存中，需要消耗大量的內(nèi)存空間。同時(shí)相較于MRPrePost 算法，HP-FIMBN 算法在4 個(gè)數(shù)據(jù)集上的內(nèi)存使用量更少，尤其在Susy 數(shù)據(jù)集上，其內(nèi)存使用量比MRPre-Post減少了19.4%。一方面，HP-FIMBN算法采用GMGS 分組方法在對(duì)頻繁1 項(xiàng)集F-list 均勻分組的同時(shí)也減小各個(gè)計(jì)算節(jié)點(diǎn)中子PPC-Tree 樹的規(guī)模；另一方面，在并行挖掘頻繁項(xiàng)集的過(guò)程中，每個(gè)節(jié)點(diǎn)只需要將以當(dāng)前組中項(xiàng)為后綴的頻繁項(xiàng)集保存在內(nèi)存中，大大降低了內(nèi)存使用量。

4 總結(jié)

為解決傳統(tǒng)頻繁項(xiàng)集挖掘算法在大數(shù)據(jù)環(huán)境下的不足，本文提出了一種混合的并行頻繁項(xiàng)集挖掘算法HP-FIMBN。首先，該算法充分考慮到集群負(fù)載對(duì)并行算法挖掘效率的影響，設(shè)計(jì)負(fù)載估計(jì)函數(shù)LE來(lái)計(jì)算出頻繁1 項(xiàng)集中每項(xiàng)的負(fù)載量，并提出了一種基于貪心策略的分組方法GM-GS，將F-list 中的每一項(xiàng)根據(jù)其負(fù)載量進(jìn)行均勻分組，既解決了數(shù)據(jù)劃分中計(jì)算節(jié)點(diǎn)負(fù)載不均衡的問(wèn)題，又降低了集群中各節(jié)點(diǎn)上子PPC-Tree 樹的規(guī)模。其次，為了加快完成兩個(gè)頻繁項(xiàng)集N-list 結(jié)構(gòu)的合并任務(wù)，提出了一種預(yù)先放棄策略EAS，該策略不僅能避免兩個(gè)N-list 結(jié)構(gòu)在合并過(guò)程中的無(wú)效計(jì)算，而且不需要遍歷初始Nlist 結(jié)構(gòu)就能得到最終的N-list，極大地提高了N-list結(jié)構(gòu)的合并效率。最后，該算法采用集合枚舉樹作為搜索空間，并提出了一種超集等價(jià)剪枝策略（SES），來(lái)避免挖掘過(guò)程中的冗余搜索，生成最終的挖掘結(jié)果。與其他并行頻繁項(xiàng)集挖掘算相比，該算法充分結(jié)合了水平型算法和垂直型算法的優(yōu)點(diǎn)，利用其獨(dú)特的方式來(lái)實(shí)現(xiàn)頻繁項(xiàng)集的挖掘。同時(shí)為了驗(yàn)證HP-FIMBN 算法的挖掘性能，本文在4 個(gè)數(shù)據(jù)集Susy、webdocs、kosarak 和accident上對(duì)HP-FIMBN、MRPrePost、LBPFP 和MREclat 四種算法進(jìn)行對(duì)比分析，實(shí)驗(yàn)結(jié)果表明相比于其他幾種算法，HP-FIMBN算法在運(yùn)行時(shí)間和內(nèi)存使用量上都具有明顯的優(yōu)勢(shì)。