基于粒計算的決策樹并行算法的應(yīng)用

周 浩，劉 萍，邱桃榮，白小明

（南昌大學(xué) 計算機(jī)科學(xué)與技術(shù)系，江西 南昌330031）

0 引 言

現(xiàn)已有許多研究學(xué)者對傳統(tǒng)的決策樹算法進(jìn)行了改進(jìn)，但是他們大部分的改進(jìn)只是為了提高分類精度，并未解決算法在處理海量數(shù)據(jù)挖掘時產(chǎn)生的延時問題。決策樹算法和當(dāng)前比較流行的云平臺Hadoop的結(jié)合是解決這一問題的有效途徑之一。

Zadeh引入了信息粒度化的思想［1］，粒度化的本質(zhì)其實就是聚類，所以它已被廣泛應(yīng)用于海量數(shù)據(jù)挖掘和復(fù)雜問題處理等方面。本文將粒計算引入，結(jié)合Hadoop平臺，提出了一種ID3決策樹分類算法。通過使用UCI標(biāo)準(zhǔn)數(shù)據(jù)集以及真實的雷電數(shù)據(jù)進(jìn)行多次測試，測試結(jié)果表明，本文算法實用有效，能很好解決傳統(tǒng)算法在處理海量數(shù)據(jù)挖掘時產(chǎn)生的延時問題。

1 MapReduce相關(guān)技術(shù)

MapReduce是一個分布式框架［2］，主要由編程模型和運行時環(huán)境這兩部分組成。其中編程模型為用戶提供了非常易用的編程接口，用戶只需要像編寫串行程序一樣實現(xiàn)兩個簡單的函數(shù) （map函數(shù)和reduce函數(shù)）即可實現(xiàn)一個分布式程序，而其它比較復(fù)雜的工作比如說節(jié)點的失效、數(shù)據(jù)的切分和節(jié)點之間的通信等，都是由運行時環(huán)境來完成。

MapReduce通過把海量數(shù)據(jù)集劃分成多個不同的小數(shù)據(jù)集然后交給搭建好的Hadoop集群中的各個計算機(jī)進(jìn)行處理來實現(xiàn)并行化。MapReduce編程模型［3］將問題抽象成Map和Reduce兩個階段。每個階段都是以＜key，value＞對作為輸入和輸出，而key和value的類型是可以由程序員自己定義或選擇的。其中Map 階段將數(shù)據(jù)解析成＜key，value＞對，迭代調(diào)用用戶編寫的map函數(shù)之后再以＜key，value＞的形式輸出到本地目錄；Reduce階段則將key相同的value進(jìn)行規(guī)約處理，并將最終結(jié)果寫到Hadoop分布式文件系統(tǒng)上 （Hadoop distributed file system，HDFS）上。其計算流程［4］如圖1所示。

圖1 MapReduce計算流程

2 基于粒計算的屬性信息增益獲取

2.1 粒的二進(jìn)制表示

給定信息系統(tǒng) （決策表）S＝（U，C∪D），其中條件屬性集C ＝｛c1，c2，…，cm｝，不失一般性設(shè)決策屬性只有一個，即D ＝｛d｝。對任意一個屬性ci∈C，i＝1，2，…，m，其中有離散屬性值的個數(shù)為ki，i＝1，2，…，m 個，那么以等價關(guān)系Ind（ci）可將U 劃分成ki個互不相交等價類，即構(gòu)成ki個信息粒。設(shè)決策屬性有h 個決策值，即有h 個不同的類型，那么就可以把U 劃分為h 個兩兩不相交的等價類，這h個等價類即為h 個信息粒。

用m 位二進(jìn)制串來表示的信息粒稱為二進(jìn)制信息粒［5］，m 為論域中對象的個數(shù)。若一個個體屬于該信息粒，那么就把該二進(jìn)制串中的相應(yīng)位的值置為1，否則置為0。該信息粒的粒度即為該二進(jìn)制串中所包含的1的個數(shù)。

2.2 基于二進(jìn)制信息粒的關(guān)聯(lián)矩陣與屬性信息增益

2.2.1 兩個具有不同屬性的二進(jìn)制信息粒之間的關(guān)聯(lián)運算

任意兩個不同屬性ci∈C，cj∈C，i≠j下對應(yīng)的兩個二進(jìn)制信息粒分別為cit，t∈｛1，2，…，ki｝和cjs，s∈｛1，2，…，kj｝，它們之間的關(guān)聯(lián)運算用符號∧表示，設(shè)運算結(jié)果所得到的信息粒用符號g表示，記為g＝cit∧cjs，該運算結(jié)果對應(yīng)的二進(jìn)制串是兩個二進(jìn)制信息粒的二進(jìn)制串之間的與運算，即有（g）b＝（cit）b∧（cjs）b。

2.2.2 二進(jìn)制信息粒向量

由屬性ci∈C，i＝1，2，…，m 對論域U 進(jìn)行粒化所構(gòu)成的ki個信息粒，并且每個信息粒以二進(jìn)制表示，即形成ki個二進(jìn)制信息粒的集合稱為屬性ci的二進(jìn)制信息粒向量，簡記為［ci］＝［ci1，ci2，…，ciki］。

2.2.3 二進(jìn)制信息粒關(guān)聯(lián)矩陣

由任一條件屬性ci∈C，i＝1，2，…，m 所構(gòu)成的ki個二進(jìn)制信息粒與決策屬性d 所構(gòu)成h 個二進(jìn)制信息粒向量之間進(jìn)行關(guān)聯(lián)運算，即建立如下關(guān)聯(lián)矩陣［5］

該關(guān)聯(lián)矩陣對應(yīng)的二進(jìn)制串矩陣表示記為

屬性ci的信息增益計算

經(jīng)過整理變?yōu)?/p>

3 基于MapReduce和粒計算的決策樹生成算法

3.1 決策樹分類的并行化設(shè)計思想

（1）二進(jìn)制信息粒關(guān)聯(lián)矩陣的并行化計算。通過設(shè)計實現(xiàn)一個Map函數(shù)和Reduce函數(shù)可以實現(xiàn)計算決策樹中任一結(jié)點下的關(guān)聯(lián)矩陣，以便為后續(xù)計算屬性信息增益提供數(shù)據(jù)。

（2）決策樹的任何分支結(jié)點進(jìn)行最佳分裂屬性選擇的并行化計算。

3.2 兩階段MapReduce函數(shù)的設(shè)計

本文采用數(shù)據(jù)和任務(wù)兩種并行方式［7－10］，在訓(xùn)練階段用了兩個MapReduce任務(wù)，第一個MapReduce任務(wù)是數(shù)據(jù)處理的并行化，對讀入的數(shù)據(jù)生成＜key，value＞對，用于計算相應(yīng)的二進(jìn)制信息粒關(guān)聯(lián)矩陣，便于后續(xù)階段計算屬性的信息增益大小。第二個MapReduce任務(wù)對樹的分枝結(jié)點并行計算出每一個子數(shù)據(jù)集的最佳分裂屬性，然后根據(jù)輸出結(jié)果生成決策規(guī)則或者構(gòu)建一層決策樹。訓(xùn)練階段的兩個MapReduce任務(wù)迭代執(zhí)行，直至構(gòu)建出滿足約束條件的決策樹。在測試階段用了一個MapReduce任務(wù)，讀入測試集的數(shù)據(jù)并根據(jù)已經(jīng)生成的決策規(guī)則進(jìn)行分類，計算出相應(yīng)的分類準(zhǔn)確率。

具體的兩個階段Map函數(shù)和Reduce函數(shù)設(shè)計［11－13］簡要描述如下：

算法1：TrainDataMap （）

算法2：TrainDataReduce （＜key，value＞，＜key’，value’＞）

/＊說明：這個階段完成對具有相同key值的數(shù)據(jù)進(jìn)行統(tǒng)計，即在每個決策樹結(jié)點下，計算二進(jìn)制信息粒關(guān)聯(lián)矩陣中的每個元素。

算法3：DecisionMap （＜key，value＞，＜key’，value’＞）

/＊說明：在已經(jīng)生成某結(jié)點下的關(guān)聯(lián)矩陣后，將計算各候選屬性的信息增益，以便確定最佳分裂屬性。

算法4：DecisionReduce （＜key，value＞，＜key’，value’＞）

3.3 剪枝處理

通過判斷sum ≤σ是否成立？σ是事先確定的最小記錄剪枝數(shù)據(jù)。

如果成立，則對結(jié)點不再進(jìn)行分枝，該結(jié)點即為葉子結(jié)點，取集合中具有最多的決策值作為該結(jié)點的決策類別，輸出＜結(jié)點號，決策值＞。

否則找出min｛si｝的那個屬性，設(shè)為cf，作為最佳分裂屬性。

4 實驗分析

4.1 測試環(huán)境

軟件環(huán)境：Hadoop－1.0.4，Ubuntu Linux 10.04.4，Jdk1.6.0＿41。

硬件環(huán)境：4 臺PC 機(jī)，其中1 臺為master，3 臺為slave。Master的配置為：CPU Pentium T4200 （雙核），內(nèi)存2G，網(wǎng)卡10Mbps，每臺slave 的配置為：CPU AMD A10－5800K （四核），內(nèi)存2G，網(wǎng)卡10Mbps。

4.2 測試數(shù)據(jù)

測試數(shù)據(jù)取自兩個領(lǐng)域：一是使用公共測試數(shù)據(jù)，即采用UCI（http：//archive.ics.uci.edu/ml/datasets.html）［14］的一些數(shù)據(jù)集，見表1；二是采用實際氣象領(lǐng)域的真實數(shù)據(jù)集。

4.3 測試結(jié)果與分析

4.3.1 算法準(zhǔn)確率的測試

本文在測試分類準(zhǔn)確性時，從原始數(shù)據(jù)集中隨機(jī)選取90%的數(shù)據(jù)作為訓(xùn)練集建立決策樹，選擇10%的數(shù)據(jù)作為測試集，對每個數(shù)據(jù)集都重復(fù)測試10次，取平均值作為測試準(zhǔn)確率。測試結(jié)果見表2。

采用本并行算法與文獻(xiàn) ［15］的算法的準(zhǔn)確率比較結(jié)果見表3。

表1 UCI數(shù)據(jù)集信息

表2 準(zhǔn)確率測試結(jié)果

表3 準(zhǔn)確率比較結(jié)果

從比較結(jié)果可以看出本文算法優(yōu)于文獻(xiàn) ［15］的算法。

此外，本文還對來自于江西省氣象局的2010年4月20日0時的真實雷電數(shù)據(jù)進(jìn)行了測試，由于真實的雷電數(shù)據(jù)都是連續(xù)型數(shù)據(jù)，所以在做測試之前運用了基于信息熵的離散化方法對數(shù)據(jù)集進(jìn)行了離散化。數(shù)據(jù)集描述見表4。

表4 雷電數(shù)據(jù)信息描述

測試方法是隨機(jī)提取該數(shù)據(jù)集中的30%作為測試數(shù)據(jù)。其余全部作為訓(xùn)練集。重復(fù)10次這樣的測試，取最后的平均值作為準(zhǔn)確率。測試結(jié)果見表5。

由表5可知，本文算法對真實的雷電數(shù)據(jù)的預(yù)測準(zhǔn)確率也有95%，說明本文算法是具有實際應(yīng)用價值的。

表5 雷電數(shù)據(jù)準(zhǔn)確率測試結(jié)果

4.3.2 算法運行時間測試及加速比

實驗數(shù)據(jù)來自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的若干標(biāo)準(zhǔn)數(shù)據(jù)集，為產(chǎn)生大規(guī)模數(shù)據(jù)，本實驗采用重復(fù)復(fù)制的手段將每個數(shù)據(jù)集放大到100M，300M，500M，1000M。并分別在slave為1臺，2臺，3臺機(jī)器組成的集群上運行，運行時間和加速比測試結(jié)果如圖2～圖7所示。

圖2 nursery數(shù)據(jù)集運行時間

圖3 zoo數(shù)據(jù)集運行時間

圖4 mushroom 數(shù)據(jù)集運行時間

從圖2到圖4可看出，在處理同一大小的數(shù)據(jù)集的時候，隨著集群節(jié)點的增加，處理時間越來越短，因為MapReduce對數(shù)據(jù)的處理在默認(rèn)的情況下是64M 為一個單位，所以在處理大于64M 的數(shù)據(jù)的時候都會把數(shù)據(jù)進(jìn)行分塊，然后分給各個節(jié)點并行處理，可想而知，當(dāng)節(jié)點越多，一次性處理的塊數(shù)就越多，這樣處理完整個數(shù)據(jù)集的時間就越短。

圖5 nursery數(shù)據(jù)集加速比

圖6 zoo數(shù)據(jù)集加速比

圖7 mushroom 數(shù)據(jù)集加速比

從圖5到圖7中我們還可以發(fā)現(xiàn)，在處理100M 的數(shù)據(jù)集的時候，1個節(jié)點，2個節(jié)點和3個節(jié)點的集群的處理時間都差不多 （加速比在1 附近），而在處理1000M 的數(shù)據(jù)集的時候處理時間卻差別很大，加速比幾乎呈一條直線，這說明本文算法可以用來解決海量數(shù)據(jù)挖掘問題。

5 結(jié)束語

本文提出了一種基于粒計算的ID3 算法，并且在Hadoop平臺上對其進(jìn)行了并行化研究。對提出的并行化算法用UCI數(shù)據(jù)集和真實的雷電數(shù)據(jù)進(jìn)行多次的測試分析，測試結(jié)果表明該算法具有較好的分類正確率、有效性和實用性，適用于處理規(guī)模較大的數(shù)據(jù)集。由于本文著重研究算法的并行化方法，所以本文的算法并未解決傳統(tǒng)的ID3算法選擇屬性取值較多的屬性作為分裂屬性這一缺點，這有待于后續(xù)的改進(jìn)。另外，還要進(jìn)一步開展包括算法的優(yōu)化和基于增量的并行化處理等方面的研究。

［1］ZHANG Sulan，GUO Ping，ZHANG Jifu，et al.Automatic semantic image annotation with granular analysis method ［J］.Acta Automatica Sinica，2012，38 （5）：689－690 （in Chinese）.［張素蘭，郭平，張繼福，等.圖像語義自動標(biāo)注及其粒度分析方法 ［J］.自動化學(xué)報，2012，38 （5）：689－690.］

［2］DONG Xicheng.Hadoop internals：In－depth study of MapReduce［M］.Beijing：China Machine Press，2013：32－34 （in Chinese）.［董西成.Hadoop技術(shù)內(nèi)幕：深入解析MapReduce架構(gòu)設(shè)計與實現(xiàn)原理 ［M］.北京：機(jī)械工業(yè)出版社，2013：32－34.］

［3］Lam C.Hadoop in action ［M］.Beijing：Posts and Telecom Press，2011：37－49 （in Chinese）. ［Lam C.Hadoop 實戰(zhàn)［M］.北京：人民郵電出版社，2011：37－49.］

［4］White T.Hadoop：The definitive guide［M］.Beijing：Tsinghua University Press，2011：28－31 （in Chinese）. ［White T.Hadoop權(quán)威指南 ［M］.北京：清華大學(xué)出版社，2011：28－31.］

［5］XU Jianfeng，LIU Lan，QIU Taorong，et al.Binary system matrix based on Ganular computing and its applications in decision－tree［J］.Journal of Guangxi Normal University，2008，26 （3）：158－159 （in Chinese）. ［徐劍鋒，劉斕，邱桃榮，等.基于粒計算的二進(jìn)制矩陣及在決策樹算法的應(yīng)用 ［J］.廣西師范大學(xué)學(xué)報，2008，26 （3）：158－159.］

［6］JIANG Shengyi，LI Xia，ZHENG Qi.Principles and practice of data mining ［M］.Beijing：Publishing House of Electronics Industry，2011：52－53 （in Chinese）.［蔣盛益，李霞，鄭琪.數(shù)據(jù)挖掘原理與實踐 ［M］.北京：電子工業(yè)出版社，2011：52－53.］

［7］XING Xiaoyu.Research and application of parallel decision tree classification algorithm ［D］.Kunming：Yunnan University of Finance and Economics，2010：25－29 （in Chinese）.［邢曉宇.決策樹分類算法的并行化研究及其應(yīng)用 ［D］.昆明：云南財經(jīng)大學(xué)，2010：25－29.］

［8］PAN Tianming.Research of the parallel decision tree algorithm based on Haddop ［D］.Shanghai：East China Normal University，2012：30－33 （in Chinese）.［潘天鳴.基于Hadoop平臺的決策樹算法并行化研究 ［D］.上海：華東師范大學(xué)，2012：30－33.］

［9］ZHU Min.Research and implementation of parallel decision tree classification algorithm based on MapReduce ［D］.Nanchang：Jiangxi Normal University，2011：13－14 （in Chinese）.［朱敏.基于MapReduce的并行決策樹分類算法研究與實現(xiàn)［D］.南昌：江西師范大學(xué)，2011：13－14.］

［10］Alham N K，Li Maozhen，Liu Yang.A MapReduce－based distributed SVM algorithm of automatic image annotation ［J］.Computers and Mathematics with Applications，2011，62（7）：2801－2811.

［11］QIAN Wangwei.Research of the ID3decision tree classification algorithm based on MapReduce ［J］.Computer and Modernization，2012，28 （2）：28－29 （in Chinese）. ［錢網(wǎng)偉.基于MapReduce的ID3決策樹分類算法研究 ［J］.計算機(jī)與現(xiàn)代化，2012，28 （2）：28－29.］

［12］Wu G，Li H，Hu X，et al.MReC4.5：C4.5ensemble classification with MapReduce ［C］//ChinaGrid Annual Conference.IEEE，2009：249－255.

［13］He Q，Zhuang F，Li J，et al.Parallel implementation of classification algorithms based on MapReduce ［M］.Rough Set and Knowledge Technology.Springer Berlin Heidelberg，2010：655－662.

［14］Lichman K B A M.｛UCI｝machine learning repository ［DB/OL］.University of California，Irvine，School of Information and Computer Sciences.http：//archive.ics.uci.edu/ml，2013－04－26.

［15］LU Qiu.Parallelization of decision tree algorithm based on MapReduce［J］.Journal of Computer Applications，2012，32 （9）：2465－2465 （in Chinese）. ［陸秋.基于MapReduce的決策樹算法并行化 ［J］.計算機(jī)應(yīng)用，2012，32 （9）：2465－2465.］