數(shù)據(jù)密集型計(jì)算環(huán)境下的離群點(diǎn)挖掘算法

陳亞麗+張龍波+張樹

摘要：在數(shù)據(jù)密集型計(jì)算環(huán)境中，數(shù)據(jù)的海量、高維、分布存儲(chǔ)等特點(diǎn)，為數(shù)據(jù)挖掘算法的設(shè)計(jì)與實(shí)現(xiàn)帶來了新的挑戰(zhàn)?；贛apReduce模型提出網(wǎng)格技術(shù)與基于密度的方法相結(jié)合的離群點(diǎn)挖掘算法，該算法分為兩步：Map階段采用網(wǎng)格技術(shù)刪除大量不可能成為離群點(diǎn)的正常數(shù)據(jù)，將代表點(diǎn)信息發(fā)送給主節(jié)點(diǎn);Reduce階段采用基于密度的聚類方法，通過改進(jìn)其核心對(duì)象選取，可以挖掘任意形狀的離群點(diǎn)。實(shí)驗(yàn)結(jié)果表明，在數(shù)據(jù)密集型計(jì)算環(huán)境中，該方法能有效的對(duì)離群點(diǎn)進(jìn)行挖掘。

引言：

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

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

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

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

在MapReduce模型基礎(chǔ)上，利用DBScan算法對(duì)離群點(diǎn)敏感的特點(diǎn)，將網(wǎng)格重心確定為DBScan算法核心對(duì)象，能有效防止由于核心對(duì)象選取不當(dāng)而產(chǎn)生的波動(dòng)現(xiàn)象，并通過設(shè)置閾值判斷集體離群點(diǎn)的存在。

算法分析與描述

在數(shù)據(jù)密集型計(jì)算環(huán)境中，離群點(diǎn)只占整個(gè)數(shù)據(jù)集的一小部分，而且有可能分布在不同的區(qū)域?；贛apReduce模型，各分節(jié)點(diǎn)將不可能成為離群點(diǎn)的數(shù)據(jù)刪除，再對(duì)剩余數(shù)據(jù)在主節(jié)點(diǎn)進(jìn)行全局離群點(diǎn)挖掘。分節(jié)點(diǎn)采用網(wǎng)格方法處理數(shù)據(jù)，將產(chǎn)生的代表信息和擬離群點(diǎn)信息發(fā)送到主節(jié)點(diǎn)。key為網(wǎng)格ID，value為網(wǎng)格五元組信息。網(wǎng)格方法可用來處理任意類型的數(shù)據(jù)，處理時(shí)間與數(shù)據(jù)的數(shù)目和輸入順序無關(guān)。因此，一定程度上可減少檢測(cè)數(shù)據(jù)量，降低網(wǎng)絡(luò)數(shù)據(jù)傳輸量。主節(jié)點(diǎn)將各個(gè)分節(jié)點(diǎn)發(fā)送的代表點(diǎn)信息整合，合并key值相同的網(wǎng)格單元信息，進(jìn)行全局范圍的數(shù)據(jù)篩選。將網(wǎng)格重心初始化為MR_DBScan核心對(duì)象，依次由高密度到低密度從未訪問數(shù)據(jù)集中選取，避免了因核心對(duì)象選取不當(dāng)而引起波動(dòng)現(xiàn)象的發(fā)生。利用網(wǎng)格刪除大量正常數(shù)據(jù)，降低了數(shù)據(jù)集聚類數(shù)，減小了存儲(chǔ)核心對(duì)象信息所需的內(nèi)存容量，提高了算法的執(zhí)行效率。

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

MR_DBScan算法概述：

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

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

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

1）MapReduce框架將輸入數(shù)據(jù)分配給9臺(tái)PC機(jī)（實(shí)驗(yàn)中的分節(jié)點(diǎn)）。

2）網(wǎng)格單元U中各維空間劃分相對(duì)獨(dú)立，每一維劃分的間隔不同。每一維的劃分以各相鄰數(shù)據(jù)點(diǎn)間的分布情況作為依據(jù)。

3）隨機(jī)選擇一個(gè)未經(jīng)訪問的點(diǎn)，根據(jù)預(yù)先設(shè)定的維度間隔距離值計(jì)算該點(diǎn)所屬的網(wǎng)格單元。輸入數(shù)據(jù)的同時(shí)，計(jì)算U的五元組信息。

4）若U為稠密單元，且其L均為稠密單元，保存U和L的五元組信息，L放入C（候選集合）中。對(duì)C中網(wǎng)格的L進(jìn)行遍歷查詢，直到所有L均為空，將U及所有L中數(shù)據(jù)全部刪除;L均為空單元，標(biāo)記U和空單元并刪除U中數(shù)據(jù)。若U為稀疏單元，其L均為空，則U標(biāo)記為離群?jiǎn)卧h除U中數(shù)據(jù)，否則將其保留。位于數(shù)據(jù)分區(qū)邊界的單元格不為空時(shí)，全部保留。

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

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

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

8）在主節(jié)點(diǎn)進(jìn)行全局離群點(diǎn)挖掘，偽代碼為：

輸入：

.D：7）中生成的候選離群數(shù)據(jù)集。

.ε：半徑參數(shù)。

.MinPts：領(lǐng)域密度閾值。

.Num：判定密度閾值。

輸出：離群點(diǎn)

方法：

標(biāo)記所有重心點(diǎn)為unvisited;

do

選擇一個(gè)單元數(shù)據(jù)點(diǎn)數(shù)最多的unvisited重心點(diǎn)p;

標(biāo)記p為visited;

if p的ε-領(lǐng)域至少有MinPts個(gè)對(duì)象

創(chuàng)建一個(gè)新簇C，將p添加到C;

令M為p的ε-領(lǐng)域中的對(duì)象集合;

for M中每個(gè)點(diǎn)p

if p是unvisited

標(biāo)記p為visited;

if p的ε-領(lǐng)域至少有MinPts個(gè)點(diǎn)，將這些點(diǎn)添加到M;

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

end for

if C中數(shù)據(jù)點(diǎn)數(shù)小于Num

標(biāo)記C為集體離群點(diǎn);（判斷是否有集體離群點(diǎn)存在）

輸出C;

else標(biāo)記p為離群點(diǎn);

輸出p;

until沒有標(biāo)記為unvisited的對(duì)象;

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

主節(jié)點(diǎn)執(zhí)行任務(wù)的總體分配和調(diào)度，分節(jié)點(diǎn)通過步驟2）、3）、4）、5）將大量非離群數(shù)據(jù)刪除，并將代表信息發(fā)送給主節(jié)點(diǎn)做進(jìn)一步的全局離群點(diǎn)挖掘。主節(jié)點(diǎn)執(zhí)行步驟6）、7）、8）、9）對(duì)分節(jié)點(diǎn)發(fā)送的數(shù)據(jù)做全局離群點(diǎn)挖掘。改進(jìn)的核心對(duì)象選取算法能很快檢測(cè)出簇，進(jìn)而加快了對(duì)離群點(diǎn)的挖掘。

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

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

本實(shí)驗(yàn)在ε=3，MinPts=4時(shí)，檢測(cè)到離群點(diǎn)數(shù)為40，較真實(shí)離群點(diǎn)數(shù)多2，能檢測(cè)出所有離群點(diǎn)數(shù)據(jù)，誤檢率為5%。分節(jié)點(diǎn)算法時(shí)間復(fù)雜度為O（N），N為網(wǎng)格單元數(shù)。主節(jié)點(diǎn)時(shí)間復(fù)雜度為O（N/P）+O（nlogn），P為分節(jié)點(diǎn)數(shù)，n為數(shù)據(jù)量。因?yàn)镺（N/P）<<O（nlogn），所以算法時(shí)間復(fù)雜度為O（nlogn）（n遠(yuǎn)小于原始數(shù)據(jù)數(shù)目）

結(jié)論

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