云計算模型中關(guān)聯(lián)規(guī)則增量更新方法

楊澤民

（山西大同大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院，山西 大同037009）

0 引 言

關(guān)聯(lián)規(guī)則挖掘可以發(fā)現(xiàn)大量數(shù)據(jù)中項集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系，挖掘關(guān)聯(lián)規(guī)則的核心是通過統(tǒng)計數(shù)據(jù)項獲得頻繁項集，傳統(tǒng)的算法大部分是基于單結(jié)點的，主要包括Apriori算法、Partition、FP2growth 及抽樣算法等。但是隨著數(shù)據(jù)集的不斷增長，數(shù)據(jù)量級別已經(jīng)到達TB 級甚至PB級，傳統(tǒng)的單結(jié)點串行算法已經(jīng)無法滿足數(shù)據(jù)量急劇增長的需要，與此同時，隨著數(shù)據(jù)集的動態(tài)增長，隱藏的關(guān)聯(lián)規(guī)則也會隨之發(fā)生變化，這就對關(guān)聯(lián)規(guī)則挖掘算法提出了更高要求，即要能準(zhǔn)確挖掘頻繁項集，又要能實時更新已有的頻繁項集，主要包括當(dāng)新的數(shù)據(jù)集添加到舊的數(shù)據(jù)集時，如何產(chǎn)生新的頻繁項集，當(dāng)從舊的數(shù)據(jù)集刪除一個數(shù)據(jù)集時，如何更新頻繁項集，以及當(dāng)最小支持度與最小置信度發(fā)生變化時，如何生成新的頻繁項集等，這些都已成為熱點研究方向。

目前，專家學(xué)者們已對關(guān)聯(lián)規(guī)則與其相關(guān)的算法進行了大量的研究，并提出很多效率較高的算法。大部分關(guān)聯(lián)規(guī)則增量式更新算法是在Apriori［1］算法的基礎(chǔ)上進行改進的，其中張愷提出一種基于云計算的Apriori算法［2］，提高傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘算法的效率。唐璐等提出一種改進的關(guān)聯(lián)規(guī)則增量式更新算法IFU［3］，用于解決數(shù)據(jù)庫和最小支持度均發(fā)生改變時關(guān)聯(lián)規(guī)則的增量式更新問題。朱曉峰等提出了一種基于MapReduce的關(guān)聯(lián)規(guī)則增量更新算法MRFUP［4］，算法只需要掃描一次數(shù)據(jù)庫，利用云計算強大的存儲和并行計算能力來解決海量數(shù)據(jù)挖掘的問題。

本文將改進串行方式關(guān)聯(lián)規(guī)則挖掘效率較低、海量數(shù)據(jù)增量更新挖掘等問題，提出一種基于云計算模式的關(guān)聯(lián)規(guī)則增量更新算法，主要貢獻如下：

（1）提出一種單節(jié)點環(huán)境下的關(guān)聯(lián)規(guī)則增量更新算法（IUM），可以有效地解決規(guī)模較小的關(guān)聯(lián)規(guī)則增量挖掘問題。

（2）采用MapReduce函數(shù)對的設(shè)計方法，將IUM 算法并行化，提出基于云計算的關(guān)聯(lián)規(guī)則增量更新算法（CIUM）。

（3）提出一種關(guān)聯(lián)規(guī)則增量更新的云計算框架，并且可以擴展到其它數(shù)據(jù)類型的挖掘應(yīng)用中。

1 云計算模型

云計算［5］是并行計算、網(wǎng)格計算、效用計算、分布式計算、虛擬化、網(wǎng)絡(luò)存儲等先進計算機技術(shù)和網(wǎng)絡(luò)技術(shù)整合的產(chǎn)物，具有高效性與普遍適用性，圖1給出了以上相關(guān)概念之間的層次關(guān)系。云計算技術(shù)與海量數(shù)據(jù)處理緊密相關(guān)，利用云計算來解決大規(guī)模樹數(shù)據(jù)挖掘是一個具有發(fā)展?jié)摿Φ姆较?。在存儲能力方面，云計算平臺提供的樹數(shù)據(jù)存儲與維護能力是傳統(tǒng)數(shù)據(jù)庫無法比擬的，海量樹數(shù)據(jù)容量可能達幾百GB甚至TB級別，如果用傳統(tǒng)數(shù)據(jù)庫進行存儲維護成本會較大，而云計算平臺則提供了分布式的存儲模式，可以將大量普通計算機的存儲能力和計算能力匯聚在一起，為海量數(shù)據(jù)提供足夠空間，同時云計算環(huán)境還提供了數(shù)據(jù)備份、并發(fā)控制、一致性維護和可靠性等策略，可以為海量數(shù)據(jù)提供可靠保障。在處理能力方面，云計算平臺提供了分布式處理能力，利用該特點，可以對數(shù)據(jù)挖掘過程進行并行處理，可以顯著提高海量數(shù)據(jù)挖掘的能力。在靈活性與可伸縮性方面，云計算平臺具備良好的靈活性與可伸縮性，非常適合對數(shù)據(jù)量彈性變化較大的海量樹數(shù)據(jù)進行處理。云計算平臺提供了向現(xiàn)有云中擴充節(jié)點的功能，以提高計算資源與存儲容量。

圖1 云計算相關(guān)概念關(guān)系

在云計算平臺下進行海量數(shù)據(jù)處理主要包括MapReduce和BSP 兩 種 模 型［6］。谷 歌 的Pregel［7］與 雅 虎 的Giraph［8］就是基于BSP模型，但BSP 模型存在著消息通信效率瓶頸。MapReduce模型主要包括Hadoop［9］與HOP［10］系統(tǒng)，本文將利用MapReduce模型來處理海量樹數(shù)據(jù)。在Hadoop平臺中執(zhí)行MapReduce操作的各階段的工作流程如下［5］：

（1）輸入文件：MapReduce庫將輸入的大數(shù)據(jù)文件分成若干獨立的數(shù)據(jù)，并在不同的機器上進行程序數(shù)據(jù)的備份。

（2）分配任務(wù)：MapReduce中Master節(jié)點分配子任務(wù)，并將子任務(wù)遞交給空閑的worker節(jié)點中。

（3）生成鍵值對：被分配的子任務(wù)的工作節(jié)點讀取輸入的的文件，從中解析出key／value鍵值對，并調(diào)用用戶編寫的Map函數(shù)處理鍵值對，并生成中間鍵值對。

（4）發(fā)送消息：分區(qū)函數(shù)將這些中間數(shù)據(jù)分成若干區(qū)，將各個區(qū)在磁盤中位置信息發(fā)送給Master，然后轉(zhuǎn)發(fā)給Reduce子任務(wù)節(jié)點。

（5）調(diào)用中間數(shù)據(jù)：Reduce子任務(wù)節(jié)點獲取由Master轉(zhuǎn)發(fā)的子任務(wù)后，根據(jù)位置信息調(diào)用磁盤上中間數(shù)據(jù)，并對這些中間按key值進行排序，相同key值進行合并操作。

（6）執(zhí)行Reduce函數(shù)：Reduce子任務(wù)節(jié)點遍歷排序后的中間數(shù)據(jù)，并將數(shù)據(jù)傳遞給用戶定義的Reduce函數(shù)。其執(zhí)行結(jié)果將被輸出到最終的輸出文件中。

（7）輸出結(jié)果：等所有Reduce子任務(wù)完成后，Master節(jié)點將所有數(shù)據(jù)返回給用戶程序，用戶程序合并數(shù)據(jù)并輸出最終數(shù)據(jù)。

綜上所述，基于Hadoop平臺的MapReduce算法工作流程簡單可行，在設(shè)計時只需考慮任務(wù)的分配策略與MapReduce函數(shù)對的設(shè)計，而對于其它并行計算中的復(fù)雜問題，如工作調(diào)度、容錯處理、分布式存儲、網(wǎng)絡(luò)通信等則交給Hadoop平臺進行處理。因此，本文將基于Hadoop平臺設(shè)計出一種關(guān)聯(lián)規(guī)則增量更新算法以改善海量數(shù)據(jù)的更新挖掘效率，實驗結(jié)果表明，算法具有可行性以及良好的運行效率。

2 云計算模型下關(guān)聯(lián)規(guī)則增量更新算法

傳統(tǒng)的Apriori算法通過逐層搜索的迭代方式來挖掘頻繁項集，主要包括兩個步驟：連接與刪除。通過對頻繁k－1項集進行兩兩連接產(chǎn)生候選k項集，連接步驟可以標(biāo)記為Lk－1Lk－1＝Ck，Ck為候選k項集。Ck中包含所有的頻繁k 項集Lk與非頻繁k 項集，即LkCk，循環(huán)掃描數(shù)據(jù)庫可以得到每個候選項集的支持度，并根據(jù)最小支持度閾值來篩選出所有的頻繁k項集。然而在循環(huán)掃描過程中需要進行大量的I／O 操作，特別是在大數(shù)據(jù)量的情況下，算法效率較低。為提高算法的執(zhí)行效率，利用頻繁項集的所有非空子集也是頻繁的這一性質(zhì)，可以對候選k項集進行剪枝操作，以提高算法運行效率。然而當(dāng)數(shù)據(jù)集發(fā)生增量更新時，傳統(tǒng)的Apriori算法已經(jīng)滿足新的需求，只能重新掃描數(shù)據(jù)庫挖掘頻繁項集，這樣會極大地增加挖掘時間與消耗系統(tǒng)資源。因此本文首先提出在單計算結(jié)點下的關(guān)聯(lián)規(guī)則增量更新算法IUM （incremental updating mining），算法描述如下：

算法1：IUM

輸入：原數(shù)據(jù)庫TDB，頻繁項集Lk，新增數(shù)據(jù)庫tdb，最小支持度s

輸出：新的頻繁項集L＊k

（1）對所有的X∈Lk，掃描新增數(shù)據(jù)集tdb，得到X 在TDB∪tdb中的支持數(shù)s（TDB∪tdb），若s（TDB∪tdb）＜s×（TDB＋tdb），則該項集為非頻繁的，并將X 從Lk中進行刪除。

（2）在tdb中找出所有的候選頻繁k項集Ck，對所有的X∈Ck，掃描tdb 并計算每個候選項集的支持數(shù)，若支持數(shù)小于s×tdb，則該候選項集是非頻繁的，可以將X 從Ck中剪掉，以此得到一個更加精簡的候選項集的集合C′k。

（3）掃描原始數(shù)據(jù)庫TDB，更新Ck中所有候選項集的支持數(shù)，并發(fā)現(xiàn)TDB∪tdb中新的頻繁項集，這些新的頻繁項集與上述更新后的Lk共同組成了新數(shù)據(jù)庫中的頻繁項集Lk＊。

在IUM 算法的執(zhí)行過程中，每次迭代只需要掃描整個數(shù)據(jù)庫一次，對于新產(chǎn)生的頻繁項集，首先根據(jù)候選項集在新增數(shù)據(jù)庫tdb 中的支持數(shù)進行修剪，然后再判斷在總數(shù)據(jù)庫中是否頻繁，這樣可以大大減少掃描數(shù)據(jù)庫的次數(shù)，因此IUM 算法在增量更新發(fā)生時的執(zhí)行效率要比使用Apriori算法要好，但是當(dāng)數(shù)據(jù)庫較大或頻繁更新時，IUM算法會因為計算量的急劇增加而導(dǎo)致運行效率的降低。因此，設(shè)計一個基于云計算模型的關(guān)聯(lián)規(guī)則增量更新算法CIUM （cloud incremental updating mining）來 解 決 海 量 數(shù)據(jù)挖掘的問題。

設(shè)計一個主控程序Driver［11］，首先由Driver對新增數(shù)據(jù)庫tdb 進行頻繁項集的挖掘，得到tdb中所有的頻繁項集L（tdb），將原有的頻繁項集L（TDB）與L（tdb）進行對比，找出其公共部分并放入最終的頻繁項集L＊中，剩余的頻繁項集L（TDB）與L（tdb）記為CR。然后進行MapReduce操作，算法描述如下：

算法2：CIUM

Map操作：并行掃描原始數(shù)據(jù)庫與新增數(shù)據(jù)庫，根據(jù)原有的頻繁項集與CR，對數(shù)據(jù)進行格式化操作形成鍵值對＜Tnum，Lk＞，并將所有鍵值對作為中間數(shù)據(jù)傳遞給Reduce操作。

Reduce操作：掃描中間結(jié)果集，將中間鍵值對進行升序排序，依次掃描數(shù)據(jù)庫并判斷X∈Lk，若條件成立則刪除該鍵值對，否則遍歷tdb，計算候選項集在tdb中的支持度，如果滿足條件s（TDB∪tdb）＜s×（TDB＋tdb），則該項集在新數(shù)據(jù)庫中就是非頻繁的，因此可將其刪除。最后對TDB＋tdb進行遍歷，計算各個項集的支持度，再根據(jù)公式判斷是否頻繁，那么新數(shù)據(jù)庫中頻繁k項集由原Lk中剩下的項集和新產(chǎn)生的頻繁項集共同組成L＊k＝ （Lk－Ldelete）∪Lnew。

云計算模型下關(guān)聯(lián)規(guī)則增量更新挖掘框架圖如圖2所示。

圖2 云計算框架

3 實驗設(shè)計與分析

本次實驗主要考察關(guān)聯(lián)規(guī)則增量更新算法是否具備可行性、良好的加速比與擴展率，在實驗中心搭建實驗所需的軟硬件平臺，實驗所需的硬件平臺見表1。

表1 硬件設(shè)施

選取了11臺計算機結(jié)點作為實驗設(shè)備，安裝并調(diào)試好Hadoop環(huán)境，其中計算機結(jié)點的分配如下：1臺作為Driver結(jié)點，控制所有程序的運行，剩余10如作為計算結(jié)點與存儲設(shè)備，在計算機結(jié)點之間使用高速網(wǎng)卡與光纖進行連接。實驗操作系統(tǒng)為Ubuntu Linux，用C＋＋實現(xiàn)并行算法，并設(shè)計一個隨機數(shù)據(jù)生成程序生成實驗所需的模擬數(shù)據(jù)，隨機數(shù)據(jù)生成程序還可以通過調(diào)整相應(yīng)的參數(shù)來控制數(shù)據(jù)的規(guī)模與復(fù)雜程度。

實驗共分為3組，第一組實驗隨機生成包含500000條記錄的數(shù)據(jù)庫，最小支持度s設(shè)置為0.02－0.1之間，最小置信度c設(shè)置為0.6，在不同的新增數(shù)據(jù)集tdb 下進行實驗，具體的參數(shù)設(shè)置見表2。

實驗結(jié)果如圖3所示。

表2 參數(shù)設(shè)置

圖3 不同支持度下運行結(jié)果

從圖3可以發(fā)現(xiàn)，隨著數(shù)據(jù)庫的增大，算法所需的時間也就越大，這是因為數(shù)據(jù)庫越大，算法產(chǎn)生的頻繁項集也就越多，所需的計算量也就越大。同時，隨著支持度的增加，算法所需的時間也就越小，因為支持度越大，產(chǎn)生的頻繁項集也就越少，所需的運算時間也就越小。

第二組實驗主要驗證并行算法在不同數(shù)據(jù)規(guī)模下的加速效果，生成不同規(guī)模的數(shù)據(jù)庫，設(shè)置新增數(shù)據(jù)庫集tdb為8000，最小支持度閾值為0.05，實驗結(jié)果如圖4所示。

圖4 加速比性能測試結(jié)果

從圖4可知，隨著數(shù)據(jù)庫規(guī)模的增大，算法的加速性能會越好，數(shù)據(jù)庫規(guī)模越大，運行所需代價減少比例越高，因此加速性能更好。

第三組實驗主要驗證并行算法的擴展率，隨機選取4個計算結(jié)點，采用5 組數(shù)據(jù)集進行實驗，數(shù)據(jù)集設(shè)置見表3。

設(shè)置tdb為9000，根據(jù)表3的設(shè)置運行算法，選擇其中幾組實驗結(jié)果，如圖5所示。

表3 參數(shù)設(shè)置

圖5 擴展率測試結(jié)果

通過實驗結(jié)果可以看出，隨著計算結(jié)點的增多，結(jié)點之間的通訊代價也就增加，算法的運行時間也會隨之增加，算法擴展率就會隨之減小。同時不同的數(shù)據(jù)集對算法擴展率也有影響，數(shù)據(jù)規(guī)模越大，算法的擴展率越好，這是因為在云計算環(huán)境下，大數(shù)據(jù)集能充分發(fā)揮計算結(jié)點的計算性能，可以充分利用系統(tǒng)的資源與潛能，最大程度地發(fā)揮計算性能。

綜上，本文提出的云計算模式下關(guān)聯(lián)規(guī)則增量更新算法具有可行性，算法適合在海量數(shù)據(jù)庫中進行關(guān)聯(lián)規(guī)則的增量挖掘，并且具有一定的擴展率。

4 結(jié)束語

本文通過將云計算與關(guān)聯(lián)規(guī)則挖掘相結(jié)合的方式，提出一種基于云計算模型的關(guān)聯(lián)規(guī)則增量更新算法，改進現(xiàn)有單結(jié)點算法的串行執(zhí)行方式，提高了算法的執(zhí)行效率與關(guān)聯(lián)規(guī)則增量更新的效率，特別是在海量數(shù)據(jù)集的情況下效果尤為明顯。大量實驗結(jié)果可以表明，本文的算法具有可行性，以及良好的加速性能與可擴展率，并且可以將算法應(yīng)用于實際的項目當(dāng)中。

未來我們將繼續(xù)更新算法并將算法應(yīng)用于其它數(shù)據(jù)類型的挖掘當(dāng)中，譬如結(jié)構(gòu)化數(shù)據(jù)的挖掘、社會關(guān)系網(wǎng)絡(luò)分析等。

［1］YE Y B，CHIANG C C.A parallel apriori algorithm for frequent item sets mining ［C］／／Proceedings of the Fourth International Conference on Software Engineering Research Mannagement and Applications，2006：87－94.

［2］ZHANG Kai，ZHENG Jing.An improved Apriori based on cloud computing［J］.Journal of Gansu Lianhe University （Natural Science Edition），2012，26 （6）：61－64（in Chinese）［張愷，鄭晶.一種基于云計算的新的關(guān)聯(lián)規(guī)則Apriori算法 ［J］.甘肅聯(lián)合大學(xué)學(xué)報（自然科學(xué)版），2012，26 （6）：61－64.］

［3］TANG Lu，JIANG Hong，SHANGGUAN Qiuzi.An improved incremental updating algorithm for association rules［J］.Computer Applications and Softwars，2012，29 （4）：246－248（in Chinese）.［唐璐，江紅，上官秋子.一種改進的關(guān)聯(lián)規(guī)則的增量式更新算法 ［J］.計算機應(yīng)用與軟件，2012，29 （4）：246－248.］

［4］ZHU Xiaofeng，LI Lingjuan，XU Xiaolong，et al.MapReduce based association rule incremental updating algorithm ［J］.Computer Technology and Development，2012，22 （4）：115－118 （in Chinese）.［朱曉峰，李玲娟，徐曉龍，等.基于MapReduce的關(guān)聯(lián)規(guī)則增量更新算法 ［J］.計算機技術(shù)與發(fā)展，2012，22 （4）：115－118.］

［5］LIU Peng.Cloud computing ［M］.Beijing：Publishing House of Electronics Industry，2010 （in Chinese）.［劉 鵬.云計算［M］.北京：電子工業(yè)出版社，2010.］

［6］Dean Jeffrey，Ghemawat Sanjay.MapReduce：Simplified data processing on large clusters［J］.Communications of the ACM，2008，51 （1）：107－113.

［7］Malewicz Grzegorz，Austern Matthew H，Bik Art J C，et al.Pregel：A system for large－scale graph processing ［C］／／Proceedings of the SIGMOD，2010：135－145.

［8］Ching Avery.Giraph：Large－scale graph processing infrastruction on Hadoop ［C］／／Proceedings of the Hadoop Summit，2011.

［9］Son J，Choi H，Chung Y D.Skew－tolerant key distribution for load balancing in MapReduce［J］.IEICE Transaction on Information and Systems，2012，95 （2）：677－680.

［10］Condie Tyson，Conway Neil，Alvaro Peter，et al.MapReduce online［C］／／Proceedings of the NSDI，2010：33－48.

［11］CHEN Guangpeng，YANG Yubin，GAO Yang，et al.Closed frequent itemset mining base on MapReduce［J］.Pattern Recognition and Artificial Intelligence，2012，25 （2）：220－224 （in Chinese）.［陳光鵬，楊育彬，高陽，等.一種基于MapReduce的頻繁閉項集挖掘算法 ［J］.模式識別與人工智能，2012，25 （2）：220－224.］