基于云計算及數據挖掘技術的海量數據處理研究

王鵬，王健安，郭暢，巴濟慈

（長春理工大學 計算機科學技術學院，長春 130022）

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

1 SPRINT算法

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

1.1 數據結構

SPRINT算法表示數據特征的方式是采用屬性表與直方圖這兩種數據結構，其中，后者是依附在前者之上，而前者又是隨著節點的劃分而分裂的。它會依據屬性的不同性質，如連續型或離散型而顯現出相應的表現形式。

屬性表是屬性值，類標記和記錄索引構成的三元組，它可以駐留在除內存外的介質上。直方圖是表示節點上的一個屬性所屬類的分布情況，當屬性是連續的數值型時，節點就涉及兩個直方圖：Cbelow表示已經處理完畢的樣本的類型分布，而Cabove表示尚沒處理的樣本，它們通過不間斷的刷新來找到最佳分裂點；當屬性是離散型時，便僅需一個直方圖，包括了這個屬性每個值的類分布信息，只需要維護一個叫做計數矩陣的統計圖。

1.2 最佳分裂點的度量和選擇

SPRINT算法使用Gini指數代替信息量作為選擇最佳分裂點的依據，它對決策樹的生成至關重要，Gini指數方法可以定義為［3］：

對有著M個類型的N項記錄的數據集S，對應的Gini為：

pi為第i類數據出現的頻率。

對數據集S劃分為S1、S2兩個部分，分別有n1、n2個記錄，則對應的Gini指數定義為：

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

1.3 SPRINT算法基本思想

傳統的SPRINT算法過程為：

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

（2）創建一個根節點M，并把全部屬性表附著在上面。

（3）對 M 執行BuildTree（S,A）。

（4）決策樹創建完畢后，就要對樹做剪枝處理了。最常用的方法是最小描述長度。由于樹的剪枝僅占SPRINT算法的執行時間的一部分，所以在驗證算法有效性的時候將忽略剪枝的時間復雜度［4］。

2 SPRINT算法并行策略

2.1 節點之間的并行

傳統SPRINT算法的核心在于數據集的分裂，屬性表依附于節點之上，當它發現了核實的分裂點便進行分裂。分裂之后繼續在新的節點上進行分類。而在SPRINT并行算法中，通過調用Map函數接受一組鍵值對，之后將輸出的中間健值對發送到Reduce函數?；谝陨咸匦?，算法就能夠用Map函數將在同一個樹層節點的全部的屬性表發送到不一樣的Reduce中去從而實現分裂的并行，如圖1所示。

圖1 節點之間的并行

2.2 屬性表之間的并行

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

圖2 屬性表之間的并行

因此，若想要使得屬性名不一樣或是節點符號不一樣的屬性表可以并行處理如圖2僅需在執行Map函數的過程中將分區函數Partitioner規定為：僅當屬性表的節點符號一樣并且屬性表的屬性也相同時才可能將它們映射到同一個Reducer。

2.3 排序的并行

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

3 并行SPRINT算法到HADOOP平臺的移植

3.1 并行SPRINT算法詳細設計

并行的SPRINT算法相比于傳統的SPRINT算法，除了需要具備屬性表和直方圖這兩類數據結構之外，還需要引入哈希表來存儲每次節點分裂之后的子節點的數據信息。通過這些記錄的子節點信息來為節點的并行分割提供依據。其中哈希表的數據結構包含兩類信息：一是決策時的節點號，用Tree-NodeID表示；另一個是當前樹節點的子節點號，用ChildNodeID表示。ChildNodeID的值包括0和1，0代表該樹節點是左子節點，1代表該節點是該樹節點的右子節點。

其中計算最佳分裂點的部分代碼如下所示：

3.2 SPRINT并行算法的移植

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

圖3 Map函數N-S圖

圖4 Reduce函數N-S圖

在上述處理結束后，屬性表就已全部分送到了對應的葉子節點上了。此時，已經結束了整個決策樹的創建。當前節點的有關文件存放到了分布式文件系統。具體的表示方法如表1所示，其中，不論是葉子節點與非葉子節點都用N代表?！癴leaf”代表這不是葉子節點，而“tleaf”代表這是葉子節點。

表1 節點信息到HDFS的保存格式

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

4 實驗結果

本實驗使用一個駕車風險高低預測的公用數據集作為訓練集，它記錄的是參保車險的車主的一些信息。其中圖5為創建的決策樹中全部節點信息，0、1代表風險的高低，P1至P4分別代表的是車主的年齡，性別，車種以及受教育程度。

圖5 決策樹中全部節點信息

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

從表2可以計算出算法的準確率E為76.2%。

通過計算我們可以發現算法的預測結果的準確率在能夠接受的范圍之內。為了達到測試算法的伸縮性的目的，本文的實驗對一千萬條數據做了運行時間的評價。分別用三次實驗構建了有著一至三個節點的集群。通過測試這些節點數量遞增的集群，得到了如表3所示的對算法的一個循環單元的執行時間信息。

表3 不同節點數的算法執行時間

通過觀察上表不難發現，在集群里每添加一個節點，算法的執行時間都會顯著下降。這表明增加節點的個數可以提高并行度，繼而提高算法效率。而這一切均可以證明，實驗已成功的將改進后的SPRINT算法移植到了基于云計算的平臺HADOOP上，并對海量的數據集實現了準確率較高的分類挖掘。

5 結束語

在這個數據呈爆炸式發展的時代，各類企業對大規模及超大規模數據進行處理和和挖掘的強烈需求促生了數據挖掘以及云計算等技術。本文就是在這個大背景下，把數據挖掘分類算法同基于云計算的HADOOP集群框架進行結合，借助于其超凡的存儲計算能力，達到了對海量數據挖掘的優化。

［1］蔣良孝，蔡之華.分布式數據挖掘研究［J］.計算機與現代化，2002，85（9）：4-7.

［2］戴元順.云計算技術簡述［J］.信息通信技術，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］韓松來，張輝，周華平.基于關聯度函數的決策樹分類算法［J］.計算機應用，2005，25（11）：2655-2657.