采用N-list結構的混合并行頻繁項集挖掘算法

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

江西理工大學 信息工程學院，江西 贛州341000

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

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

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

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

1 相關概念介紹

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

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

count：節(jié)點計數(shù)

pre-order：先序編碼

post-order：后序編碼

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

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

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

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

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

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

（-項集N-list）給定任意兩個具有相同前綴的頻繁(-1)-項集和，其對應的N-list結構分別表示為：

則-項集的N-list 定義如下：

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

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

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

2 HP-FIMBN 算法

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

2.1 獲取頻繁1 項集

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

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

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

表2 頻繁1 項集獲取過程Table 2 Process of getting F-list

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

2.2 頻繁1 項集分組

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

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

證明 對于頻繁項來說，其N-list 的長度表示該項在PPC-Tree 樹中的節(jié)點個數(shù)，顯然對于每一項來說，節(jié)點數(shù)的最大值為該項的支持度。此外在構造PPC-Tree 樹時，樹中每一項的節(jié)點數(shù)與其在Flist 中的位置有關。對于頻繁項來說，假設其在F-list中的位置為，則最壞情況是排在之前的-1 項中任意項組合在PPC-Tree 中都有對應的路徑，且該路徑包含項，在此情況下的路徑最多有2條。因此頻繁1 項集中的每一項的N-list長度不超過該項支持度與2之間的最小值。

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

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

GM-GS 分組策略

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

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

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

2.3 并行挖掘頻繁項集

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

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

并行挖掘頻繁項集的Map 階段

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

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

以表2 中的原始數(shù)據(jù)為例，若采用GM-GS 方法，經(jīng)過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é)點生成子PPC-Tree 樹，并對PPC-Tree 樹進行先序、后序遍歷生成2-項集的N-list 結構；然后提出EAS 策略來加快完成兩個頻繁項集N-list 結構的合并過程，最后采用集合枚舉樹作為搜索空間，同時提出SES 策略來避免挖掘過程中的冗余搜索，生成最終的挖掘結果。

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

給定任意兩個頻繁-項集，其N-list 分別表示為-和-，長度為和，具體形式如下：

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

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

EAS 策略

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

輸出：合并結果-。

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

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

表7 兩種N-list結構合并方法對比Table 7 Comparison of two methods for merging N-list

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

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

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

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

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

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

并行挖掘頻繁項集的Reduce過程

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

輸出：頻繁項集。

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

（1）通過調(diào)用insert_tree()函數(shù)在各計算節(jié)點上構建PPC-Tree 子樹。在此過程中為了說明GM-GS對降低PPC-Tree子樹規(guī)模起到的作用，以表5、表6中的兩組數(shù)據(jù)分別構建PPC-Tree 子樹，如圖4 所示?？梢钥闯霾捎肎M-GS 分組方法后各計算節(jié)點上PPCTree子樹的規(guī)模大致相同，而未采用GM-GS分組方法導致計算節(jié)點上PPC-Tree子樹的規(guī)模相差較大。

圖4 PPC-Tree子樹對比Fig.4 Comparison of PPC-Tree

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

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

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

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

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

表9 所有頻繁項集Table 9 All frequent itemsets

2.4 HP-FIMBN 算法步驟

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

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

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

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

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

2.5 算法的復雜度分析

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

在獲取頻繁1 項集的Map 階段，每個計算節(jié)點需要遍歷每條記錄中的每一項，假設每個節(jié)點上的記錄數(shù)目為，記錄的平均長度為，則該階段的時間復雜度為：

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

因此挖掘頻繁1 項集的時間復雜度為：

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

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

對于HP-FIMBN 算法來說其時間復雜度為：

在MRPrePost 算法中前兩個階段的時間復雜度與HP-FIMBN算法基本相同，而在合并兩個頻繁(-1)-項集的N-list 結構時，需要遍歷初始N-list 結構，將PP-code相同的元素進行合并得到最終的N-list結構，假設-項集的初始N-list 結構平均長度為，其時間復雜度為：

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

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

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

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

3 實驗結果及比較

3.1 實驗環(huán)境

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

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

3.2 實驗數(shù)據(jù)

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

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

3.3 評價指標

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

其中，表示算法在單個節(jié)點上的運行時間，T表示并行計算時的運行時間，S越大，則表示并行計算所耗費的相對時間較少，集群效率得到提升。

3.4 HP-FIMBN 算法可行性分析

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

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

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

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

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

圖7 有無GM-GS 策略時算法運行時間的比較Fig.7 Comparison of algorithm running time with or without GM-GS strategy

3.5 HP-FIMBN 算法性能比較

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

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

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

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

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

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

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

4 總結

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