一種基于Hadoop架構的并行挖掘算法研究

曾俊

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

關鍵詞： 挖掘算法； Hadoop架構； 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 引 言

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

1 決策樹挖掘算法SPRINT算法

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

[GinisplitD=m1m2GiniD1+m1m2GiniD2] （1）

1.1 并行化方案設計

1.1.1 決策樹節點的并行

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

1.1.2 屬性選擇度量的并行

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

1.1.3 Gini指標排序的并行

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

2 基于Mapreduce框架的SPRINT算法具體實現

2.1 決策樹根節點的創建與分裂

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

2.1.1 Job1階段

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

2.1.2 Job2階段

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

2.2 決策樹主要階段的生成

2.2.1 Job3階段

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

2.2.2 Job4階段

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

2.3 決策樹結構的完成

決策樹是將上面得到的數據按照一定規則分配好后，將樹的基本構造完成。三個階段的試驗方法完成之后，能夠將SPRINT串行算法運行在云計算平臺Hadoop上，進而完成在大量的數據中挖掘和提取數據的工作。

3 SPRINT算法并行化實驗

3.1 SPRINT準確率驗證

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

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

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

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

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

4 結 語

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

參考文獻

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

[2] 周建華.一種基于Hadoop架構的網絡輿情熱點話題挖掘方法[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].河北工業科技，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算法的研究與實現[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.數據挖掘：概念與技術[M].范明，孟小峰，譯.北京：機械工業出版社，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] 李國杰，程學旗.大數據的研究現狀與科學思考[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權威指南[M].華東師范大學數據科學與工程學院，譯.北京：清華大學出版社，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