結(jié)合局部敏感哈希和隨機游走的異常檢測算法*

舒 敏，劉華文，鄭忠龍，徐曉丹

浙江師范大學 數(shù)理與信息工程學院，浙江 金華 321004

1 引言

隨著信息技術的快速發(fā)展，數(shù)據(jù)呈現(xiàn)爆炸式的增長。然而由于設備故障、信號干擾、人為操作失誤等各種因素，數(shù)據(jù)在收集過程中可能會出現(xiàn)一定的偏差或異常。檢測并排除數(shù)據(jù)中的異常點是數(shù)據(jù)挖掘的主要任務之一。由于能夠檢測數(shù)據(jù)中的異常點及噪聲，異常檢測在現(xiàn)實中得到廣泛應用，如欺詐檢測[1]、網(wǎng)絡入侵[2]、醫(yī)療數(shù)據(jù)分析[3]等。

異常檢測可通過如統(tǒng)計方法或鄰域判定等多種方式實現(xiàn)。例如，統(tǒng)計方法通常假定大部分正常的數(shù)據(jù)對象服從相同的數(shù)據(jù)分布，而異常的數(shù)據(jù)不屬于該數(shù)據(jù)分布。由于統(tǒng)計方法高度依賴于數(shù)據(jù)分布的假定，因而只適用于低維的數(shù)據(jù)，不適合高維的數(shù)據(jù)[4]。面向鄰域的異常點檢測方法則是根據(jù)每個數(shù)據(jù)對象的鄰域情況來判斷其是否屬于異常數(shù)據(jù)。典型的方法包括局部異常因子算法（local outlier factor，LOF）[5]和K最近鄰算法（K-nearest neighbor，KNN）[6]等，其中LOF算法通過比較每個點與其第k個鄰域的局部密度來判斷該點是否為異常點。注意到LOF算法對鄰域k的選擇較為敏感，若k的取值不合理，將導致檢測結(jié)果不準確，且只適用于維度較低的數(shù)據(jù)。KNN算法[6]是以數(shù)據(jù)點到第k個近鄰的距離來表示該點異常程度。該方法簡單直觀，可以較好地適應中等維數(shù)的數(shù)據(jù)，但數(shù)據(jù)稀疏會導致異常檢測的結(jié)果出現(xiàn)較大誤差。鄰域離散度算法（dispersion of neighbors，DON）[7]根據(jù)數(shù)據(jù)對象所在鄰域的離散度來判斷其是否為異常點。盡管該算法可以避免邊緣處正常數(shù)據(jù)對象被誤判為異常點，但需要計算大規(guī)模高維數(shù)據(jù)的離散度。

隨著信息技術的快速發(fā)展，各個領域都出現(xiàn)了大規(guī)模的數(shù)據(jù)。盡管目前已提出了許多異常點檢測算法，但大部分檢測算法在處理大規(guī)模高維度數(shù)據(jù)時效率較低。如何從大規(guī)模數(shù)據(jù)中高效地檢測異常點越來越受到關注。大數(shù)據(jù)的數(shù)據(jù)量大、維度高、數(shù)據(jù)分布復雜且稀疏等特性給異常點的檢測帶來了很大的挑戰(zhàn)。針對此問題，本文提出了一種適用于大規(guī)模數(shù)據(jù)的異常點檢測方法，該方法首先采用局部敏感哈希技術高速處理大規(guī)模數(shù)據(jù)，避免了數(shù)據(jù)高維性帶來的維災難問題，同時還保證原始空間中數(shù)據(jù)的相似性，進而運用高效的距離度量準則構(gòu)造數(shù)據(jù)的相似矩陣。在此基礎上，利用隨機游走技術區(qū)分正常數(shù)據(jù)和異常數(shù)據(jù)。實驗結(jié)果表明，本文所提出的異常點檢測算法能有效地檢測出數(shù)據(jù)中的異常點。

本文的結(jié)構(gòu)組織如下：第2章介紹異常點檢測的相關工作；第3章簡述局部敏感哈希和隨機游走的基本原理；第4章介紹本文所提算法的主要思路及細節(jié)；第5章給出了實驗比較并對實驗結(jié)果加以分析；第6章總結(jié)全文，并給出了未來工作展望。

2 相關工作

目前，文獻中已提出了許多異常點檢測算法，它們大致可分為[8]：基于統(tǒng)計的異常點檢測方法、基于鄰域的異常點檢測方法、基于子空間的異常點檢測方法、基于分類的異常點檢測方法、基于孤立的異常檢測方法。

基于統(tǒng)計的異常點檢測方法通常假定正常的數(shù)據(jù)對象產(chǎn)生于某一個統(tǒng)計模型而不屬于該分布規(guī)律的數(shù)據(jù)對象為異常點[4]。該方法擁有成熟的概率統(tǒng)計知識作為支撐，因此檢測出異常數(shù)據(jù)可以有很好的解釋。但它高度依賴于數(shù)據(jù)模型分布的假定，即要求已知數(shù)據(jù)服從某種分布，而實際情況中數(shù)據(jù)集很難服從該假定。其次，此方法檢測的數(shù)據(jù)對象是單一維度的，并不合適用在高維度數(shù)據(jù)。

基于鄰域的異常點檢測方法主要通過比較每個數(shù)據(jù)對象其鄰域來判斷數(shù)據(jù)是否異常。LOF算法[5]就是一種典型的基于鄰域的檢測算法，其主要的思想是通過比較每個點和第k鄰域局部密度來判斷該點是否為異常點。由于LOF算法對參數(shù)k比較敏感，而不合理的k值會導致較差的檢測效果，為此文獻[9]提出了基于連接性的異常因子算法（connectivity based outlier factor，COF）。該算法根據(jù)最短路徑和數(shù)據(jù)對象的連接性來確定鄰域k，計算與其鄰域的平均連接距離，并以此作為相對密度來判斷異常點。由于COF算法計算量大，因此在處理大規(guī)模數(shù)據(jù)集時效率較低。以上算法檢查出的邊緣數(shù)據(jù)點的異常程度較高，但是在某些情況下邊緣數(shù)據(jù)點并非異常點。DON算法[7]根據(jù)數(shù)據(jù)對象所在鄰域的離散度來判斷異常點，可以避免邊緣處的正常數(shù)據(jù)對象被誤判為異常點，然而此算法計算高維數(shù)據(jù)的離散度，會存在部分數(shù)據(jù)維度信息沒有使用，將會導致算法可靠性下降。基于局部距離的異常因子算法（local distance-based outlier factor，LDOF）[10]將數(shù)據(jù)對象到k個近鄰的距離的均值與k個近鄰彼此之間的距離均值的比值作為該數(shù)據(jù)對象的異常度。注意到，此算法在大規(guī)模高維數(shù)據(jù)集下運行速度較慢。

基于子空間的異常點檢測方法主要是為每個數(shù)據(jù)對象尋找最佳的子空間并計算相應的異常程度。具有解釋的局部異常檢測算法（local outlier detection with interpretation，LODI）[11]通過特征分解尋找近鄰間隔最大化的子空間，然后進行異常度計算。子空間異常度算法（subspace outlier degree，SOD）[12]和相關異常概率算法（correlation outlier probability，COP）[13]，這兩種算法能夠?qū)γ總€數(shù)據(jù)點選擇最佳的子空間進行異常值計算，但算法復雜性比較高。

基于分類的異常點檢測方法主要通過學習數(shù)據(jù)對象的邊界，將邊界外的數(shù)據(jù)點作為異常點。由于數(shù)據(jù)標簽種類不同，分類的形式有單分類和多分類，因此基于分類的異常檢測方法分為單分類的異常點檢測和多分類的異常點檢測。單分類的異常點檢測是學習數(shù)據(jù)集的一個邊界，邊界內(nèi)包裹的數(shù)據(jù)屬于正常點，邊界之外的數(shù)據(jù)則是異常點。代表性的算法如一類支持向量機算法（one class support vector machine，One-class-SVM）[14]，該算法在高維特征空間中通過非線性核映射計算一個最小超球體作為邊界，將邊界內(nèi)的數(shù)據(jù)作為正常點，而邊界外的數(shù)據(jù)作為異常點。通常這類問題要求已知的數(shù)據(jù)集大多數(shù)屬于同一類，而另一類數(shù)據(jù)集的樣本數(shù)目很少，此方法效率會較慢。多分類的異常檢測方法主要對數(shù)據(jù)集學習多個邊界，將不包含在任何邊界內(nèi)的數(shù)據(jù)點定義為異常點。最具有代表性的是基于神經(jīng)網(wǎng)絡的多分類異常點檢測[15]。此方法分為兩個階段：第一個階段利用正常的多分類訓練數(shù)據(jù)來訓練模型；第二個階段將測試數(shù)據(jù)輸入模型，若網(wǎng)絡接收則為正常點，反之為異常點。

基于孤立的異常點檢測方法是將異常點與其余點分開，即通過隔離異常點而不是分析正常點的方法來進行異常點的檢測。孤立森林（isolation forest，iForest）[16]主要采用隨機超平面遞歸地分隔異常點，如果某個數(shù)據(jù)點越容易與其余數(shù)據(jù)點分隔開，那么該數(shù)據(jù)點的異常程度也越高，此方法在選擇分隔維度和分隔點時具有隨機性和無目的性。為此，參考文獻[17]提出了熵引導孤立樹（entropy-guided isolation tree，EGiTree），它在選擇分隔維度和分隔點時具有很強的目的性，并且在同一個階段完成異常程度的計算。但是這類方法不適合特別高維的數(shù)據(jù)，因為高維空間可能存在大量噪音維度或無關維度，而這會影響樹的構(gòu)建。

3 基本概念

3.1 局部敏感哈希

局部敏感哈希（locality sensitive Hashing，LSH）[18-20]是一種面向大規(guī)模數(shù)據(jù)的最近鄰獲取技術。LSH的主要思想是設計一種特殊的哈希函數(shù)，使得兩個相似度很大的數(shù)據(jù)能以較高概率映射成相同的哈希值，而兩個相似度很小的數(shù)據(jù)則以很小的概率映射成相同的哈希值。

基于隨機投影的LSH是一種經(jīng)典的方法。具體是利用隨機超平面將高維的數(shù)據(jù)向量投影到超平面之上，使高維空間的數(shù)據(jù)向量之間相似性在海明空間得以保存。假設數(shù)據(jù)集為X=[x1,x2,…,xn]∈Rn×d，隨機向量v的每一項均取自標準正態(tài)分布N(0,1)，則隨機投影的哈希函數(shù)定義如下：

隨機超平面技術可用來近似衡量數(shù)據(jù)之間余弦相似度。數(shù)據(jù)點xi和xj經(jīng)過隨機投影之后相似的哈希值概率為：

等式（2）中θ(xi,xj)表示數(shù)據(jù)點xi和xj之間的角度。從等式中可以知道數(shù)據(jù)點之間的角度越小，則數(shù)據(jù)點之間越相似，相似的數(shù)據(jù)是能以較高的概率映射成相同的哈希值，而不相似的數(shù)據(jù)映射成相同的哈希值的概率較小。

數(shù)據(jù)點xi經(jīng)過等式（1）投影之后，轉(zhuǎn)化為數(shù)據(jù)點的一個二進制位。重復L次，將這L個二進制位連接起來獲得長度為L的二進制向量。這樣，高維空間數(shù)據(jù)之間的相似度量轉(zhuǎn)化為海明空間二進制之間的相似性度量。

3.2 隨機游走

給定圖G和一個出發(fā)節(jié)點，隨機游走[21-22]主要思想是在給定的出發(fā)節(jié)點上隨機選擇鄰節(jié)點，并移動到鄰節(jié)點上，將此時節(jié)點作為新的出發(fā)節(jié)點，一直重復以上過程。隨機游走是隨機過程的一種方式。文中隨機過程是馬爾可夫鏈，為此介紹馬爾可夫鏈原理。隨機過程是概率空間中一組隨機變量yt=y(t)，t為任意參數(shù)。馬爾可夫鏈是如果隨機過程中隨機變量yt取有限個值，即y1…yt…yn，并稱它們?yōu)闋顟B(tài)變量，yt表示第t時刻的狀態(tài)，以及它們的取值{1,2,…,n}稱為狀態(tài)空間，那么對于狀態(tài)i,j,k0,k1…,滿足以下概率：

這樣的隨機過程是馬爾可夫鏈，等式（3）是狀態(tài)i轉(zhuǎn)移到狀態(tài)j的轉(zhuǎn)化概率aij。也就是說馬爾可夫鏈下一時刻的狀態(tài)僅僅由當前的狀態(tài)決定，不依賴以往的任何狀態(tài)。圖1給出隨機游走的過程：在t=0時刻從節(jié)點1出發(fā)，在t=1時刻以1/2的轉(zhuǎn)移概率達到節(jié)點4后選擇下一個目標。

Fig.1 Process of random walks(The number on edge indicates transition probability)圖1 隨機游走的過程（邊上的數(shù)字表示轉(zhuǎn)移概率）

4 結(jié)合LSH和隨機游走的異常檢測算法

本章介紹基于LSH和隨機游走的異常點檢測算法，分為兩個階段：第一階段度量數(shù)據(jù)相似性，利用LSH將原始數(shù)據(jù)向量表示成海明空間的二進制向量形式，其保證了原始數(shù)據(jù)空間的相似性，之后度量每個數(shù)據(jù)點的最近鄰k個點，并構(gòu)造相似矩陣S；第二階段建立相似矩陣S與轉(zhuǎn)移概率P之間的關系，并構(gòu)造馬爾可夫鏈，進而使用隨機游走來區(qū)分正常點與異常點。

4.1 數(shù)據(jù)相似性

給定數(shù)據(jù)集X=[x1,x2,…,xn]∈Rn×d，假設哈希函數(shù)族H，其中函數(shù)族中每一個函數(shù)均為等式（1）所示。對于LSH哈希函數(shù)族H，它是從H中均勻隨機地選擇L個哈希函數(shù)h1,h2,…,hL。

數(shù)據(jù)點x經(jīng)過這L個哈希函數(shù)，可以把L個二進制位連接起來，使得原始數(shù)據(jù)集可表示成海明空間二進制形式，即B(x)={h1(x),h2(x),…,hL(x)}∈{0,1}L。

對于具有n個數(shù)據(jù)點的集合X?Rn×d，經(jīng)過隨機投影之后，可得到相應的二進制向量集B，如下所示：

假設數(shù)據(jù)集的相似矩陣為S={sij}n×n，sij表示海明空間中數(shù)據(jù)點B(xi)和B(xj)之間的相似度。在相似矩陣S中，不考慮每個數(shù)據(jù)點之間的相似性，而只考慮數(shù)據(jù)最近鄰k個點之間的相似性，因此，sij表示形式如下所示：

式（5）中dH(,)表示海明距離，kB(x)表示數(shù)據(jù)點B(x)的最近鄰k個點。從等式中可知，如果數(shù)據(jù)點B(xj)是數(shù)據(jù)點B(xi)最近鄰k個點之一，那么數(shù)據(jù)點B(xi)和B(xj)之間相似度是非零數(shù)，反之相似度為0。理想情況，正常數(shù)據(jù)的最近鄰k僅僅含有正常數(shù)據(jù)，而異常數(shù)據(jù)的最近鄰k同時含有正常和異常數(shù)據(jù)。

4.2 隨機游走

由前一階段可得到相似矩陣S，將相似矩陣S表示成有向圖的形式，并稱此有向圖是相似圖G，其中相似圖G的頂點對應數(shù)據(jù)集X，相似圖G的邊對應相似矩陣S。在相似圖G中，正常數(shù)據(jù)點的鄰邊僅僅連接在正常數(shù)據(jù)點上，然而異常數(shù)據(jù)點的鄰邊存在正常數(shù)據(jù)點和異常數(shù)據(jù)點均有邊的情況。

在相似圖G上采用隨機游走的過程來識別正常點與異常點[22]。而此時，隨機游走的過程是一個離散時間的馬爾可夫鏈。定義從某一時刻數(shù)據(jù)點B(xi)到下一時刻數(shù)據(jù)點B(xj)的轉(zhuǎn)移概率aij為：

由于所有的正常點和所有的異常點之間是沒有任何連接的。根據(jù)此定義，若隨機游走的初始點是正常的數(shù)據(jù)點，那么它會一直在正常的數(shù)據(jù)點之間游走，不會離開正常點的范圍，相反，隨機游走的初始點是異常的數(shù)據(jù)點，則隨機游走最后可能處于正常的數(shù)據(jù)點之間游走的狀態(tài)，因為隨機游走一旦脫離了異常狀態(tài)，到達正常狀態(tài)，它將不可能返回異常狀態(tài)。隨機游走的初始點處在不同的數(shù)據(jù)點上，通過觀察隨機游走狀態(tài)的最后概率分布，異常點最終會被識別出來，即正常點的概率越來越大，而異常點的概率越來越小。

設P={aij}∈Rn×n是轉(zhuǎn)移矩陣，轉(zhuǎn)移矩陣P與相似矩陣S有關。定義是經(jīng)過t步后所有數(shù)據(jù)點的狀態(tài)概率，則t+1步狀態(tài)轉(zhuǎn)移為：

因此t步轉(zhuǎn)移概率為π(t)=π(0)·Pt，其中π(0)為所有數(shù)據(jù)點的初始概率，并設定為：

式（8）表明了初始狀態(tài)每個數(shù)據(jù)點均有可能。對于第t步所有數(shù)據(jù)點的狀態(tài)概率，由于π(t)沒有要求收斂，因此選擇T步平均作為最后的結(jié)果，如下所示：

式（9）表明在數(shù)據(jù)集X中初始隨機游走，之后計算T步所有隨機游走的概率分布平均之和。隨機游走最終狀態(tài)轉(zhuǎn)移是：正常數(shù)據(jù)點狀態(tài)概率高而對于異常數(shù)據(jù)點狀態(tài)概率低。結(jié)合LSH和隨機游走的異常檢測算法（outlier detection algorithm with locality sensitive Hashing and random walks，LSH-RWOD）描述如下：

算法1LSH-RWOD算法

輸入：數(shù)據(jù)集X，二進制碼長度L，最近鄰k，步數(shù)T，異常點個數(shù)ε。

輸出：異常數(shù)據(jù)點xj。

（1）使用式（1）得到數(shù)據(jù)集X的二進制編碼B。

（2）利用式（5）構(gòu)造數(shù)據(jù)集相似矩陣S。

（3）由式（6）數(shù)據(jù)之間的相似性sij和轉(zhuǎn)移概率aij之間的關系，求轉(zhuǎn)移矩陣P。

（5）fort=1…T

①計算t步狀態(tài)轉(zhuǎn)移概率：π=π·P。

②計算所有t步狀態(tài)轉(zhuǎn)移概率：。

（6）對最終轉(zhuǎn)移概率進行排序，返回中前ε個元素作為異常點。

4.3 算法時間復雜度分析

LSH-RWOD算法時間復雜度主要由相似度的構(gòu)造和隨機游走這兩部分組成。假設數(shù)據(jù)量及維度分別為n和d，且編碼長度為L，則相似矩陣S的構(gòu)造的時間復雜度為O(nL2)，而隨機游走的時間復雜度為O(n2)。因此，LSH-RWOD算法的時間復雜度為O(nL2)+O(n2)。通常情況下，編碼長度L遠小于n，故LSH-RWOD算法的時間復雜度為O(n2)。

5 實驗分析

使用幾組數(shù)據(jù)集來檢測LSH-RWOD算法的異常檢測效果。除One-class-SVM以外的對比算法均根據(jù)數(shù)據(jù)點的局部鄰域來計算異常程度，并且LSHRWOD算法中也涉及最近鄰k，為此實驗將局部鄰域和最近鄰統(tǒng)一設置為20，該值的變化對算法性能的比較影響不大。針對SOD算法，本實驗根據(jù)參考文獻[12]中意見將參數(shù)l設為k，α設為0.8。對于LSHRWOD算法其不同的二進制碼長度L一定程度上會影響異常檢測的效果，根據(jù)文獻[19,21]的建議，本實驗將L分別設置為24、32、48、64、96，同時將步數(shù)T設置為1 000。

5.1 實驗環(huán)境

實驗采用由索引結(jié)構(gòu)支持的數(shù)據(jù)挖掘應用開發(fā)環(huán)境（environment for developing knowledge discovery in database-applications supported by index-structures，ELKI）中的數(shù)據(jù)（http://elki-project.github.io/）和異常檢測數(shù)據(jù)集（outlier detection data sets，ODDS）中的數(shù)據(jù)（http://odds.cs.stonybrook.edu#table1）。所有的數(shù)據(jù)均做了標準化的處理，其中Mnist是手寫數(shù)字樣本，數(shù)字0樣本作為正常數(shù)據(jù)點，從數(shù)字6隨機抽取的樣本作為異常點，異常點所占比例為9.2%。Musk是麝香數(shù)據(jù)集，包含幾個麝香類和非麝香類，將非麝香類j146、j147和252數(shù)據(jù)記為正常點，而麝香類213和211記為異常值，異常點的數(shù)據(jù)所占比例為3.2%。Arrhythmia的樣本包含正常的患者和心律失常的患者，將心律失常的患者標記為異常點數(shù)據(jù)，所占比例為45.8%。Speech為不同口音的英語語音片段組成數(shù)據(jù)集，大部分數(shù)據(jù)對應于美國口音，只有1.7%對應于其他7種口音之一，這些數(shù)據(jù)標為異常點。InternetAds是由來自網(wǎng)頁的圖像組成，分為廣告和不廣告兩種類型，將是廣告的數(shù)據(jù)標記為異常點數(shù)據(jù)，其所 占的比例為13.9%。實驗數(shù)據(jù)集簡要描述信息如表1所示。

Table 1 Experimental datasets表1 實驗數(shù)據(jù)集

為驗證所提算法的有效性，實驗將LSH-RWOD算法與6種流行的異常點檢測算法進行比較，它們分別是局部異常因子算法（local outlier factor，LOF）[5]、基于局部距離的異常因子算法（local distance-based outlier factor，LDOF）[10]、子空間異常度算法（subspace outlier degree，SOD）[12]、一類支持向量機算法（one class support vector machine，One-class-SVM）[14]、基于連接性的異常因子算法（connectivity based outlier factor，COF）[9]和相關異常概率算法（correlation outlier probability，COP）[13]，其中 LOF 算法、COF 算法和LDOF算法是屬于鄰域的異常點檢測方法，SOD算法和COP算法為子空間的異常點檢測方法，而Oneclass-SVM算法是基于分類的異常點檢測算法。所有的算法均采用ELKI數(shù)據(jù)包中的源碼，實驗也在ELKI中進行比較。

5.2 評價指標

為了衡量各種算法的異常點檢測效果，實驗使用曲線下面積（area under curve，AUC）、平均精度（average precision，AP）、MaxF1這三個度量標準作為評價指標。三個評價指標值越接近1，則表明該算法異常檢測的效果越好。

AUC是受試者工作特征（receiver operating characteristic，ROC）曲線下的面積，其值介于0和1之間。假設數(shù)據(jù)集為D，數(shù)據(jù)集中異常點集合為C，正常點集合為D-C，T(ε)為算法檢測出前ε個異常數(shù)據(jù)點集，則有：

AP為PR曲線的面積。PR曲線的表示為：

MaxF1是算法檢測出前ε個異常點的數(shù)據(jù)集中基于精確度P(ε)和召回率R(ε)的最大調(diào)和平均，其表示形式為：

5.3 實驗結(jié)果

本文提出的LSH-RWOD算法，不同的二進制位在一定程度上會影響檢測效果，為此，比較各個數(shù)據(jù)集上不同二進制位其LSH-RWOD算法的AUC值，如表2所示。從表中可以看出二進制位越長，在一定程度上檢測效果越好，其主要原因是二進制位越長，使得原始信息損失越小，且構(gòu)造的相似性越準確。

Table 2 AUC value for different binary LSH-RWOD algorithm on each dataset表2 各個數(shù)據(jù)集上不同二進制LSH-RWOD算法的AUC值

由于LSH-RWOD算法采用了LSH技術獲取數(shù)據(jù)的相似性，而LSH存在著一定的隨機性。為了驗證LSH-RWOD算法的穩(wěn)定性，在相同的數(shù)據(jù)集上固定二進制的長度L，多次循環(huán)運行LSH-RWOD算法，獲取評價指標的平均值，并作為最終的檢測結(jié)果。為了避免二進制長度較小，導致原始信息損失，設二進制長度為L=96。

圖2給出LSH-RWOD算法在實驗數(shù)據(jù)集中不同循環(huán)次數(shù)的平均AUC值。從圖2中可以看到，當循環(huán)次數(shù)在140次以下時，檢測效果在評價指標值的0.1范圍內(nèi)波動，而當循環(huán)次數(shù)達到140次以上，檢測效果趨于穩(wěn)定。因此，本文所有的實驗均是循環(huán)200次后的平均值。同時觀察到算法在循環(huán)20次時檢測效果基本上比穩(wěn)定狀態(tài)較好，主要原因在于本文算法采用哈希編碼來構(gòu)造相似矩陣，從而使得相似的數(shù)據(jù)映射成相似的哈希值概率更高，同時不相似的數(shù)據(jù)映射成相似哈希值的概率較低。由于不相似的數(shù)據(jù)點也可能映射成相似的哈希值，從而導致構(gòu)造的相似矩陣可能存在誤差，但是多次循環(huán)其包含的相似矩陣S的誤差種類多于較小循環(huán)次數(shù)中相似矩陣S的誤差種類，從而穩(wěn)定狀態(tài)的平均結(jié)果會稍低于循環(huán)20次時的平均結(jié)果。

Fig.2 AverageAUC value of each datum in different cycles圖2 各個數(shù)據(jù)不同循環(huán)次數(shù)下的平均AUC值

圖3和圖4是LSH-RWOD算法在各個數(shù)據(jù)集中不同循環(huán)次數(shù)的平均AP值和MaxF1值。當循環(huán)次數(shù)達到140次以上時，檢測效果趨于穩(wěn)定。且注意到循環(huán)次數(shù)較低時其異常檢測效果不穩(wěn)定，產(chǎn)生的主要原因是LSH-RWOD算法采用哈希編碼來構(gòu)造相似矩陣，此過程的哈希編碼技術具有一定的概率性，使得相似矩陣S存在誤差，而當循環(huán)次數(shù)過多時，LSH-RWOD算法包含誤差種類多于較小循環(huán)次數(shù)中誤差種類，因此循環(huán)次數(shù)過少，實驗結(jié)果有時不盡理想。

Fig.3 AverageAP value of each datum in different cycles圖3 各個數(shù)據(jù)不同循環(huán)次數(shù)下的平均AP值

Fig.4 Average MaxF1 value of each datum in different cycles圖4 各個數(shù)據(jù)不同循環(huán)次數(shù)下的平均MaxF1值

綜上所述，本文提出的LSH-RWOD算法具有穩(wěn)定性。

從表2的實驗結(jié)果可知，為更好地保留樣本的信息，選擇L=96構(gòu)造數(shù)據(jù)的二進制位。LSH-RWOD算法將原始數(shù)據(jù)哈希到海明空間二進制表示，哈希函數(shù)選擇隨機向量v均取自標準正態(tài)分布，同時參考圖2～圖4的實驗結(jié)果，LSH-RWOD算法結(jié)果取自各個數(shù)據(jù)集循環(huán)200次得到的平均值。

在評價指標AUC下，不同方法在各個數(shù)據(jù)集中異常檢測效果，如表3所示。實驗表明在該評價指標，LSH-RWOD算法在Mnist、Musk、Arrhythmia這三個數(shù)據(jù)集上優(yōu)于其他算法。但在Speech數(shù)據(jù)集上，One-class-SVM算法的檢測效果是優(yōu)于LSH-RWOD算法的，原因是One-class-SVM算法適合解決極度不平衡的數(shù)據(jù)集，即一種類型樣本的數(shù)目遠遠多于另一種類型樣本的數(shù)目，那該方法異常檢測的效果會更明顯。而在Speech數(shù)據(jù)集上，它包含異常樣本比例最小，因此，One-class-SVM算法能更有效檢測出邊界外的異常數(shù)據(jù)點。在Internet Ads數(shù)據(jù)集上，One-class-SVM算法也是優(yōu)于LSH-RWOD算法，其主要原因是Internet Ads數(shù)據(jù)集維數(shù)過大，此時LSHRWOD算法的二進制長度較小不能完全刻畫數(shù)據(jù)的原始數(shù)據(jù)信息，導致部分數(shù)據(jù)信息流失，在計算相似矩陣時存在誤差，使得在隨機游走的過程中識別異常點的效果變差。LOF、LDOF、SOD、COF、COP這五種算法在各個數(shù)據(jù)集中檢測效果均在80%以下，原因是局部鄰域較小，并不能刻畫數(shù)據(jù)點的局部特性，且這些算法不能較好地處理大規(guī)模維度高的數(shù)據(jù)，因此異常檢測效果差。

Table 3 AUC value of different algorithms in each dataset表3 不同算法在各個數(shù)據(jù)集中的AUC值 %

在評價指標AP下，不同方法在各個數(shù)據(jù)集中異常檢測效果，如表4所示。實驗表明LSH-RWOD算法在這五組數(shù)據(jù)上遠優(yōu)于其他算法。LOF、LDOF、SOD、One-class-SVM、COF、COP這六種算法在Mnist、Musk、Speech、Internet Ads這四組數(shù)據(jù)集上檢測效果過差，原因是這四個數(shù)據(jù)集中異常數(shù)據(jù)的比例在15%以下，局部鄰域較小，不能準確刻畫數(shù)據(jù)點的局部性，因此大部分算法表現(xiàn)效果不佳是合理的。而在Arrhythmia數(shù)據(jù)集上，此數(shù)據(jù)集異常點所含比例大，這六種方法較其他數(shù)據(jù)集，檢測效果較好。

Table 4 AP value of different algorithms in each dataset表4 不同算法在各個數(shù)據(jù)集中的AP值 %

在評價指標MaxF1下，不同方法在各個數(shù)據(jù)集中異常檢測效果，如表5所示。實驗表明LSH-RWOD算法優(yōu)于其他算法。在這五組數(shù)據(jù)集上，樣本所含異常點的比例按從小到大的順序分別為Speech、Musk、Mnist、InternetAds、Arrhythmia。而 LOF、LDOF、SOD、COF、COP五種算法在前四個數(shù)據(jù)集上表現(xiàn)效果不佳，主要原因是局部鄰域較小，不能很好地刻畫數(shù)據(jù)點的局部性，但在Arrhythmia數(shù)據(jù)集上，這五種方法較其他數(shù)據(jù)集，檢測效果較好。

Table 5 MaxF1 value of different algorithms in each dataset表5 不同算法在各個數(shù)據(jù)集中的MaxF1值 %

綜合分析可以知道，LSH-RWOD方法在這五組數(shù)據(jù)集上異常檢測效果整體優(yōu)于其他算法。

6 結(jié)束語

針對大規(guī)模數(shù)據(jù)的特點，本文結(jié)合局部敏感哈希和隨機游走技術，提出了一種高效的異常點檢測算法LSH-RWOD，以克服大規(guī)模、高維數(shù)據(jù)的異常點檢測問題。首先，利用局部敏感哈希高效地處理大規(guī)模數(shù)據(jù)，隨后運用數(shù)據(jù)之間距離獲取其相似性，并轉(zhuǎn)化為相應的轉(zhuǎn)移概率，在此基礎上，使用隨機游走技術計算數(shù)據(jù)之間的游走概率，從而最終辨別異常數(shù)據(jù)。為驗證有效性，LSH-RWOD算法與六種常用的異常檢測算法在公開數(shù)據(jù)集上進行實驗比較。實驗結(jié)果表明，所提出的方法能有效地檢測出異常點，性能總體上優(yōu)于其他異常點檢測算法。未來的工作將分析LSH方法之間的關系，并使用集成學習技術進一步提高異常點檢測的準確度。