王鵬，王健安，郭暢，巴濟(jì)慈

（長春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長春 130022）

隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，存儲(chǔ)于計(jì)算機(jī)中的數(shù)據(jù)文件呈爆炸式的發(fā)展。這些數(shù)據(jù)又稱為海量數(shù)據(jù)，這類數(shù)據(jù)常常伴隨著噪聲而且是異構(gòu)數(shù)據(jù)，其很難直接被用戶理解。如何從這樣的數(shù)據(jù)里提取出規(guī)律和模式已經(jīng)成為一個(gè)難題。數(shù)據(jù)挖掘作為一門能夠高效的、便于擴(kuò)展的解決以上問題的技術(shù)應(yīng)運(yùn)而生。選擇云計(jì)算做海量數(shù)據(jù)的分類數(shù)據(jù)挖掘處理，可以減少構(gòu)建分布式計(jì)算平臺(tái)的開銷，同時(shí)將底層屏蔽掉，便于開發(fā)，使得原有的設(shè)備擁有對(duì)大數(shù)據(jù)集的較高處理效率，增加了節(jié)點(diǎn)的個(gè)數(shù)和容錯(cuò)能力，提高了從海量數(shù)據(jù)中提取有效信息的能力［1，2］。

1 SPRINT算法

SPRINT算法主要包括樹的創(chuàng)建與剪枝過程，由于在創(chuàng)建決策樹時(shí)要求數(shù)次遍歷數(shù)據(jù)，但剪枝卻不需此過程，所以，對(duì)樹的剪枝時(shí)間基本僅有創(chuàng)建數(shù)的百分之一。因此，我們把重點(diǎn)放在樹的創(chuàng)建上；另外一方面，基于二叉樹簡(jiǎn)潔又精準(zhǔn)的特點(diǎn)，本文選擇的是創(chuàng)建二叉樹。

1.1 數(shù)據(jù)結(jié)構(gòu)

SPRINT算法表示數(shù)據(jù)特征的方式是采用屬性表與直方圖這兩種數(shù)據(jù)結(jié)構(gòu)，其中，后者是依附在前者之上，而前者又是隨著節(jié)點(diǎn)的劃分而分裂的。它會(huì)依據(jù)屬性的不同性質(zhì)，如連續(xù)型或離散型而顯現(xiàn)出相應(yīng)的表現(xiàn)形式。

屬性表是屬性值，類標(biāo)記和記錄索引構(gòu)成的三元組，它可以駐留在除內(nèi)存外的介質(zhì)上。直方圖是表示節(jié)點(diǎn)上的一個(gè)屬性所屬類的分布情況，當(dāng)屬性是連續(xù)的數(shù)值型時(shí)，節(jié)點(diǎn)就涉及兩個(gè)直方圖：Cbelow表示已經(jīng)處理完畢的樣本的類型分布，而Cabove表示尚沒處理的樣本，它們通過不間斷的刷新來找到最佳分裂點(diǎn)；當(dāng)屬性是離散型時(shí)，便僅需一個(gè)直方圖，包括了這個(gè)屬性每個(gè)值的類分布信息，只需要維護(hù)一個(gè)叫做計(jì)數(shù)矩陣的統(tǒng)計(jì)圖。

1.2 最佳分裂點(diǎn)的度量和選擇

SPRINT算法使用Gini指數(shù)代替信息量作為選擇最佳分裂點(diǎn)的依據(jù)，它對(duì)決策樹的生成至關(guān)重要，Gini指數(shù)方法可以定義為［3］：

對(duì)有著M個(gè)類型的N項(xiàng)記錄的數(shù)據(jù)集S，對(duì)應(yīng)的Gini為：

pi為第i類數(shù)據(jù)出現(xiàn)的頻率。

對(duì)數(shù)據(jù)集S劃分為S1、S2兩個(gè)部分，分別有n1、n2個(gè)記錄，則對(duì)應(yīng)的Gini指數(shù)定義為：

處理屬性的類型不相同的屬性，采差別化的方法：如果是連續(xù)的數(shù)值型屬性P，經(jīng)過排序后，設(shè)其結(jié)果為＜p1,p2,…,pn＞，由于分裂只會(huì)發(fā)生在相鄰節(jié)點(diǎn)之間，故有n-1個(gè)選擇，分裂的形式是P≤pi與P＞pi這兩個(gè)部分，這是就選擇相鄰兩值的中間值即（pi+pi+1）/2為待選的最佳分裂點(diǎn)。從小到大依次掃描，為每個(gè)待選的分裂點(diǎn)生成屬性表的直方圖，并計(jì)算它們的基尼值，取最小點(diǎn)為最佳分裂點(diǎn)；而如果是離散型的屬性Q，就假設(shè)有n個(gè)不一樣的取值。要做的工作就是把這些值組合為兩個(gè)集合，即存在2m個(gè)選擇。算出所有的基尼指數(shù)，選用指數(shù)最小的為最佳分裂點(diǎn)。

1.3 SPRINT算法基本思想

傳統(tǒng)的SPRINT算法過程為：

（1）把數(shù)據(jù)集S做豎直的分割，之后生成屬性表，它們表示著這個(gè)數(shù)據(jù)集全部的特征。若屬性為連續(xù)型，就要進(jìn)行排序處理了。

（2）創(chuàng)建一個(gè)根節(jié)點(diǎn)M，并把全部屬性表附著在上面。

（3）對(duì) M 執(zhí)行BuildTree（S,A）。

（4）決策樹創(chuàng)建完畢后，就要對(duì)樹做剪枝處理了。最常用的方法是最小描述長度。由于樹的剪枝僅占SPRINT算法的執(zhí)行時(shí)間的一部分，所以在驗(yàn)證算法有效性的時(shí)候?qū)⒑雎约糁Φ臅r(shí)間復(fù)雜度［4］。

2 SPRINT算法并行策略

2.1 節(jié)點(diǎn)之間的并行

傳統(tǒng)SPRINT算法的核心在于數(shù)據(jù)集的分裂，屬性表依附于節(jié)點(diǎn)之上，當(dāng)它發(fā)現(xiàn)了核實(shí)的分裂點(diǎn)便進(jìn)行分裂。分裂之后繼續(xù)在新的節(jié)點(diǎn)上進(jìn)行分類。而在SPRINT并行算法中，通過調(diào)用Map函數(shù)接受一組鍵值對(duì)，之后將輸出的中間健值對(duì)發(fā)送到Reduce函數(shù)。基于以上特性，算法就能夠用Map函數(shù)將在同一個(gè)樹層節(jié)點(diǎn)的全部的屬性表發(fā)送到不一樣的Reduce中去從而實(shí)現(xiàn)分裂的并行，如圖1所示。

圖1 節(jié)點(diǎn)之間的并行

2.2 屬性表之間的并行

SPRINT算法在處理屬性表時(shí)需要各自求出Gini指數(shù)并對(duì)最佳分裂點(diǎn)進(jìn)行處理，這些操作都符合并行特征，可以采取并行的處理方式。但是由于進(jìn)行操作的節(jié)點(diǎn)的屬性表必須是有著一樣的屬性名稱，所以，屬性表之間的并行還需要在節(jié)點(diǎn)并行的策略基礎(chǔ)之上才能實(shí)現(xiàn)，而且全部的屬性表均標(biāo)記上它所依附的節(jié)點(diǎn)的特定符號(hào)。

圖2 屬性表之間的并行

因此，若想要使得屬性名不一樣或是節(jié)點(diǎn)符號(hào)不一樣的屬性表可以并行處理如圖2僅需在執(zhí)行Map函數(shù)的過程中將分區(qū)函數(shù)Partitioner規(guī)定為：僅當(dāng)屬性表的節(jié)點(diǎn)符號(hào)一樣并且屬性表的屬性也相同時(shí)才可能將它們映射到同一個(gè)Reducer。

2.3 排序的并行

在進(jìn)行連續(xù)型屬性的分裂之前，需要算出基尼指數(shù)和選擇候選最佳分裂點(diǎn)，所以一定要預(yù)先進(jìn)行排序。如果屬性是連續(xù)型的，需要這兩個(gè)直方圖Cbelow和Cabove，分別代表未被掃描和已掃描過的屬性表。連續(xù)型的屬性的直方圖的掃描過程為：一邊對(duì)已排好序的屬性進(jìn)行掃描一邊做刷新處理，把掃描的每一個(gè)節(jié)點(diǎn)都視為待選最佳分裂點(diǎn)進(jìn)行處理，同時(shí)算出它的Gini指數(shù)。這樣結(jié)束掃描時(shí)，就將Gini指數(shù)最小的待選最佳分裂點(diǎn)選作最終分裂點(diǎn)。

3 并行SPRINT算法到HADOOP平臺(tái)的移植

3.1 并行SPRINT算法詳細(xì)設(shè)計(jì)

并行的SPRINT算法相比于傳統(tǒng)的SPRINT算法，除了需要具備屬性表和直方圖這兩類數(shù)據(jù)結(jié)構(gòu)之外，還需要引入哈希表來存儲(chǔ)每次節(jié)點(diǎn)分裂之后的子節(jié)點(diǎn)的數(shù)據(jù)信息。通過這些記錄的子節(jié)點(diǎn)信息來為節(jié)點(diǎn)的并行分割提供依據(jù)。其中哈希表的數(shù)據(jù)結(jié)構(gòu)包含兩類信息：一是決策時(shí)的節(jié)點(diǎn)號(hào)，用Tree-NodeID表示；另一個(gè)是當(dāng)前樹節(jié)點(diǎn)的子節(jié)點(diǎn)號(hào)，用ChildNodeID表示。ChildNodeID的值包括0和1，0代表該樹節(jié)點(diǎn)是左子節(jié)點(diǎn)，1代表該節(jié)點(diǎn)是該樹節(jié)點(diǎn)的右子節(jié)點(diǎn)。

其中計(jì)算最佳分裂點(diǎn)的部分代碼如下所示：

3.2 SPRINT并行算法的移植

SPRINT并行算法的移植的過程主要是完成其算法的MapReduce化，通過Map（）和Reduce（）兩個(gè)函數(shù)實(shí)現(xiàn)。這兩個(gè)函數(shù)算法N-S圖如圖3和圖4所示。

圖3 Map函數(shù)N-S圖

圖4 Reduce函數(shù)N-S圖

在上述處理結(jié)束后，屬性表就已全部分送到了對(duì)應(yīng)的葉子節(jié)點(diǎn)上了。此時(shí)，已經(jīng)結(jié)束了整個(gè)決策樹的創(chuàng)建。當(dāng)前節(jié)點(diǎn)的有關(guān)文件存放到了分布式文件系統(tǒng)。具體的表示方法如表1所示，其中，不論是葉子節(jié)點(diǎn)與非葉子節(jié)點(diǎn)都用N代表?！癴leaf”代表這不是葉子節(jié)點(diǎn)，而“tleaf”代表這是葉子節(jié)點(diǎn)。

表1 節(jié)點(diǎn)信息到HDFS的保存格式

采用了這樣的表示方法，就能夠方便的從HDFS中提取到簡(jiǎn)單易懂的決策樹結(jié)構(gòu)。所以本階段的主要工作就是從保存在HDFS中的上一階段的Reduce輸出中得到整顆樹的構(gòu)造情況。

4 實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)使用一個(gè)駕車風(fēng)險(xiǎn)高低預(yù)測(cè)的公用數(shù)據(jù)集作為訓(xùn)練集，它記錄的是參保車險(xiǎn)的車主的一些信息。其中圖5為創(chuàng)建的決策樹中全部節(jié)點(diǎn)信息，0、1代表風(fēng)險(xiǎn)的高低，P1至P4分別代表的是車主的年齡，性別，車種以及受教育程度。

圖5 決策樹中全部節(jié)點(diǎn)信息

為了判斷算法挖掘產(chǎn)生出的模式是否正確，在實(shí)際操作的過程中，就是把將全部的樣本集分割成了五個(gè)沒有交集的組，去測(cè)試準(zhǔn)確率。由此得到的數(shù)據(jù)如表2所示。

從表2可以計(jì)算出算法的準(zhǔn)確率E為76.2%。

通過計(jì)算我們可以發(fā)現(xiàn)算法的預(yù)測(cè)結(jié)果的準(zhǔn)確率在能夠接受的范圍之內(nèi)。為了達(dá)到測(cè)試算法的伸縮性的目的，本文的實(shí)驗(yàn)對(duì)一千萬條數(shù)據(jù)做了運(yùn)行時(shí)間的評(píng)價(jià)。分別用三次實(shí)驗(yàn)構(gòu)建了有著一至三個(gè)節(jié)點(diǎn)的集群。通過測(cè)試這些節(jié)點(diǎn)數(shù)量遞增的集群，得到了如表3所示的對(duì)算法的一個(gè)循環(huán)單元的執(zhí)行時(shí)間信息。

表3 不同節(jié)點(diǎn)數(shù)的算法執(zhí)行時(shí)間

通過觀察上表不難發(fā)現(xiàn)，在集群里每添加一個(gè)節(jié)點(diǎn)，算法的執(zhí)行時(shí)間都會(huì)顯著下降。這表明增加節(jié)點(diǎn)的個(gè)數(shù)可以提高并行度，繼而提高算法效率。而這一切均可以證明，實(shí)驗(yàn)已成功的將改進(jìn)后的SPRINT算法移植到了基于云計(jì)算的平臺(tái)HADOOP上，并對(duì)海量的數(shù)據(jù)集實(shí)現(xiàn)了準(zhǔn)確率較高的分類挖掘。

5 結(jié)束語

在這個(gè)數(shù)據(jù)呈爆炸式發(fā)展的時(shí)代，各類企業(yè)對(duì)大規(guī)模及超大規(guī)模數(shù)據(jù)進(jìn)行處理和和挖掘的強(qiáng)烈需求促生了數(shù)據(jù)挖掘以及云計(jì)算等技術(shù)。本文就是在這個(gè)大背景下，把數(shù)據(jù)挖掘分類算法同基于云計(jì)算的HADOOP集群框架進(jìn)行結(jié)合，借助于其超凡的存儲(chǔ)計(jì)算能力，達(dá)到了對(duì)海量數(shù)據(jù)挖掘的優(yōu)化。

［1］蔣良孝，蔡之華.分布式數(shù)據(jù)挖掘研究［J］.計(jì)算機(jī)與現(xiàn)代化，2002，85（9）：4-7.

［2］戴元順.云計(jì)算技術(shù)簡(jiǎn)述［J］.信息通信技術(shù)，2010（2）：29-35.

［3］Naohiro Ishii，TakahiroY amada，Yongguang Bao.Rough Set Based Learning for Classification［C］.20th IEEE International Conference on Tools with Artificial Intelligence，2008（2）：97-104.

［4］韓松來，張輝，周華平.基于關(guān)聯(lián)度函數(shù)的決策樹分類算法［J］.計(jì)算機(jī)應(yīng)用，2005，25（11）：2655-2657.