一種改進(jìn)的SPRINT算法

白玲玲，韓天鵬

（1.中共阜陽(yáng)市委黨校 教務(wù)處，安徽 阜陽(yáng) 236034；2.阜陽(yáng)師范學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，安徽 阜陽(yáng) 236037）

共享在互聯(lián)網(wǎng)和無(wú)線網(wǎng)絡(luò)上的微博、個(gè)人博客、基于Web 2.0的圖片和視頻產(chǎn)生了大量的數(shù)據(jù)；其中存儲(chǔ)在半結(jié)構(gòu)化XML文檔、HTML文檔和非結(jié)構(gòu)化的照片、音頻和視頻中的數(shù)據(jù)也日益豐富.同樣網(wǎng)絡(luò)搜索、商業(yè)銷(xiāo)售、生物醫(yī)學(xué)、自然觀察和科學(xué)計(jì)算等領(lǐng)域也都有大量的數(shù)據(jù)［1］.這些數(shù)據(jù)類型多樣，具有規(guī)模大，變化速度快、分布式存儲(chǔ)、異構(gòu)性、半結(jié)構(gòu)化或非結(jié)構(gòu)化等相同特征.基于數(shù)據(jù)流的離群挖掘算法并不能完全滿足滿足獲取、管理、分析和理解大量快速變化數(shù)據(jù)的需要，數(shù)據(jù)密集型計(jì)算就是在這樣的背景下?tīng)I(yíng)運(yùn)而生［2-3］.

聚類是數(shù)據(jù)挖掘中最重要的技術(shù)之一，它旨在將物理或抽象主體與相似主題相關(guān)聯(lián).Jiang等人提出了在 MapReduce中使用 k-means聚類算法，并通過(guò) MapReduce［4］實(shí)現(xiàn)了 k-means［5］算法的轉(zhuǎn)換.Hong 等人提出了DRICA（動(dòng)態(tài)粗糙增量聚類算法）作為解決數(shù)據(jù)更新問(wèn)題的一種方法，確保了算法的穩(wěn)定性并克服了在所有數(shù)據(jù)上實(shí)現(xiàn)算法的低效率［6-7］.

頻繁項(xiàng)目集挖掘是關(guān)聯(lián)規(guī)則挖掘，序列模式挖掘，關(guān)聯(lián)挖掘和多層次挖掘的最基本和重要的過(guò)程［8-9］.Apriori挖掘算法基于云計(jì)算，在事務(wù)集和基于MapReduce模型的項(xiàng)目集上實(shí)現(xiàn)雙重二進(jìn)制編碼，該算法只需要布爾AND和OR運(yùn)算，效率較高［10］.Li等人提出了基于閉項(xiàng)目集挖掘算法的CMFS算法，該算法使用約束最大頻繁項(xiàng)集深度優(yōu)先策略和修剪算法［11］.Hong等人提出了FIMDS算法，該算法可以從分布式數(shù)據(jù)中挖掘頻繁項(xiàng)集，使用頻繁模式樹(shù)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)，有助于從每個(gè)部分模式樹(shù)（FP-tree）根獲取項(xiàng)目組頻率［12］.

離群數(shù)據(jù)挖掘是數(shù)據(jù)挖掘中使用的主要方法之一.異常值是一個(gè)與其他數(shù)據(jù)對(duì)象不同的數(shù)據(jù)對(duì)象，由不同的機(jī)制產(chǎn)生的［13］.數(shù)據(jù)密集型計(jì)算中的大多數(shù)離群挖掘算法涉及擴(kuò)展和改進(jìn)經(jīng)典離群值挖掘算法.最近，提出了許多基于數(shù)據(jù)流的傳統(tǒng)異常值檢測(cè)算法.由于時(shí)間復(fù)雜度高，責(zé)任響應(yīng)速度尚未達(dá)到，結(jié)果誤差較大，準(zhǔn)確性不理想.異常值檢測(cè)算法應(yīng)用于數(shù)據(jù)的研究仍處于初級(jí)階段.對(duì)數(shù)據(jù)密集型計(jì)算環(huán)境中異常值檢測(cè)的研究具有重要意義.Pan利用基于Hadoop平臺(tái)的SPRINT算法，采用并行方法構(gòu)建決策樹(shù)，然后解決Hadoop平臺(tái)中的并行問(wèn)題.

1 基本算法分析

Shafer等人在1996年提出了基于SLIQ的SPRINT決策樹(shù)算法［20］.SPRINT算法結(jié)合了屬性列表和類別列表.屬性列表用于存儲(chǔ)屬性值，直方圖用于記錄指定節(jié)點(diǎn)前后部分的分類分布，并使用散列表代替SLIQ來(lái)記錄屬性子節(jié)點(diǎn)的屬性值，訓(xùn)練元組的形成.屬性列表和組織圖數(shù)據(jù)結(jié)構(gòu)不需要存儲(chǔ)或存儲(chǔ)器，這消除了存儲(chǔ)能力的大小限制.SPRINT算法不僅簡(jiǎn)單，準(zhǔn)確，快速，還改善了數(shù)據(jù)結(jié)構(gòu)，這使挖掘問(wèn)題更容易解決.

SPRINT算法使用屬性列表和直方圖來(lái)幫助計(jì)算最佳分割點(diǎn)和分割屬性.屬性列表的每個(gè)元組都由數(shù)據(jù)記錄索引，屬性值和類別ID組成.在SPRINT算法的初始化中，為每個(gè)屬性創(chuàng)建一個(gè)屬性列表，連續(xù)屬性的屬性列表需要根據(jù)其屬性值進(jìn)行預(yù)先排序.

隨著節(jié)點(diǎn)被分成子屬性列表中的子節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)維護(hù)的屬性列表將被擴(kuò)展.每個(gè)節(jié)點(diǎn)都維護(hù)一個(gè)直方圖，計(jì)數(shù)矩陣，散列表等.直方圖用于描述所選連續(xù)屬性劃分的分類分布信息.計(jì)數(shù)矩陣用于確定分類的數(shù)量和屬性值的離散屬性的節(jié)點(diǎn)選擇的屬性列表的關(guān)系.直方圖和標(biāo)記矩陣用于支持基尼指數(shù)的計(jì)算.哈希表記錄拆分后的最佳拆分屬性和可用子節(jié)點(diǎn)信息；然后，用于幫助分割其他屬性列表.

對(duì)于特定節(jié)點(diǎn)，在確定最佳分裂屬性及其分裂節(jié)點(diǎn)之后，可以直接在子節(jié)點(diǎn)之間劃分與該屬性相對(duì)應(yīng)的屬性列表.由于不同特性列表的序列不同，不能直接劃分.相反，在劃分其他屬性列表之前，應(yīng)該從節(jié)點(diǎn)的最佳分割屬性及其分割點(diǎn)信息生成散列表.哈希表用于記錄節(jié)點(diǎn)所在的子節(jié)點(diǎn)，還用于分割其他屬性列表.

2 算法的改進(jìn)

2.1 改進(jìn)算法的數(shù)據(jù)結(jié)構(gòu)

屬性列表具有與SPRINT算法相同的功能：它用于記錄分配信息.訓(xùn)練數(shù)據(jù)集根據(jù)初始化期間的屬性分解為獨(dú)立的屬性列表.每個(gè)屬性列表由屬性值，類別值和索引值組成.屬性列表的數(shù)量取決于屬性的數(shù)量.最初，根節(jié)點(diǎn)用于維護(hù)整個(gè)屬性列表.與連續(xù)屬性對(duì)應(yīng)的每個(gè)屬性列表都已預(yù)先排列，并且隨著節(jié)點(diǎn)數(shù)量的增加，屬性列表將被拆分.分割屬性列表屬于相應(yīng)的子節(jié)點(diǎn).

直方圖用于描述類分布，并對(duì)應(yīng)于SPRINT算法中決策樹(shù)中的樹(shù)節(jié)點(diǎn)；它的結(jié)構(gòu)與M-BCBT算法中的直方圖不同.直方圖用于計(jì)算屬于樹(shù)節(jié)點(diǎn)的最佳拆分屬性及其拆分節(jié)點(diǎn).為了利用MapReduce編程框架，對(duì)直方圖結(jié)構(gòu)進(jìn)行了一些更改.數(shù)據(jù)被分成幾個(gè)塊并存儲(chǔ)在群集環(huán)境中，以便與MapReduce進(jìn)行數(shù)據(jù)處理.直方圖用于記錄屬于每個(gè)數(shù)據(jù)塊掃描節(jié)點(diǎn)的屬性值分布.對(duì)于連續(xù)屬性，每個(gè)數(shù)據(jù)塊都有兩個(gè)對(duì)應(yīng)的直方圖，即Cbelow和Cabove，它們?nèi)Q于當(dāng)前數(shù)據(jù)塊的屬性列表中的掃描位置.Cbelow表示a≤R的類分布條件的所有記錄，而Cabove表示a>R的類分布條件的所有記錄，其中參數(shù)a是掃描值的連續(xù)屬性，R表示最佳分割值.每個(gè)直方圖記錄由數(shù)據(jù)塊索引和所有類記錄組成.

2.2 M-BCBT算法描述

Master Server中構(gòu)建分類器的核心程序包括啟動(dòng)，規(guī)劃和控制整個(gè)決策樹(shù)模型.一系列在Slaves上運(yùn)行的MapReduce任務(wù)用于計(jì)算拆分屬性和屬性列表的拆分.核心流程是維護(hù)一個(gè)全局決策樹(shù).全局決策樹(shù)用于保存已建立的部分.Build Classifier程序流程如下：

Require：NodeQueue NQ，TreeModel TM，Training record

（x，y）∈D， Attribute set Att

Troot=new Node

Initiate（Troot， D，Att）

TM=Troot

NQ.push_back（Troot）

BuildTree（NQ）.

在最初階段，核心程序根據(jù)預(yù)處理屬性列表中的信息建立根節(jié)點(diǎn).然后，將根節(jié)點(diǎn)添加到全局節(jié)點(diǎn)隊(duì)列中，并調(diào)用構(gòu)建樹(shù)功能以創(chuàng)建隊(duì)列節(jié)點(diǎn)的子樹(shù).BuildTree的程序流程如下：

Require：NodeQueue NQ， TreeModel TM， Training record

（x，y） ∈D

For each Tcurr∈NQ do

If JudgeLeaf（Tcurr） is false then

bestSplit=FindBestSplit（Tcurr）

Tcurr→splitAtt=bestSplit→splitAtt

If bestSplit→splitAtt is category then

Tcurr→leftAttSet=bestSplit→leftAttSet

Tcurr→rightAttSet=bestSplit→rightAttSet

Else Tcurr→splitValue=bestSplit→splitValue

parationTrainingSet（Tcurr→D， leftD， rightD）

remove（Tcurr→splitAtt）

Create new nodes Tleft，Tright

Initiate（Tleft， leftD，Att）

nitiate（Tright， rightD，Att）Tcurr→left=Tleft

Tcurr→right=Tright

NQ.push_back（Tleft）

NQ.push_back（Tright）

Else Tcurr→isLeaf=true

Tcurr→label=y.

每個(gè)非葉子節(jié)點(diǎn)只有兩個(gè)分支，在決策樹(shù)模型中只執(zhí)行二分裂.在構(gòu)建決策樹(shù)的過(guò)程中，Tcurr表示從全局節(jié)點(diǎn)隊(duì)列中提取并按順序處理的樹(shù)節(jié)點(diǎn).首先，需要檢查T(mén)curr是否是葉節(jié)點(diǎn).如果訓(xùn)練數(shù)據(jù)元組Tcurr是“純”（全部3個(gè)組件屬于同一個(gè)類別）或者訓(xùn)練數(shù)據(jù)元組的數(shù)量達(dá)到用戶定義的閾值，則Tcurr標(biāo)記為葉節(jié)點(diǎn).在第一種情況下，每個(gè)節(jié)點(diǎn)根據(jù)它所屬的類別進(jìn)行標(biāo)記.在第二種情況下，每個(gè)節(jié)點(diǎn)所屬類別的數(shù)量被用作標(biāo)簽.其次，核心計(jì)算拆分節(jié)點(diǎn)并選擇最佳拆分屬性.Tcurr根據(jù)最佳分割信息和分割屬性進(jìn)行標(biāo)記.訓(xùn)練集用于將Tcurr的屬性列表分成左側(cè)和右側(cè)，用于生成子樹(shù)Tleft和Tright.然后，Tleft和Tright被添加到全局節(jié)點(diǎn)隊(duì)列中.隊(duì)列NQ中的節(jié)點(diǎn)被迭代刪除.當(dāng)隊(duì)列為空時(shí)，程序結(jié)束并且決策樹(shù)模型完成.

2.3 計(jì)算最佳分割點(diǎn)

計(jì)算最佳分割點(diǎn)的算法與SPRINT算法類似，并涉及掃描連續(xù)屬性計(jì)算分割點(diǎn)或離散屬性技術(shù)矩陣的屬性列表.該算法采用MapReduce技術(shù)實(shí)現(xiàn)了最佳分割點(diǎn)的并行處理，提高了算法的效率.假設(shè)N個(gè)Mapper任務(wù)用于處理掃描統(tǒng)計(jì)信息，以便每個(gè)Mapper任務(wù)只處理訓(xùn)練數(shù)據(jù)集的1/N.信息匯總和分割點(diǎn)計(jì)算通過(guò)Reducer執(zhí)行，它返回最佳分割信息和分割屬性.

算法的主要優(yōu)點(diǎn)是它只需要計(jì)算每個(gè)數(shù)據(jù)塊的類別分布.該算法執(zhí)行一系列MapReduce任務(wù)來(lái)構(gòu)建當(dāng)前樹(shù)節(jié)點(diǎn)的直方圖和塊直方圖.然后，它計(jì)算基尼指數(shù)以確定每個(gè)最佳分割點(diǎn).FindBestSplit算法的Mapper部分和Reducer部分的描述分別如下：

Mapper算法：

Require：Current node Tcurr，Attribute set Att，Class set Y

For each A∈Att do

Class Count array countY for Y

Index=firstreCord（Tcurr→D）

For all（x，y）∈（Tcurr→D，Attribute list of A） do

county［findY（Y，y）］++

Output（（findA（A）），（Index， countY））.

Reducer（ ）算法：

Require：Key k， Value Set V， Attribute set Att， Class set Y

For All k do

If Att［k］is continuous then

For all distinct values∈V do

If sameBlock（value ［i］） then

Output（（k），（value ［i］， sumCount（value ［i］）））.

上面的偽代碼在FindBestSplit的Map階段描述了Mapper任務(wù).每個(gè)映射器獨(dú)立收集每個(gè)數(shù)據(jù)塊的類別分布信息，并輸出一個(gè)密鑰表，其中密鑰為屬性索引的屬性下標(biāo)索引，其值由數(shù)據(jù)塊序號(hào)和類別關(guān)鍵值組成.

3 結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境的構(gòu)建

實(shí)驗(yàn)在Hadoop 0.20.2分布式平臺(tái)上進(jìn)行，該平臺(tái)由9臺(tái)PC機(jī)組成，具有2.93 GHz的CPU，2 GB內(nèi)存，200 GB硬盤(pán)和Red Hat Linux操作系統(tǒng).Eclipse3.3.2是一個(gè)開(kāi)發(fā)工具，其中一個(gè)是服務(wù)器節(jié)點(diǎn)，另外八個(gè)是數(shù)據(jù).

UCI數(shù)據(jù)庫(kù)是數(shù)據(jù)挖掘的主要數(shù)據(jù)源之一.本實(shí)驗(yàn)使用UCI數(shù)據(jù)庫(kù)中的KDD Cup 1999數(shù)據(jù)集，該數(shù)據(jù)由4 000 000條記錄和40個(gè)屬性組成，其中34個(gè)是連續(xù)屬性，5個(gè)是離散屬性，1個(gè)是類標(biāo)記屬性（離散屬性）.

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

為了分析M-BCBT算法的性能，筆者評(píng)估了時(shí)間效率，可擴(kuò)展性，并行性和準(zhǔn)確性.實(shí)驗(yàn)數(shù)據(jù)是重復(fù)實(shí)驗(yàn)的平均值.操作時(shí)間由算法運(yùn)行時(shí)間，I/O通訊時(shí)間和數(shù)據(jù)預(yù)處理時(shí)間組成.

在實(shí)驗(yàn)1中，比較了SPRINT和M-BCBT的計(jì)算時(shí)間，以評(píng)估時(shí)間性能并測(cè)試M-BCBT算法的可擴(kuò)展性.通過(guò)使用相同的訓(xùn)練數(shù)據(jù)集和增加訓(xùn)練集的大小來(lái)比較SPRINT和M-BCBT的運(yùn)行時(shí)間的趨勢(shì).對(duì)于每個(gè)實(shí)驗(yàn)，參數(shù)保持不變，操作時(shí)間見(jiàn)圖1.

隨著訓(xùn)練數(shù)據(jù)集的大小增加，M-BCBT的操作效率逐漸優(yōu)于SPRINT的操作效率.當(dāng)只有少量數(shù)據(jù)時(shí)，HDFS需要分割訓(xùn)練數(shù)據(jù)并將分布存儲(chǔ)在數(shù)據(jù)節(jié)點(diǎn)中；M-BCBT的預(yù)處理時(shí)間遠(yuǎn)高于算法的運(yùn)行時(shí)間，導(dǎo)致M-BCBT的總時(shí)間效率低于SPRINT.在數(shù)據(jù)集達(dá)到一定大小后，并行化使M-BCBT的決策樹(shù)建立更高效，縮短了計(jì)算時(shí)間.與此同時(shí)，對(duì)于大型數(shù)據(jù)集，SPRINT算法的運(yùn)行時(shí)間迅速增加.SPRINT算法對(duì)于大數(shù)據(jù)具有良好的可擴(kuò)展性，但仍有許多限制，例如數(shù)據(jù)結(jié)構(gòu)限制以及存儲(chǔ)器中散列表和直方圖存儲(chǔ)的限制.M-BCBT算法使用MapReduce框架和HDFS分布式文件系統(tǒng)來(lái)提高算法的可伸縮性.

圖1 訓(xùn)練不同大小數(shù)據(jù)集的操作時(shí)間

圖2 算法運(yùn)算時(shí)間隨數(shù)據(jù)節(jié)點(diǎn)數(shù)的變化趨勢(shì)

在實(shí)驗(yàn)2中，研究M-BCBT算法在并行總操作時(shí)間特性.在使用相同的訓(xùn)練數(shù)據(jù)集情況下，其會(huì)隨著Hadoop聚類數(shù)據(jù)節(jié)點(diǎn)數(shù)量的增加而減少.算法的其他參數(shù)對(duì)于每個(gè)實(shí)驗(yàn)都保持不變.圖2列出了多個(gè)觀測(cè)值的平均值.隨著聚類節(jié)點(diǎn)數(shù)量的增加，M-BCBT的工作時(shí)間呈指數(shù)下降.

在實(shí)驗(yàn)3中，考察了測(cè)試算法分裂點(diǎn)計(jì)算時(shí)間和屬性表分裂的趨勢(shì).使用相同的訓(xùn)練數(shù)據(jù)集并保持其大小不變，Hadoop聚類數(shù)據(jù)節(jié)點(diǎn)的數(shù)量增加，并檢查M-BCBT算法的MapReduce任務(wù)分割點(diǎn)計(jì)算時(shí)間和屬性表分割時(shí)間的趨勢(shì).算法的其他參數(shù)保持不變.結(jié)果的平均值顯示見(jiàn)圖3.隨著節(jié)點(diǎn)數(shù)量的增加，分割點(diǎn)計(jì)算時(shí)間線性下降，屬性表分割時(shí)間線性增加.隨著節(jié)點(diǎn)數(shù)量的增加，分叉點(diǎn)計(jì)算優(yōu)化過(guò)程得到改善，算法的效率得到提高.然而，屬性表拆分方法限制了算法在效率方面的改進(jìn).

圖3 屬性表分割時(shí)間和分割點(diǎn)計(jì)算時(shí)間

圖4 M-BCBT算法的準(zhǔn)確率趨勢(shì)

實(shí)驗(yàn)4是M-BCBT算法和SPRINT算法的測(cè)試和精度比較.在這個(gè)實(shí)驗(yàn)中，Hadoop集群數(shù)據(jù)節(jié)點(diǎn)的數(shù)量保持不變，并使用相同的訓(xùn)練數(shù)據(jù)集.改變數(shù)據(jù)集大小，觀察和比較M-BCBT算和SPRINT算法之間的準(zhǔn)確度.對(duì)于每個(gè)實(shí)驗(yàn)，所有其他參數(shù)保持不變.觀察結(jié)果的平均值見(jiàn)圖4.與SPRINT算法相比，M-BCBT算法的準(zhǔn)確度沒(méi)有明顯變化，并且隨著數(shù)據(jù)集的增加，這兩種算法獲得相似的準(zhǔn)確度，因?yàn)樵贛-BCBT算法中仍然采用精確查找技術(shù)，準(zhǔn)確度不會(huì)受到算法框架變化的影響.

從結(jié)果來(lái)看，相同的M-BCBT精度會(huì)提高算法的時(shí)間效率.該算法具有良好的可擴(kuò)展性，可滿足海量數(shù)據(jù)的需求.但該算法的結(jié)構(gòu)復(fù)雜，復(fù)雜性受到性能限制.

4 結(jié)語(yǔ)

隨著大數(shù)據(jù)的發(fā)展，挖掘有用的信息已成為人們關(guān)注的主題.數(shù)據(jù)密集型環(huán)境只能在大數(shù)據(jù)挖掘研究的背景下考慮.目前對(duì)數(shù)據(jù)密集型計(jì)算環(huán)境中的數(shù)據(jù)挖掘算法的研究集中在改進(jìn)傳統(tǒng)的大規(guī)模聚類算法上.在本文中，引入了一種稱為M-BCBT的決策樹(shù)分類算法，該算法基于SPRINT算法和MapRe-duce計(jì)算框架，適用于數(shù)據(jù)密集型計(jì)算.通過(guò)實(shí)驗(yàn)測(cè)試了M-BCBT算法的性能.結(jié)果表明，M-BCBT算法具有良好的可擴(kuò)展性和高水平的數(shù)據(jù)可用性.當(dāng)大量數(shù)據(jù)時(shí)，大規(guī)模聚類的運(yùn)行時(shí)間會(huì)減少.