劉 威，路來君，王洪肖，曹延波

(吉林大學a.綜合信息礦產(chǎn)預測研究所，長春130026;b.公共計算機教學與研究中心，長春130012;c.地球科學學院，長春130026)

0 引 言

隨著地學研究和勘查工作的不斷深入，地學領域已積累了大規(guī)模的多尺度、多元化、多分辨率的海量地學數(shù)據(jù)。如何從海量的地學數(shù)據(jù)中挖掘隱含的、有潛在使用價值信息的過程，是解決地學問題的首要任務［1］。在地學各研究領域中，面向海量的地學數(shù)據(jù)，使用決策樹算法進行礦產(chǎn)預測非常艱難，生成決策樹的效率非常低。

筆者主要探討在傳統(tǒng)決策樹算法基礎上，結(jié)合G4ICCS(Geology Geography Geochemistry Geophysics Information Cloud Computing System)系統(tǒng)的分布式編程和并行計算的功能，提出了SPRINT(Scalable Parallelizable Induction of Decision Trees)算法的并行處理機制。

1 數(shù)據(jù)挖掘中決策樹的基本思想

決策樹的基本思想是:首先對訓練集樣本進行數(shù)據(jù)挖掘處理，然后生成一棵類二叉或多叉決策樹。決策樹的葉子節(jié)點表示某個類別，其他非葉子節(jié)點表示非類別屬性，測試結(jié)果形成非葉子節(jié)點的分支。每個分類規(guī)則對應一條從根到葉子的路徑，所以一棵決策樹能變換成若干分類規(guī)則，按照這些分類規(guī)則可對未知類別樣本進行預測。在地學領域中經(jīng)常使用決策樹進行礦產(chǎn)預測，地質(zhì)數(shù)據(jù)量十分龐大，因此，預測過程非常復雜艱難，生成決策樹的效率非常低［2］。目前，常用的決策樹算法有CLS(Concept Learning System)、ID3(Iterative Dichotomiser 3)、C4.5(Classification 4.5)、C5.0(Classification 5.0)、CART(Classification And Regression Tree)、SLIQ(Supervised Learning In Quest)和SPRINT等。其中SLIQ和SPRINT算法適合面向大規(guī)模訓練數(shù)據(jù)集進行決策樹的生成，二者都可用于分類屬性和連續(xù)屬性處理工作。

2 決策樹的SPRINT算法

SPRINT算法是一種具有高度可伸縮性的決策樹算法。與其他決策樹算法一樣，建樹分為兩個步驟:生成樹和剪枝［3］。其算法的核心是貪心算法，在生成樹階段算法遞歸地劃分訓練集，直到每個訓練集都屬于同一類或相當小為止。SPRINT算法改進了C4.5算法需將所有數(shù)據(jù)讀入內(nèi)存的缺點，通過其獨創(chuàng)的預排序技術和廣度優(yōu)先技術，大大加快了算法的運行速度。

SPRINT算法的關鍵在于決策樹的建立，建樹的過程如下［4］:

1)如果訓練樣本集T滿足某停止擴展的條件，則返回;

2)找到任意屬性Si的一個值，產(chǎn)生一個以Si為分裂屬性的分割值;

3)比較每個屬性的分割值，從中選擇最佳分割值，將樹T分為T1和T2;

4)遞歸調(diào)用建樹算法對T1和T2生成決策樹。

建樹算法終止的條件為某個節(jié)點中的訓練集樣本屬于同一類，或節(jié)點訓練樣本數(shù)小于預設的閥值。

EVA考核對企業(yè)融資結(jié)構(gòu)的影響研究..................................................................................................................................李昕潼 池國華（75）

SPRINT算法采用G指數(shù)衡量分割點的優(yōu)劣程度［5］。假設一個數(shù)據(jù)集S擁有m條記錄，分別屬于n個互不相關的類，則數(shù)據(jù)集S的G指數(shù)可表示為

其中pj=t/m，t為數(shù)據(jù)集中屬于類j的記錄數(shù)。如果集合分成兩部分T1和T2，其分別擁有m1和m2條數(shù)據(jù)，則該分割的G指數(shù)表示為

通過該方式可找到最為精確的分割點，但使用該方法也有其局限性，對于數(shù)值型數(shù)據(jù)，要找到其G指數(shù)必須對整個訓練集合按照此屬性排序，取兩個值的中間值作為分裂點，以計算G指數(shù)值。對于大規(guī)模數(shù)據(jù)集，如果此數(shù)據(jù)集的某些屬性含有大量不同取值，算法的運行效率會受到一定影響。

3 SPRINT算法的并行處理

為使SPRINT算法對連續(xù)屬性的處理更加高效，筆者引入了哈希表。哈希表的主要作用是記錄連續(xù)屬性分割點兩側(cè)的數(shù)據(jù)記錄，運行并行化算法后，可非常方便地通過哈希表為并行節(jié)點的分割提供依據(jù)。這里設置的哈希表形式為:(Cnid，Ccid)，其中Cnid代表當前樹節(jié)點的節(jié)點號，Ccid代表當前節(jié)點的子節(jié)點的節(jié)點號，Ccid的取值為0和1，0表示左子節(jié)點，1表示右子節(jié)點。哈希表中第i條記錄表示原數(shù)據(jù)集中第i條記錄被分到的樹節(jié)點號［6-10］。

并行化的PSPRINT算法

輸入:訓練集樣本T，輸出:決策樹。

生成決策樹:參數(shù)為Ti，A，M。

循環(huán)結(jié)構(gòu):循環(huán)條件為“隊列不能空值”。

在上述算法中，Ti代表第i個子訓練樣本集，A表示分類屬性集合，M表示總的子訓練樣本集數(shù)目。

4 算法效果比較及分析

通過上述算法改進，得到了新的PSPRINT算法，并將算法移植到Hadoop架構(gòu)的G4ICCS系統(tǒng)上并行執(zhí)行。筆者采用了將PSPRINT與MapReduce水平劃分進行結(jié)合的方法部署PSPRINT算法。水平劃分即將總的訓練集按照計算節(jié)點數(shù)量平均分布在每個計算節(jié)點上，通過對每個計算節(jié)點上的數(shù)據(jù)集計算G指數(shù)，然后匯總?cè)∽顑?yōu)G指數(shù)屬性作為分割點，并遞歸調(diào)用生成樹算法生成決策樹。

下面以部分成礦數(shù)據(jù)時代表為測試數(shù)據(jù)，比較改進前后算法的效果，測試數(shù)據(jù)如表1所示。

表1 部分成礦時代數(shù)據(jù)表Tab.1 The part of mineragenetic epoch data

為比較基于PSPRINT算法的運行效果，筆者分別在單機環(huán)境下和G4ICCS云計算平臺上運行該算法，得到兩種不同平臺上算法的運行時間，實驗結(jié)果如表2所示。用于實驗的計算機節(jié)點配置如下:CPU Intel Core2 Duo T5450雙核1.66 GHz，Cache Memory 2 MByte，硬盤Deskstar 7 200轉(zhuǎn)320 GByte，內(nèi)存DDR2 4 GByte。

表2 算法測試實驗結(jié)果Tab.2 The result of algorithm testing

通過實驗結(jié)果可看出，并行化后的SPRINT算法在G4ICCS平臺上獲得了良好的運行速度。在測試樣本相同的情況下，計算節(jié)點數(shù)為8時算法速度比單節(jié)點環(huán)境下提高約6～9倍。由此可看出，在PSPRINT算法中引入哈希表可加快算法對數(shù)據(jù)集的掃描速度，節(jié)約算法對數(shù)據(jù)集中屬性排序的時間，再加上MapReduce框架的高效任務調(diào)度與分配機制，算法并行化處理效果良好。

5 結(jié) 語

筆者利用云計算技術的Hadoop架構(gòu)研究了數(shù)據(jù)挖掘中決策樹并行算法，充分利用Hadoop架構(gòu)的分布式PC集群提供的并行計算能力，實現(xiàn)了獨立PC很難完成的海量計算任務，解決G4ICCS系統(tǒng)中大規(guī)模數(shù)據(jù)挖掘問題。同時，決策樹并行算法大幅提高了系統(tǒng)數(shù)據(jù)挖掘速度，保證系統(tǒng)能及時有效地從原始數(shù)據(jù)中挖掘出有價值的信息，為礦產(chǎn)預測工作提供可靠依據(jù)。隨著信息獲取技術手段的不斷進步，地學數(shù)據(jù)規(guī)模將會越來越大，對數(shù)據(jù)挖掘算法并行性的研究意義重大。

［1］韓冰，路來君.地學G4I系統(tǒng)中空間元數(shù)據(jù)的設計技術［J］.世界地質(zhì)，2011，30(2):307-312.HAN Bing，LU Lai-jun.Design Technology of Spatial Metadata in Geological G4I System［J］.Global Geology，2011，30(2):307-312.

［2］劉小虎，李生.決策樹的優(yōu)化算法［J］.軟件學報，1998，9(10):797-800.LIU Xiao-hu，LI Sheng.An Optimized Algorithm of Decision Tree［J］.Journal of Software，1998，9(10):797-800.

［3］馮少榮，肖文俊.基于樣本選取的決策樹改進算法［J］.西南交通大學學報，2009，44(5):643-647.FENG Shao-rong，XIAO Wen-jun.Improved Decision Tree Algorithm Based on Samples Selection［J］.Journal of Southwest Jiaotong University，2009，44(5):643-647.

［4］WANG Ying-chun，LI Da-yong，YIN Ji-long，et al.Application of Decision Tree Algorithm in Stamping Process［J］.Journal of Shanghai Jiaotong University(Science)，2005，E-10(4):368-372.

［5］ZHANG Yong-qiang，GUO You-min，JIN Chen-wang，et al.Classification Decision Tree Algorithm Assisting in Diagnosing Solitary Pulmonary Nodule by SPECT/CT Fusion Imaging［J］.Academic Journal of Xi'an Jiaotong University，2008，20(2):119-124.

［6］唐華松，姚耀文.數(shù)據(jù)挖掘中決策樹算法的探討［J］.計算機應用，2001，18(8):18-22.TANG Hua-song，YAO Yao-wen.Research on Decision Tree in Data Mining［J］.Application Research of Computers，2001，18(8):18-22.

［7］王喆，陸楠，周春光.基于決策樹歸納的聚類方法與實現(xiàn)［J］.吉林大學學報:信息科學版，2003，21(2):132-137.WANG Zhe，LU Nan，ZHOU Chun-guang.Clustering Method and Realization on Inductive Decision Tree［J］.Journal of Jilin University:Information Science Edition，2003，21(2):132-137.

［8］王苗，柴瑞敏.一種改進的決策樹分類屬性選擇方法［J］.計算機應用工程，2010，46(8):127-129.WANG Miao，CHAI Rui-min.Improved Classification Attribute Selection Scheme for Decision Tree ［J］.Computer Engineering and Applications，2010，46(8):127-129.

［9］HU Xue-gang，LI Pei-pei，WU Xi-dong，et al.A Semi-Random Multiple Decision-Tree Algorithm for Mining Data Streams［J］.Journal of Computer Science＆ Technology，2007，22(5):711-724.

［10］閆昭，劉磊.基于多線程LL(1)分析表自動生成的并行算法［J］.吉林大學學報:信息科學版，2009，27(1):85-89.YAN Zhao，LIU Lei.Design of Parallel Algorithm on Autogeneration of LL(1)Analytical Table ［J］.Journal of Jilin University:Information Science Edition，2009，27(1):85-89.