楊 潔，黃 剛

(南京郵電大學(xué) 計算機學(xué)院，江蘇 南京 210003)

基于云計算的SPRINT算法研究

楊 潔，黃 剛

(南京郵電大學(xué) 計算機學(xué)院，江蘇 南京 210003)

決策樹是數(shù)據(jù)挖掘中非常重要的一種技術(shù)，常用來做數(shù)據(jù)分析和預(yù)測。傳統(tǒng)的決策樹算法在處理海量數(shù)據(jù)挖掘時，受到CPU和內(nèi)存的限制，導(dǎo)致算法存在消耗時間過長，容錯性差，存儲量小的缺點。面對海量數(shù)據(jù)的處理，云計算在這方面具有非常多的優(yōu)勢。針對決策樹中優(yōu)秀的SPRINT算法，首先對SPRINT算法進行了優(yōu)化，然后為了讓優(yōu)化后的算法更好地應(yīng)用于云計算，對算法實現(xiàn)了并行化。傳統(tǒng)的SPRINT算法在生成決策樹時，會發(fā)生多值偏向問題，在生成一個節(jié)點時，通過計算兩層的Gini指數(shù)來降低多值偏向的影響。在算法并行化時，通過將數(shù)據(jù)分發(fā)到各個處理器執(zhí)行，然后進行匯總處理，從而減少算法執(zhí)行的總時間。實驗結(jié)果表明：基于云計算平臺的SPRINT改進算法具有更好的分類正確率，同時算法的執(zhí)行速度也得到了明顯的提高。

云計算；MapReduce；SPRINT算法；Gini指數(shù)

0 引 言

數(shù)據(jù)挖掘發(fā)展至今，已經(jīng)產(chǎn)生了許多實用的數(shù)據(jù)挖掘方法，包括決策樹算法、貝葉斯方法、人工神經(jīng)網(wǎng)絡(luò)方法、支持向量機方法、聚類分析方法等。SPRINT算法是決策樹算法中的一種經(jīng)典算法。SPRINT算法是對SLIQ算法的進一步優(yōu)化，在內(nèi)存的數(shù)據(jù)量駐留方面，改進了決策樹的數(shù)據(jù)結(jié)構(gòu)。由于種種優(yōu)點，越來越多的人投身到SPRINT算法的研究中，主要集中在對算法的本身進行改進。但是，如今的數(shù)據(jù)量越來越大，無疑給算法工程師帶來了許多新的艱巨挑戰(zhàn)。單純對算法本身的改進已經(jīng)不能滿足于現(xiàn)在的需求，而云計算的出現(xiàn)解決了這個問題。然而，僅僅將傳統(tǒng)的SPRINT算法應(yīng)用于云計算平臺，并不能充分發(fā)揮云計算的計算能力。

文中對SPRINT算法進行改進，通過計算兩層的Gini指數(shù)來產(chǎn)生一個決策節(jié)點。改進后的算法雖然增加了計算量，但產(chǎn)生的分割屬性優(yōu)于未改進的SPRINT算法，即產(chǎn)生了更優(yōu)的決策樹。

1 云計算平臺

1.1 云計算簡介

云計算這個新名詞出現(xiàn)在2007年的第3季度，不到半年，它受到的關(guān)注程度就遠(yuǎn)遠(yuǎn)超過了先前大熱的網(wǎng)格計算，并且在今天也沒有任何減弱的趨勢[1]。云計算具有以下特點:“云”具有很大的規(guī)模性；云計算為了方便用戶接入，使用了虛擬化技術(shù)，該技術(shù)可以讓用戶在任意地點使用各種不同的終端設(shè)備從“云”獲得自己需要的服務(wù)；作為商業(yè)模型，“云”在創(chuàng)建階段和維護階段，在開銷方面，也具有前所未有的性價比[2]。1.2 MapReduce編程模型

MapReduce最初來源于Google的幾篇論文，是一種用于處理海量數(shù)據(jù)挖掘的并行編程模型[3]。

MapReduce的運行模型如圖1所示。

圖1 MapReduce的運行模型

MapReduce降低了編程人員的要求，在編程時他們不需要關(guān)心程序運行的具體細(xì)節(jié)，只需要編寫兩個主要的函數(shù)：

Map：(in_key，in_value)→{(keyi,valuei)|i=1,2,…,k}

Reduce：(key，[value1，value2，…，valuem])→(key，out_value)

Map函數(shù)需要的輸入?yún)?shù)和Reduce函數(shù)所輸出的結(jié)果會根據(jù)不同的應(yīng)用發(fā)生變化。in_key和in_value是Map的輸入?yún)?shù)，它們指明了Map操作所要處理的原始數(shù)據(jù)是什么。Map操作結(jié)束后，會產(chǎn)生一些中間結(jié)果，它們以鍵值對的形式存在，即(key，value)對。在Map階段結(jié)束后，系統(tǒng)會對所有的中間結(jié)果進行整理，使具有相同key的value集結(jié)在一起，也就是說，Reduce的輸入?yún)?shù)是(key，[value1，value2，…，valuem])。Reduce的工作就是對這些具有相同鍵key的value值進行歸并處理，最終產(chǎn)生(key,out_value)的結(jié)果。其中每一個Reduce都會產(chǎn)生自己的結(jié)果，最后，將所有Reduce的結(jié)果合在一起就成了最終結(jié)果[4]。

2 SPRINT算法

2.1 基本思想

SPRINT算法創(chuàng)建決策樹的過程：

輸入：節(jié)點n，數(shù)據(jù)集D，分割方法CL；

輸出：一棵決策樹，根節(jié)點為n，決策樹基于數(shù)據(jù)集D和分割算法CL。

ProcedureBuildTree(n,D,CL)

初始化根節(jié)點：

以CL為分割依據(jù)，計算D中的數(shù)據(jù)，生成節(jié)點信息；

If(節(jié)點n滿足分割條件)

選擇最好的效果將D分為D1、D2；

創(chuàng)建節(jié)點n的子節(jié)點n1、n2；

TDTree(n1，D1，CL)；

TDTree(n2，D2，CL)；

endIf

end

SPRINT算法的終止條件一般存在3種情況：

(1)當(dāng)前生成的節(jié)點中，所有的樣本數(shù)據(jù)如果都屬于同一個類，那么這個節(jié)點就是一個葉節(jié)點，即算法終止計算，同時用這個共同的類作為該葉節(jié)點的類標(biāo)記。

(2)所有屬性都已經(jīng)用完，沒有多余的屬性用作測試屬性。

(3)當(dāng)前節(jié)點內(nèi)的樣本數(shù)少于用戶規(guī)定的閾值，則用該節(jié)點內(nèi)占大多數(shù)的類作為該葉節(jié)點的類標(biāo)記[5]。

2.2 SPRINT算法的數(shù)據(jù)結(jié)構(gòu)

SPRINT算法定義了兩個特殊的數(shù)據(jù)結(jié)構(gòu)：屬性列表和類直方圖。在SPRINT算法之前的決策樹方法中，數(shù)據(jù)都必須長時間駐留在內(nèi)存，限制了大數(shù)據(jù)的處理，SPRINT使用屬性列表解決了這個問題，并取消了數(shù)據(jù)的多次排序。屬性列表用一個三元組表示，即<屬性值，類別標(biāo)識，行索引>。其中行索引是自動生成的。初始化根節(jié)點時，對于離散屬性，屬性列表沒有什么強制要求，而對于連續(xù)屬性，屬性列表則需要對它進行排序處理。在算法生成決策樹的過程中，隨著數(shù)據(jù)的不斷分割，節(jié)點不斷的生成，與節(jié)點相對應(yīng)的屬性列表也在被分割，然而屬性列表順序卻沒有改變，也就是說該屬性列表也是有序的，因此，不用對屬性列表進行重排[6]。

類直方圖的作用是記錄節(jié)點上數(shù)據(jù)的屬性類別的分布情況，這些數(shù)據(jù)用于計算對應(yīng)節(jié)點的最佳分割屬性。決策樹節(jié)點在處理連續(xù)屬性時，需要維護2個統(tǒng)計直方圖，分別為Cbelow和Cabove。其中，Cbelow表示A≤C的類分布情況，Cabove表示A>C的類分布情況，A代表數(shù)據(jù)中該連續(xù)屬性的一個值，C代表當(dāng)前選取的連續(xù)屬性分割值。隨著樹的創(chuàng)建，直方圖不斷更新，以尋找最佳分割點。對于每一個離散屬性，節(jié)點只需要維護1個直方圖，該直方圖也被稱為統(tǒng)計矩陣，用來對這個離散屬性具有的所有離散值分布情況進行記錄[7]。

2.3 分割指數(shù)

SPRINT算法采用Gini指數(shù)作為分割標(biāo)準(zhǔn)。在屬性選擇標(biāo)準(zhǔn)中，Gini指數(shù)算法是采用數(shù)據(jù)集的不純度作為屬性選擇標(biāo)準(zhǔn)的。一個節(jié)點t的Gini指數(shù)計算公式為：

(1)

其中，P(i|t)表示給定節(jié)點t中屬于類i的記錄所占的比例；C表示所有類的總個數(shù)。

如果以A作為集合，將集合劃分成節(jié)點B1和節(jié)點B2，則分割后的Gini指數(shù)計算方法為：

(2)

其中，n,n1,n2分別為A,B1,B2的記錄數(shù)。

SPRINT算法在所有的屬性中，選擇Ginisplit(A)具有最小值的A*作為分割標(biāo)準(zhǔn)，因為Ginisplit(A)越小表明分割屬性選擇得越好[8]。

3 SPRINT算法存在的缺點和改進方案

SPRINT算法通過Gini值來選擇分割屬性，然而這會引發(fā)多值偏向問題。多值偏向會導(dǎo)致生成非最優(yōu)甚至是錯誤的決策樹，原因在于多值偏向在選擇分割屬性時，往往會選擇取值個數(shù)較多的屬性作為分割屬性，這就將分割結(jié)果與屬性的取值個數(shù)關(guān)聯(lián)到了一起，這種關(guān)聯(lián)是沒有道理的。文獻(xiàn)[9]首先通過理論分析，研究了多值偏向問題，然后直接通過算法表達(dá)式進行推理，證明了選擇Gini指數(shù)作為分割標(biāo)準(zhǔn)確實會引發(fā)多值偏向問題[9]。

針對多值偏向問題，文中提出了一種對SPRINT算法的改進方案。假設(shè)A為測試屬性，屬性A具有2個屬性值，每個屬性值對應(yīng)的概率為p1,p2。算法先對屬性A進行第一次分割，{B1,B2}為這兩個節(jié)點的屬性，分別對應(yīng)的不純度為Ginisplit(B1)和Ginisplit(B2)，則：

(3)

算法的詳細(xì)步驟如下：

(1)存在屬性候選集Q，算法依次從Q中選取每一個屬性作為測試屬性A，對A先進行一次二元分割，生成兩個新節(jié)點{B1,B2}，并且每個節(jié)點的屬性值概率分別為p1和p2，此時不用計算兩個節(jié)點的Gini值。然后算法對B1和B2節(jié)點再次進行分割，又分別產(chǎn)生兩個節(jié)點，共計四個節(jié)點。計算Ginisplit(B1)和Ginisplit(B2)。

(4)對于所有生成的節(jié)點，如果滿足算法的停止條件，就將該節(jié)點設(shè)置為葉節(jié)點，并用它的所屬類標(biāo)記，否則，就運用步驟(1)～(3)對節(jié)點繼續(xù)進行分割，直到算法結(jié)束。

4 基于MapReduce的并行化

4.1 原始數(shù)據(jù)的預(yù)處理

在云計算平臺中，考慮到負(fù)載均衡的原則，采用水平分割對整個數(shù)據(jù)集進行分段，將數(shù)據(jù)集平均地分配到所有處理器中。這樣數(shù)據(jù)集中的種類屬性能夠被均勻分組，不需要對數(shù)據(jù)再進行其他操作[10]。由于SPRINT算法對于連續(xù)數(shù)據(jù)是有特別要求的，即要求連續(xù)數(shù)據(jù)是已經(jīng)排好序的。在算法開始時，由于原始數(shù)據(jù)中的連續(xù)屬性是沒有經(jīng)過排序的，所以，在對數(shù)據(jù)水平分割后，處理器需要對其中的連續(xù)屬性進行排序和重新分組操作，使得連續(xù)屬性的屬性列表是一張相鄰有序的表[11]。

4.2 并行計算節(jié)點的最佳分割屬性

在并行環(huán)境中，計算當(dāng)前節(jié)點的最佳分割屬性時，需要對連續(xù)屬性和離散屬性分別進行處理。

對于連續(xù)屬性，算法初始化Cbelow和Cabove類直方圖，同時各個節(jié)點進行通信。Cbelow記錄該處理器之下的數(shù)據(jù)，Cabove記錄該處理器之上的數(shù)據(jù)[12]。然后對該屬性列表的所有數(shù)據(jù)進行檢索，同時更新兩個類直方圖，并且根據(jù)直方圖的信息，計算每個連續(xù)值的Gini指數(shù)。在當(dāng)前計算的所有連續(xù)值中選取一個具有最小Gini指數(shù)的連續(xù)值作為該屬性的第一層最佳分割點。

對于離散屬性，每個處理器根據(jù)自身所擁有的數(shù)據(jù)建立對應(yīng)該屬性局部的類直方圖C，同時獲取一個協(xié)助處理器，這個協(xié)助處理器的任務(wù)是匯總同一屬性的所有局部類直方圖，將這些信息相加，就得到了該屬性的全局類直方圖信息[13]。然后根據(jù)協(xié)助處理器所記錄的該屬性全局直方圖信息，就能夠計算出該屬性的第一層最佳分割點。

4.3 分割節(jié)點的屬性列表

完成最佳分割點的計算之后，每個處理器根據(jù)該最佳分割和行索引，對自己擁有的屬性列表進行分割，同時創(chuàng)建局部哈希表。然后，所有處理器進行通信，共享自己剛剛建立的局部哈希表，所有哈希表進行匯總整理后，就可以創(chuàng)建全局哈希表。每個處理通過查找該全局哈希表，對自己的數(shù)據(jù)進行分割，分割完后，將分割的數(shù)據(jù)存入子節(jié)點中。分配完后，決策樹的一個節(jié)點就創(chuàng)建了。重復(fù)以上步驟，直到滿足節(jié)點不再需要分割的條件，即為葉子節(jié)點[14]。

5 實 驗

5.1 實驗內(nèi)容

實驗所選取的數(shù)據(jù)集來自于UCI網(wǎng)站的Acute Inflammations數(shù)據(jù)集。該數(shù)據(jù)集的數(shù)據(jù)來源是一個醫(yī)學(xué)專家數(shù)據(jù)集測試系統(tǒng)，它將執(zhí)行的推斷是診斷泌尿系統(tǒng)的兩種疾病。數(shù)據(jù)集總共包含6個屬性，其中有1個連續(xù)屬性。數(shù)據(jù)集內(nèi)的數(shù)據(jù)形式為“35,9nonoyesyesyesyesno”，最后2個是類別屬性，decision:Inflammation of urinary bladder和decision:Nephritis of renal pelvis origin。實驗選擇第一個類別屬性。

實驗對數(shù)據(jù)集使用未改進的SPRINT算法進行分割，產(chǎn)生的決策樹如圖2所示。

圖2 原SPRINT算法生成的決策樹

然后將同一數(shù)據(jù)集用改進后的算法進行分類，產(chǎn)生的決策樹如圖3所示。

圖3 改進SPRINT算法生成的決策樹

5.2 實驗結(jié)果分析

下面，分析改進后的算法是如何生成圖2的決策樹的，僅分析第一個分割屬性的生成過程。算法依次將各個節(jié)點作為第一個分類屬性，然后選取另一個分類屬性進行決策。如果選擇Buring of urethra對樣本先進行分類，接著分別選取5個其他的屬性進行分類，左子樹用Temperature of patient分類，結(jié)果為：

Ginisplit(Temperature of patient<38.0)=20/50Gini(左)+30/50Gini(右)=20/50(1- (20/20)2-(0/20)2)+30/50(1-(9/30)2- (21/30)2)=0.252

若左子樹用Occurrence of nausea分類，結(jié)果為：

Ginisplit(Occurrence of nausea)=41/50Gini(左)+9/50Gini(右)=41/50(1-(20/41)2- (21/41)2)+9/50(1-(9/9)2-(0/9)2)= 0.409 7

若左子樹用Lumbar pain分類，結(jié)果為：

Ginisplit(Lumbar pain)=20/50(1-(20/20)2- (0/20)2)+30/50(1-(9/30)2-(21/30)2)= 0.252

若左子樹用Urine pushing分類，結(jié)果為：

Ginisplit(Urine pushing)=0/50(1-(0)2-(0)2)+50/50(1-(21/50)2-(29/50)2)=0.487 2

若左子樹用Micturition pains分類，結(jié)果為：

Ginisplit(Micturition pains)=29/50(1-(29/29)2-(0/29)2)+21/50(1-(0/21)2-(21/21)2)=0

然后計算右子樹，得到Ginisplit(Urine pushing)=0，那么最小的Ginisplit’(Buring of urethra)=50/120Ginisplit(Micturition pains) +70/120Ginisplit(Urine pushing)=0。

用同樣的方法計算其他分割點的Ginisplit’，選出最小的Ginisplit’(A*)，A*=Buringofurethra時，Ginisplit’(A*)最小，所以選擇Buringofurethra作為第一層的分割屬性。

5.3 改進算法應(yīng)用于并行化環(huán)境

實驗運用Adult數(shù)據(jù)集。實驗過程中，不斷添加物理機的個數(shù)，產(chǎn)生的折線圖如圖4所示。

圖4 生成第一個節(jié)點和計算節(jié)點數(shù)量的關(guān)系

從圖中可以看出，隨著計算節(jié)點的不斷增加，算法運行時間不斷縮減。

6 結(jié)束語

文中對SPRINT算法進行了改進，當(dāng)算法選取最佳分割屬性時，不僅考慮該次分割的Gini指數(shù)，而且繼續(xù)考慮下次分割帶來的Gini指數(shù)。改進算法在層數(shù)上明顯優(yōu)于原算法。在算法的執(zhí)行時間上，通過在云計算平臺上增加計算節(jié)點，可以大大提高算法的執(zhí)行速度。實驗結(jié)果表明，文中提出的算法是有效的。

[1] 李玲娟，張 敏．云計算環(huán)境下關(guān)聯(lián)規(guī)則挖掘算法的研究[J]．計算機技術(shù)與發(fā)展，2011，21(2)：43-46．

[2] 張曉洲．云計算關(guān)鍵技術(shù)及發(fā)展現(xiàn)狀研究[J]．網(wǎng)絡(luò)與信息，2011，25(9)：36-37.

[3] 王靜紅，王熙照，邵艷華，等．決策樹算法的研究及優(yōu)化[J].微機發(fā)展(現(xiàn)更名：計算機技術(shù)與發(fā)展)，2004，14(9)：30-32.

[4] Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters[J].Communications of the ACM，2008，51(1):107-113.

[5] Settouti N,Aourag H.A comparative study of the physical and mechanical properties of hydrogen using data mining research techniques[J].JOM,2015，67(9):1-9.

[6] Hu Q H，Che X J，Zhang L，et al．Rank entropy-based decision trees for monotonic classification[J]．IEEE Transactions on Knowledge and Data Engineering，2012，24(99):1.

[7] 王熙照，楊晨曉．分支合并對決策樹歸納學(xué)習(xí)的影響[J]．計算機學(xué)報，2007，30(8):1251-1258.

[8] Chen Jin，Luo Delin，Mu Fenxiang.An improved ID3 decision tree algorithm[C]//Proceedings of 2009 4th international conference on computer science & education.[s.l.]:[s.n.],2009:127-130.

[9] 韓松來，張 輝，周華平．決策樹算法中多值偏向問題的理論分析[C]//全國自動化新技術(shù)學(xué)術(shù)交流會會議論文集(一).出版地不詳:出版者不詳,2005.

[10] Elyasigomari V,Mirjafari M S,Screen H R C,et al.Cancer classification using a novel gene selection approach by means of shuffling based on data clustering with optimization[J].Applied Soft Computing,2015，35：43-51.

[11] 王云飛．SPRINT分類算法的改進[J]．科學(xué)技術(shù)與工程，2008,8(23)：6248-6252.

[12] 董 峰，劉遠(yuǎn)軍．?dāng)?shù)據(jù)挖掘中決策樹SPRINT算法探討[J]．邵陽學(xué)院學(xué)報:自然科學(xué)版，2007，4(2)：23-25.

[13] 魏紅寧.基于SPRINT方法的并行決策樹分類研究[J].計算機應(yīng)用，2005，25(1)：39-41.

[14] Yang Shiueng-Bien,Yang Shen-I.New decision tree based on genetic algorithm[C]//Computer control and automation.[s.l.]:[s.n.],2010:115-118.

Research on SPRINT Algorithm Based on Cloud Computing

YANG Jie,HUANG Gang

(School of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Decision tree is a very important technology in data mining,which is often used for data analysis and forecasting.When the traditional decision tree algorithm is dealing with massive data mining,the CPU and memory is limited,resulting in its shortcomings like long time-consuming,poor fault tolerance and small storage capacity.Faced with massive data processing,cloud computing has a lot of advantages in this respect.It places emphasis on the good algorithm of SPRINT.First of all,it is optimized,and then parallelized in order to make the optimized algorithm better applied to cloud computing.When traditional SPRINT algorithm generates the decision tree,multi-valued bias problem will happen,and when it generates a node,through the calculation of Gini index of two layer,the effects of multi-valued bias is reduced.In parallel algorithm,through the distribution of data to the processor execution,then collecting and processing,the total time of execution is reduced.The experimental results show that the improved SPRINT algorithm based on cloud computing platform has better classification accuracy,and at the same time,its execution speed gets obvious improvement.

cloud computing;MapReduce;SPRINT algorithm;Gini index

2016-04-12

2016-08-10

時間：2017-01-10

國家自然科學(xué)基金資助項目(GZ211018)

楊 潔(1991-)，男，研究方向為計算機云計算與大數(shù)據(jù)應(yīng)用；黃 剛，教授，研究方向為計算機軟件理論及應(yīng)用。

http://www.cnki.net/kcms/detail/61.1450.TP.20170110.1028.070.html

TP301.6

A

1673-629X(2017)03-0108-05

10.3969/j.issn.1673-629X.2017.03.022