李子茂　駱　慶　劉　晶

（中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院　武漢　430074）

1　引言

離群點(diǎn)檢測是數(shù)據(jù)管理中的熱點(diǎn)問題之一［1］，在許多領(lǐng)域有著廣泛的應(yīng)用，如信用卡詐騙、網(wǎng)絡(luò)入侵檢測等。在早期文獻(xiàn)［2］中，離群點(diǎn)被描述為：在一個(gè)數(shù)據(jù)集中，若某個(gè)數(shù)據(jù)點(diǎn)與其他數(shù)據(jù)點(diǎn)的差距非常大以至于被懷疑是通過其他機(jī)制生成的，那么該數(shù)據(jù)點(diǎn)就被認(rèn)為是離群點(diǎn)。

目前，絕大多數(shù)離群點(diǎn)算法都是針對集中式環(huán)境設(shè)計(jì)的。隨著物聯(lián)網(wǎng)、云計(jì)算和社交網(wǎng)絡(luò)等技術(shù)的興起，數(shù)據(jù)的種類和規(guī)模正在不斷地增長和積累，大數(shù)據(jù)時(shí)代到來。集中式算法處理效率有限，在多數(shù)情況下不能滿足用戶的需求。因此，一些學(xué)者開始使用分布式算法并行計(jì)算離群點(diǎn)，以提高計(jì)算效率。

本文提出了一種基于方差的數(shù)據(jù)劃分方法，數(shù)據(jù)劃分過程中建立KD樹，通過KD樹計(jì)算劃分后的數(shù)據(jù)塊的K近鄰將劃分后的數(shù)據(jù)塊均勻地分配到各個(gè)計(jì)算節(jié)點(diǎn)，同時(shí)能夠很好地保證同一計(jì)算點(diǎn)上數(shù)據(jù)的近鄰性?；谠搫澐炙惴?，提出了一種基于R樹的分布式離群點(diǎn)檢測算法-VDOD。最后通過使用真實(shí)數(shù)據(jù)集和人工合成數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，驗(yàn)證了本文提出的基于方差的數(shù)據(jù)劃分方法和VDOD算法的有效性。

2　相關(guān)工作

離群點(diǎn)檢測的研究最早始于統(tǒng)計(jì)領(lǐng)域［1］，基于統(tǒng)計(jì)的離群點(diǎn)檢測技術(shù)假定被檢數(shù)據(jù)符合某個(gè)概率分布模型，凡不符合該分布模型的數(shù)據(jù)點(diǎn)被視為離群點(diǎn)。自那以后，從事數(shù)理統(tǒng)計(jì)、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域研究的學(xué)者們分別從不同的角度提出了多種離群點(diǎn)檢測技術(shù)和方法［2］。概括起來，主要的離群點(diǎn)檢測技術(shù)有：基于統(tǒng)計(jì)的方法、基于聚類的方法、基于分類的方法、基于距離［3］、基于密度［4］和基于信息熵的方法等，本文主要針對基于距離的離群點(diǎn)檢測方法。

基于距離的離群點(diǎn)最早由Knorr等［5］提出，是一種目前被廣泛認(rèn)可的定義標(biāo)準(zhǔn)。Knorr提出了三個(gè)檢測 DB（k，r）離群點(diǎn)的算法［6］，分別是：基于索引的（Index-based）算法、嵌套循環(huán)（nested loop）算法和基于網(wǎng)格（cell-based）的算法。另外，Angiulli等［7］提出了一個(gè)基于k近鄰（KNN）度量離群程度的方法。Wu等［8］提出了一種基于抽樣的方法來考察被測對象與其近鄰的關(guān)系，即對每個(gè)對象，僅考察對象與一個(gè)較小的隨機(jī)抽樣的樣本集之間的關(guān)系，避免了對整個(gè)數(shù)據(jù)集進(jìn)行距離計(jì)算。還出現(xiàn)了針對特定應(yīng)用背景的離群點(diǎn)檢測算法，文獻(xiàn)［9］提出了不確定數(shù)據(jù)的基于距離的離群點(diǎn)檢測算法。

在分布式環(huán)境中離群點(diǎn)檢測的相關(guān)研究主要有文獻(xiàn)［10～13］。其中文獻(xiàn)［10］所研究的問題與本文相同，但提出的PENL算法采用的是基于數(shù)量的數(shù)據(jù)劃分方法，不考慮數(shù)據(jù)分布情況，對于數(shù)據(jù)集中任意一個(gè)數(shù)據(jù)點(diǎn) p，在最壞情況下，必須與其他所有數(shù)據(jù)點(diǎn)計(jì)算距離，才能得到最終結(jié)果。因此當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，PENL算法需要大量的網(wǎng)絡(luò)開銷，計(jì)算效率不高。與本文研究問題最為接近的工作有文獻(xiàn)［11］，對PENL算法進(jìn)行改進(jìn)提出了BOD算法，采用基于空間的數(shù)據(jù)劃分。該算法中同一計(jì)算節(jié)點(diǎn)的數(shù)據(jù)有很好的近鄰性，網(wǎng)絡(luò)開銷也大大降低，但是該算法分配到各個(gè)計(jì)算節(jié)點(diǎn)后數(shù)據(jù)量不均衡，并行計(jì)算效率不佳。另外 He Qing［12～13］等基于MapReduce計(jì)算離群點(diǎn)和構(gòu)建并行KD樹檢測離群點(diǎn)。

3　問題描述

本文主要研究在分布式環(huán)境下，如何并行地計(jì)算出數(shù)據(jù)集內(nèi)所有的基于距離的離群點(diǎn)。下面形式化地給出基于距離的離群點(diǎn)的定義和介紹分布式框架。表1列出了本文使用的主要符號(hào)。

3.1　基于距離的離群點(diǎn)檢測

在以下的討論中，設(shè)數(shù)據(jù)集為 X={x1，x2，…，xi，…，xP}，P 為數(shù)據(jù)集的大??；xi∈X ，為數(shù)據(jù)集X 中的數(shù)據(jù)點(diǎn)，記為 (xi1，xi2，…，xij，…，xid)。每個(gè)數(shù)據(jù)點(diǎn)是一個(gè)類型為 A=(A1，A2，…，Ad)的d元組，其中d為數(shù)據(jù)集維度，Aj為屬性，d(xi，xj)為度量數(shù)據(jù)對象xi，xj∈X的距離函數(shù)。其中

定義1r鄰域。對任意實(shí)數(shù)r≥0，數(shù)據(jù)對象xi的 r-鄰域 Q(xi，r)，定義為

定義2DB(k，r)離群點(diǎn)。給定一個(gè)正整數(shù)k，如果數(shù)據(jù)點(diǎn) x的r鄰域的基數(shù)小于k，則 x是DB(k，r)離群點(diǎn)。

3.2　分布式框架

分布式環(huán)境如圖1所示，集群包含固定個(gè)數(shù)的計(jì)算節(jié)點(diǎn) N={n1，n2，…，n|N|}（|N|為節(jié)點(diǎn)個(gè)數(shù)），每個(gè)節(jié)點(diǎn)都存儲(chǔ)數(shù)據(jù)集X的一個(gè)子集，并包含一個(gè)查詢處理引擎，用于接收查詢參數(shù)和輸出結(jié)果，節(jié)點(diǎn)之間可以相互通信。

表1　符號(hào)表

圖1　分布式框架

4　數(shù)據(jù)劃分

4.1　塊的切分

在介紹劃分方法之前，首先介紹下該方法的兩個(gè)主要輸入?yún)?shù)：

1）塊（block）：即所需要切分的空間區(qū)域。對于d維空間內(nèi)的一個(gè)塊b，可以使用塊的下界點(diǎn)b.min、上界點(diǎn)b.max表示，記b=［b.min，b.max］。其中對于任意屬于塊b的數(shù)據(jù)點(diǎn)滿足?i∈[0，d-1]，b.Min[i]≤ p[i]≤b.max[i]。

2）切分維度。取值范圍為［0，d-1］整形變量，用于標(biāo)識(shí)將被切分的維度。

總體上切分算法是一個(gè)遞歸調(diào)用的過程。對于一個(gè)d維數(shù)據(jù)塊b，需要h次劃分將其劃分為2h個(gè)數(shù)據(jù)量相等的子塊，h滿足2h≥N2≥2h-1。劃分?jǐn)?shù)據(jù)塊時(shí)從方差最大的第i維的中值點(diǎn)Node-data處進(jìn)行切分，分成2個(gè)數(shù)據(jù)量相等的子塊bleft，bright。其中bleft的下界點(diǎn)bleft.min與b的下界點(diǎn)b.min相同，bleft的上界點(diǎn)的第i維值 bleft.max［i］=Node-data［i］，? j∈［0，d-1］且 j≠ I，bleft.max［j］=b.max［j］。相應(yīng)的 bright.max=b.max，bright.min［i］=Node-data［i］，?j∈［0，d-1］且 j≠ I，bright.min［j］=b.min［j］。算法1描述了切分的具體過程。

算法1 spilt（block b，dimension D）

1）記切分次數(shù)為h，h初始為0；

2）WHILE（2h＜N2）DO；

3）FOR所有子塊；

4）計(jì)算數(shù)據(jù)集在0到d-1維上各自的方差，取最大方差維作為spilt；

5）數(shù)據(jù)點(diǎn)集在第spilt維進(jìn)行排序，位于中間的那個(gè)數(shù)據(jù)點(diǎn)被選為Node-data；

6）沿著Node-data進(jìn)行垂直spilt維的切割，計(jì)算切割后左右子塊的b.min，b.max；

7）END FOR；

8）h=h+1；

9）ENDWHILE。

4.2　塊的分配

當(dāng)切分結(jié)束后，最終得到的塊的集合表示為B={b1，b2，…，bn}，顯然塊的數(shù)目大于N，需要根據(jù)劃分時(shí)建立的KD樹［14］來分配數(shù)據(jù)塊。通過計(jì)算各個(gè)數(shù)據(jù)塊的幾何中心的距離，可以得出數(shù)據(jù)塊的K近鄰數(shù)據(jù)塊。每次分配數(shù)據(jù)塊將數(shù)據(jù)塊按照標(biāo)記進(jìn)行排序，將第一個(gè)數(shù)據(jù)塊和它的p近鄰或p-1近鄰分配到同一計(jì)算節(jié)點(diǎn)。重復(fù)該過程，直至所有數(shù)據(jù)塊被分配完。

5　VDOD算法

5.1　局部離群點(diǎn)計(jì)算

算法首先通過R樹［15］結(jié)構(gòu)對數(shù)據(jù)點(diǎn)進(jìn)行批量過濾，在本文的計(jì)算中，限定每個(gè)R樹葉子節(jié)點(diǎn)包含的數(shù)據(jù)點(diǎn)的個(gè)數(shù)的范圍為［k，3k］。具體過濾方法如下：

方法一：如果點(diǎn) x到MBR m1的最小距離Min_dist(m1，x)＞r，則 m1中不存在 x 的近鄰點(diǎn)。

方法二：如果已經(jīng)計(jì)算出數(shù)據(jù)點(diǎn)的近鄰點(diǎn)的個(gè)數(shù)超過k個(gè)，那么繼續(xù)查找它的近鄰是沒有意義的，因?yàn)樵摂?shù)據(jù)點(diǎn)已經(jīng)可以判定為非離群點(diǎn)。

具體過程如算法2所示。

算法2VDOD局部算法

輸入：數(shù)據(jù)集X，考察的近鄰個(gè)數(shù)k，距離閾值r

輸出：所有的局部離群點(diǎn)集S，部分全局離群點(diǎn)O

1）初始化堆H為空；

2）nn（p，r）→ 計(jì)算 p以r為半徑的鄰居數(shù)目；

3）FOR X中的每一個(gè)數(shù)據(jù)點(diǎn)xi；

4）R樹根節(jié)點(diǎn)的孩子節(jié)點(diǎn)加入到H中；

5）WHILE（H不為空）DO；

6）取H首元素h；

7）IF（Min_dist(xi，h)＞r）DO；

8）h的孩子節(jié)點(diǎn)加入到H中；

9）END IF；

10）ELSE；

11）計(jì)算h中 xi的近鄰點(diǎn)數(shù)目nn（xi，r）；

12）IF（nn（ xi，r）≥ k）DO；

13）停止計(jì)算離群點(diǎn)，并將xi從X中移除；

14）END IF；

15）ELSE；

16）IF（?j∈［0，d-1］，xi［j］-b.min［j］≥ r且b.max［j］-xi［j］ ≥ r）DO；

17）將 xi移除到O中；

18）END IF；

19）END ELSE；

20）END ELSE；

21）ENDWHILE；

22）END FOR；

23）X中剩余的數(shù)據(jù)點(diǎn)為局部離群點(diǎn)集S，輸出S、O。

5.2　全局離群點(diǎn)計(jì)算

如5.1節(jié)所述，如果節(jié)點(diǎn)n中存在局部離群點(diǎn)，則節(jié)點(diǎn)n需要與其相鄰的節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)通信。KD樹上的兩個(gè)數(shù)據(jù)塊，若其中一個(gè)數(shù)據(jù)塊的b.min或b.max在另一數(shù)據(jù)塊的空間范圍內(nèi)，則這兩個(gè)數(shù)據(jù)塊一定相鄰。對于節(jié)點(diǎn)n的任意塊b可求得其它節(jié)點(diǎn)上與其相鄰的塊的集合neig（b）。算法3展示了全局離群點(diǎn)計(jì)算的具體過程。

算法3 outlier_judgement（）。

輸入：塊b中的局部離群點(diǎn)集S，其它節(jié)點(diǎn)上與b相鄰的塊集合neig（b）

輸出：S中的全局離群點(diǎn)

1）FOR集合neig（b）中的每一個(gè)塊 b′DO；2）初始化集合send_（b→b′）；

3）FOR S中的每一個(gè)數(shù)據(jù)點(diǎn)p DO；

4）IFmin_dist（p，b′）≤r THEN；

5） send_（b→b′）→ p；

6） END IF；

7）END FOR；

8）將send_（b→ b′）發(fā)送到 b′所在的節(jié)點(diǎn)；

9）END FOR。

VOOD算法復(fù)雜度分析：算法2的復(fù)雜度下界為Ω(d*|X|*log(|X|))，最差情況為O(d*|X|*|X|)。在算法3中，記局部離群點(diǎn)的個(gè)數(shù)為|S|，每個(gè)局部離群點(diǎn)都需要在其它塊進(jìn)行k次查找，則算法4的復(fù)雜度下界為Ω(k * d*|S|*log(|S|) ) ，最差情況為O(k*d*|S|*|S|)。

6　實(shí)驗(yàn)分析

6.1　真實(shí)數(shù)據(jù)集

本小節(jié)主要使用真實(shí)數(shù)據(jù)集來測試VDOD算法性能。試驗(yàn)中使用的集群包括8個(gè)計(jì)算節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的配置為Intel Core i5 2400 3.10GHz CPU，8GB內(nèi)存，500GB硬盤，操作系統(tǒng)為Red Hat Linux 6.1。算法采用JAVA語言編寫，JDK版本為1.8.3，數(shù)據(jù)集為UCI提供的home sensors for home activity monitoring數(shù)據(jù)集（鏈接地址為http：//archive.ics.uci.edu/Ml/datasets），共包括919438條真實(shí)數(shù)據(jù)，每條數(shù)據(jù)包括5維可度量屬性。實(shí)驗(yàn)中的對比算法為BOD算法，主要的衡量標(biāo)準(zhǔn)為查詢處理時(shí)間和通信量（以網(wǎng)絡(luò)間傳輸?shù)臄?shù)據(jù)點(diǎn)個(gè)數(shù)來度量）。表2描述了相關(guān)的實(shí)驗(yàn)結(jié)果。

表2　實(shí)驗(yàn)結(jié)果（真實(shí)數(shù)據(jù)）

如表2所示，本文提出的VDOD算法和BOD算法相比，檢測離群點(diǎn)的處理時(shí)間和通信量都明顯減少。另一方面，通過對表2中1～4行實(shí)驗(yàn)結(jié)果的比較，容易發(fā)現(xiàn)：隨著查詢半徑r的增大，數(shù)據(jù)集中的離群點(diǎn)表少，BOD和VDOD算法的處理時(shí)間和通信量都隨之減少；當(dāng)查詢閾值k增大時(shí)，離群點(diǎn)變多，導(dǎo)致BOD算法和VDOD算法的處理時(shí)間和通信量都增加。

6.2　人工數(shù)據(jù)集

由于真實(shí)數(shù)據(jù)集規(guī)模有限，且無法變化數(shù)據(jù)維度等參數(shù)，因此本小節(jié)使用人工合成數(shù)據(jù)進(jìn)一步地對算法進(jìn)行測試。合成數(shù)據(jù)集為聚簇分布數(shù)據(jù)，各維的取值范圍為0～10000。具體生成方法如下：對于包含a個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集，隨機(jī)生成a/1000聚簇點(diǎn)，每個(gè)聚簇內(nèi)平均包含1000個(gè)數(shù)據(jù)點(diǎn)。在每個(gè)聚簇內(nèi)，數(shù)據(jù)點(diǎn)以聚簇點(diǎn)為中心呈高斯分布［16］。實(shí)驗(yàn)相關(guān)變量的默認(rèn)值和變化范圍如表3所示。

表3　參數(shù)設(shè)置

本小節(jié)主要在分布式環(huán)境下對比了VDOD算法與BOD算法的性能。圖2描述了集群規(guī)模對算法性能的影響。可以看出隨著集群規(guī)模的擴(kuò)大，集群的計(jì)算能力提高，VDOD和BOD算法的處理時(shí)間都隨之減少，說明這兩種算法都有很好的性能加速比。另外在圖3中，節(jié)點(diǎn)個(gè)數(shù)的增加也導(dǎo)致了局部離群點(diǎn)的增多。VDOD算法的通信量輕微增加，而對于BOD算法，更多的節(jié)點(diǎn)意味著更多的數(shù)據(jù)劃分，因此網(wǎng)絡(luò)傳輸量也隨之增加。

圖2　集群規(guī)模與處理時(shí)間

圖3　集群規(guī)模與通信量

圖4、5描述了數(shù)據(jù)量對算法性能的影響。隨著數(shù)據(jù)量的增加，VDOD和BOD算法都需要消耗更多的系統(tǒng)時(shí)間，也會(huì)產(chǎn)生更多的網(wǎng)絡(luò)開銷。但通過對比容易發(fā)現(xiàn)，VDOD算法的處理時(shí)間和網(wǎng)絡(luò)開銷明顯低于BOD算法，而且增長速度緩慢。

圖4　數(shù)據(jù)量與時(shí)間

圖5　數(shù)據(jù)量與通信量

7　結(jié)語

本文研究了分布式環(huán)境下基于距離的離群點(diǎn)檢測問題。首先，提出了一種新型的基于方差的數(shù)據(jù)劃分方法，劃分過程中建立KD樹。該方法對維度不敏感，減少了對數(shù)據(jù)近鄰性的破壞，同時(shí)數(shù)據(jù)基本上實(shí)現(xiàn)了均勻分配，提高了并行計(jì)算的效率。基于劃分方法，提出了VDOD離群點(diǎn)計(jì)算算法，該算法包括兩個(gè)步驟：在每個(gè)計(jì)算節(jié)點(diǎn)本地，基于R樹索引進(jìn)行批量過濾，剪枝掉了大部分的不必要計(jì)算，最終快速地計(jì)算出局部離群點(diǎn)；進(jìn)一步地，利用KD樹快速確定需要通信的相鄰塊，并計(jì)算輸出最終結(jié)果。最后通過大量的實(shí)驗(yàn)說明了本文提出的VDOD算法的正確性和有效性。

［1］XUEAnrong，JU Shiguang，HEWeihua，etal.Study on algorithms for local outlier detections［J］.Chiness Journal of Computer，2007，20（8）：1455-1463.

［2］ Hawkins D-M，Identification of Outlier［M］.Londin：Chapman and Hall，1980：1-28.

［3］楊茂林.離群檢測算法研究［D］.武漢：華中科技大學(xué)，2012：1-119.YANG Maolin.Research on Algorithms for Outlier Detection［D］.Wuhan：Huazhong University of Science and Technology，2012：1-119.

［4］Lozano E，Acufia E.Parallel.algorithms for distancebased and density-based outlier［C］//Proceedings of the 15th IEEE international Conference on DataMining.Houston，USA，2005：729-732.

［5］Knorr E-M，Ng R-T.Algorithms for mining distancebased outlier in large datasets［C］//Proceeding of 24th Internatioanal Conference on Very Large Data Bases.New York，USA，1998：392-403.

［6］Knorr E-M，Ng R-T，Tucakov V.Distance-based outliers：algorithms and applications［J］.The VLDB Journal，2000，8（3-4）：237-253.

［7］Angiulli F，Basta S，Lodi S，etal.Distributed strategies for mining outliers in large data sets［J］.IEEE Transactions on Knowledge and Data Engineering，2013，25，25（7）：1520-1532.

［8］Bay S-D，Schwabacher M.Mining distance-based outlier in near linear time with randomization and a simple pruning rule［C］//Proceeding of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington，USA，2003：29-38.

［9］Cao K Y，Wang G R，Han D H，et al.Continuous outlier monitoring on uncertain data streams［J］.Journal of Computer Science and Technology，2014，29（3）：436-448.

［10］Hung E，Cheung D-W.Parallel mining of outliers in large database.Distributed and Parallel DataBase［J］.Department of Computer Science and Information Systems，2002，12（1）：5-26.

［11］王習(xí)特，申德榮，白梅，等.BOD：一種高效的分布式離群點(diǎn)檢測算法［J］.計(jì)算機(jī)學(xué)報(bào)，2016，39（1）：36-51.WANG Xite，SHEN Derong，BAIMei，etal.BOD：An Efficient Algorithm for Distributed Outlier Detection［J］.Chinese JournalofComputer，2016，39（1）：36-51.

［12］Koufakou A，Secretan Secretan J，Reeder L，et al.Fast parallel outlier detection for categorical datasets using MapReduce［C］//Proceeding of the IEEE International Joint Conference on Neural Networks.Hong Kong，China，2008：3298-3304.

［13］He Qing，Ma Yun-Long，Wang Qun，et al.Parallel outlier detection using KD-tree based on MapReduce［C］//Proceedings of the 3rd International Conference on Cloud Computing Technology and science.Athens，Greece，2011：75-80.

［14］范文山，王斌.啟發(fā)式探查最佳分割平面的快速KD-Tree構(gòu)建方法［J］.計(jì)算機(jī)學(xué)報(bào)，2009，32（2）：185-192.FAN Wenshan，WANG Bin，A Fast KD-Tree Construction Method by Probing the Optimal Splitting Plane Heuristically［J］.Chinese Journal of Computer，2009，32（2）：185-192.

［15］胡昱璞，牛保寧.動(dòng)態(tài)確定K值聚類算法的R-樹空間索引構(gòu)建［J］.計(jì)算機(jī)科學(xué)與探索，2016，10（2）：173-181.HU Yupu，NIU Baoning.R-tree Spatial Index Construction Based on Dynamical K-value Clustering Algorithm［J］.Journalof Frontiers of Computer Scicence and Technology，2016，10（2）：173-181.

［16］WANG Xite，SHEN Derong，NIE Tiezheng，etal.An Efficient Algorithmfor Distributed Outlier Detection in Large Multi-Dimensional Datasets［J］.Journal of Computer Science and Technology，2015，30（6）：1233-1248.