數(shù)據(jù)密集型計算環(huán)境下離群點(diǎn)挖掘算法設(shè)計與實(shí)現(xiàn)

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

(山東理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院， 山東 淄博 255091)

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

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

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

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

1 算法分析與描述

1.1 LOF算法

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

(1)

(2)

reachdistk(o←o′)=

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

(3)

其中Nk(o)為對象o的k-距離范圍內(nèi)數(shù)據(jù)總數(shù)

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

1.2 MR_LOF算法

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

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

T：網(wǎng)格類型；

P:網(wǎng)格單元中數(shù)據(jù)點(diǎn)數(shù)，設(shè)為單元格密度；

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

Max：數(shù)據(jù)中最大值；

Min：數(shù)據(jù)中最小值.

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

輸入：d維數(shù)據(jù)集D、網(wǎng)格閾值N；

輸出：離群點(diǎn)的集合Outlier；

算法形式化描述如下：

1)MapReduce框架對任務(wù)進(jìn)行統(tǒng)一調(diào)度.

2) U中各維空間獨(dú)立劃分，每一維的劃分由相鄰數(shù)據(jù)點(diǎn)間的分布情況決定.

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

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

5) 將代表點(diǎn)和擬離群點(diǎn)信息發(fā)送給主節(jié)點(diǎn).

6) 主節(jié)點(diǎn)將不同分節(jié)點(diǎn)發(fā)送的代表點(diǎn)劃分到相應(yīng)的U中，實(shí)時更新U的五元組信息，直到所有數(shù)據(jù)全部錄入網(wǎng)格.

7) 重復(fù)4)中步驟，得候選離群數(shù)據(jù)集及離群點(diǎn).

8) 主節(jié)點(diǎn)進(jìn)行全局離群點(diǎn)挖掘，流程圖如圖1所示.

圖1 主節(jié)點(diǎn)算法流程圖

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

主節(jié)點(diǎn)執(zhí)行任務(wù)的總體分配和調(diào)度，分節(jié)點(diǎn)通過步驟2)、3)、4)、5)進(jìn)行數(shù)據(jù)約簡，并將代表信息發(fā)送給主節(jié)點(diǎn)為全局離群點(diǎn)挖掘做準(zhǔn)備.主節(jié)點(diǎn)執(zhí)行步驟6)、7)、8)、9)對分節(jié)點(diǎn)發(fā)送的數(shù)據(jù)做全局離群點(diǎn)挖掘.改進(jìn)的算法能快速的檢測到稠密區(qū)域，通過只計算稀疏區(qū)域數(shù)據(jù)的LOF值，加快了對離群點(diǎn)的挖掘.

2 實(shí)驗(yàn)結(jié)果與分析

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

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

實(shí)驗(yàn)1實(shí)驗(yàn)節(jié)點(diǎn)數(shù)和數(shù)據(jù)維度分別為10臺和40維，同一數(shù)據(jù)集數(shù)據(jù)遞增時，進(jìn)行LOF算法、GDLOF算法和MR_LOF算法離群點(diǎn)挖掘運(yùn)行時間對比.圖2為離群點(diǎn)挖掘時間隨數(shù)據(jù)量遞增的變化情況.

圖2 檢測時間隨數(shù)據(jù)量遞增變化情況

由圖可知，隨著數(shù)據(jù)量的增加算法的運(yùn)行時間均增大，但MR_LOF算法的曲線增長速度相對其他算法較緩慢。當(dāng)數(shù)據(jù)量急劇增大時，一定程度上能夠降低算法執(zhí)行的時間復(fù)雜度，性能優(yōu)于LOF算法和基于網(wǎng)格的GDLOF算法.

實(shí)驗(yàn)2數(shù)據(jù)量相同情況下，MR_LOF算法、LOF算法、GDLOF算法離群點(diǎn)挖掘時間隨節(jié)點(diǎn)數(shù)的變化情況如圖3所示.

圖3 檢測時間與節(jié)點(diǎn)數(shù)目間關(guān)系

當(dāng)數(shù)據(jù)量和數(shù)據(jù)維度數(shù)不變時，節(jié)點(diǎn)數(shù)越多，離群點(diǎn)挖掘花費(fèi)的時間越少.考慮實(shí)際應(yīng)用中數(shù)據(jù)處理終端數(shù)目遠(yuǎn)大于實(shí)驗(yàn)中節(jié)點(diǎn)數(shù)，該算法適用于數(shù)據(jù)密集型計算環(huán)境下的離群點(diǎn)挖掘.

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

圖4 隨數(shù)據(jù)維度增加檢測時間變化曲線

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

3 結(jié)束語

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

[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]薛安榮,鞠時光,何偉華,等.局部離群點(diǎn)挖掘算法研究[J].計算機(jī)學(xué)報,2007,30(8):1 455-1 463.

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

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

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