基于Apriori算法與MapReduce優(yōu)化模型的并行式數(shù)據(jù)聚類方法*

呂立新 楊 帆

(1安徽商貿(mào)職業(yè)技術學院信息與人工智能學院 安徽蕪湖 241000；2菲律賓科技大學工程技術學院 菲律賓馬尼拉 0900)

數(shù)據(jù)聚類結合了智能算法、計算機科學等綜合性技術，將數(shù)學理論知識應用在現(xiàn)實生產(chǎn)領域，能夠將海量數(shù)據(jù)整合集中，挖掘出其中的隱含規(guī)律，為社會各領域發(fā)展提供信息支持[1]。Apriori算法是關聯(lián)規(guī)則挖掘技術的重要分支，幫助研究者找出各種數(shù)據(jù)之間的相互關系，已經(jīng)在數(shù)據(jù)聚類領域展現(xiàn)了優(yōu)勢[2]。傳統(tǒng)Apriori算法雖然在數(shù)據(jù)聚類方面有所成效，但是容易對系統(tǒng)節(jié)點負載造成負擔，且數(shù)據(jù)聚類時間開銷不理想等問題凸顯。為了高效率、高精度聚類大規(guī)模數(shù)據(jù)挖掘一個事件與另一個事件的相互關聯(lián)[3]，該研究將Apriori算法與分布式的MapReduce框架模型結合，且分別對其實施改進，形成一種嶄新有效的并行式數(shù)據(jù)聚類方法，起到輔助決策作用。

1改進Apriori算法與MapReduce優(yōu)化模型在并行式數(shù)據(jù)聚類中的應用

1.1 MapReduce模型的開源實施框架

研究中的MapReduce優(yōu)化編程模型采用Apache Hadoop開源實施框架，其優(yōu)點是營造了應用程度與數(shù)千個獨立計算的計算機與PB級數(shù)據(jù)工作同步展開的環(huán)境，是一種被Apache允許的、數(shù)據(jù)密集型、分布式應用程序。MapReduce優(yōu)化模型的Apache Hadoop開源實施框架操作呈現(xiàn)顯著的周期性特征[4]，其運行機理如圖1所示。

圖1 Apache Hadoop開源實施框架運行機理

由圖1可知，Apache Hadoop的核心包括HDFS存儲系統(tǒng)、MapReduce處理組件兩部分，其中，HDFS組件既能為目標數(shù)據(jù)塊創(chuàng)建多個副本，也能高吞吐量提取數(shù)據(jù)，滿足了Apriori算法挖掘海量數(shù)據(jù)關聯(lián)規(guī)則的高性能需求。其中，Reduce階段包括Sort，Shuffle和Reduce3個子階段，Shuffle階段運行數(shù)據(jù)花費的時間超過Reduce階段三分之一[5]，優(yōu)化潛力較大。

1.2基于W-DPC策略的Apriori候選項集結合方法

Apriori算法的基本描述如下：定義數(shù)據(jù)庫D用于存儲關聯(lián)規(guī)則挖掘所需的事務t，t包含多項屬性i；假設X與Y是事務的屬性，X?Y則表示二者的關聯(lián)規(guī)則。關聯(lián)規(guī)則擁有支持度與置信度，分別描述為Support、Confidence，計算方法如公式(1)與公式(2)所示：

(1)

(2)

公式中，事務總數(shù)用M表示，屬性X與屬性Y相同時間出現(xiàn)的事務的次數(shù)為Count(X∪Y)，屬性X出現(xiàn)的次數(shù)為Support(X)。不難看出，支持度是事務同時擁有兩個屬性的數(shù)量同事務總數(shù)量的比值；而置信度是支持度與屬性之一X的支持度的比值。通過設置最小支持度與置信度的方式約束數(shù)據(jù)關聯(lián)規(guī)則的最低標準，進而完成數(shù)據(jù)聚類。

Apriori算法進行關聯(lián)規(guī)則挖掘過程中需多次掃描數(shù)據(jù)庫、生成候選項集，提高了數(shù)據(jù)聚類的冗余程度。Shuffle階段是MapReduce模型與Apriori算法結合運行的關鍵步驟，其特點是產(chǎn)生大規(guī)模的計算數(shù)據(jù)和較長的候選項集，passes過程的運行負載提升，影響數(shù)據(jù)聚類的運行效率。不僅如此，map計算任務執(zhí)行完畢reduce才能開始其合并value的運算，再一次延長了整個Apriori算法進行關聯(lián)規(guī)則挖掘的效果[6]。為了增強Apriori算法在MapReduce模型框架下的適應能力、挖掘有效的數(shù)據(jù)信息，優(yōu)化了Apriori候選項集結合方法，步驟如下：

Step 1：設定閾值，將閾值之上的一項集輸出生成下一階段候選項集，經(jīng)過閾值對比獲得頻繁二項集，循環(huán)操作Step 1生成第三候選項集；

Step 2：確定固定數(shù)量的passes量。將候選二項集與候選三項集的時間展開比較確定passes量：結合三個passes的前提是候選二項集生成時長多出候選三項集生成時長3/2倍；結合兩個passes的前提是候選二項集生成時長多出候選三項集生成時長不足3/2倍[7]。

通過以上方法可以確定MapReduce模型框架下Apriori算法執(zhí)行的passes量，reduce無需等待map任務執(zhí)行完畢再開始工作，節(jié)省了等待時間，提升了Apriori算法在MapReduce模型中并行式聚類的效率。

1.3 二項頻繁集快速生成策略

Apriori算法執(zhí)行效率慢的原因之一是候選集過多，非頻繁項集耗費大量時間。為進一步加快頻繁項集生成速度，對Apriori算法頻繁2-項集生成策略進行改進：提取數(shù)據(jù)中的一項頻繁集定義為Q，合并Q與每一個事務集，以此得到各事務集中頻繁性低的數(shù)據(jù)，將其剔除，得到數(shù)據(jù)集K；定義二項子集為E，從K集中生成，再在二項子集中生成二項候選集；創(chuàng)建h表存儲關鍵值形式的二項候選集，當存入的關鍵值是第一次存入則需實施正規(guī)的數(shù)據(jù)存儲處理步驟，且關鍵值對應的v為1，反之存入的關鍵值已經(jīng)存在則對表中的關鍵值加1[8]；存儲完畢將表中關鍵值轉換為二項候選集，Apriori算法二項候選集挖掘關聯(lián)規(guī)則的支持度即為關鍵值對應的v。

以上對Apriori算法挖掘關聯(lián)規(guī)則的過程進行了優(yōu)化，明顯降低Apriori算法生成二項頻繁集的時間復雜度，從而降低Apriori算法挖掘時間開銷。MapReduce優(yōu)化模型下改進算法獲得頻繁項集的過程為：

(1)輸入原始數(shù)據(jù)集D，將數(shù)據(jù)集劃分為 h個規(guī)模相當?shù)臄?shù)據(jù)塊，并將h個數(shù)據(jù)塊轉換為格式對，其中key、value分別表示事務編號以及事務所包含的項集) ，將數(shù)據(jù)塊發(fā)送至節(jié)點為n個DataNode節(jié)點分配這些數(shù)據(jù)塊；

(2)運行Map程序并掃描數(shù)據(jù)塊，通過Map函數(shù)獲取頻繁1-項集。

(3)以減少節(jié)點之間的通信量為目的，編寫 Combiner基于W-DPC策略確定待結合的passes項集數(shù)量，reduce無需等待map任務執(zhí)行完畢再開始工作，節(jié)省等待時間。

(4)以獲得的頻繁1-項集為基礎，基于二項頻繁集快速生成策略獲取頻繁2-項集。減少頻繁集生成過程中無效候選項集帶來的負載與干擾，降低算法時間復雜度。

(5)利用Reduce函數(shù)合并符合最小支持度的局部頻繁項集，高效率、低開銷生成全局候選頻繁項集。

(6)以Reduce階段的全局候選頻繁項集為基礎并行式產(chǎn)生候選項集：頻繁項集分割為相同的數(shù)據(jù)塊并執(zhí)行Map函數(shù)處理；Map函數(shù)處理數(shù)據(jù)塊實現(xiàn)頻繁項集向鍵值對的轉換，Map函數(shù)獨自處理輸入的數(shù)據(jù)塊；全部Map節(jié)點將具有相應鍵的鍵值對傳輸至Reduce函數(shù)，由Reduce分離鍵與值得到符合支持度閾值的候選項集。

(7)頻繁項集為空集時終止運算，反之，循環(huán)操作步驟(3)～步驟(5)。

2實驗與分析

2.1實驗環(huán)境設置

2.2負載均衡測試

實驗以V3數(shù)據(jù)集為樣本進行數(shù)據(jù)聚類測試，利用方法挖掘數(shù)據(jù)集的關聯(lián)規(guī)則。在此過程中記錄了每個計算節(jié)點的事務數(shù)，繪制成條形圖如圖2所示。

圖2 各節(jié)點事務數(shù)分布統(tǒng)計

由圖2不難看出，方法在各節(jié)點上的事務數(shù)分布約在533條上下，沒有出現(xiàn)過多或者過少的情況?？梢娫诜植际酵诰螂A段，每個計算節(jié)點的計算數(shù)據(jù)量接近，說明數(shù)據(jù)聚類任務呈現(xiàn)均衡的分布式狀態(tài)，實現(xiàn)了較好的負載均衡。

2.3時間復雜度測試

實驗在6個數(shù)據(jù)集下展開數(shù)據(jù)聚類，各方法獨立運行10次后取其時間開銷均值，統(tǒng)計了包括方法在內(nèi)的三種數(shù)據(jù)聚類方法的時間復雜度情況，結果如表2所示。

表2 三種數(shù)據(jù)聚類方法的運行時間統(tǒng)計/s

分析表2可知，在不同規(guī)模數(shù)據(jù)集之下，完成相同聚類目標的前提下，方法的運行時間最少，時間復雜度最低。處理N2數(shù)據(jù)集800事務數(shù)僅花費了2064s，當數(shù)據(jù)集事務數(shù)增加到3200時，時間開銷達到最高為3013s，可見該方法的聚類時間花費較為平穩(wěn)、波動不大，時間復雜度較低。相比之下，布爾矩陣約簡Apriori聚類優(yōu)化算法聚類時間高出方法約1/3甚至更多，時間波動幅度相對較大。遺傳Apriori聚類算法時間復雜度表現(xiàn)亦是如此，聚類運行效率更低，處理3200事務數(shù)時花費9546s。

總體而言，通過上述方法降低了MapReduce模型運行之下的數(shù)據(jù)聚類時間復雜度，這是因為上述方法分別對Apriori算法與MapReduce模型運行策略進行了優(yōu)化，基于W-DPC策略設計了嶄新的Apriori候選項集結合方法，確定了MapReduce模型框架下Apriori算法執(zhí)行的passes量，reduce無需等待map任務執(zhí)行完畢再開始工作，因而passes階段的運行負載有效降低，聚類的整體時間復雜度有所降低。

3結論

提出的基于Apriori算法與MapReduce優(yōu)化模型的并行式數(shù)據(jù)聚類方法，可有效解決海量數(shù)據(jù)的分類問題，降低了聚類的時間復雜度、實現(xiàn)了各節(jié)點的均衡負載。一方面，基于W-DPC策略設計Apriori候選項集結合方法，預先確定MapReduce模型框架下Apriori算法執(zhí)行的passes量，reduce無需等待map任務執(zhí)行完畢再開始工作；另一方面，引入二項頻繁集快速生成策略，及時剔除無效候選集，降低Apriori算法生成二項頻繁集的時間復雜度。綜上，文章方法展現(xiàn)了良好的大規(guī)模數(shù)據(jù)聚類性能，為提升社會各領域信息數(shù)據(jù)智能分析效率提供了有效參考。