劉姜

（撫順職業(yè)技術(shù)學院 信息工程系，遼寧 撫順113006）

一種基于云計算的關聯(lián)規(guī)則改進研究

劉姜

（撫順職業(yè)技術(shù)學院 信息工程系，遼寧 撫順113006）

隨著數(shù)據(jù)挖掘技術(shù)的成熟，其中關聯(lián)規(guī)則在大規(guī)模數(shù)據(jù)中的應用成為了目前的熱點。為了提高在大規(guī)模數(shù)據(jù)下進行數(shù)據(jù)挖掘的效率，在MapReduce中通過引入歸并函數(shù)Fusion來提高執(zhí)行剪枝任務的效率并進行了優(yōu)化研究，提出了一種基于云理論的關聯(lián)規(guī)則Apriori算法，詳細論述了實現(xiàn)的過程以及關鍵技術(shù)。通過實驗表明，該方法取得了良好的實驗效果，克服了Apriori算法耗時多、識別率低下等問題，是實現(xiàn)在大規(guī)模數(shù)據(jù)進行數(shù)據(jù)挖掘的實用工具。

MapReduce；數(shù)據(jù)挖掘：關聯(lián)規(guī)則；Apriori算法

數(shù)據(jù)挖掘是由半自動化或自動化的計算器工具對資料存儲庫中的海量資料進行有條理且可重復的探索與分析的過程，對研究人員與知識需求者來說，其主要目的在于發(fā)掘出未知的、新穎的、有價值的、可利用的知識與規(guī)律。通過這些知識與規(guī)律，人們可以預測未來可能發(fā)生的結(jié)果。

數(shù)據(jù)挖掘作為一個新型智能資料分析技術(shù)，與傳統(tǒng)分析技術(shù)“假設－收集－檢驗＂的不同點在于，其使用“發(fā)現(xiàn)－匹配＂等算法來獲取資料之間的有價值關聯(lián)。不同種類資?的涌現(xiàn)也導致數(shù)據(jù)挖掘技術(shù)經(jīng)歷了多次變革，由原本的事務集數(shù)據(jù)挖掘轉(zhuǎn)向文件挖掘、多媒體挖掘、Web頁面集挖掘、時序氣象資料挖掘及三維結(jié)構(gòu)DNA挖掘等。數(shù)據(jù)挖掘與以往的數(shù)據(jù)庫查詢也有相當程度的不同，其處理目標在于分析海量且復雜的數(shù)據(jù)庫，其服務對象在于高級決策者，其主旨在于為高級決策者的決策提供有形且有力的數(shù)據(jù)支持。近年來，數(shù)據(jù)挖掘已成?各?同專業(yè)的研究熱點之一[1]。Apriori算法是數(shù)據(jù)挖掘技術(shù)中的經(jīng)典算法，由于傳統(tǒng)的Apriori算法需要重復搜索數(shù)據(jù)庫來得到候選集，影響了其運行的效率和計算精度。隨著第四次IT產(chǎn)業(yè)革命的到來，云計算已成為大規(guī)模計算未來發(fā)展的方向，由Google提出的MapReduce編程框架是云計算中的核心技術(shù)之一，它適用于處理大規(guī)模數(shù)據(jù)集，計算效率非常高[2]。

針對傳統(tǒng) Apriori算法性能差的特點，本文立足MapReduce框架使用云計算技術(shù)傳統(tǒng)的Apriori算法進行了改進，充分利用云計算的大數(shù)據(jù)存儲和計算的能力來提高Apriori算法的運行效率。

1 傳統(tǒng)的Apriori算法

傳統(tǒng)的Apriori算法是在海量數(shù)據(jù)庫中挖掘關聯(lián)規(guī)則最基本的算法，由數(shù)據(jù)庫專家是由Agrawal Rakesh等人在1994年所提出的[3]。該算法目的在于快速地尋找海量數(shù)據(jù)庫中的頻繁項集，是一種單維單層的布林關聯(lián)規(guī)則，與市場購物籃分析的結(jié)果相同。使用Apriori算法進行關聯(lián)規(guī)則挖掘時是利用支持度閾值來減少在尋找頻繁項集時，全部項所可能生成的候選項集組合個數(shù)，主要分為以下幾個步驟：

1)Apriori算法將先掃描一次整個事務集合，由此計算每一個項的支持度（出現(xiàn)頻率）。該動作結(jié)束后，根據(jù)預設的最小支持度閾值（min_sup）限制，便可得到所有頻繁項集的集合F1；

2)循環(huán)依序選取上一步經(jīng)迭代所得到的頻繁(K-1)項集，進而產(chǎn)生新的候選K項集；

3)Apriori算法須將重新再掃描整個事務集合一次，該動作是為了要重新計算新候選K項集的支持度計數(shù) （出現(xiàn)次數(shù)）。接著，通過子集函數(shù)subset()來確定包含在每一個事務ti中的CK所有候選K項集；

4)經(jīng)過計算候選K項集的支持度計數(shù)（出現(xiàn)次數(shù)）后，Apriori算法將剔除支持度計數(shù)少于最小支持度計數(shù)閾值（N*min_sup）的候選K項集。該動作是為了要從候選K項集中選取所有的頻繁K項集；

5)當計算到FK=Φ時，這意味沒有新的頻繁項集能夠產(chǎn)生。此時，Apriori算法產(chǎn)生頻繁項集的部份計算結(jié)束；

6)輸出頻繁K項集集合的結(jié)果。

Apriori算法的偽代碼如下：

2 優(yōu)化M apReduce框架

MapReduce是目前非常流行的分布式計算架構(gòu)主要是通過網(wǎng)絡來處理在云端上儲存的大量數(shù)據(jù)[4]。將要執(zhí)行的MapReduce程序復制到 Master node以 及各個Worker，Master node會決定要給哪臺WorkerWorker去執(zhí)行Map程序或者Reduce程序。通過Map程序?qū)?shù)據(jù)切成許多區(qū)塊，經(jīng)過Map階段產(chǎn)生出 Key/Value，將此 Key/Value存儲在 Local disc，然后經(jīng)過Shuffle（將相同屬性的key排序在一起）。而Reduce程序?qū)⑦@些Shuffle后的結(jié)果進行整合，最再將產(chǎn)生出來。

由于MapReduce只能對單個數(shù)據(jù)集合進行操作的情況下去執(zhí)行，對于Apriori算法中需要進行剪枝操作(也就是再次訪問讀取數(shù)據(jù)庫中的事務記錄)，會導致計算效率會下降。這就需要對MapReduce框架進行優(yōu)化。我們引入了一個歸并函數(shù)Fusion，用于將候選項集合中不需要二次讀取數(shù)據(jù)庫性質(zhì)的項集進行刪除。Fusion函數(shù)的流程如圖1所示。

圖1 Fusion函數(shù)流程圖Fig.1 Flow chart fusion function

3 云計算下改進的Apriori算法

在改進后的MapReduce計算框架基礎上，提出了基于此框架的關聯(lián)規(guī)則Apriori算法，稱為動態(tài)數(shù)據(jù)分配Apriori算法(DDAS:Dynamic Data Apriori Scheduler)。算法的主要思想是：將Apriori算法中關于頻繁集和項集的計算部署到云計算環(huán)境下執(zhí)行，同時采用改進的MapReduce計算框架，簡化了任務執(zhí)行的復雜度，提高系統(tǒng)響應時間，并且控制剪枝任務的數(shù)量避免引起任務抖動[5]。

1)Map函數(shù)從數(shù)據(jù)庫中讀取文件記錄[6]，并將這些事務記錄保存為項集，同時判斷是否可以進行連接，不能進行連接的舍棄，從而產(chǎn)生頻繁集的一個列表。同時，Map函數(shù)將輸入的數(shù)據(jù)切割成固定大小，并記錄下頻繁集中的所有記錄在數(shù)據(jù)庫中出現(xiàn)的頻度，最后將產(chǎn)生的候選集結(jié)果當做中間結(jié)果返回。

2)MapReduce框架中的節(jié)點會選擇Mapper對讀取的表進行遍歷，然后將預處理得到中間結(jié)果輸出給Reducer，并將最終得到的結(jié)果進行存儲。

3)對于Apriori算法存在剪枝任務須再次讀取數(shù)據(jù)的特性，我們采用自身合并(self-Fusion)操作，引入Fusion函數(shù)。Fusion函數(shù)基于最小支持度和Apriori性質(zhì)(任何非頻繁項集的子集都不可能是頻繁項集的子集)對項集進行壓縮，計算出頻繁項集集合，刪除掉候選項集中不符合Apriori性質(zhì)的項集。如果此時項集已經(jīng)為空（即處理完成），則將結(jié)果保存到數(shù)據(jù)庫上并輸出去給用戶；否則，執(zhí)行2）[7-9]。

4 實驗及分析

在局域網(wǎng)內(nèi)使用4節(jié)點的集群環(huán)境，每個節(jié)點的配置相同，CPU是酷睿2 1.83 GHz，內(nèi)存2 G；千兆以太網(wǎng)卡。操作系統(tǒng)是Ubuntu Linux 13.10，Java環(huán)境為 JDK 1.7，Hadoop版本是0.20.2，HBase版本為0.90.1，配置好MapReduce的分布式計算環(huán)境。使用來自于加里福利亞大學提供的一個公用數(shù)據(jù)集進行測試，這個數(shù)據(jù)集記錄了某血液中心獻血者的一些數(shù)據(jù)，我們選擇其中呢 40人的數(shù)據(jù)作為實驗樣本。

在Eclipse平臺下編寫了改進版本的Apriori算法與傳統(tǒng)的Apriori算法測試結(jié)果進行比較，結(jié)果如圖2所示。

圖2 所用時間趨勢Fig.2 Diagram of time trend

通過改進版本的Apriori算法，所使用的時間如圖2所示，較傳統(tǒng)的特征方法有明顯的減少，以40人的樣本數(shù)為例，改進版本的Apriori算法所用時間為Apriori算法的1/3。

本文將網(wǎng)絡環(huán)境下的數(shù)據(jù)識別作為必要手段，統(tǒng)計了處理前后隨著樣本數(shù)變化在識別率方面的差異，如圖3所示。實驗結(jié)果表明使用改進版本的Apriori算法能夠有效提升數(shù)據(jù)的識別率，以40人的樣本數(shù)為例，傳統(tǒng)的Apriori算法識別率為73%，而改進版本的Apriori算法的識別率為91%，在識別率方面提升了18%。

圖3 識別率的差異Fig.3 Diagram of recognition rate

5 結(jié)束語

文中通過對傳統(tǒng)的關聯(lián)規(guī)則Apriori算法進行分析，在現(xiàn)有的云計算框架MapReduce的基礎上進行改進，提出了一種新的關聯(lián)規(guī)則改進Apriori算法，通過利用云計算的高速數(shù)據(jù)處理能力來解決傳統(tǒng)關聯(lián)規(guī)則Apriori算法性能較差的缺點。實驗表明，該算法簡單易實現(xiàn)，所需時間大幅降低，能夠有效提高關聯(lián)規(guī)則Apriori算法的運算效率。

[1]韓家煒.數(shù)據(jù)挖掘[M].北京：機械工業(yè)出版社，2009.

[2]陳康，鄭緯民.云計算：系統(tǒng)實例與研究現(xiàn)狀[J].軟件學報，2009，20（5）：1337-1348.CHEN Kang,ZHENG Wei-Min.Cloud Computing:System Instances and Current Research[J].Journal of Software, 2009,20(5):1337-1348.

[3]邵峰晶，于忠清.數(shù)據(jù)挖掘原理與算法[M].北京：中國水利水電出版社，2003.

[4]鄭啟龍，房明，汪勝，等.基于MapReduce模型的并行科學計算[J].微電子學與計算機，2009，26（8）：13-17.ZHENG long,FANG Ming,WANG Sheng,et al.Scientific parallel computing based on mapReduce model[J].Microel Ectronics&Computer,2009,26(8):13-17.

[5]Apache基金會.Hadoop[EB/OL].(2009)[2014].http://lucene.apache.org/hadoop/.

[6]王鄂，李 銘.云計算下的海量數(shù)據(jù)挖掘研究[J].現(xiàn)代計算機(專業(yè)版)，2009，10（11）：22-25.WANG E,LI Ming.Research on mass data mining under cloud computing[J].Modern Computer,2009,10(11):22-25.

[7]劉華元，袁琴琴，王保保.并行數(shù)據(jù)挖掘算法綜述[J].電子科技，2006，9(1)：65-73.LIU Hua-yuan,YUAN Qin-qin,WANG Bao-bao.Review of the parallel data mining algorithm[J].Electronic science and technology,2006,9(1):65-73.

[8]李志堅，莫建麟.一種改進的基于概念格的數(shù)據(jù)挖掘算法[J].重慶師范大學學報：自然科學版，2013（2）：92-95.LI Zhi-jian,MO Jian-lin.An improved concept lattice-based data mining algorithm[J].Journal of Chongqing Normal University:Natural Science,2013（2）：92-95.

[9]朱德利.基于Weka的就業(yè)數(shù)據(jù)分析和模式挖掘--以重慶市信管專業(yè)為例 [J].重慶師范大學學報：自然科學版，2014（4）：120-125.ZHU De-li.Employment data analysis and pattern mining based on Weka--take specialty of information management and information system in chongqing for example[J].Journal of Chongqing Normal University:Natural Science,2014（4）：120-125.

An improved association rules based on cloud computing

LIU Jiang
（Department of Information Engineering，F(xiàn)ushun Vocational Technology Institute，F(xiàn)ushun 113006，China）

With the mature of data mining technology,including the application of association rules in large scale data has become the current hot spot.In order to improve the efficiency of data mining,in MapReducethe is introduced Fusion function and optimized,the Apriori algorithm based on Cloud was designed,the process and key technology was discussed in details.Experiments show that this method has obtained the good experimental effect,overcomes the Apriori algorithm is time-consuming and low recognition rate,It is a practical tool that realizing the data mining.

MapReduce;data mining;association rule;Apriori algorithm

TN919.5

A

1674－6236（2015）10-0048-03

2014-10-26 稿件編號：201410191

劉 姜(1980—)，男，遼寧昌圖人，講師。研究方向：計算機網(wǎng)絡應用與安全。