李運娣

(河南工程學院 計算機學院，河南 鄭州 451191)

大數(shù)據(jù)環(huán)境下決策樹算法并行化研究

李運娣

(河南工程學院 計算機學院，河南 鄭州 451191)

決策樹算法是數(shù)據(jù)挖掘中重要的分類算法，但目前多數(shù)針對決策樹的改進方法都基于傳統(tǒng)的串行算法，不能滿足大數(shù)據(jù)環(huán)境下對海量數(shù)據(jù)挖掘的需要.針對大數(shù)據(jù)集中串行挖掘算法效率低下的問題，采用MapReduce對決策樹算法進行了并行化實現(xiàn)，同時引入修正參數(shù)來改進ID3算法傾向于多值屬性選取的問題.實驗結(jié)果表明，該算法具有較好的并行性和擴展性，能有效處理大數(shù)據(jù)集的分類問題.

決策樹；MapReduce；大數(shù)據(jù)；并行化

數(shù)據(jù)挖掘[1]是知識發(fā)現(xiàn)的有效手段，能夠讓人們獲取未知的知識、提升數(shù)據(jù)的價值.隨著網(wǎng)絡(luò)的普及和大數(shù)據(jù)時代的到來，數(shù)據(jù)呈爆炸式增長.與此同時，計算機硬件的提升則相對有限.在大數(shù)據(jù)環(huán)境下，傳統(tǒng)的數(shù)據(jù)挖掘算法的局限越來越明顯，很難滿足大數(shù)據(jù)分析的需求.

分類問題是數(shù)據(jù)挖掘研究的熱點問題，目前有很多成熟的分類算法，決策樹算法[2]是其中一個經(jīng)典的算法.基于信息熵的ID3算法是決策樹分類模型中最常用的算法，該算法用信息增益作為屬性選擇的準則，選擇信息增益最大屬性作為決策樹構(gòu)造的分裂點.ID3算法的不足之處在于基于信息熵的計算方法偏向于特征值數(shù)目較多的屬性，而此屬性往往不是最優(yōu)的.隨著數(shù)據(jù)量的增加，算法的計算量也快速增加，大大降低了算法的效率，內(nèi)存駐留問題限制了數(shù)據(jù)處理的規(guī)模.針對這些問題，本課題提出了許多相應(yīng)的決策樹改進方法[3-5]，這些方法在一定程度上改善了決策樹算法在應(yīng)用過程中所面臨的問題，但無法有效應(yīng)對海量數(shù)據(jù)的挖掘問題.

并行機制是海量數(shù)據(jù)挖掘的一種有效解決方法，也是近年來數(shù)據(jù)挖掘算法研究的熱點.傳統(tǒng)的并行方法主要是基于消息傳遞的如PVM和MPI并行編程模型[6].PVM有較好的負載平衡能力和容錯性，而MPI相對簡單，在消息傳遞領(lǐng)域應(yīng)用廣泛.基于消息傳遞的并行化算法適合處理計算密集型問題，當處理數(shù)據(jù)密集型問題時，通訊代價快速增加會使系統(tǒng)性能大大降低.傳統(tǒng)的方法抽象度較低，需要顯式處理一些編程的底層細節(jié)問題，這提高了并行程序設(shè)計的復雜度.云計算的提出，尤其是MapReduce編程模型[7]的興起，降低了并行程序設(shè)計的難度，又由于數(shù)據(jù)的分布存儲避免了大量數(shù)據(jù)在網(wǎng)絡(luò)上的傳輸，MapReduce更適合大數(shù)據(jù)環(huán)境下海量數(shù)據(jù)的處理需求[8-9].ID3算法的應(yīng)用非常廣泛，但其并行化研究較少.因此，對MapReduce編程模型進行深入研究，對經(jīng)典的決策樹ID3算法理論進行剖析，利用信息增益計算過程中屬性間的相互獨立性并基于文件橫向分裂的方式進行了ID3算法的MapReduce并行化設(shè)計和實現(xiàn)，同時引入了修正參數(shù)來改進其傾向于多值屬性選取的問題.

1 相關(guān)知識

本研究主要對已有的ID3算法運用MapReduce編程模型進行并行化設(shè)計和實現(xiàn)，下面對ID3算法和MapReduce并行編程模型進行介紹.

1.1 ID3算法

ID3算法是一個貪心算法，它從根節(jié)點開始，采用信息增益作為選擇分枝屬性的分裂準則，計算各屬性的信息增益，然后選擇信息增益最大的屬性為節(jié)點，自頂向下遞歸構(gòu)造決策樹.ID3決策樹構(gòu)造的相關(guān)理論描述如下：

設(shè)S是一個含有t個樣本的數(shù)據(jù)集合，Ci(i=1,2, …,n)為S中樣本的分類，每個分類Ci中含有的樣本數(shù)為ti，則S中樣本分類所需要的期望信息為

(1)

設(shè)A為樣本集合S的一個屬性且有v個不同的取值{a1,a2, …,av}，選擇屬性A對S進行劃分，將S分為v個子集{S1,S2, …,Sv}，Sj為集合S中屬性A的值為aj的樣本集合，則基于屬性A對集合S進行分類的期望信息為

(2)

信息增益為原信息需求與新信息需求之間的差值，則屬性A相應(yīng)于樣本集合S的信息增益定義為Gain(S,A)=E(S)-E(S,A)，Gain(S,A)越大，說明使用屬性A作為測試屬性進行分類提供的信息越多，ID3算法就是選擇信息增益最大的屬性作為當前節(jié)點的分裂屬性來進行決策樹構(gòu)造的.

1.2 MapReduce并行編程模型

Google公司于2004年最先提出MapReduce技術(shù)，它是一種并行編程模型，主要通過大規(guī)模服務(wù)器集群解決大數(shù)據(jù)集的并行計算問題.MapReduce一經(jīng)推出，立即引起了工業(yè)界和學術(shù)界的廣泛關(guān)注，它通過接受用戶自己編寫的Map函數(shù)和Reduce函數(shù)自動在大規(guī)模數(shù)據(jù)集上并行執(zhí)行，在系統(tǒng)層面上解決了可擴展性與容錯性等問題.MapReduce編程模型采取“分而治之”的思想，先對大數(shù)據(jù)集進行分割，得到成百上千的小數(shù)據(jù)塊，然后把這些小數(shù)據(jù)塊分配給多個計算節(jié)點來共同完成計算任務(wù)，計算完成后再把各計算節(jié)點得到的結(jié)果進行歸并，從而得到任務(wù)最終的計算結(jié)果，具體過程如圖1所示.

圖1 MapReduce的計算過程Fig.1 MapReduce calculation process

MapReduce的并行計算過程主要分為Map和Reduce兩個階段.在Map階段，Map任務(wù)先將輸入數(shù)據(jù)塊轉(zhuǎn)換成鍵/值對，鍵一般為數(shù)據(jù)記錄文件的行號，值為該行文件對應(yīng)的內(nèi)容，然后自定義Map函數(shù)對輸入鍵/值對進行處理，產(chǎn)生一系列的中間鍵/值對緩存在內(nèi)存中，緩存的中間鍵/值對定期寫入硬盤并記錄位置信息，以便下一階段的處理.在Reduce階段，對Map階段產(chǎn)生的中間鍵/值對進行處理，Reduce函數(shù)合并所有具有相同鍵值的中間鍵/值對，形成較小的值的集合，Reduce處理后的結(jié)果可添加到對應(yīng)分區(qū)的輸出文件中.整個文件的最終輸出結(jié)果可以通過合并所有Reduce處理輸出而得到.

MapReduce模型的核心是Map和Reduce函數(shù)，使用者只需要關(guān)注這兩個函數(shù)的具體計算任務(wù)即可，其他并行模式中的復雜問題如分布式文件系統(tǒng)、工作調(diào)度等都是由MapReduce模型后臺處理的.由于簡潔性、實用性、可擴展性等優(yōu)點，MapReduce已成為當前最流行的并行數(shù)據(jù)處理模型，它在大數(shù)據(jù)集的存儲、管理與處理過程中也越來越受到人們的關(guān)注.

2 決策樹算法的并行化實現(xiàn)

決策樹算法中最耗費資源的階段是最佳分裂屬性的選擇部分，利用MapReduce對該階段進行并行化計算會大大提高決策樹生成的效率，使之適應(yīng)大數(shù)據(jù)處理的需求.在ID3算法中，信息增益的計算是基于屬性間相互獨立的，可以利用MapReduce并行地計算出信息增益所需的各個屬性的相應(yīng)信息，從而快速選出最佳分裂屬性.

2.1 Map階段的設(shè)計

假定樣本數(shù)據(jù)文件按行存儲，每行一個記錄樣本，數(shù)據(jù)具有內(nèi)部無關(guān)性.Map階段的任務(wù)是讀取樣本數(shù)據(jù)文件，然后按需要對每個記錄進行解析.信息增益的計算需要統(tǒng)計訓練數(shù)據(jù)集屬于每類的元組數(shù)及每類中每個屬性的各屬性值的元組數(shù)，所以Map函數(shù)的輸入為以記錄形式存儲的訓練數(shù)據(jù)集，輸出key設(shè)計為所屬類別或所屬類別、屬性名、屬性值，value的值為1.Map函數(shù)偽代碼如下：

Map(key,value)

Input:訓練數(shù)據(jù)集S

Output:對

Begin

fori=1 tondo

提取所屬類別和每個屬性的屬性值

key=所屬類別，value=1,輸出對

對每個屬性值do

key=<所屬類別，屬性名，屬性值>，value=1, 輸出對

end do

end for

end

2.2 Reduce階段的設(shè)計

Reduce階段的任務(wù)比較單一，主要是對Map階段輸出的對進行統(tǒng)計輸出而得到全局結(jié)果.Reduce函數(shù)的輸入數(shù)據(jù)為Map階段輸出的對，在函數(shù)內(nèi)部對具有相同key值的記錄進行累加，最后輸出對，key′為Map階段輸出的key值，value′為所有相同key值的累加結(jié)果.Reduce函數(shù)偽代碼如下：

Reduce(key,value)

Input: Map函數(shù)生成的對

Output:對

Begin

對所有相同的key值do

累計計數(shù)其value值，結(jié)果保存到sum

end do

key′=key,value′=sum

輸出對

end

2.3 并行執(zhí)行ID3算法

引入修正參數(shù)后，修正的信息增益表示為Gain′(S, A)=f(v)Gain(S, A).將Gain′(S, A)作為新的屬性選擇判斷標準，屬性的取值個數(shù)越多，f(v)越小，減少了ID3算法屬性選擇時傾向于多值屬性的問題.利用MapReduce對決策樹算法中最耗費資源的最佳分裂屬性的選擇部分進行并行化計算，以提高決策樹的生成效率，使之適應(yīng)大數(shù)據(jù)處理的需求，改進后的ID3算法執(zhí)行步驟描述如下：

Generate_Decision_Tree

輸入：訓練數(shù)據(jù)集S，候選屬性集C

輸出：一棵決策樹

(1)創(chuàng)建一個節(jié)點N；

(2)如果S中樣本都為同一個類別C，則返回N作為樹中一個葉子節(jié)點，將其類別標為C；

(3)如果C為空，則返回N作為樹的葉節(jié)點，將其類別標為S中樣本出現(xiàn)次數(shù)最多的類別；

(4)對S中的數(shù)據(jù)樣本進行MapReduce操作，根據(jù)各個Reduce節(jié)點返回的統(tǒng)計輸出結(jié)果，計算并找出最大修正信息增益屬性，以此屬性作為分裂屬性；

(5)用分裂屬性所對應(yīng)的每一個屬性值ai來劃分S，假設(shè)Si是S中相應(yīng)屬性值為ai的元組的集合；

(6)對當前節(jié)點N所長出的滿足分裂屬性的屬性值為ai的樹的分支Si；

(7)如果Si為空，則為決策樹增加一個新的葉節(jié)點，類別為S中的多數(shù)類；

(8)否則，增加一個由Generate_DecisionTree( Si, 候選屬性集)所返回的新節(jié)點.

3 實驗

本實驗主要驗證決策樹算法并行化后具有高效性和可擴展性，以適應(yīng)海量數(shù)據(jù)處理的需求，實驗數(shù)據(jù)來自UCI數(shù)據(jù)集.算法基于Hadoop平臺，實現(xiàn)了該方法的MapReduce化，實驗所用集群由7臺PC機組成.其中，1臺為Master節(jié)點，另外6臺為Slave節(jié)點.為了方便對比，同時進行了單機決策樹ID3算法和MPI環(huán)境下的并行ID3算法.

首先，對串行算法、基于MPI并行化方法與本研究中基于MapReduce并行化方法在處理相同數(shù)據(jù)規(guī)模時所需要的時間進行了對比，結(jié)果如圖2所示.從圖2可以看出，當數(shù)據(jù)規(guī)模較小時，集群與單機計算時間相差不大，當數(shù)據(jù)規(guī)模增加時，單機隨著數(shù)據(jù)規(guī)模的增加而快速增長，數(shù)據(jù)規(guī)模越大，這種增長趨勢越明顯，達到一定程度時會由于機器內(nèi)存不足而使程序無法正常運行，而集群則始終平穩(wěn)運行.隨著數(shù)據(jù)規(guī)模的增加，集群的優(yōu)勢較明顯，計算時間增加平穩(wěn)，各個節(jié)點的資源消耗波動較小，系統(tǒng)顯示了良好的可擴展性.同時，由于MPI方法的通信開銷較大，在相同情況下基于MPI并行化的決策樹ID3算法的性能要低于基于MapReduce并行化算法.

為了考查集群規(guī)模對數(shù)據(jù)處理的影響，對本算法在不同節(jié)點數(shù)量的集群上進行了實驗，結(jié)果如圖3所示.從圖3可知，集群規(guī)模與數(shù)據(jù)處理能力密切相關(guān)，隨著節(jié)點數(shù)量的增加，處理相同規(guī)模的數(shù)據(jù)所需的運行時間越短，特別是隨著數(shù)據(jù)規(guī)模的增加，這種趨勢越來越明顯.

圖2 不同數(shù)據(jù)量下3種方法運行時間比較Fig.2 Comparison of three methods’ runtimefor different data sizes

圖3 集群對比Fig.3 Cluster comparison

4 結(jié)語

決策樹算法是數(shù)據(jù)挖掘中重要的分類算法，ID3是決策樹算法中的經(jīng)典算法，但它存在偏袒屬性值數(shù)目較多這一缺點，而且傳統(tǒng)的并行算法不能滿足大數(shù)據(jù)環(huán)境下對海量數(shù)據(jù)處理的需求.針對上述問題，引入了修正參數(shù)來解決ID3算法傾向于多值屬性選取的問題，然后借助當前流行的MapReduce編程模型對決策樹ID3算法進行了并行化實現(xiàn).實驗表明，改進后的算法與傳統(tǒng)的決策樹算法相比具有較大的優(yōu)勢，能夠有效地支持海量數(shù)據(jù)的計算，具有良好的可擴展性，能夠滿足大數(shù)據(jù)環(huán)境下對大規(guī)模數(shù)據(jù)處理的需求.

[1] HAN J,KAMBER M,PEI J.數(shù)據(jù)挖掘概念與技術(shù)[M].3版.北京:機械工業(yè)出版社,2012.

[2] QUILAN J R.Induction of decision trees[J].Machine Learning,1986,1(1):81-106.

[3] 黃愛輝,陳湘濤.決策樹ID3算法的改進[J].計算機工程與科學,2009,31(6):109-111.

[4] 馮少榮,肖文俊.基于樣本選取的決策樹改進算法[J].西南交通大學學報,2009,44(5):643-647.

[5] 黃宇達,范太華.決策樹ID3算法的分析與優(yōu)化[J].計算機工程與設(shè)計,2012,33(8):3089-3093.

[6] 任波,王乘.MPI集群通信性能分析[J].計算機工程,2004,30(11):71-73.

[8] 宋杰,郭朝鵬,王智，等.大數(shù)據(jù)分析的分布式MOLAP技術(shù)[J].軟件學報,2014,25(4):731-752.

[9] 覃雄派,王會舉,杜小勇，等.大數(shù)據(jù)分析——RDBMS與MapReduce的競爭與共生[J].軟件學報,2012,23(1):32-45.

Research on parallelization of decision tree algorithm under big data environment

LI Yundi

(CollegeofComputerScience,HenanUniversityofEngineering,Zhengzhou451191,China)

Decision tree is an important classification algorithm in data mining, but most of the improvement methods for decision tree are based on the traditional serial algorithm, which can’t meet the need of massive data mining under big data environment. For the inefficiency of serial mining algorithm in massive data, MapReduce is used to parallelize the decision tree algorithm. At the same time, the modified parameters are introduced to avoid the ID3 algorithm tending to multi-valued attribute selection problem. The experimental results show that the proposed algorithm has good parallelism and scalability, and can effectively deal with massive data classification problem.

decision tree; MapReduce; big data; parallelization

2017-01-12

河南省高等學校重點科研項目(16A520004)

李運娣(1978-)，女，河南鶴壁人，講師，主要研究方向為分布式系統(tǒng)、圖像處理與數(shù)據(jù)挖掘.

TP311

A

1674-330X(2017)02-0057-05