丁 偉，萬定生，樊 龍

(河海大學計算機與信息學院，江蘇 南京 210098)

0 引言

國務院于2010～2012 年開展了第一次全國水利普查。普查主要內(nèi)容包括河流湖泊基本情況、水利工程基本情況、經(jīng)濟社會用水情況、河流湖泊治理保護情況、水土保持情況、水利行業(yè)能力建設情況以及灌區(qū)和地下水取水井情況8 大專題33 小類近1 億個基本對象［1-2］。面對如此寶貴的、海量的水利普查數(shù)據(jù)資源，可以利用數(shù)據(jù)挖掘技術［3］，從海量的水利普查數(shù)據(jù)中獲取有價值的知識、規(guī)律或模型，為謀劃水利事業(yè)的長遠發(fā)展提供可靠、安全、可用的信息。但是由于傳統(tǒng)數(shù)據(jù)挖掘算法(如:C4.5、FP-Growth等)［4-5］，無論在計算能力還是在并行化能力方面遠遠不能滿足當前的需求，所以如何采用更好的數(shù)據(jù)挖掘模式來實現(xiàn)低成本、高效率、高可靠的數(shù)據(jù)處理分析，已經(jīng)成為亟待解決的問題。

基于上述背景，本文提出一種基于Map/Reduce的水利普查數(shù)據(jù)決策樹［6］分類挖掘方法——MRC4.5 算法。以河南省地下水取水井數(shù)據(jù)為樣本，對基于Map/Reduce 編程模型的MRC4.5 算法進行決策樹分類挖掘，實驗結(jié)果表明該算法的分析結(jié)果和分類規(guī)則符合要求，具有一定的實用價值。

1 相關理論與技術

1.1 C4.5 算法基本原理

C4.5 算法的基本思想是利用信息熵原理［7］，選擇信息增益率［8］最大的屬性作為分類屬性，然后遞歸構(gòu)造決策樹的分支，直至完成決策樹的構(gòu)建。其算法思想如下［9-10］:

假設訓練數(shù)據(jù)樣本集D={X1，X2，…，Xn}，每個樣本包含的屬性集合Ai(i=1，2，…，m)共有m 個不同值，其中，Am為類別屬性，其余均為非類別屬性。設屬性Am有t 個不相同的值，則樣本集D 被Am的不同取值劃分為D1，D2，…，Dt個子集，樣本集D 對該分類的信息熵為:

假設Ai(0≤i≤m -1)有k 個不同的取值，那么Ai在樣本集D 被類別屬性Am劃分的基礎上將D1，D2，…，Dt劃分為t×k 個子集，則樣本集D 對該分類的信息熵為:

屬性Ai的信息增益計算公式如下:

Gain(D，Ai)=Info(D)-Info(D，Ai)

屬性Ai的分割信息熵為:

由此得出信息增益率為:

1.2 Map/Reduce 編程模型

Map/Reduce［11-12］編程模型開源實現(xiàn)是Hadoop平臺，是當今主流的并行編程框架。Map/Reduce 可以有效計算大規(guī)模數(shù)據(jù)集，充分利用分布式并行計算的優(yōu)點。Map/Reduce 是Master/Slave 結(jié)構(gòu)，由一個作為任務主控節(jié)點的JobTracker 和多個作為任務計算節(jié)點的TaskTracker 組成［13］。JobTracker 可以運行在集群中任意節(jié)點上，主要負責任務分配、調(diào)度和管理所有的TaskTracker，將一個大任務分割出來的若干子任務分配給空閑的TaskTracker 進行處理，同時也可以對執(zhí)行失敗的任務重新分配執(zhí)行。Map/Reduce 核心計算過程包括Map 階段和Reduce 階段［14］。Map 函數(shù)接收一組Key/Value 經(jīng)過處理形成一組新的Key/Value 對，作為中間結(jié)果交給Ruduce 函數(shù)，Reduce 函數(shù)對中間值聚合起來的Key/Value 對進行處理得到最終結(jié)果。

2 并行MRC4.5 算法

基于單一節(jié)點下的C4.5 算法在水利普查數(shù)據(jù)規(guī)模較大時會面臨空間和時間上的雙重瓶頸，甚至出現(xiàn)異常。本文的MRC4.5 算法是基于Map/Reduce編程模型實現(xiàn)的并行化處理方法，可以有效地解決這些問題。MRC4.5 在決策樹構(gòu)造過程中，采用屬性并行計算和節(jié)點并行分裂，在挖掘過程主要分為連續(xù)屬性離散化階段和節(jié)點循環(huán)分裂階段。

2.1 基于聚類的連續(xù)屬性離散化

該階段利用并行K-means［15-16］算法對樣本數(shù)據(jù)集中的連續(xù)屬性進行聚類，并根據(jù)最終聚類結(jié)果對屬性進行離散化處理。并行K-means 聚類算法的輸入是連續(xù)屬性Ai和分類數(shù)目k。算法的設計如下:

Map 函數(shù)的主要任務是完成屬性Ai中每個記錄到各個中心點距離的計算，并標記其屬于新的聚類中心。Map 函數(shù)輸入鍵值對格式為＜key=lineNum，value=vi＞，其中l(wèi)ineNum 代表當前行號，vi代表所對應屬性值。首先每個Map 函數(shù)都要讀取聚類中心描述文件，來獲取上一輪迭代(初始聚類)的聚類中心，對于輸入的每條記錄，采用歐氏距離公式［17］計算出距離其最近的類中心，并做新的類別標記。Map 函數(shù)輸出鍵值對格式為＜key=id，value=item ＞，其中id代表當前記錄所屬類別標示，item 表示所對應的記錄。Map 函數(shù)的偽代碼如下:

Reduce 函數(shù)的任務是根據(jù)Map 端的輸出，更新聚類中心，供下一輪迭代使用。Reduce 函數(shù)輸入鍵值對格式為＜key=id，value=list_items ＞，其中id 代表記錄所屬聚類的類別標示，list_items 表示所屬該類別的記錄集合。Reduce 函數(shù)會統(tǒng)計key 相同的記錄個數(shù)和各個記錄分量的和，并求其均值，從而得到新的聚類中心。Reduce 函數(shù)輸出鍵值對格式為＜key=id，value=new_point ＞，其中id 代表聚類的類別標示，new_point 表示均值向量。Reduce 函數(shù)的偽代碼如下:

最后，通過比較上一輪Map/Reduce 任務得到的聚類中心與本輪得到的聚類中心的距離，若變化小于給定的閾值，則算法結(jié)束;否則，更新聚類中心描述文件，進行新的一輪迭代。

2.2 分裂指標并行計算

分裂指標并行計算主要負責生成屬性表，并統(tǒng)計出每個屬性表的分裂指標信息。Map 函數(shù)的任務是對樣本數(shù)據(jù)集進行預處理，并將其轉(zhuǎn)化為屬性表。Map 函數(shù)輸入的鍵值對格式為＜key=＜node_ID，flag ＞，value=items ＞，其中node_ID 表示當前待分裂樣本數(shù)據(jù)所屬節(jié)點編碼(由于根節(jié)點最先分裂，所以node_ID 初始值為0 即標示根節(jié)點)，flag 是用來區(qū)分下文所生成的屬性分裂信息的標記位(flag 的默認取值為1)，items=＜record_ID，value1，value2，value3，…，calss_label ＞。Map 函數(shù)將對輸入的待分類訓練樣本數(shù)據(jù)集進行逐條掃描，將每條記錄進行解析，并格式化為屬性表結(jié)構(gòu)進行輸出，此外，還要將待分類樣本數(shù)據(jù)集保存到最終的結(jié)果文件中，作為下一個階段的輸入。Map 函數(shù)的輸出格式為:＜＜node_ID，att_ID ＞，＜record_ID，value，calss_label ＞＞，其中node_ID 表示當前屬性表所屬節(jié)點編碼，att_ID=i(i=1，2，3，…)表示樣本數(shù)據(jù)集中的第i 個屬性，record_ID 表示每個屬性記錄所在的行號數(shù)，value 表示屬性值，calss_label 表示該屬性值對應所屬的類別。

當Reduce 端接收到Map 端分發(fā)來的鍵值對，Reduce 端的shuffle 過程會將具有相同key 值的Map 輸出鍵值對進行合并，并進行分組操作。這里定義Reduce 端的分組規(guī)則為:將有相同節(jié)點編碼(node_ID)和屬性編碼(att_ID)的屬性表劃分到同一個組中，那么同一節(jié)點的同一屬性的數(shù)據(jù)就會被劃分至相同組中，最后調(diào)用用戶自定義的Reduce 函數(shù)計算每一組的分裂指標信息。Reduce 函數(shù)計算當前待分裂節(jié)點的每一個屬性的分裂信息，并將每個屬性的取值，信息增益率等信息進行輸出。Reduce 函數(shù)的輸出格式為＜＜node_ID，flag ＞，＜att_ID，gainRation，Split，dis_label ＞＞，其中flag 是屬性分裂信息標記位(flag 的默認取值為-1)，gainRation 表示在當前節(jié)點下該屬性的信息增益率，Split 表示對應屬性的取值集合，dis_label 表示當前待分裂樣本數(shù)據(jù)集中類別屬性的統(tǒng)計結(jié)果，為判斷葉子節(jié)點做準備。

2.3 節(jié)點并行分裂

該階段主要負責統(tǒng)計上一個階段的計算結(jié)果，選擇信息增益率最大的屬性作為最佳分裂節(jié)點，并對其進行分裂。Map 端的輸入是上一個階段的輸出結(jié)果，包含了待分裂的樣本數(shù)據(jù)集和屬性分裂信息。Map端無需對數(shù)據(jù)進行特殊處理，僅負責對數(shù)據(jù)的分發(fā)。為了確保同一層中的節(jié)點能夠同時進行分裂，這里定義Map 端的分發(fā)規(guī)則為:將具有相同節(jié)點編碼(node_ID)的樣本數(shù)據(jù)分發(fā)到同一個Reduce 上。當Reduce 端接收到Map 端分發(fā)來的數(shù)據(jù)，MRC4.5 算法將對Reduce 的輸入數(shù)據(jù)進行預排序，這里定義Reduce 端排序規(guī)則為:在不改變節(jié)點編碼(node_ID)的前提下，根據(jù)flag 的取值對輸入數(shù)據(jù)進行排序，很容易區(qū)分當前數(shù)據(jù)是屬性分裂信息還是待分裂的樣本數(shù)據(jù)，從而確保在Reduce 函數(shù)執(zhí)行分裂任務時，先遍歷屬性分裂信息后遍歷待分裂的樣本數(shù)據(jù)。

Reduce 函數(shù)的操作如下:

1)首先遍歷所有屬性分裂信息，根據(jù)屬性分裂信息中的類標簽統(tǒng)計結(jié)果判斷當前的節(jié)點是否為葉子節(jié)點。如果當前節(jié)點為葉子節(jié)點，就不再遍歷待分裂的數(shù)據(jù)集，同時將當前節(jié)點編碼、葉子節(jié)點標示和葉子節(jié)點的屬性取值等信息保存到最終的結(jié)果文件中，以便最后構(gòu)造一棵完整的決策樹。其中，當所有屬性的類標簽統(tǒng)計結(jié)果中只包含同一種類別屬性或者當前節(jié)點所含的樣本數(shù)據(jù)量小于預定的閾值，則認定當前節(jié)點為葉子節(jié)點。

2)如果當前節(jié)點不是葉子節(jié)點，則通過比較各個屬性的信息增益率的大小，選擇具有最大增益率的屬性作為最佳分裂節(jié)點，然后基于該屬性的取值構(gòu)造如下hash 表:

其中vi表示最佳分裂屬性的取值。每個屬性取值對應一個分支編碼。這樣就可以通過遍歷每一條待分裂的樣本數(shù)據(jù)，根據(jù)hash 表中最佳分裂屬性的值決定將其分裂到具體某一個分支上。

3)遍歷所有待分裂的樣本數(shù)據(jù)集，依據(jù)hash 表進行節(jié)點分裂，并將結(jié)果輸出作為下一個階段分裂的輸入，同時將最佳分裂節(jié)點信息包括非葉子節(jié)點標示、當前節(jié)點編碼、分裂屬性、分裂屬性分支情況保存到最終的結(jié)果文件中。Reduce 函數(shù)的偽代碼如下:

以根節(jié)點分裂為例:通過上述過程，首先從所有屬性分裂信息中，找出具有最大信息增益率的屬性作為根節(jié)點，依據(jù)該屬性的取值(假設該屬性取值個數(shù)為2)來構(gòu)造hash 表，然后掃描所有待分裂樣本數(shù)據(jù)集，將其節(jié)點編碼重置為00 或者01，最后將結(jié)果輸出到HDFS 上，除了輸出待分裂的樣本數(shù)據(jù)集，用來作為下一階段循環(huán)分裂的輸入數(shù)據(jù)，還要將根節(jié)點分裂信息保存到?jīng)Q策樹節(jié)點信息文件中。

3 實驗分析

本次實驗數(shù)據(jù)選取一組河南省地下水取水井數(shù)據(jù)，主要針對井深情況進行分析，一共選取了6 個屬性指標，分別是井口井管內(nèi)徑、所處地貌類型、取水井類型、所取地下水類型、年取水量和井深。

3.1 測試1:單機模式對比實驗

實驗內(nèi)容:通過輸入幾組不同規(guī)模的實驗數(shù)據(jù)集，比較單機模式上串行C4.5 算法與基于Hadoop 集群上MRC4.5 算法在處理相同規(guī)模的數(shù)據(jù)集時，從數(shù)據(jù)集輸入到完成所消耗的時間。實驗情況如表1 所示。

表1 實驗結(jié)果統(tǒng)計分析表

上述實驗結(jié)果表明:隨著輸入數(shù)據(jù)集規(guī)模不斷增大，基于單機模式的C4.5 算法在內(nèi)存和計算開銷逐漸增大，使得機器性能下降，直至出現(xiàn)內(nèi)存溢出，而在Hadoop 集群上則能夠完成這些計算任務，這表明MRC4.5 算法具有處理大規(guī)模數(shù)據(jù)集的能力。當輸入的數(shù)據(jù)集規(guī)模較小時，基于Hadoop 集群的MRC4.5 算法所消耗的時間開銷遠大于單機模式下的串行C4.5 算法，這是因為Hadoop 集群上Job 的啟動和交互需要消耗一定的時間，且占總耗時比例較大，隨著輸入數(shù)據(jù)集的規(guī)模不斷增大，基于Hadoop 集群的MRC4.5 算法的優(yōu)勢就會顯現(xiàn)出來。

3.2 測試2:MRC4.5 算法加速比

實驗內(nèi)容:加速比是檢驗并行算法的并行策略是否有效的重要指標。為了驗證MRC4.5 算法的并行策略的有效性，本次實驗選取了A 和B 共2 組不同規(guī)模的實驗數(shù)據(jù)集，分別在不同節(jié)點數(shù)量的Hadoop集群上運行MRC4.5 算法對其進行挖掘，并統(tǒng)計出從數(shù)據(jù)集輸入到完成所消耗的時間。實驗結(jié)果如圖1所示。

圖1 不同節(jié)點集群對比實驗結(jié)果圖

上述實驗結(jié)果表明:隨著集群中計算節(jié)點數(shù)量的增加，MRC4.5 算法在處理A、B 這2 個規(guī)模逐漸增大的數(shù)據(jù)集時，運行時間均呈遞減的趨勢。由此可知，增加Hadoop 集群中的計算節(jié)點數(shù)量可以顯著提高MRC4.5 算法處理相同規(guī)模作業(yè)的能力，這說明基于Hadoop 集群的MRC4.5 算法具有良好的加速比。

4 結(jié)束語

本文通過分析傳統(tǒng)串行C4.5 算法在處理水利普查數(shù)據(jù)決策樹分類挖掘時表現(xiàn)的不足，結(jié)合Hadoop 云計算技術以及決策樹的并行思想，提出基于Map/Reduce 的并行決策樹分類挖掘算法(MRC4.5算法)。該算法首先使用K-means 聚類算法替代二元分割法對連續(xù)屬性進行離散化，從而使離散化結(jié)果更加精確和豐富，然后利用Map/Reduce 編程模型成功實現(xiàn)了串行C4.5 算法的并行化，最后通過實驗證明MRC4.5 算法的并行策略是有效、可行的，且在Hadoop 平臺上具有較高的執(zhí)行效率和良好的加速比。

［1］龐進武，程益聯(lián)，羅志東.水利普查與信息化［J］.水利信息化，2012(1):19-22.

［2］陳龍，萬定生，顧昕辰.基于Hive 的水利普查數(shù)據(jù)倉庫［J］.計算機與現(xiàn)代化，2014(5):127-130.

［3］毛國君，段立娟，王實，等.數(shù)據(jù)挖掘原理與算法［M］.北京:清華大學出版社，2005.

［4］丁靜，楊善林，羅賀，等.云計算環(huán)境下的數(shù)據(jù)挖掘服務模式［J］.計算機科學，2012，39(S1):217-219.

［5］何清，莊福振，曾立，等.PDMiner:基于云計算的并行分布式數(shù)據(jù)挖掘工具平臺［J］.中國科學:信息科學，2014，44(7):871-885.

［6］謝金梅，王艷妮.決策樹算法綜述［J］.軟件導刊，2008，7(11):83-85.

［7］李楠，段隆振，陳萌.決策樹C4.5 算法在數(shù)據(jù)挖掘中的分析及其應用［J］.計算機與現(xiàn)代化，2008(12):160-163.

［8］姚亞夫，邢留濤.決策樹C4.5 連續(xù)屬性分割閾值算法改進及其應用［J］.中南大學學報(自然科學版)，2011，42(12):3772-3776.

［9］顏巍.基于云平臺的數(shù)據(jù)挖掘算法的研究與實現(xiàn)［D］.成都:電子科技大學，2013.

［10］徐鵬，林森.基于C4.5 決策樹的流量分類方法［J］.軟件學報，2009，20(10):2692-2704.

［11］Dean J，Ghemawat S.MapReduce:Simplified data processing on large clusters［J］.Communications of the ACM，2008，51(1):107-113.

［12］Borthakur D.The Hadoop Distributed File System:Architecture and Design［DB/OL］.http://web.mit.edu/～mriap/hadoop/hadoop-0.13.1/docs/hdfs _ design.pdf，2007-11-21.

［13］Lam C.Hadoop 實戰(zhàn)［M］.韓翼中，譯.北京:人民郵電出版社，2011.

［14］Dean J，Ghemawat S.MapReduce:Simplified data processing on large clusters［C］// Proceedings of the 6th Symposium on Operating Systems Design and Implementation.2004:137-149.

［15］周麗娟，王慧，王文伯，等.面向海量數(shù)據(jù)的并行KMeans 算法［J］.華中科技大學學報(自然科學版)，2012，40(S1):150-152.

［16］潘吳斌.基于云計算的并行K-means 氣象數(shù)據(jù)挖掘研究與應用［D］.南京:南京信息工程大學，2013.

［17］韓光輝.基于歐氏距離的實例選擇算法研究［D］.保定:河北大學，2011.