數據密集型計算環境下離群點挖掘算法設計與實現

陳亞麗， 張龍波， 李彩虹， 張樹森， 劉希昱

(山東理工大學 計算機科學與技術學院， 山東 淄博 255091)

數據密集型計算作為大規模分布式計算的一種計算方式，在科學研究、商業智能、生物信息、環境監控等眾多鄰域有著廣泛的應用.在數據密集型計算中，數據大多數情況下以分布方式存儲，網絡傳輸速度限制了大量數據在不同機器間的自由移動，傳輸速度能否跟得上系統收集、處理和分析數據的速度成了算法是否可行的決定因素之一[1].由于離群點數據只占總體數據的很少一部分，因此在各分節點進行數據預處理，將大量非離群數據刪除，然后將少量的代表信息發送給主節點，在主節點進行全局離群點挖掘.

Google基于大規模數據集的MapReduce并行運算模型，有利于大量數據輸入和輸出操作.Map對鍵值對進行處理，將產生的中間鍵值對>傳遞給Reduce.Reduce將并行子任務的中間數據合并，并進行相應的處理，最后輸出結果.該模型將所有數據操作類型用統一的編程模型連接起來，使數據能夠在由普通計算機組成的集群中運行，在一定程度上實現了全局化的資源管理與調度[2].

現有的基于離群度的離群點挖掘算法主要不同在于離群度的計算方法設置不同.LOF[3]算法以局部離群點因子作為離群點關于其局部領域內密度的異常程度度量，對離群點挖掘有顯著的作用.但是該方法需要對每個數據計算局部離群因子值，花費的代價很大，限制了其在數據密集型計算環境中的應用.COF[4]算法根據參數k和數據對象的連接性確定鄰域，與其鄰域的平均連接距離比作為基于連接的離群系數COF，但時間復雜度高于LOF.SLOF[5]算法通過計算鄰域距離和空間局部離群系數，解決空間數據的自相關性和異質性約束性.該方法采用了R*樹的索引方法查找鄰域，在高維大規模數據中，算法的執行效率不高.GDLOF[6]算法通過證明稠密單元和稠密區域中的點不可能成為離群點，減小了數據LOF值的計算量，提高了執行效率.ODRKNN[7]算法用每個數據點的反向K近鄰數來衡量偏離程度.反向K近鄰數越少，越有可能是一個離群點.大量數據點離群度的計算和鄰域查詢在某種程度上增加了算法的計算復雜度，降低了算法在高維大規模數據集中的可擴展性.

本文基于MapReduce模型，根據對象的局部離群點因子值(LOF)與1的接近程度，只需計算部分可能會成為離群點數據的LOF值，彌補了LOF算法需要計算所有點的鄰域和局部密度的不足.各分節點使用網格進行數據約簡，將中間結果等少量信息發送給主節點，進而減少數據傳輸量，提高網絡傳輸速度.主節點使用網格期望值做參考值，篩選出位于高密度區的數據，只對分布在邊緣的數據進行LOF值計算，最后統計出具有較高LOF值的數據作為離群點.

1 算法分析與描述

1.1 LOF算法

LOF算法由給定參數的最少鄰居數k和最近鄰距離來確定鄰域，通過對象k-距離、可達距離和可達密度的計算，確定數據對象鄰域的平均可達密度與數據對象自身的可達密度比為對象的局部離群點因子值.根據離群點因子值的大小來判斷數據對象是否為離群點.

(1)

(2)

reachdistk(o←o′)=

max{distk(o),dist(o,o′)}

(3)

其中Nk(o)為對象o的k-距離范圍內數據總數

公式(1)、(2)、(3)分別給出了o的局部離群點因子、對象o的局部可達密度和從o’到o的可達距離的計算方法.該算法能很好地解決局部離群點的挖掘問題，但是存在計算量大等缺點，不適用于對數據密集型計算環境中離群點數據的挖掘.

1.2 MR_LOF算法

網絡傳輸量大、計算復雜度高等因素限制了LOF算法在數據密集型計算環境下可用性.本文在LOF算法基礎上提出一種MR-LOF算法，該算法利用MapReduce模型在各分節點采用網格進行數據篩選，將代表點信息發送給主節點，主節點進行全局離群點挖掘.其中key為網格ID，value為網格五元組信息。主節點將網格期望值k鄰近中距離最遠的點確定為檢測對象，因數據的LOF值在簇內約等于1，簇邊緣略大于1，離簇越遠值越大，根據其LOF值與1的關系判斷是否需要對k鄰近中其他點進行檢測.該算法只需計算部分稀疏區域數據的LOF值，很大程度上加快了離群點挖掘速度.

定義：U(T,P,E,Max,Min)為網格單元五元組

T：網格類型；

P:網格單元中數據點數，設為單元格密度；

E: U中去掉最大值、最小值，剩余數據的期望值；

Max：數據中最大值；

Min：數據中最小值.

若U中P不小于某一給定閾值N，即|P|N，U為稠密單元Udense；若U中P小于某一給定閾值N，即|P|

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

輸出：離群點的集合Outlier；

算法形式化描述如下：

1)MapReduce框架對任務進行統一調度.

2) U中各維空間獨立劃分，每一維的劃分由相鄰數據點間的分布情況決定.

3) 根據預先設定的維度間隔距離值計算數據所屬的網格單元.輸入數據的同時，計算U的五元組信息.

4) 若U為Udense，且其L均為Udense，保存U和L的五元組信息，L放入C(候選集合)中.對C中網格的L進行遍歷查詢，直到所有L均為空，將U及所有L中數據全部刪除；L均為Unull，標記U和Unull并刪除U中數據.若U為Usparse，其L均為空，則U為Uoutlr并刪除U中數據，否則將其保留.位于數據分區邊界的單元格不為空時，全部保留.

5) 將代表點和擬離群點信息發送給主節點.

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

7) 重復4)中步驟，得候選離群數據集及離群點.

8) 主節點進行全局離群點挖掘，流程圖如圖1所示.

圖1 主節點算法流程圖

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

主節點執行任務的總體分配和調度，分節點通過步驟2)、3)、4)、5)進行數據約簡，并將代表信息發送給主節點為全局離群點挖掘做準備.主節點執行步驟6)、7)、8)、9)對分節點發送的數據做全局離群點挖掘.改進的算法能快速的檢測到稠密區域，通過只計算稀疏區域數據的LOF值，加快了對離群點的挖掘.

2 實驗結果與分析

采用三組實驗來驗證本文算法的有效性.實驗1在數據量遞增時，通過對三種算法離群點挖掘時間的比較來驗證MR_LOF算法對海量數據的處理能力.實驗2伴隨數據處理節點的增加，分析了三種算法的離群點挖掘時間變化趨勢.實驗3中數據維度增加時，通過比較來驗證MR_LOF算法對高維數據的處理是否具有良好的可擴展性.

實驗平臺配置如下：10臺相同配置的PC機(通過局域網連接)，CPUPentiumDual-CoreE6500，內存2G，YLMFOS(Ubuntu) 操作系統，Hadoop0.20，1個主節點master，9個分節點slaves，用裝有Hadoop插件的eclipse進行代碼編輯，編譯jdk1.7.測試數據來自KDDCup1999，共有41個屬性，34個為連續屬性，7個為離散屬性.包括五大類數據，正常連接、dos、u2r、r2l、probe入侵和攻擊.

實驗1實驗節點數和數據維度分別為10臺和40維，同一數據集數據遞增時，進行LOF算法、GDLOF算法和MR_LOF算法離群點挖掘運行時間對比.圖2為離群點挖掘時間隨數據量遞增的變化情況.

圖2 檢測時間隨數據量遞增變化情況

由圖可知，隨著數據量的增加算法的運行時間均增大，但MR_LOF算法的曲線增長速度相對其他算法較緩慢。當數據量急劇增大時，一定程度上能夠降低算法執行的時間復雜度，性能優于LOF算法和基于網格的GDLOF算法.

實驗2數據量相同情況下，MR_LOF算法、LOF算法、GDLOF算法離群點挖掘時間隨節點數的變化情況如圖3所示.

圖3 檢測時間與節點數目間關系

當數據量和數據維度數不變時，節點數越多，離群點挖掘花費的時間越少.考慮實際應用中數據處理終端數目遠大于實驗中節點數，該算法適用于數據密集型計算環境下的離群點挖掘.

實驗3數據量一定時，MR_LOF算法、基于單元格的FORMAUC算法[8]和GDLOF算法離群點挖掘時間隨數據維度的變化情況如圖4所示.

圖4 隨數據維度增加檢測時間變化曲線

所有算法的檢測時間隨著數據維度的增加均呈現增長趨勢.MR_LOF算法類似于模糊查詢的方法在高維數據中具有明顯的優勢，同等條件下檢測時間增長與其他算法相比較緩慢.因此，MR_LOF算法用于挖掘高維數據中的離群點是可行的.

3 結束語

針對數據密集型計算環境下離群點挖掘問題，本文提出網格與基于密度的算法相結合的MR_LOF算法，將單元期望值k鄰近中距離最遠的點作為檢測對象，根據其LOF值與1的相差程度判斷數據稀疏區域.該算法不用計算所有數據的LOF值，只需計算稀疏區域中數據的LOF值.通過篩選稠密區域數據，加快了離群點檢測速度，提高了算法的執行效率.實驗結果分析可知，MR_LOF算法能有效地解決海量、分布、高速變化的數據密集型環境中離群點挖掘問題.

[1]Kouzes R T, Anderson G A, Elbert S T,etal. The Changing Paradigm of Data-Intensive Computing [J]. Computer, 2009,42(1):26-34.

[2]Dean J, Ghemawat S. MapReduce: a flexible data processing tool [J]. Communications of the ACM, 2010, 53(1):72-77.

[3]Breunig M M, Kriegel H P, Raymond T N,etal. LOF: identifying density-based local outliers[J]. ACM SIGMOD Record, 2000, 29(2): 93-104.

[4]Tang J, Chen Z, Fu A,etal. Enhancing Effectiveness of Outlier Detections for Low Density Patterns[J]. Lecture Notes in Computer Science, 2002,2336:535-548.

[5]薛安榮,鞠時光,何偉華,等.局部離群點挖掘算法研究[J].計算機學報,2007,30(8):1 455-1 463.

[6]張凈,孫志揮.GDLOF:基于網格和稠密單元的快速局部離群點探測算法[J].東南大學學報：自然科學版,2005,35(6):863-866.

[7]岳峰,邱保志.基于反向K近鄰的孤立點檢測算法[J].計算機工程與應用,2007,43(7):182-184.

[8]崔貫勛,李梁,王勇，等.快速的基于單元格的離群數據挖掘算法[J].計算機應用,2009,29(12):3 000-3 302.