李運(yùn)娣

(河南工程學(xué)院 計(jì)算機(jī)學(xué)院，河南 鄭州 451191)

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

李運(yùn)娣

(河南工程學(xué)院 計(jì)算機(jī)學(xué)院，河南 鄭州 451191)

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

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

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

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

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

1 相關(guān)知識(shí)

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

1.1 ID3算法

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

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

(1)

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

(2)

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

1.2 MapReduce并行編程模型

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

圖1 MapReduce的計(jì)算過(guò)程Fig.1 MapReduce calculation process

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

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

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

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

2.1 Map階段的設(shè)計(jì)

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

Map(key,value)

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

Output:對(duì)

Begin

fori=1 tondo

提取所屬類別和每個(gè)屬性的屬性值

key=所屬類別，value=1,輸出對(duì)

對(duì)每個(gè)屬性值do

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

end do

end for

end

2.2 Reduce階段的設(shè)計(jì)

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

Reduce(key,value)

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

Output:對(duì)

Begin

對(duì)所有相同的key值do

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

end do

key′=key,value′=sum

輸出對(duì)

end

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

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

Generate_Decision_Tree

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

輸出：一棵決策樹(shù)

(1)創(chuàng)建一個(gè)節(jié)點(diǎn)N；

(2)如果S中樣本都為同一個(gè)類別C，則返回N作為樹(shù)中一個(gè)葉子節(jié)點(diǎn)，將其類別標(biāo)為C；

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

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

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

(6)對(duì)當(dāng)前節(jié)點(diǎn)N所長(zhǎng)出的滿足分裂屬性的屬性值為ai的樹(shù)的分支Si；

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

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

3 實(shí)驗(yàn)

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

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

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

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

圖3 集群對(duì)比Fig.3 Cluster comparison

4 結(jié)語(yǔ)

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

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

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

[3] 黃愛(ài)輝,陳湘濤.決策樹(shù)ID3算法的改進(jìn)[J].計(jì)算機(jī)工程與科學(xué),2009,31(6):109-111.

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

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

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

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

[9] 覃雄派,王會(huì)舉,杜小勇，等.大數(shù)據(jù)分析——RDBMS與MapReduce的競(jìng)爭(zhēng)與共生[J].軟件學(xué)報(bào),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

河南省高等學(xué)校重點(diǎn)科研項(xiàng)目(16A520004)

李運(yùn)娣(1978-)，女，河南鶴壁人，講師，主要研究方向?yàn)榉植际较到y(tǒng)、圖像處理與數(shù)據(jù)挖掘.

TP311

A

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