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

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

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

1 引言

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

3 基本概念

3.1 局部敏感哈希

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

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

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

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

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

3.2 隨機(jī)游走

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

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

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

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

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

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

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

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

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

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

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

4.2 隨機(jī)游走

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

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

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

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

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

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

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

算法1LSH-RWOD算法

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

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

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

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

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

（5）fort=1…T

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

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

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

4.3 算法時(shí)間復(fù)雜度分析

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

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

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

5.1 實(shí)驗(yàn)環(huán)境

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

Table 1 Experimental datasets表1 實(shí)驗(yàn)數(shù)據(jù)集

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

5.2 評(píng)價(jià)指標(biāo)

為了衡量各種算法的異常點(diǎn)檢測(cè)效果，實(shí)驗(yàn)使用曲線下面積（area under curve，AUC）、平均精度（average precision，AP）、MaxF1這三個(gè)度量標(biāo)準(zhǔn)作為評(píng)價(jià)指標(biāo)。三個(gè)評(píng)價(jià)指標(biāo)值越接近1，則表明該算法異常檢測(cè)的效果越好。

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

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

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

5.3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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