大數(shù)據(jù)環(huán)境下基于Hadoop框架的數(shù)據(jù)挖掘算法的研究與實現(xiàn)

洪波，呂燕霞，黃磊（武漢市勞動和社會保障信息中心 湖北 武漢 430022）

大數(shù)據(jù)環(huán)境下基于Hadoop框架的數(shù)據(jù)挖掘算法的研究與實現(xiàn)

洪波，呂燕霞，黃磊
（武漢市勞動和社會保障信息中心 湖北 武漢 430022）

為了提高大數(shù)據(jù)環(huán)境下的數(shù)據(jù)挖掘速度，對分布式計算構(gòu)架Hadoop進行分析與研究，提出一種基于Hadoop平臺的大數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘算法MRPrePost。該算法在PrePost算法基礎(chǔ)上改進而來，采用Hadoop平臺降低分布式編程的難度且易于管理，通過一種自底向上的深度優(yōu)化策略改進PrePost算法，降低內(nèi)存開銷，同時采用負載均衡的分組策略，來提高并行算法的性能，最終試驗表明，該算法運行速度快，適應(yīng)大數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘。

大數(shù)據(jù)；Hadoop；關(guān)聯(lián)規(guī)則；數(shù)據(jù)挖掘

隨著智能設(shè)備的普及，全世界在2010年的信息量已達ZB級別，預(yù)計2020年將上升到35ZB，大數(shù)據(jù)時代已經(jīng)來臨，如何快速準(zhǔn)確地挖掘出潛在的價值信息變得越來越重要。數(shù)據(jù)挖掘技術(shù)已經(jīng)發(fā)展多年，但發(fā)展速度趕不上信息量的爆炸式增長，現(xiàn)有的算法在處理大數(shù)據(jù)時顯得力不從心，如Apriori算法需多次檢索原數(shù)據(jù)庫，容易造成 I/O開銷[2]，F(xiàn)PGrowth算法在迭代挖掘頻繁時，產(chǎn)生的子樹結(jié)構(gòu)太多，不利于大數(shù)據(jù)挖掘[2]。因此根據(jù)大數(shù)據(jù)環(huán)境的特點，研究相應(yīng)的數(shù)據(jù)挖掘算法變得十分的迫切。本文基于Hadoop平臺，對PrePost算法進行改進，提出一種基于Hadoop平臺的大數(shù)據(jù)挖掘算法MRPrePost，該算法能夠適應(yīng)大數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘，計算速度快，為大數(shù)據(jù)時代下的數(shù)據(jù)挖掘技術(shù)研究提供一種新思路。

1 相關(guān)技術(shù)簡介

1.1 關(guān)聯(lián)規(guī)則挖掘技術(shù)

關(guān)聯(lián)規(guī)則挖掘以找出各事務(wù)相互間的聯(lián)系為目的，在各行各業(yè)廣泛應(yīng)用，如在超市購物中的應(yīng)用，根據(jù)交易記錄找尋各類型物品之間的相關(guān)性，進而分析購物者的購買行為，并依據(jù)分析結(jié)果指導(dǎo)貨架布局、貨存安排和對客戶分類。在進行數(shù)據(jù)挖掘之前，需要設(shè)定最小支持數(shù)和最小置信度，設(shè)定好參數(shù)之后，將挖掘出支持數(shù)大于或等于設(shè)定的最小支持數(shù)的項集，進而依據(jù)最小置信度得出有效的關(guān)聯(lián)規(guī)則[3]，關(guān)聯(lián)規(guī)則挖掘主要在于挖掘全部的頻繁項集。

設(shè)I={i1，i2，…，in}，其中 in為項，事物數(shù)據(jù)庫集Data={T1，T2，…，Tn}，其中Tn為事物，使得T?I，則關(guān)聯(lián)規(guī)則的邏輯蘊含形式為：A?B，A?I，B?I，且A∩B，A，B同為I的子集。

支持度為項集A、B的并集在事務(wù)集Data中出現(xiàn)的頻率。置信度為在項集A發(fā)生的條件下B發(fā)生的頻率。

1.2 Hadoop簡介

Hadoop是Apache的一個開源項目[4]，是可以提供開源、可靠、可擴展的分布式計算工具[7]。Hadoop主要包括HDFS和MapReduce兩個組件，分別用于解決大數(shù)據(jù)的存儲和計算。

1）HDFS

HDFS是獨立的分布式文件系統(tǒng)，為MapReduce計算框架提供存儲服務(wù)，具有較高的容錯性和高可用性，基于塊存儲以流數(shù)據(jù)模式進行訪問，數(shù)據(jù)節(jié)點之間相互備份[5-7]。默認存儲塊大小為64 M，用戶也可以自定義大小。

HDFS是基于主從結(jié)構(gòu)的分布式文件系統(tǒng)，結(jié)構(gòu)上包括NameNode目錄管理、DataNode的數(shù)據(jù)存儲和Client的訪問客戶端3部分[8]。NameNode主要負責(zé)系統(tǒng)的命名空間、集群的配置管理以及存儲塊的復(fù)制；DataNode是分布式文件系統(tǒng)存儲的基本單元；Client為與分布式文件系統(tǒng)的應(yīng)用程序[9]。體系結(jié)構(gòu)圖如圖1所示。

圖1 HDFS體系構(gòu)架圖

2）MapReduce

MapReduce是一種分布式計算框架，適用于離線大數(shù)據(jù)計算[10]。采用函數(shù)式編程模式，利用Map和 Reduce函數(shù)來實現(xiàn)復(fù)雜的并行計算。原理如圖2所示。

圖2 分布式計算原理

2 基于 Hadoop平臺的 MRPrePost挖掘算法

文中提出的MRPrePost算法是在改進的PrePost算法基礎(chǔ)上發(fā)展而來，可通過并行化平臺對數(shù)據(jù)進行關(guān)聯(lián)規(guī)則挖掘，該算法算法主要分為3部分，流程如圖3所示。

圖3 基于Hadoop平臺的MRPrePost算法流程圖

2.1 統(tǒng)計頻繁1項集

并行化計算首先將數(shù)據(jù)庫進行水平分片處理[11-13]，每一個子文件稱為Block，每個Block被分配到集群的worker節(jié)點上，作為Map函數(shù)的輸入值，并統(tǒng)計相應(yīng)節(jié)點上Block文件出現(xiàn)的次數(shù)。具體過程為Map函數(shù)將Block文件分成pair＜key=num，String＞，之后對String按照項集進行分割，形成pair＜key，value=1＞，其中key為單個的項，Combine函數(shù)將具有相同key值的鍵值進行初步合并，將得到的新鍵值作為下一階段Reduce的輸入，最后合并來自各個節(jié)點的鍵值對，根據(jù)設(shè)定好的支持數(shù)閾值生成頻率1項集FIM1，同時根據(jù)支持數(shù)降序排列生成全局F-list。統(tǒng)計過程如表1所示。

表1頻繁1項集統(tǒng)計過程

假設(shè)最小支持數(shù)閾值為minsupp=2，則F-list序列

為（b:4；c:4；e:3；f:3；a:2）。

具體代碼為：

Procedure:Mapper （Long Writable key，Text Writable values，Context context）

forearch values do

items[]＜-split（values）

for i=0 to items.length-1 do

set＜key，value＞=＜items[i]，1＞

context.write（key，value）

end

end

Procedure:combiner（TextWritable key，Iterator＜LongWritable＞values，Context context）

sum＜-0

foreach LongWritable value in values do

sum+=value.get（）

end

context.write（key，newLongWritable（sum））

Procedure:Reducer（TextWritable key，Iterator＜LongWritable＞values，Context context）

sum＜-0

for i=0 tovalues.size（）-1 do

sum+=values[i]

end

if sum＞=minsupp do

context.write（key，newLongWritable（sum））

end

2.2 對F-list均勻分組

設(shè)置支持數(shù)閾值可以方便的調(diào)節(jié)F-list規(guī)模，當(dāng)挖掘比價精準(zhǔn)的關(guān)聯(lián)規(guī)則時，需要得到盡可能多的頻繁1項集，但過多的項集導(dǎo)致無法在內(nèi)存中建立PPC-Tree樹，使得后續(xù)挖掘工作無法進行，為了避免這種情況的發(fā)生，可將PPC-Tree樹分割成多個獨立的子樹，降低了PPC-tree樹的深度和占用的內(nèi)存空間[14]。

對F-list分組涉及到系統(tǒng)的負載均衡問題，處理不好嚴(yán)重影響系統(tǒng)性能。本文采用將F-list中所有的項集均勻分散到N組中，記為G-list，其中組員記為（gid），設(shè)N=2，最小支持數(shù)minsupp=2，則分組情況如表2所示。

表2 監(jiān)控的指標(biāo)

2.3 并行挖掘頻繁模式

對F-list分組是為了將事務(wù)重新劃分，保證劃分后能夠建立獨立的PPC-tree樹，本次采用將事務(wù)記錄集的各條記錄中的非頻繁項去除，頻繁項按照支持數(shù)降序組成一條路徑path，沿著path這條路徑遍歷所有的項集，如果path[k]對應(yīng)的組號為gid，則將gid與path[k]左邊的所有項組成鍵值對然后發(fā)送到Reduce函數(shù)，傳輸之前必須進行序列化，因此需要對path[1，2...，k]進行Java序列化處理，建立序列化對象PathArray。預(yù)處理之后，各節(jié)點啟動新任務(wù)，Map階段根據(jù)G-list將事務(wù)記錄的路徑分配到不同的Reduce節(jié)點中，具體過程如下舉例說明。表3為G-list的hash的映射過程。

表3 監(jiān)控數(shù)據(jù)指標(biāo)

在Map階段：

1）讀取緩存中的F-list和G-list，將G-list項集中的各個數(shù)據(jù)項用序號代替。

2）建立hash表HTable，以G-list中項作為key組號gid作為值value。

3）依次讀取頻繁項item，利用步驟二的組號gid，并以gid作為鍵key，將排在item左邊的全部頻繁項作為值 value構(gòu)成鍵對值＜key=gid；value= items＞，作為Map階段的輸出值，為了避免重復(fù)，刪除HTable中的value=gid的所有鍵值對，如果hash過程找不到對應(yīng)的組號，則繼續(xù)前一個項進行相同操作，直到一條記錄處理完畢。

4）重復(fù)3）直到所有記錄完成分配。

例如將最后一條事務(wù)記錄經(jīng)預(yù)處理之后變?yōu)椋?，2，3，4），當(dāng)讀取4時，組號為gid=1，于是輸出鍵值對＜key，value＞=＜1:（1，2，3，4）。同時刪除value=1的所有鍵值對，繼續(xù)讀取3，組號為gid=2，輸出鍵值對＜key.value＞=＜2:（1，2，3）＞，同時刪除value=2的所有鍵值對。繼續(xù)讀取2、1，在HTable中不能找到對應(yīng)的組號，無需輸出任何數(shù)據(jù)。記錄如表4所示。

表4記錄

2.4 算法性能測試

選取美國10年間發(fā)生的交通事故數(shù)據(jù)集accidents.dat，來測試MRPrePost算法的性能[15]，將數(shù)據(jù)集在集群模式上對MRApriori算法、PFP-Growth算法及MRPrePost算法進行對比試驗。硬件上選用配置相同的臺式機，CPU主頻為2.11GHz，內(nèi)存為2G，硬盤為256 G。操作系統(tǒng)均為Ubuntu10.0。經(jīng)過運算，3種算法的速度對比如圖4所示。

圖4 3種算法速度對比

從圖4中可看出3種算法隨著支持數(shù)的增加，運算得時間都減少，同時可看出MRPrePost算法的速度最快，效果最好。

3 結(jié) 論

文中針對現(xiàn)有大數(shù)據(jù)挖掘算法規(guī)則繁瑣、計算速度慢等問題，提出了一種基于Hadoop平臺的使用并行關(guān)聯(lián)技術(shù)的大數(shù)據(jù)挖掘算法MRPrePost，將“并行化”處理數(shù)據(jù)的方法融入PrePost挖掘算法中，縮短計算時間。與MRApriori算法、PFP-Growth算法的性能測試結(jié)果表明：改進后的算法能夠適應(yīng)大數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘，縮短了挖掘算法的計算時間，具有一定的現(xiàn)實意義。

[1]王海濤，陳樹寧.常用數(shù)據(jù)挖掘算法研究[J].電子設(shè)計工程，2011（11）:90-93.

[2]胡志剛，梁曉揚.基于Hadoop的海量網(wǎng)格數(shù)據(jù)建模[J].計算機系統(tǒng)應(yīng)用，2010（10）:22-24.

[3]吳澤倫.基于Hadoop的數(shù)據(jù)挖掘算法并行化研究與實現(xiàn)[D].北京：北京郵電大學(xué)，2014.

[4]金連，王宏志，黃沈濱，等.基于Map-Reduce的大數(shù)據(jù)缺失值填充算法 [J].計算機研究與發(fā)展，2013（S1）:29-33.

[5]胡善杰.在云環(huán)境下的數(shù)據(jù)挖掘算法的并行化研究[D].成都：電子科技大學(xué)，2013.

[6]錢愛玲，瞿彬彬，盧炎生，等.多時間序列關(guān)聯(lián)規(guī)則分析的論壇輿情趨勢預(yù)測[J].南京航空航天大學(xué)學(xué)報，2012（6）:32-35.

[7]呂奕清，林錦賢.基于MPI的并行PSO混合K均值聚類算法[J].計算機應(yīng)用，2011（2）:26-29.

[8]白云龍.基于Hadoop的數(shù)據(jù)挖掘算法研究與實現(xiàn)[D].北京：北京郵電大學(xué)，2011.

[9]劉軍.Hadoop大數(shù)據(jù)處理[M].北京：人民郵電出版社，2013.

[10]胡金安.云數(shù)據(jù)中心計算資源監(jiān)控系統(tǒng)的設(shè)計與實現(xiàn)[D].成都：電子科技大學(xué)，2012.

[11]孫寅林.基于分布式計算平臺的海量日志分析系統(tǒng)的設(shè)計與實現(xiàn)[D].西安：西安電子科技大學(xué)，2012.

[12]胡光民，周亮，柯立新.基于Hadoop的網(wǎng)絡(luò)日志分析系統(tǒng)研究[J].電腦知識與技術(shù)，2010（22）:13-16.

[13]楊旻.Hadoop云計算平臺在高校實驗室教學(xué)環(huán)境中的實現(xiàn)[J].電腦知識與技術(shù)，2011（9）：34-38.

[14]黃立勤，柳燕煌.基于MapReduce并行的Apriori算法改進研究[J].福州大學(xué)學(xué)報：自然科學(xué)版，2011 （5）:36-39.

[15]耿生玲，李永明，劉震.關(guān)聯(lián)規(guī)則挖掘的軟集包含度方法[J].電子學(xué)報，2013（4）:38-41.

Research and design of distributed cloud monitoring platform system based on Hadoop

HONG Bo，LV Yan-xia，HUANG Lei
（Wuhan City Labor and Social Security Information Center，Wuhan 430022，China）

In order to increase the speed of data mining for large data environment，analyze and study on distributed computing architecture Hadoop，put forward a kind of large data association rule mining algorithm based on Hadoop platform MRPrePost.In PrePost algorithm based on improved the algorithm，and reduce the difficulty of the distributed programming with Hadoop platform and easy to manage，through the depth of a bottom-up PrePost algorithm optimization strategy，reduce the memory overhead，at the same time using grouping strategy of load balancing，to improve the performance of parallel algorithm，the final test shows that the algorithm is fast，to adapt to the big data mining association rules.

big data；Hadoop；association rules；data mining

TN918

A

1674－6236（2017）07-0041-04

2016-04-09稿件編號：201604090

洪 波（1976—），男，安徽涇縣人，中級職稱。研究方向：數(shù)據(jù)挖掘。