李 肖

（暨南大學(xué)，廣州 510632）

1 引言

高維孤立點(diǎn)檢測(cè)描述為，在d維空間中給定一個(gè)N個(gè)數(shù)據(jù)點(diǎn)或?qū)ο蟮募?，及預(yù)期的孤立點(diǎn)的數(shù)目n，發(fā)現(xiàn)與剩余的數(shù)據(jù)相比顯著相異的、異常的或不一致的頭n個(gè)對(duì)象[1]。本文采用R樹實(shí)現(xiàn)算法，R樹是一個(gè)高度平衡樹，它是B樹在k維上的自然擴(kuò)展，可以直接對(duì)空間對(duì)象的MBR進(jìn)行索引。結(jié)果數(shù)據(jù)通過(guò)多維可視化方法表示，包括平行坐標(biāo)表示法和圓形坐標(biāo)表示法。

高維孤立點(diǎn)檢測(cè)可應(yīng)用于各行業(yè)領(lǐng)域，例如新浪微博等互聯(lián)網(wǎng)傳播平臺(tái)。新浪微博具有強(qiáng)弱關(guān)系同時(shí)存在于一個(gè)平臺(tái)屬性特征，不同類別事件在新浪微博平臺(tái)中傳播的信息流和時(shí)間線也有差異，可以根據(jù)不同類別熱門微博的轉(zhuǎn)發(fā)深度和轉(zhuǎn)發(fā)寬度，構(gòu)建出不同類別熱門的傳播模式結(jié)構(gòu)，進(jìn)而發(fā)現(xiàn)用戶的異常行為，監(jiān)控明星認(rèn)證用戶的熱度[2]。

2 基于距離的孤立點(diǎn)檢測(cè)算法概述

為了更精確描述孤立點(diǎn)，引入了就舉例的離群點(diǎn)的概念。如果數(shù)據(jù)集合D中對(duì)象至少有pct部分與對(duì)象o的距離大于dmin，則稱對(duì)象o是以pct和dmin為參數(shù)的基于距離的離群點(diǎn)，即DB（pct，dmin）離群點(diǎn)。即可以將基于距離的離群點(diǎn)看作是沒(méi)有“足夠多”近鄰的對(duì)象，其中近鄰基于到給定對(duì)象的距離定義[3]。

三種基于距離的離群點(diǎn)的算法概述如下：

基于索引的算法：采用多維索引結(jié)構(gòu)（如R樹或k-d樹）搜索每個(gè)對(duì)象o在半徑dmin范圍內(nèi)的近鄰。設(shè)M是一個(gè)離群點(diǎn)的dmin鄰域內(nèi)的最大對(duì)象數(shù)目。因此，一但找到對(duì)象o的M+1個(gè)近鄰，o就不是離群點(diǎn)。這個(gè)算法在最壞情況下的復(fù)雜度為O（kn2），其中n是數(shù)據(jù)集中對(duì)象的數(shù)目，k是維數(shù)。當(dāng)k增加時(shí)，基于索引的算法具有良好的可伸縮性。然而，復(fù)雜度評(píng)估只考慮了搜索時(shí)間，即使建造索引的任務(wù)本身就是計(jì)算密集的。

嵌套-循環(huán)算法：嵌套-循環(huán)算法與基于索引的算法在最壞情況下具有相同的計(jì)算復(fù)雜度，但它避免了索引結(jié)構(gòu)的構(gòu)建，并試圖最小化I/O的次數(shù)。他把內(nèi)存的緩沖空間分為兩半，把數(shù)據(jù)集合分為了若干邏輯塊。通過(guò)精心選擇邏輯塊裝入每個(gè)緩沖區(qū)域的順序，能夠改善I/O效率。

基于單元的算法：為了避免O（n2）的計(jì)算復(fù)雜度，為駐留內(nèi)存的數(shù)據(jù)集開(kāi)發(fā)了基于單元的算法。它的復(fù)雜度使O（ck+n），其中c是依賴于單元數(shù)目的常數(shù)，k是維數(shù)。該算法逐個(gè)單元地，而不是逐個(gè)對(duì)象地計(jì)算離群點(diǎn)。對(duì)于一個(gè)給定的單元，它累計(jì)三個(gè)計(jì)數(shù)——單元中對(duì)象的樹木，單元和第一層中對(duì)象的數(shù)目，單元和兩個(gè)層中的對(duì)象的數(shù)目。該算法的一個(gè)變形是關(guān)于n線性的，并且確保對(duì)數(shù)據(jù)集的掃描不超過(guò)三遍。他可以用于大型駐留磁盤的數(shù)據(jù)集，但對(duì)于高維數(shù)據(jù)不能很好地伸縮。

上述三種算法比較，見(jiàn)表1。

表1 孤立點(diǎn)挖掘方法比較

一般適用于較低維。

對(duì)高維數(shù)據(jù)進(jìn)行孤立點(diǎn)檢測(cè)時(shí)會(huì)遇到兩方面的問(wèn)題：算法效率的下降和基于距離的孤立點(diǎn)意義的失效。為解決上述問(wèn)題，本文研究了嵌入循環(huán)算法，以及基于R樹的高維孤立點(diǎn)檢測(cè)算法，給出其分析和實(shí)現(xiàn)。對(duì)兩種算法從實(shí)際結(jié)果上進(jìn)行比對(duì)。比對(duì)結(jié)果證明本文提出的基于R樹索引的孤立點(diǎn)檢測(cè)算法能在高維條件下有效地檢測(cè)孤立點(diǎn)，并且有較好的運(yùn)行效率。

3 嵌入循環(huán)的高維孤立點(diǎn)檢測(cè)算法

3.1 相關(guān)概念

高維數(shù)據(jù)嵌入循環(huán)孤立點(diǎn)檢測(cè)算法在文獻(xiàn)中給出了詳細(xì)介紹，現(xiàn)對(duì)其中內(nèi)容進(jìn)行說(shuō)明。

定義1 對(duì)任意點(diǎn)p，任意點(diǎn)q，p與q之間的歐幾里得距離記作 dist（p，q）。

定義2 對(duì)任意的正整數(shù)k和數(shù)據(jù)集D，計(jì)算點(diǎn)p與所有點(diǎn)之間的距離，并選取前k個(gè)最近的點(diǎn)作為它的k近鄰，點(diǎn)p到它的k近鄰的最大距離記作Dk（p）。

定義3 對(duì)數(shù)據(jù)集D，給定參數(shù)N為D中數(shù)據(jù)總數(shù)，參數(shù)k為數(shù)據(jù)的近鄰個(gè)數(shù)，參數(shù)n為孤立點(diǎn)個(gè)數(shù)，若僅存在少于n個(gè)其他點(diǎn)p' 且Dk（p'）> Dk（p），則一個(gè)點(diǎn)p是Dk的孤立點(diǎn)。

3.2 算法描述

本算法采用嵌入循環(huán)算法思想。計(jì)算孤立點(diǎn)的嵌入式算法對(duì)每個(gè)輸入點(diǎn)p，計(jì)算出它與其k近鄰的最大距離Dk（p），然后再用Dk（p）的值選出前n個(gè)點(diǎn)。為了計(jì)算Dk（p），算法對(duì)每個(gè)點(diǎn)p都需掃描一遍數(shù)據(jù)集。為了選出前n個(gè)點(diǎn)作為孤立點(diǎn)，算法需對(duì)所有Dk（p）的值進(jìn)行降序排列。

輸入：

images/BZ_127_188_344_1188_565.png

輸出：從數(shù)據(jù)集選出的前n個(gè)具有最大Dk的點(diǎn)。

算法步驟：

（1） 計(jì)算點(diǎn) p 的 Dk。

（2） 對(duì) Dk 排序。

3.3 算法分析

嵌入式循環(huán)算法，每次遍歷處理一個(gè)點(diǎn)，需遍歷數(shù)據(jù)集 N次，故算法對(duì)距離計(jì)算的復(fù)雜性為O（N2）。由于每一個(gè)點(diǎn)需要O（k）的空間存儲(chǔ)它的k個(gè)最近鄰的距離，在這種情況下每次一個(gè)點(diǎn)q要訪問(wèn)一次內(nèi)存，對(duì)于每一個(gè)p查看是否q比p的當(dāng)前kth個(gè)鄰居更近。于是，數(shù)據(jù)集需要被掃描N次。

3.4 算法實(shí)現(xiàn)

3.5 算法實(shí)現(xiàn)小結(jié)

嵌入式循環(huán)算法實(shí)現(xiàn)的關(guān)鍵在于運(yùn)用了一個(gè)大根堆和一個(gè)小根堆，均用STL中的優(yōu)先隊(duì)列實(shí)現(xiàn)，大根堆是priority_queue＜TYPE> dist，小根堆是 priority_queue＜node> Dk，Dist與Dk的具體功能見(jiàn)表2。

表2 Dist與Dk功能表

使用堆的原因：從算法本身的功能看，計(jì)算Dk并不需要把p與它的k近鄰的距離全部排序，只要得到其中最大的距離，該值即為Dk。而求出的孤立點(diǎn)也不用嚴(yán)格按照從大到小的情況輸出，只要基本有序就可以了。從實(shí)現(xiàn)的角度看，優(yōu)先隊(duì)列本質(zhì)是靜態(tài)的堆，由于對(duì)孤立點(diǎn)的記錄只有ID號(hào)和距離，所以靜態(tài)數(shù)組就可以滿足需求，不用花費(fèi)額外的CPU去建立結(jié)點(diǎn)，形成鏈?zhǔn)蕉选?/p>

4 基于R樹的高維孤立點(diǎn)檢測(cè)算法

4.1 相關(guān)概念

已有定義同第三章，并補(bǔ)充以下定義：

定義1 在d維歐幾里得空間Ed中，給定有界區(qū)間Ii（o），d維最小邊界矩形（Minimum Bounding Rectangle，MBR）定義為Id（o）最小外包圖元，即各邊平行于d維的外接矩形。

定義2在d維歐幾里得空間中，對(duì)任意點(diǎn)p與矩形R，矩形R由它的對(duì)角線rr'表示，其中r=（r1，r2，…，rd），r'=（r'1，r'2，…，r'd）。點(diǎn)p與矩形R的最小距離

4.2 算法描述

采用基于R樹的索引算法的思想，具體如下：將所有的數(shù)據(jù)點(diǎn)都存儲(chǔ)在R樹中，利用點(diǎn)p當(dāng)前的Dk判斷一個(gè)區(qū)域是否可能存在孤立點(diǎn)，如果p點(diǎn)與該區(qū)域之間的距離超過(guò)當(dāng)前Dk，則該區(qū)域不可能存在孤立點(diǎn)，進(jìn)行剪枝，對(duì)保留下來(lái)的區(qū)域進(jìn)行排序，按順序繼續(xù)進(jìn)行孤立點(diǎn)檢測(cè)。

通過(guò)查閱文獻(xiàn)和對(duì)R樹中插入，刪除，區(qū)域查詢，節(jié)點(diǎn)分裂等算法的研究，使用排序前剪枝和基本有序兩種新策略，新策略在本節(jié)算法步驟和實(shí)現(xiàn)小結(jié)中有詳細(xì)說(shuō)明。

輸入：

數(shù)據(jù)集N D D中數(shù)據(jù)總量k點(diǎn)p的鄰居數(shù)量d數(shù)據(jù)的維度n孤立點(diǎn)總數(shù)M可用內(nèi)存數(shù)

輸出：從數(shù)據(jù)集選出的前n個(gè)具有最大Dk的點(diǎn)。算法步驟：

（1） 計(jì)算點(diǎn)p的Dk，具體如下。

（2）對(duì)Dk排序，具體如下。

4.3 算法分析

即使I/O優(yōu)化，嵌入循環(huán)的方法仍需要O（N2）的計(jì)算工作量，仍然是昂貴的，特別是在數(shù)據(jù)點(diǎn)的位數(shù)比較大時(shí)尤其如此。通過(guò)R樹進(jìn)行進(jìn)行剪枝，不再對(duì)明顯不是點(diǎn)p的k近鄰的數(shù)據(jù)點(diǎn)進(jìn)行距離計(jì)算，可使距離計(jì)算的工作量大大減小。

4.4 算法實(shí)現(xiàn)

4.5 算法實(shí)現(xiàn)小結(jié)

除了大根堆求點(diǎn)p的Dk和小根堆求孤立點(diǎn)，基于R樹索引算法實(shí)現(xiàn)的關(guān)鍵在于對(duì)R樹進(jìn)行區(qū)域查詢之后進(jìn)行剪枝。實(shí)現(xiàn)剪枝操作分兩步，第一步是判斷當(dāng)前查詢結(jié)點(diǎn)的每一個(gè)孩子是否有可能包含孤立點(diǎn)，只有可能的孩子才會(huì)再接下來(lái)的計(jì)算中出現(xiàn)，第二步是對(duì)所有可能存在孤立點(diǎn)的結(jié)點(diǎn)按可能性遞減的順序排序。剪枝的數(shù)據(jù)結(jié)構(gòu)采用優(yōu)先隊(duì)列實(shí)現(xiàn)的小根堆priority_queue＜myRTREEVECTORNODE> myRtreeVector：這種數(shù)據(jù)結(jié)構(gòu)使兩步剪枝操作合為一步，因?yàn)樵诩尤牒⒆咏Y(jié)點(diǎn)過(guò)程中已經(jīng)基本排序了，myRtreeVector的具體功能如表3。

表3 myRtreeVector功能表

采用小根堆記錄結(jié)點(diǎn)的原因：從算法本身的功能看，越早發(fā)現(xiàn)更近的區(qū)域剪枝效果越好，因?yàn)榧糁κ且罁?jù)與當(dāng)前區(qū)域的最近距離進(jìn)行的。所以利用小根堆可以達(dá)到首先計(jì)算最近區(qū)域中孤立點(diǎn)的目的。從實(shí)現(xiàn)角度看，結(jié)點(diǎn)按MINDIST基本有序即可以有比較好的效果，完全有序代價(jià)較大，但效果并無(wú)顯著提高。

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

5.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)

算法編寫使用VS2008，繪圖使用gunplot，計(jì)算機(jī)系統(tǒng)參數(shù)表4。

表4

實(shí)驗(yàn)數(shù)據(jù)來(lái)自http：//archive.ics.uci.edu/ml/index.html 的MAGIC Gamma Telescope Data Set數(shù)據(jù)集，具體如表5。.

表5

5.2 R樹索引算法的正確性

為了驗(yàn)證算法的正確性，本文進(jìn)行了以下四組實(shí)驗(yàn)，從低維到高維逐步對(duì)比了嵌套循環(huán)高維孤立點(diǎn)算法以及基于R樹高維孤立點(diǎn)算法。

5.2.1 實(shí)驗(yàn)一

本實(shí)驗(yàn)使用上述數(shù)據(jù)集中的9000個(gè)記錄，且截取這9000個(gè)記錄中的前三維。孤立點(diǎn)應(yīng)隨機(jī)地分布在9000個(gè)記錄構(gòu)成的簇的周圍。實(shí)驗(yàn)的目的為驗(yàn)證基于R樹的孤立點(diǎn)算法能夠像嵌入循環(huán)k近鄰孤立點(diǎn)算法一樣有效地識(shí)別孤立點(diǎn)。

輸入：

45（N*0.5%）n 360（N*4%）N 9000 d 3 k

實(shí)驗(yàn)結(jié)果：結(jié)果如圖1和2。

圖1 嵌入循環(huán)算法結(jié)果

圖2 樹索引算法結(jié)果

結(jié)果分析：從圖2和圖3看出，越稀疏的地方點(diǎn)的顏色越深，并且兩圖結(jié)果類似。所以R樹索引算法具有識(shí)別孤立點(diǎn)的功能，且效果與嵌入循環(huán)算法類似。

5.2.2 實(shí)驗(yàn)二

本實(shí)驗(yàn)使用上述數(shù)據(jù)集中的3000個(gè)記錄，且截取這3000個(gè)記錄中的前三維。孤立點(diǎn)應(yīng)隨機(jī)地分布在3000個(gè)記錄構(gòu)成的簇的周圍。實(shí)驗(yàn)的目的為考察基于R樹的孤立點(diǎn)算法與嵌入循環(huán)算法在結(jié)果上的區(qū)別。

輸入：

images/BZ_128_1292_2976_2292_3124.png

實(shí)驗(yàn)結(jié)果：結(jié)果如表6。

表6 實(shí)驗(yàn)二結(jié)果

結(jié)果分析：兩種算法記錄號(hào)不同之處在表中第二列用下劃線標(biāo)出，從表中看出兩點(diǎn)：第一，兩種算法檢測(cè)出的孤立點(diǎn)完全相同，只是排列次序上略有不同。第二，這種次序上的不同是小范圍內(nèi)的，即附近的記錄會(huì)有對(duì)換次序的情況，不存在大范圍內(nèi)的對(duì)換。能挖掘出相同的孤立點(diǎn)，說(shuō)明兩種算法對(duì)孤立點(diǎn)的評(píng)價(jià)標(biāo)準(zhǔn)在理論上相同，即使R樹算法經(jīng)過(guò)剪枝后再搜索也并未影響挖掘質(zhì)量。兩種算法的挖掘結(jié)果在排列上略有不同，說(shuō)明兩種算法在計(jì)算點(diǎn)p與其他點(diǎn)q（包含p自己）的順序不同，造成計(jì)算結(jié)果插入堆中的次序不同，從而導(dǎo)致小范圍內(nèi)次序不同。計(jì)算次序不同是R樹索引算法比嵌入循環(huán)算法效率高的關(guān)鍵。

5.2.3 實(shí)驗(yàn)三

本實(shí)驗(yàn)使用上述數(shù)據(jù)集中的3000個(gè)記錄，且截取這3000個(gè)記錄中的前六維。孤立點(diǎn)應(yīng)隨機(jī)地分布在3000個(gè)記錄構(gòu)成的簇的周圍。實(shí)驗(yàn)的目的為驗(yàn)證基于R樹的孤立點(diǎn)算法在六維情況下能夠有效地識(shí)別孤立點(diǎn)。

輸入：

K 15（N*0.5%）N 120（N*4%）N 3000 D 6

輸出：結(jié)果如圖3和圖4所示。

圖3 平行坐標(biāo)表示的檢測(cè)結(jié)果

結(jié)果分析：從圖3和圖4看出，越稀疏的地方顏色越深，說(shuō)明R樹索引算法在六維條件下同樣有效。

圖4 圓形坐標(biāo)表示的檢測(cè)結(jié)果

5.2.4 實(shí)驗(yàn)四

本實(shí)驗(yàn)使用上述數(shù)據(jù)集中的3000個(gè)記錄，由于第十一維的取值范圍是兩個(gè)離散值，h或g，不影響孤立點(diǎn)的選取，所以截取這3000個(gè)記錄中的前十維作為實(shí)驗(yàn)數(shù)據(jù)。孤立點(diǎn)應(yīng)隨機(jī)地分布在3000個(gè)記錄構(gòu)成的簇的周圍。實(shí)驗(yàn)的目的為驗(yàn)證基于R樹的孤立點(diǎn)算法能夠在高維條件下（如10維）有效地識(shí)別孤立點(diǎn)。

輸入：

15（N*0.5%）n 120（N*4%）N 3000 d 10 k

實(shí)驗(yàn)結(jié)果：輸出結(jié)果如圖5和圖6所示。

圖5 平行坐標(biāo)表示的檢測(cè)結(jié)果

圖6 圓形坐標(biāo)表示的檢測(cè)結(jié)果

結(jié)果分析：從圖5和6看出，越稀疏的地方顏色越深，說(shuō)明R樹索引算法在十維條件下同樣有效。

5.3 R樹索引算法的效率

為了探究算法的效率，本文進(jìn)行了以下實(shí)驗(yàn)。

本實(shí)驗(yàn)使用上述數(shù)據(jù)集中的15000個(gè)記錄，并截取這15000個(gè)記錄的前3維，數(shù)據(jù)大小從3000到15000個(gè)記錄，每次遞增3000。實(shí)驗(yàn)的目的為探究?jī)煞N算法的運(yùn)行時(shí)間與數(shù)據(jù)規(guī)模的關(guān)系，并探究?jī)煞N算法在這種關(guān)系上的差別。

實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 不同數(shù)據(jù)規(guī)模下的執(zhí)行時(shí)間

結(jié)果分析：從實(shí)驗(yàn)結(jié)果驗(yàn)證了，兩種算法的時(shí)間復(fù)雜度都是O（kN2），但是R樹索引算法N2之前的系數(shù)明顯小于嵌入式循環(huán)算法，這是因?yàn)镽樹索引算法在計(jì)算距離時(shí)運(yùn)用了剪枝條件，而嵌入式循環(huán)算法在計(jì)算距離時(shí)是遍歷所有點(diǎn)的。所以R樹索引算法比嵌入循環(huán)算法更有效。

6 結(jié)論

數(shù)據(jù)維度越高，數(shù)據(jù)規(guī)模越大，本文提出的R樹索引算法相對(duì)于嵌入循環(huán)算法在時(shí)間上的優(yōu)勢(shì)越大。從兩種算法實(shí)際運(yùn)行結(jié)果說(shuō)明，基于R樹索引算法能在高維條件下有效地檢測(cè)孤立點(diǎn)，并且當(dāng)時(shí)間復(fù)雜度為O（kN2）時(shí)，相對(duì)于嵌入循環(huán)算法有更小的k值。下一步打算對(duì)更底層的R樹進(jìn)行優(yōu)化。