楊 潔，黃 剛

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

基于云計(jì)算的SPRINT算法研究

楊 潔，黃 剛

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

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

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

0 引 言

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

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

1 云計(jì)算平臺(tái)

1.1 云計(jì)算簡介

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

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

MapReduce的運(yùn)行模型如圖1所示。

圖1 MapReduce的運(yùn)行模型

MapReduce降低了編程人員的要求，在編程時(shí)他們不需要關(guān)心程序運(yùn)行的具體細(xì)節(jié)，只需要編寫兩個(gè)主要的函數(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é)果會(huì)根據(jù)不同的應(yīng)用發(fā)生變化。in_key和in_value是Map的輸入?yún)?shù)，它們指明了Map操作所要處理的原始數(shù)據(jù)是什么。Map操作結(jié)束后，會(huì)產(chǎn)生一些中間結(jié)果，它們以鍵值對(duì)的形式存在，即(key，value)對(duì)。在Map階段結(jié)束后，系統(tǒng)會(huì)對(duì)所有的中間結(jié)果進(jìn)行整理，使具有相同key的value集結(jié)在一起，也就是說，Reduce的輸入?yún)?shù)是(key，[value1，value2，…，valuem])。Reduce的工作就是對(duì)這些具有相同鍵key的value值進(jìn)行歸并處理，最終產(chǎn)生(key,out_value)的結(jié)果。其中每一個(gè)Reduce都會(huì)產(chǎn)生自己的結(jié)果，最后，將所有Reduce的結(jié)果合在一起就成了最終結(jié)果[4]。

2 SPRINT算法

2.1 基本思想

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

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

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

ProcedureBuildTree(n,D,CL)

初始化根節(jié)點(diǎn)：

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

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

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

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

TDTree(n1，D1，CL)；

TDTree(n2，D2，CL)；

endIf

end

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

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

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

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

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

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

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

2.3 分割指數(shù)

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

(1)

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

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

(2)

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

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

3 SPRINT算法存在的缺點(diǎn)和改進(jìn)方案

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

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

(3)

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

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

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

4 基于MapReduce的并行化

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

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

4.2 并行計(jì)算節(jié)點(diǎn)的最佳分割屬性

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

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

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

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

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

5 實(shí) 驗(yàn)

5.1 實(shí)驗(yàn)內(nèi)容

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

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

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

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

圖3 改進(jìn)SPRINT算法生成的決策樹

5.2 實(shí)驗(yàn)結(jié)果分析

下面，分析改進(jìn)后的算法是如何生成圖2的決策樹的，僅分析第一個(gè)分割屬性的生成過程。算法依次將各個(gè)節(jié)點(diǎn)作為第一個(gè)分類屬性，然后選取另一個(gè)分類屬性進(jìn)行決策。如果選擇Buring of urethra對(duì)樣本先進(jìn)行分類，接著分別選取5個(gè)其他的屬性進(jìn)行分類，左子樹用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

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

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

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

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

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

從圖中可以看出，隨著計(jì)算節(jié)點(diǎn)的不斷增加，算法運(yùn)行時(shí)間不斷縮減。

6 結(jié)束語

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

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

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

[3] 王靜紅，王熙照，邵艷華，等．決策樹算法的研究及優(yōu)化[J].微機(jī)發(fā)展(現(xiàn)更名：計(jì)算機(jī)技術(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] 王熙照，楊晨曉．分支合并對(duì)決策樹歸納學(xué)習(xí)的影響[J]．計(jì)算機(jī)學(xué)報(bào)，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]//全國自動(dòng)化新技術(shù)學(xué)術(shù)交流會(huì)會(huì)議論文集(一).出版地不詳:出版者不詳,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ìn)[J]．科學(xué)技術(shù)與工程，2008,8(23)：6248-6252.

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

[13] 魏紅寧.基于SPRINT方法的并行決策樹分類研究[J].計(jì)算機(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

時(shí)間：2017-01-10

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

楊 潔(1991-)，男，研究方向?yàn)橛?jì)算機(jī)云計(jì)算與大數(shù)據(jù)應(yīng)用；黃 剛，教授，研究方向?yàn)橛?jì)算機(jī)軟件理論及應(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