一種基于Hadoop架構(gòu)的并行挖掘算法研究

曾俊

摘 要： 基于Hadoop架構(gòu)，提出一種并行的決策樹挖掘算法實現(xiàn)大數(shù)據(jù)集間的知識挖掘。通過MapReduce并行編程模式實現(xiàn)Hadoop架構(gòu)下SPRINT并行挖掘算法的頻繁項集，解決了大數(shù)據(jù)集挖掘效率低下，時間消耗量大的問題。SPRINT算法通過對原始數(shù)據(jù)集進行劃分，并將分塊數(shù)據(jù)發(fā)給不同Map進程并行計算，使系統(tǒng)存儲和計算資源得到有效利用，運用MapReduce各計算節(jié)點將挖掘結(jié)果數(shù)據(jù)匯聚，減少中間結(jié)果數(shù)據(jù)量，使并行挖掘時間顯著減少。SPRINT算法并行化實驗表明，Hadoop架構(gòu)下的SPRINT并行挖掘算法具有良好的可擴展性和集群加速比。

關(guān)鍵詞： 挖掘算法； Hadoop架構(gòu)； SPRINT； 并行化； 決策樹； MapReduce

中圖分類號： TN911.1?34； TP311 文獻標識碼： A 文章編號： 1004?373X（2018）01?0117?03

Abstract： A parallel decision tree mining algorithm based on Hadoop is proposed to realize the knowledge mining between large data sets. The frequent item sets of SPRINT parallel mining algorithm under the Hadoop architecture is realized with the MapReduce parallel programming mode to solve the problems of low efficiency and large time consumption for large data sets mining. The original data set is divided with SPRINT algorithm， and its block data is sent to different Map process for parallel computing， which can utilize the system storage and computing resources availably. The MapReduce is used to aggregate the mining results of each computing node， reduce the data quantity of the intermediate results， and decrease the parallel mining time significantly. The SPRINT parallel algorithm was verified with experiments. The experimental results show that the SPRINT parallel mining algorithm under Hadoop architecture has strong scalability and perfect speedup ratio.

Keywords： mining algorithm； Hadoop architecture； SPRINT； parallelization； decision tree； MapReduce

0 引 言

數(shù)據(jù)挖掘是通過對數(shù)據(jù)的分析，在大量數(shù)據(jù)集中進行有價值信息尋找的技術(shù)。文獻[1]提出一種決策樹挖掘算法（SDT），SDT算法對未知數(shù)據(jù)集、已知數(shù)據(jù)集進行同時挖掘，并建立決策樹，從而快速對未知數(shù)據(jù)集進行理解，進而對未知數(shù)據(jù)集的特性進行關(guān)注。但SDT算法以傳統(tǒng)串行思想為基礎(chǔ)，只能對小規(guī)模數(shù)據(jù)進行處理，對于規(guī)模大的數(shù)據(jù)，挖掘效率比較低下，在進行決策樹的構(gòu)造時，時間會較長，同時還會因內(nèi)存限制，造成無法運行[2]。Hadoop從基礎(chǔ)構(gòu)架的角度來說屬于分布式，能夠在未知的條件下對分布式的應(yīng)用程序進行并行性的開發(fā)，文件系統(tǒng)（HDFS）通過流式數(shù)據(jù)訪問模式，可進行超大文件的存儲[3]。本文基于Hadoop架構(gòu)，提出一種并行的決策樹挖掘算法來實現(xiàn)大數(shù)據(jù)集間的知識挖掘。

1 決策樹挖掘算法SPRINT算法

SPRINT算法采用的屬性選擇度量為Gini指標，對于SPRINT而言，在數(shù)據(jù)集[D]中，條數(shù)據(jù)記錄分為[D1，][D2，]分別對應(yīng)包含的數(shù)據(jù)記錄為[m1]條，[m2]條，Gini指標計算公式：

[GinisplitD=m1m2GiniD1+m1m2GiniD2] （1）

1.1 并行化方案設(shè)計

1.1.1 決策樹節(jié)點的并行

在由拓撲結(jié)構(gòu)組成的決策樹中，通過各樹節(jié)點的不斷分裂，就生成了樹，從實際的角度上來說就是將數(shù)據(jù)集進行分裂。圖1為樹節(jié)點并行化，在圖1a）中，傳統(tǒng)SPRINT算法在分裂時將某個樹節(jié)點上的屬性列表看作整體，決策樹會在節(jié)點分裂時產(chǎn)生，主要是由不斷遞歸來完成的。在MapReduce的框架計算結(jié)構(gòu)當中，Map具有強大的映射處理功能，能夠借助于PatITioer完成函數(shù)的定義，將不同進行不同Reducer的對映射，之后進行進一步的處理。由于這樣的原因，相應(yīng)的Reducer上會反應(yīng)決策樹當中的節(jié)點屬性，最后進行并行處理，見圖1b）。在生成樹中，每層算法均一樣，只要執(zhí)行一次循環(huán)，屬性列表的節(jié)點和分裂構(gòu)造就可實現(xiàn)。

1.1.2 屬性選擇度量的并行

SPRINT算法中，在進行節(jié)點的屬性度量中Gini主要進行一個可并行化的過程。圖2為節(jié)點屬性度的計算并行。在樹節(jié)點并行機制上，進行屬性列表的Gini指標計算的建立，在相同樹節(jié)點中，不同的節(jié)點在相應(yīng)的決策樹上都有其屬性。由于上面的原因，想要保證并行化的樹節(jié)點標記，在尋址階段應(yīng)當滿足上面提到的Patitioner規(guī)則。相同的屬性和樹節(jié)點在進行標記時，才能夠?qū)崿F(xiàn)Reducer的處理和實施。

1.1.3 Gini指標排序的并行

在SPRINT的一個算法當中，數(shù)據(jù)如果屬于一個連續(xù)性的屬性列表，在進行Gini指標的計算時需要尋找分裂點，因此，該連續(xù)值屬性列表需要進行排序。在數(shù)據(jù)集完全拆分成屬性列表后，SPRINT算法會進行連續(xù)值屬性列表的排序，當數(shù)據(jù)集規(guī)模非常龐大時，整個算法受設(shè)計的排序算法影響較大，可通過MapReduce框架的天然排序特性得到解決。

2 基于Mapreduce框架的SPRINT算法具體實現(xiàn)

2.1 決策樹根節(jié)點的創(chuàng)建與分裂

兩個任務(wù)要在第一個階段來完成，基本的屬性列表都是要形成的，屬性列表是由拆分之后的數(shù)據(jù)集組成的，之后出現(xiàn)了決策樹的根節(jié)點；另一方面根據(jù)根節(jié)點分裂的情況，之后每個Job的作業(yè)控制由MRApp Master負責。

2.1.1 Job1階段

在Job1階段，Map過程負責拆分數(shù)據(jù)集，生成屬性列表，用來表征全部數(shù)據(jù)集的信息。Input Format組件實現(xiàn)MapReduce框架的讀取操作，在Input Format中，通過Record Reader由Input Split的多個鍵值對，由Map（）函數(shù)對其進行處理，從HDFS上進行數(shù)據(jù)集中樣本對象的讀取，并進行Map操作。在SPRINT算法中，Reducer通過映射之后對已經(jīng)排序過的屬性列表進行處理。

2.1.2 Job2階段

Job2階段是判斷、匯總、執(zhí)行Job1的處理結(jié)果，Job1的輸出就是Job2的Map過程的輸入，由于根節(jié)點只有一個，因此全部屬性列表在一個Reduce上進行分發(fā)。在進行輸入時，包括每一個屬性的分裂點以及Gini的值，Gini對應(yīng)的屬性值為節(jié)點分裂最小的屬性值。

2.2 決策樹主要階段的生成

2.2.1 Job3階段

Job3階段的任務(wù)目的和Job1類似，分裂出的子節(jié)點可作為下一輪分裂樹節(jié)點的“根節(jié)點”。在這里，實現(xiàn)屬性表的映射是Map的任務(wù)。在Hadoop MapReduce框架中，通過借助一定的組件，Map能夠從HDFS上面讀取一定的數(shù)據(jù)信息。在第一個階段中Patitioner進行時，Map根據(jù)情況的不同分發(fā)不同的數(shù)據(jù)，因此能夠完成并行的機制。

2.2.2 Job4階段

該階段和Job2的目的有一定的相似性，能夠分割最佳的樹節(jié)點屬性，差別是Job4階段分裂的樹節(jié)點較多。Job4作業(yè)的Map過程是收集依附于某個樹節(jié)點的全部屬性列表數(shù)據(jù)。相對于第一階段Job2的Reduce來說，Job4作業(yè)的Reduce在選擇最佳分割屬性前，要判斷該節(jié)點是否有葉節(jié)點生成，也就是對其是否達到循環(huán)終止條件進行判斷。若達到終止條件，則不再分裂樹節(jié)點的所有屬性列表；反之，算法繼續(xù)執(zhí)行。

2.3 決策樹結(jié)構(gòu)的完成

決策樹是將上面得到的數(shù)據(jù)按照一定規(guī)則分配好后，將樹的基本構(gòu)造完成。三個階段的試驗方法完成之后，能夠?qū)PRINT串行算法運行在云計算平臺Hadoop上，進而完成在大量的數(shù)據(jù)中挖掘和提取數(shù)據(jù)的工作。

3 SPRINT算法并行化實驗

3.1 SPRINT準確率驗證

實驗對比分析SPRINT算法的MapReduce模型和串行模型，對SPRINT算法的分類準確率進行測試。實驗數(shù)據(jù)樣本來源于UCI，在UCI中選取3個數(shù)據(jù)集，分類進行測試，具體如表1所示。其中35%樣本作為測試數(shù)據(jù)，65%樣本作為訓練數(shù)據(jù)。Hadoop平臺共有3個計算節(jié)點數(shù)目。

圖3為SPRINT算法的3個數(shù)據(jù)集的準確率比較，由圖3知，表1當中三個樣本集的并行和串行模型準確率都是非常接近的，能夠看到此算法對最后的準確率影響是比較小的。

3.2 集群并行化的可擴展性和加速比

實驗通過不同規(guī)模的集群計算節(jié)點、不同大小的數(shù)據(jù)集，對SPRINT算法并行的可擴展性效果和集群加速比進行驗證。實驗數(shù)據(jù)來源于UCI，根據(jù)3.1實驗數(shù)據(jù)集Adult的樣本，隨機生成規(guī)模不同的實驗樣本，具體見表2。圖4，圖5為可擴展比實驗結(jié)果。

從圖4和圖5可以看出，SPRINT算法具有比較好的集群和可擴展性，能夠提升大規(guī)模數(shù)據(jù)計算的速度；可擴展性和集群加速比隨著集群節(jié)點的增加均有一定程度的下降，原因是由于并行化程度和對應(yīng)的數(shù)據(jù)集大小均已達到最大化，不能隨著集群的運算節(jié)點的增加而增長。

4 結(jié) 語

本文基于Hadoop架構(gòu)，提出一種并行的決策樹挖掘算法實現(xiàn)大數(shù)據(jù)集間的知識挖掘。通過MapReduce并行編程模式實現(xiàn)Hadoop架構(gòu)下SPRINT并行挖掘算法的頻繁項集，解決了大數(shù)據(jù)集挖掘效率低下，時間消耗量大的問題。SPRINT算法通過對原始數(shù)據(jù)集進行劃分，并將分塊數(shù)據(jù)發(fā)給不同Map進程并行計算，使系統(tǒng)存儲和計算資源得到有效利用，運用MapReduce，各計算節(jié)點將挖掘結(jié)果數(shù)據(jù)匯聚，減少中間結(jié)果數(shù)據(jù)量，使并行挖掘時間顯著減少。SPRINT算法并行化實驗表明，Hadoop架構(gòu)下的SPRINT并行挖掘算法具有良好的可擴展性和集群加速比。

參考文獻

[1] DONG Guozhu， HAN Qian. Mining shared decision trees between datasets [R]. USA： Wright State University， 2010.

[2] 周建華.一種基于Hadoop架構(gòu)的網(wǎng)絡(luò)輿情熱點話題挖掘方法[J].河北北方學院學報（自然科學版），2014，30（6）：19?24.ZHOU Jianhua. A mining method for hot topics of network public opinion based on Hadoop architecture [J]. Journal of Hebei North University （natural science edition）， 2014， 30（6）： 19?24.

[3] 張振友，孫燕，丁鐵凡，等.一種新型的基于Hadoop框架的分布式并行FP?Growth算法[J].河北工業(yè)科技，2016，33（2）：169?178.

ZHANG Zhenyou， SUN Yan， DING Tiefan， et al. A new distributed parallel FP?Growth algorithm based on Hadoop framework [J]. Hebei industrial science and technology， 2016， 33（2）： 169?178.

[4] 施亮，錢雪忠.基于Hadoop的并行FP?Growth算法的研究與實現(xiàn)[J].微電子學與計算機，2015，32（4）：150?154.

SHI Liang， QIAN Xuezhong. Research and implementation of FP?Growth algorithm based on parallel Hadoop [J]. Microelectronics & computer， 2015， 32（4）： 150?154.

[5] HAN jiawei， KAMBER M.數(shù)據(jù)挖掘：概念與技術(shù)[M].范明，孟小峰，譯.北京：機械工業(yè)出版社，2008.

HAN Jiawei， KAMBER M. Data mining： concepts and techniques [M]. Translated by FAN Ming， MENG Xiaofeng. Beijing： Mechanical Industry Press， 2008.

[6] ZAKI M J. Fast vertical mining using diffsets [R]. New York， USA： Rensselaer Polytechnic Institute， 2001.

[7] Apache. Apache Hadoop [EB/OL]. [2012?12?03]. http：//hadoop.apache.org/.

[8] MAITREYA S， JHAB C K. MapReduce： simplified data analysis of big data [J]. Procedia computer science， 2015， 57： 563?571.

[9] 李國杰，程學旗.大數(shù)據(jù)的研究現(xiàn)狀與科學思考[J].中國科學院院刊，2012，27（6）：647?651.

LI Guojie， CHENG Xueqi. Big data research status and scientific thinking [J]. Chinese Science Research Institute Journal， 2012， 27（6）： 647?651.

[10] NESI Paolo， PANTALEO Gianni， SANESI Gianmarco. A Hadoop based platform for natural language processing of Web pages and documents [J]. Journal of visual languages and computing， 2015， 31： 130?138.

[11] WHITE T. Hadoop權(quán)威指南[M].華東師范大學數(shù)據(jù)科學與工程學院，譯.北京：清華大學出版社，2010.

WHITE T. Hadoop authoritative guide [M]. Translated by the School of Data Science and Engineering， East China Normal University. Beijing： Tsinghua University Press， 2010.endprint