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

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

0 引 言

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

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

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

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

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

圖1 MapReduce計(jì)算流程

2 基于粒計(jì)算的屬性信息增益獲取

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

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

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

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

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

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

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

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

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

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

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

屬性ci的信息增益計(jì)算

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

3 基于MapReduce和粒計(jì)算的決策樹(shù)生成算法

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

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

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

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

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

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

算法1：TrainDataMap （）

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

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

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

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

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

3.3 剪枝處理

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

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

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

4 實(shí)驗(yàn)分析

4.1 測(cè)試環(huán)境

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3.2 算法運(yùn)行時(shí)間測(cè)試及加速比

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

本文提出了一種基于粒計(jì)算的ID3 算法，并且在Hadoop平臺(tái)上對(duì)其進(jìn)行了并行化研究。對(duì)提出的并行化算法用UCI數(shù)據(jù)集和真實(shí)的雷電數(shù)據(jù)進(jìn)行多次的測(cè)試分析，測(cè)試結(jié)果表明該算法具有較好的分類正確率、有效性和實(shí)用性，適用于處理規(guī)模較大的數(shù)據(jù)集。由于本文著重研究算法的并行化方法，所以本文的算法并未解決傳統(tǒng)的ID3算法選擇屬性取值較多的屬性作為分裂屬性這一缺點(diǎn)，這有待于后續(xù)的改進(jìn)。另外，還要進(jìn)一步開(kāi)展包括算法的優(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）.［張素蘭，郭平，張繼福，等.圖像語(yǔ)義自動(dòng)標(biāo)注及其粒度分析方法 ［J］.自動(dòng)化學(xué)報(bào)，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è)計(jì)與實(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 實(shí)戰(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ì)算的二進(jìn)制矩陣及在決策樹(shù)算法的應(yīng)用 ［J］.廣西師范大學(xué)學(xué)報(bào)，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ù)挖掘原理與實(shí)踐 ［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）.［邢曉宇.決策樹(shù)分類算法的并行化研究及其應(yīng)用 ［D］.昆明：云南財(cái)經(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平臺(tái)的決策樹(shù)算法并行化研究 ［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的并行決策樹(shù)分類算法研究與實(shí)現(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決策樹(shù)分類算法研究 ［J］.計(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的決策樹(shù)算法并行化 ［J］.計(jì)算機(jī)應(yīng)用，2012，32 （9）：2465－2465.］