數據密集型計算環境下的離群點挖掘算法

陳亞麗+張龍波+張樹

摘要：在數據密集型計算環境中，數據的海量、高維、分布存儲等特點，為數據挖掘算法的設計與實現帶來了新的挑戰。基于MapReduce模型提出網格技術與基于密度的方法相結合的離群點挖掘算法，該算法分為兩步：Map階段采用網格技術刪除大量不可能成為離群點的正常數據，將代表點信息發送給主節點;Reduce階段采用基于密度的聚類方法，通過改進其核心對象選取，可以挖掘任意形狀的離群點。實驗結果表明，在數據密集型計算環境中，該方法能有效的對離群點進行挖掘。

引言：

隨著數據海量增長、數據類型日益增多，如何快速處理數據密集型計算環境中數據是目前急需解決的問題。我們把以高效的方式獲取、管理、分析和理解海量且高速變化的數據來滿足目標需求的計算過程稱為數據密集型計算[1]。數據可能以極高的速度生成，對數據的過濾、整合和存儲等一系列操作必須能適應數據的生成速度。另外，數據密集型計算任務需要在合理的時間內分析和處理數據。但是，大多數情況下，數據以分布方式存儲。因此，決定因素不再是計算能力，而是傳輸速度能否跟得上系統收集、處理和分析數據的速度[2]。Google基于大規模數據集的并行運算編程模型MapReduce將所有數據操作類型通過統一的編程模型連接起來，使海量、高速變化、異構和分布存儲的數據能夠在由普通計算機組成的集群中運行，在一定程度上實現了全局化的資源管理與調度。

數據密集型計算環境中數據的海量、快速變化、分布、異構等特點給離群點數據的挖掘帶來了新的挑戰。數據量的增長速度甚至超過了單個主存儲器或硬盤容量增長的速度[3，4]， 地理位置的分布性和網絡傳輸速度限制了大量數據在不同機器間的自由移動[5]。通過只傳輸中間處理結果等少量信息減小數據傳輸量以提高網絡傳輸速度。采用分布式集群進行離群點挖掘成為了一種趨勢。

相關工作：現有的方法大多是基于統計分布、深度、距離、聚類或網格等的離群點挖掘方法。文獻[6]基于統計分布提出了100多種針對不同數據分布的離群點挖掘方法。為減少距離計算，引進空間索引結構KD-樹、R-樹和X-樹等查找數據點的k鄰近[7]。這些方法在低維空間中時間復雜度接近O（NlogN）。但是，隨著維度的增加，方法失效。基于聚類的DBScan[8]算法檢測出聚類的同時也檢測出了離群點。缺點是數據量增大時，對內存容量要求高，I/0開銷很大。張凈等人提出的IGDLOF算法根據鄰居網格[9]中數據分布情況判斷該單元格是否為稀疏單元，依次進行數據篩選。基于網格的OMAGT[10]算法，降低了挖掘大數據集時對內存的要求，但是需計算局部可達密度。基于網格和密度思想的FOMAUC[11]算法能有效提高算法效率和挖掘準確度，但是該算法不適用于高維大數據集，其整個過程都是在內存中進行的，對內存要求比較高。目前，基于MapReduce模型的離群點挖掘算法研究相對較少。

MapReduce是由Google提出的主要用于海量數據處理的軟件框架。它將數據看作一系列的<key，value>，處理過程包括Map映射和Reduce規約兩個階段。用戶實現一個Map函數來處理輸入<key，value>，產生相應的中間<key，value>。Reduce函數合并所有具有相同key值的中間鍵值對，并作為后續MapReduce的輸入，在此基礎上完成用戶所需的功能。MapReduce程序可自動分布到一個由普通機器組成的超大集群上并發執行[12]。因此，此模型在一定程度上能滿足數據密集型計算環境下離群點挖掘的需求。

在MapReduce模型基礎上，利用DBScan算法對離群點敏感的特點，將網格重心確定為DBScan算法核心對象，能有效防止由于核心對象選取不當而產生的波動現象，并通過設置閾值判斷集體離群點的存在。

算法分析與描述

在數據密集型計算環境中，離群點只占整個數據集的一小部分，而且有可能分布在不同的區域。基于MapReduce模型，各分節點將不可能成為離群點的數據刪除，再對剩余數據在主節點進行全局離群點挖掘。分節點采用網格方法處理數據，將產生的代表信息和擬離群點信息發送到主節點。key為網格ID，value為網格五元組信息。網格方法可用來處理任意類型的數據，處理時間與數據的數目和輸入順序無關。因此，一定程度上可減少檢測數據量，降低網絡數據傳輸量。主節點將各個分節點發送的代表點信息整合，合并key值相同的網格單元信息，進行全局范圍的數據篩選。將網格重心初始化為MR_DBScan核心對象，依次由高密度到低密度從未訪問數據集中選取，避免了因核心對象選取不當而引起波動現象的發生。利用網格刪除大量正常數據，降低了數據集聚類數，減小了存儲核心對象信息所需的內存容量，提高了算法的執行效率。

網格單元為一個五元組U（T，P，G，Max，Min），即U（網格類型，點數，重心，最大值，最小值）。P為每個U中的數據點總數，也稱為單元格密度。U中去掉最大值、最小值，每一維上數據坐標的算術平均值為重心G的值。若U中的數據點總數P不小于某一給定的閾值N，即|P|N，U是稠密單元; |P|

MR_DBScan算法概述：

輸入：d維數據集D、網格閾值N、閾值Num;

輸出：離群點的集合Outlier;

算法過程及形式化描述如下：

1）MapReduce框架將輸入數據分配給9臺PC機（實驗中的分節點）。

2）網格單元U中各維空間劃分相對獨立，每一維劃分的間隔不同。每一維的劃分以各相鄰數據點間的分布情況作為依據。

3）隨機選擇一個未經訪問的點，根據預先設定的維度間隔距離值計算該點所屬的網格單元。輸入數據的同時，計算U的五元組信息。

4）若U為稠密單元，且其L均為稠密單元，保存U和L的五元組信息，L放入C（候選集合）中。對C中網格的L進行遍歷查詢，直到所有L均為空，將U及所有L中數據全部刪除;L均為空單元，標記U和空單元并刪除U中數據。若U為稀疏單元，其L均為空，則U標記為離群單元并刪除U中數據，否則將其保留。位于數據分區邊界的單元格不為空時，全部保留。

5）分節點將代表點和擬離群點信息發送給主節點。

6）主節點將不同分節點發送的代表點劃分到相應的U中，實時更新U的五元組信息，直到所有數據全部錄入網格。

7）重復4）中步驟，篩選數據，得候選離群數據集及部分離群點。

8）在主節點進行全局離群點挖掘，偽代碼為：

輸入：

.D：7）中生成的候選離群數據集。

.ε：半徑參數。

.MinPts：領域密度閾值。

.Num：判定密度閾值。

輸出：離群點

方法：

標記所有重心點為unvisited;

do

選擇一個單元數據點數最多的unvisited重心點p;

標記p為visited;

if p的ε-領域至少有MinPts個對象

創建一個新簇C，將p添加到C;

令M為p的ε-領域中的對象集合;

for M中每個點p

if p是unvisited

標記p為visited;

if p的ε-領域至少有MinPts個點，將這些點添加到M;

if p還不是任何簇的成員，將p添加到C;

end for

if C中數據點數小于Num

標記C為集體離群點;（判斷是否有集體離群點存在）

輸出C;

else標記p為離群點;

輸出p;

until沒有標記為unvisited的對象;

9）將4）、7）、8）步驟中檢測出的離群點信息匯總輸出。

主節點執行任務的總體分配和調度，分節點通過步驟2）、3）、4）、5）將大量非離群數據刪除，并將代表信息發送給主節點做進一步的全局離群點挖掘。主節點執行步驟6）、7）、8）、9）對分節點發送的數據做全局離群點挖掘。改進的核心對象選取算法能很快檢測出簇，進而加快了對離群點的挖掘。

實驗結果與分析

實驗平臺配置如下：10臺相同配置的PC機（通過局域網連接），CPU Pentium Dual-Core E6500，內存2G，YLMF OS（Ubuntu） 操作系統，Hadoop0.20，1個主節點master，9個分節點slaves，用裝有Hadoop插件的eclipse進行代碼編輯，編譯jdk1.7。測試數據來自KDD Cup 1999，是MIT林肯實驗室進行的一項網絡入侵檢測評估中所采集的真實數據。共有41個屬性，34個為連續屬性，7個為離散屬性。數據對象包括五大類，正常連接、dos、u2r、r2l、probe入侵和攻擊。

本實驗在ε=3，MinPts=4時，檢測到離群點數為40，較真實離群點數多2，能檢測出所有離群點數據，誤檢率為5%。分節點算法時間復雜度為O（N），N為網格單元數。主節點時間復雜度為O（N/P）+O（nlogn），P為分節點數，n為數據量。因為O（N/P）<<O（nlogn），所以算法時間復雜度為O（nlogn）（n遠小于原始數據數目）

結論

本文針對數據密集型計算環境下離群點挖掘問題提出了基于MapReduce模型的分布式離群點數據挖掘算法MR_DBScan。該算法利用MapReduce框架，將網格方法與基于密度的聚類方法DBScan有效結合，對DBScan算法核心對象選取作出改進、并通過設置閾值判斷是否存在集體離群點。由實驗結果分析可知，MR_DBScan算法能有效地解決海量、分布、高速變化的密集型數據中離群點挖掘問題。但是，本文算法也存在一定的不足，網格單元密度閾值、ε、MinPts均需要人為設置。進一步研究的方向是，怎樣以自適應的方式來設定閾值，使該算法對數據的處理趨于智能化。