一種改進的SPRINT算法

白玲玲，韓天鵬

（1.中共阜陽市委黨校 教務處，安徽 阜陽 236034；2.阜陽師范學院 計算機與信息工程學院，安徽 阜陽 236037）

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

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

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

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

1 基本算法分析

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

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

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

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

2 算法的改進

2.1 改進算法的數據結構

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

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

2.2 M-BCBT算法描述

Master Server中構建分類器的核心程序包括啟動，規(guī)劃和控制整個決策樹模型.一系列在Slaves上運行的MapReduce任務用于計算拆分屬性和屬性列表的拆分.核心流程是維護一個全局決策樹.全局決策樹用于保存已建立的部分.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）.

在最初階段，核心程序根據預處理屬性列表中的信息建立根節(jié)點.然后，將根節(jié)點添加到全局節(jié)點隊列中，并調用構建樹功能以創(chuàng)建隊列節(jié)點的子樹.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.

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

2.3 計算最佳分割點

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

算法的主要優(yōu)點是它只需要計算每個數據塊的類別分布.該算法執(zhí)行一系列MapReduce任務來構建當前樹節(jié)點的直方圖和塊直方圖.然后，它計算基尼指數以確定每個最佳分割點.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任務.每個映射器獨立收集每個數據塊的類別分布信息，并輸出一個密鑰表，其中密鑰為屬性索引的屬性下標索引，其值由數據塊序號和類別關鍵值組成.

3 結果分析

3.1 實驗環(huán)境的構建

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

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

3.2 實驗結果及分析

為了分析M-BCBT算法的性能，筆者評估了時間效率，可擴展性，并行性和準確性.實驗數據是重復實驗的平均值.操作時間由算法運行時間，I/O通訊時間和數據預處理時間組成.

在實驗1中，比較了SPRINT和M-BCBT的計算時間，以評估時間性能并測試M-BCBT算法的可擴展性.通過使用相同的訓練數據集和增加訓練集的大小來比較SPRINT和M-BCBT的運行時間的趨勢.對于每個實驗，參數保持不變，操作時間見圖1.

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

圖1 訓練不同大小數據集的操作時間

圖2 算法運算時間隨數據節(jié)點數的變化趨勢

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

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

圖3 屬性表分割時間和分割點計算時間

圖4 M-BCBT算法的準確率趨勢

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

從結果來看，相同的M-BCBT精度會提高算法的時間效率.該算法具有良好的可擴展性，可滿足海量數據的需求.但該算法的結構復雜，復雜性受到性能限制.

4 結語

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