大數據環境下基于Hadoop框架的數據挖掘算法的研究與實現

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

大數據環境下基于Hadoop框架的數據挖掘算法的研究與實現

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

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

大數據；Hadoop；關聯規則；數據挖掘

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

1 相關技術簡介

1.1 關聯規則挖掘技術

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

設I={i1，i2，…，in}，其中 in為項，事物數據庫集Data={T1，T2，…，Tn}，其中Tn為事物，使得T?I，則關聯規則的邏輯蘊含形式為：A?B，A?I，B?I，且A∩B，A，B同為I的子集。

支持度為項集A、B的并集在事務集Data中出現的頻率。置信度為在項集A發生的條件下B發生的頻率。

1.2 Hadoop簡介

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

1）HDFS

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

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

圖1 HDFS體系構架圖

2）MapReduce

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

圖2 分布式計算原理

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

文中提出的MRPrePost算法是在改進的PrePost算法基礎上發展而來，可通過并行化平臺對數據進行關聯規則挖掘，該算法算法主要分為3部分，流程如圖3所示。

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

2.1 統計頻繁1項集

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

表1頻繁1項集統計過程

假設最小支持數閾值為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均勻分組

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

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

表2 監控的指標

2.3 并行挖掘頻繁模式

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

表3 監控數據指標

在Map階段：

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

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

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

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

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

表4記錄

2.4 算法性能測試

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

圖4 3種算法速度對比

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

3 結 論

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

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

[2]胡志剛，梁曉揚.基于Hadoop的海量網格數據建模[J].計算機系統應用，2010（10）:22-24.

[3]吳澤倫.基于Hadoop的數據挖掘算法并行化研究與實現[D].北京：北京郵電大學，2014.

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

[5]胡善杰.在云環境下的數據挖掘算法的并行化研究[D].成都：電子科技大學，2013.

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

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

[8]白云龍.基于Hadoop的數據挖掘算法研究與實現[D].北京：北京郵電大學，2011.

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

[10]胡金安.云數據中心計算資源監控系統的設計與實現[D].成都：電子科技大學，2012.

[11]孫寅林.基于分布式計算平臺的海量日志分析系統的設計與實現[D].西安：西安電子科技大學，2012.

[12]胡光民，周亮，柯立新.基于Hadoop的網絡日志分析系統研究[J].電腦知識與技術，2010（22）:13-16.

[13]楊旻.Hadoop云計算平臺在高校實驗室教學環境中的實現[J].電腦知識與技術，2011（9）：34-38.

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

[15]耿生玲，李永明，劉震.關聯規則挖掘的軟集包含度方法[J].電子學報，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—），男，安徽涇縣人，中級職稱。研究方向：數據挖掘。