洪波，呂燕霞，黃磊（武漢市勞動(dòng)和社會(huì)保障信息中心 湖北 武漢 430022）

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

洪波，呂燕霞，黃磊
（武漢市勞動(dòng)和社會(huì)保障信息中心 湖北 武漢 430022）

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

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

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

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

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

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

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

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

1.2 Hadoop簡(jiǎn)介

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

1）HDFS

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

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

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

2）MapReduce

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

圖2 分布式計(jì)算原理

2 基于 Hadoop平臺(tái)的 MRPrePost挖掘算法

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

圖3 基于Hadoop平臺(tái)的MRPrePost算法流程圖

2.1 統(tǒng)計(jì)頻繁1項(xiàng)集

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

表1頻繁1項(xiàng)集統(tǒng)計(jì)過(guò)程

假設(shè)最小支持?jǐn)?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 對(duì)F-list均勻分組

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

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

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

2.3 并行挖掘頻繁模式

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

表3 監(jiān)控?cái)?shù)據(jù)指標(biāo)

在Map階段：

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

2）建立hash表HTable，以G-list中項(xiàng)作為key組號(hào)gid作為值value。

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

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

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

表4記錄

2.4 算法性能測(cè)試

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

圖4 3種算法速度對(duì)比

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

3 結(jié) 論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[15]耿生玲，李永明，劉震.關(guān)聯(lián)規(guī)則挖掘的軟集包含度方法[J].電子學(xué)報(bào)，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稿件編號(hào)：201604090

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