曾俊

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

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

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

1 決策樹挖掘算法SPRINT算法

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

[GinisplitD=m1m2GiniD1+m1m2GiniD2] （1）

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

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

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

1.1.2 屬性選擇度量的并行

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

1.1.3 Gini指標(biāo)排序的并行

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

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

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

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

2.1.1 Job1階段

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

2.1.2 Job2階段

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

2.2 決策樹主要階段的生成

2.2.1 Job3階段

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

2.2.2 Job4階段

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

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

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

3 SPRINT算法并行化實(shí)驗(yàn)

3.1 SPRINT準(zhǔn)確率驗(yàn)證

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

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

3.2 集群并行化的可擴(kuò)展性和加速比

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

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

4 結(jié) 語

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

參考文獻(xiàn)

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

[2] 周建華.一種基于Hadoop架構(gòu)的網(wǎng)絡(luò)輿情熱點(diǎn)話題挖掘方法[J].河北北方學(xué)院學(xué)報(bào)（自然科學(xué)版），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算法的研究與實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(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].范明，孟小峰，譯.北京：機(jī)械工業(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] 李國杰，程學(xué)旗.大數(shù)據(jù)的研究現(xiàn)狀與科學(xué)思考[J].中國科學(xué)院院刊，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].華東師范大學(xué)數(shù)據(jù)科學(xué)與工程學(xué)院，譯.北京：清華大學(xué)出版社，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