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

劉姜

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

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

劉姜

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Apriori算法的偽代碼如下：

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

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

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

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

3 云計(jì)算下改進(jìn)的Apriori算法

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

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

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

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

4 實(shí)驗(yàn)及分析

在局域網(wǎng)內(nèi)使用4節(jié)點(diǎn)的集群環(huán)境，每個(gè)節(jié)點(diǎn)的配置相同，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的分布式計(jì)算環(huán)境。使用來自于加里福利亞大學(xué)提供的一個(gè)公用數(shù)據(jù)集進(jìn)行測(cè)試，這個(gè)數(shù)據(jù)集記錄了某血液中心獻(xiàn)血者的一些數(shù)據(jù)，我們選擇其中呢 40人的數(shù)據(jù)作為實(shí)驗(yàn)樣本。

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

圖2 所用時(shí)間趨勢(shì)Fig.2 Diagram of time trend

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

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

圖3 識(shí)別率的差異Fig.3 Diagram of recognition rate

5 結(jié)束語(yǔ)

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

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

[2]陳康，鄭緯民.云計(jì)算：系統(tǒng)實(shí)例與研究現(xiàn)狀[J].軟件學(xué)報(bào)，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].北京：中國(guó)水利水電出版社，2003.

[4]鄭啟龍，房明，汪勝，等.基于MapReduce模型的并行科學(xué)計(jì)算[J].微電子學(xué)與計(jì)算機(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基金會(huì).Hadoop[EB/OL].(2009)[2014].http://lucene.apache.org/hadoop/.

[6]王鄂，李 銘.云計(jì)算下的海量數(shù)據(jù)挖掘研究[J].現(xiàn)代計(jì)算機(jī)(專業(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]李志堅(jiān)，莫建麟.一種改進(jìn)的基于概念格的數(shù)據(jù)挖掘算法[J].重慶師范大學(xué)學(xué)報(bào)：自然科學(xué)版，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].重慶師范大學(xué)學(xué)報(bào)：自然科學(xué)版，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 稿件編號(hào)：201410191

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