席婷婷，趙旭俊，蘇建花

太原科技大學計算機科學與技術(shù)學院，太原 030024

目前，在已有的無監(jiān)督離群點檢測方法中，已經(jīng)驗證了基于鄰域的方案[1]對于離群點檢測是非常有效的，并被廣泛地應(yīng)用于各個方面。此類算法從局部出發(fā)，通過每個對象的鄰域來看其孤立情況，既可以檢測各種形狀的簇，同時也適合于全局情況，該方法從預定義的鄰域大小推導出距離或密度來衡量每個對象的異常值得分。

然而，這類算法也存在很多問題。第一，如何選擇合適的鄰域大小，即參數(shù)的選擇問題。幾乎所有的異常點檢測算法都要求一個或多個參數(shù)的輸入，參數(shù)k的值的選擇影響著相關(guān)算法的性能。以LOF[2]算法以及其改進算法RDOS[3]為例，參數(shù)k的值的選擇在很大程度上取決于數(shù)據(jù)集的先驗知識，即使是有經(jīng)驗的用戶要選擇一個適當?shù)膋值也不是一件容易的事。第二，如何測量對象偏離其相應(yīng)正常數(shù)據(jù)點的程度。大部分的離群點檢測算法定義了各種計算離群分數(shù)的函數(shù)，目的是為每個對象分配一個離群點分數(shù)，以此將真實的離群點與正常點區(qū)分，然而每個點的計算均需要從全局出發(fā)，使得算法效率大大降低。第三，Wang 等人[4]將馬爾科夫隨機游走應(yīng)用到離群點檢測中，將平穩(wěn)分布向量作為離群點分數(shù)，其算法效率和精度大大提升。然而這類算法在隨機游走的過程中極有可能訪問不到處于邊緣的孤立節(jié)點，產(chǎn)生懸掛鏈路問題，使得隨機游走在達到平衡之前提前終止。針對該問題現(xiàn)有的解決方案是給離群點賦予更多的權(quán)重，使其有更多的機會被訪問，但并未充分考慮該節(jié)點周圍的局部信息。

本文提出了一種基于馬爾科夫隨機游走的兩階段離群點檢測算法，該算法第一階段根據(jù)均勻采樣策略生成一系列的DLS-delaunary 圖，在不依賴用戶指定參數(shù)的情況下，為下一步馬爾科夫隨機游走提供每個數(shù)據(jù)對象的鏈路結(jié)構(gòu)，減少參數(shù)對算法精度的影響。第二階段利用節(jié)點的連通性，得到轉(zhuǎn)移概率矩陣，引入并重新定義重啟向量，將本節(jié)點及其相鄰節(jié)點的連通性考慮在內(nèi)，確保DLS-delaunary 圖中的每個節(jié)點都有機會被重新選中，以此解決懸掛鏈路問題，從而確定馬爾科夫隨機游走的方式，該圖強大的連通性也保證了隨機游走過程能夠得到唯一的平穩(wěn)分布向量。由于離群點對象的數(shù)量比正常點對象的數(shù)量要少得多，則導致離群點在不同圖上的偏差值會遠遠大于正常點的偏差值，因此，訪問概率發(fā)生巨大的變化的點就是要找的離群點。

1 相關(guān)工作

近年來，基于鄰域離群點挖掘的研究取得了一定的進展，研究者們已經(jīng)提出的一些相關(guān)檢測算法并得到一定程度的應(yīng)用。本章主要研究兩種類型的孤立點檢測：基于鄰域信息的方法和基于圖形的方法。

1.1 基于鄰域的離群點檢測方法

在這類算法中，鄰域的定義起著重要的作用，合理的鄰域的定義可以有效地提高算法的性能[5]。Campos等人[6]在各種數(shù)據(jù)集的基礎(chǔ)上，提供了基于局部信息的孤立點檢測方法的全面的比較。KNN是最著名的分類算法之一，將對象與其第k個最近鄰的距離視為異常值得分，以適應(yīng)離群點檢測的問題。該方法簡單且有效，可在均勻分布的數(shù)據(jù)集中找到異常值，但是不能找到適當?shù)膋值來捕獲具有不同密度的數(shù)據(jù)集的異常值。為了降低人為因素對實驗結(jié)果的影響，其改進算法RKNN算法[7]在不需要提前指定參數(shù)k的情況下，可自適應(yīng)的選擇近鄰來確定k值。Wang 等人[8]提出了一種有效的基于MST 的kNN 的離群點檢測方法，它可以同時檢測全局和局部離群點，但因為在現(xiàn)實中，通常很難檢測到所有符合用戶直覺的異常值，因此可將其作為一個組件納入當前的離群點檢測框架可能是有意義的。石鴻雁等人[9]也為降低人為因素做出了貢獻，但是實驗結(jié)果仍然擺脫不了參數(shù)的選取。LOF 通過引入一個局部可達距離來估計每個數(shù)據(jù)對象的局部密度來解決這個問題，離群點分數(shù)被定義為k-鄰域內(nèi)的平均局部密度與物體的局部密度之比。

由以上可知，基于鄰域的算法對于離群點檢測是有效的，然而還存在兩方面的問題：一是對用于確定鄰域的大小的參數(shù)是敏感的；二是當待觀察值具有多樣性時，性能會比較差。因此，本文考慮遵循上述研究的理念，并嘗試依據(jù)所建的圖形來捕獲每個數(shù)據(jù)對象周圍的鄰域關(guān)系。

1.2 基于圖形的離群點檢測算法

近年來，由于基于圖形或網(wǎng)格的離群點檢測方法具有魯棒性，在數(shù)據(jù)集中捕捉遠距離關(guān)聯(lián)性的能力非凡以及能夠有效地捕獲數(shù)據(jù)集中隱含的潛在連接等優(yōu)點，引起了越來越多學者的興趣。Akoglu 等人[10]和Randshus等人[11]提供了基于圖的離群點檢測方法以及由動態(tài)網(wǎng)格表示的數(shù)據(jù)的全面調(diào)查。但是，基于圖的離群點檢測算法強調(diào)了數(shù)據(jù)集的整體結(jié)構(gòu)，但很少注意每個節(jié)點周圍的局部信息，從而導致了高假陽性。OutRank 算法[12]首先提出利用隨機游走過程的平穩(wěn)分布來表示每個數(shù)據(jù)的離群程度，該方法從原始數(shù)據(jù)構(gòu)造一個完全連通的無向圖，然后應(yīng)用馬爾可夫隨機游走過程計算離群點分數(shù)。ODIN 算法[13]是基于索引數(shù)的孤立點檢測算法，通過數(shù)據(jù)的局部信息構(gòu)造有向無權(quán)圖，然后利用圖結(jié)構(gòu)信息來定義離群點的得分，該算法的核心思想是：在有向的k近鄰圖中，離群點的索引數(shù)明顯小于正常點的數(shù)量。該方法只考慮了圖的靜態(tài)結(jié)構(gòu)信息，而忽略了可能隱藏在圖中的相關(guān)性。FKMOD算法[14]通過構(gòu)造剪枝的k-近鄰最小生成樹來確定全局離群點，但是算法在進行剪枝確定聚類時仍需要參數(shù)設(shè)定。RDOS 算法用共享鄰居擴展了鄰域定義以確定給定對象的局部信息，并且還采用核密度估計來估計局部密度。VOS 算法[15]與以前的研究相比，特別設(shè)計了一種利用每個對象的top-k相似鄰域構(gòu)造了一個加權(quán)有向的虛擬圖，這一機制確保了所提出的虛擬圖能夠發(fā)揮有效作用。但該算法還有其無法改進的問題，比如算法中k值仍然是人為定義以及關(guān)于虛擬點的存在雖然可以將全局信息考慮在內(nèi)，但該點的位置卻會影響每個點的訪問概率。

2 基于馬爾科夫隨機游走的離群點檢測

現(xiàn)有的基于馬爾科夫隨機游走的離群點檢測，存在兩個關(guān)鍵性的問題：第一，如何適當?shù)臉?gòu)造鄰域圖進行數(shù)據(jù)點的相似性度量；第二，如何在隨機游走達到平穩(wěn)狀態(tài)時，使離群點的訪問概率明顯區(qū)別于正常點。針對上述問題，本文提出了基于馬爾科夫隨機游走的兩階段離群點檢測算法，首先，利用數(shù)據(jù)集的幾何關(guān)系構(gòu)造適合馬爾科夫隨機游走的DLS-delaunay圖；然后根據(jù)潛在異常值應(yīng)該具有較低的訪問概率的假設(shè)，采用重新定義的重啟向量來解決孤立節(jié)點引起的懸掛鏈路問題；最后采用迭代方法，在隨機過程達到平衡后，將平穩(wěn)分布的平均偏差值作為每個對象的離群分數(shù)。

2.1 構(gòu)建DLS-delaunary圖

針對現(xiàn)有的基于馬爾科夫隨機游走的算法，鄰域圖的構(gòu)建都僅僅依賴于用戶給定的固定參數(shù)，而未考慮每個點周圍的實際情況。本文提出使用DLS-delaunary圖的幾何關(guān)系來確定每個數(shù)據(jù)對象的鄰域，圖中每個數(shù)據(jù)對象與該點空間上相鄰的點都存在邊直接相連，從而形成一種有效的鄰域關(guān)系。

定義1 Delaunay三角剖分。對給定n×n的空間數(shù)據(jù)集D=(X1,X2,…,Xn)進行三角網(wǎng)劃分，其中當劃分成的三角網(wǎng)滿足以下兩個特性即為delaunay 三角剖分圖G(V,E)：

（1）空球準則，單個三角形或不規(guī)則的四面體的外接圓或外接球內(nèi)部不包含除頂點外的其他點。

（2）最大-最小角準則，每個三角的角度都滿足是所有可能三角形中最小的。

定義2 DLS-delaunary 圖。設(shè)有無向圖G(V,E)為delaunary 三角剖分圖，其中V表示三角剖分圖中各個三角形頂點集，E表示三角剖分圖中各個三角形的邊的集合，圖中數(shù)據(jù)點pi與pj相連的邊為edge(pi,pj)，若兩點pi到pj間的歐氏距離dist(pi,pj)足以下公式：

則將該圖定義為DLS-delaunary三角剖分F(S,T)，即為圖G(V,E)的子圖，其中F?G，S=V，T?E，ω為選定侯選邊的距離閾值。

定義3 空間鄰域。對于任意?pi,pj∈D，若在定義2 的DLS-delaunary 圖中有邊edge(pi,pj) 相連，那么pi和pi即為空間相鄰點，而數(shù)據(jù)點pi所有的空間相鄰點的集合稱為的pi空間鄰域DN(Pi)。

由以上定義得出的DLS-delaunary 圖為無向圖，只將鄰域限制在一組具有高相似度的節(jié)點上，該方法根據(jù)不同數(shù)據(jù)點周圍的具體情況，對數(shù)據(jù)對象間的相互關(guān)系有不同的描述，其中每個節(jié)點代表一個數(shù)據(jù)對象，每條邊表示兩個節(jié)點之間的相似性，據(jù)此圖即可得出有關(guān)整個數(shù)據(jù)集中每個數(shù)據(jù)對象的相似性信息。以下為構(gòu)建DLS-delaunary圖的詳細步驟。

步驟1 計算數(shù)據(jù)集D的樣本期望。

假設(shè)有數(shù)據(jù)對象pi,pj∈D()i,j=1,2,…,n，點之間的鄰域關(guān)系用邊edge(pi,pj)表示，構(gòu)造delaunay三角剖分，用N(Pi)表示pi的所有鄰居，由于在delaunay 三角剖分圖中，所有邊的概率均為1n，即樣本的期望可簡化為樣本均值mean(p)的計算，如下：

其中，Sdist(pi,pj)是pi和pj之間的歐式距離，也就是三角剖分圖edge(pi,pj)的長度。

步驟2 計算數(shù)據(jù)集D的標準偏差.以貝塞爾公式來計算求得delaunay三角剖分圖與pi相關(guān)的所有邊的標準差ST_dev(pi)，如公式（2）所示：

通過循環(huán)迭代公式（2）即可得到delaunay圖所有邊的標準差。由于聚類邊界中的點傾向于具有比簇內(nèi)的點擁有更長的delaunay 邊edge(pi,pj)，在現(xiàn)實世界中，由長邊連接的簇間點不能定義為相鄰點。

步驟3 建立DLS-delaunary圖，制定邊的移除規(guī)則。

對于圖G(V,E)上任意一點p，設(shè)p與點相連點的集合為U，若U′是包含所有到p點的歐氏距離小于等于ω的邊的集和合，則：

以p點為起點當點v與p點距離小于預設(shè)值的侯選邊edge(v,p)會被加入候選集合U′中，組成每個點的新的鄰域。對于每個數(shù)據(jù)對象v，如果其鄰居v∈N(v)滿足公式（3），則加入到候選集合U′，將不符合條件的邊移除即移除edge(v,p) ，并將邊edge(v,p) 從v的鄰域N(v)中刪除，再從p的鄰域N(pi)中刪除點v。對于delaunary 三角剖分圖中所有的點p連接的邊均用公式（3）鑒別，將不符合條件的邊舍棄，重復循環(huán)迭代直至所有的邊均在給定范圍內(nèi)。由上述步驟可知，DLSdelaunary 圖閾值的選擇只取決于數(shù)據(jù)集D，即相應(yīng)數(shù)據(jù)集的均值和標準差，并且可以在不依賴用戶的情況下自動導出，由此得到自動閾值的離群點檢測算法。

2.2 基于DLS-delaunary圖鄰域相似性

由于馬爾科夫隨機游走的方式是由DLS-delaunary圖節(jié)點的鏈路結(jié)構(gòu)來確定的，因此，若一個數(shù)據(jù)對象與圖中其他對象的連通性較低，那么該點更有可能是一個離群點。而一個節(jié)點的連通性是根據(jù)圖中相關(guān)節(jié)點給出的加權(quán)投票來確定的，加權(quán)投票法的規(guī)則為高連接性節(jié)點比低連通性的節(jié)點投票的權(quán)重更大，來自任意節(jié)點投票的權(quán)重大小按與源節(jié)點相鄰的節(jié)點的數(shù)量來縮放。本文算法通過考慮節(jié)點的連通性和鄰居節(jié)點的分布來決定一個節(jié)點的權(quán)值，因此某一節(jié)點的連通性是由本節(jié)點的連通性和相鄰節(jié)點的連通性來表示的，正如公式（4）所示：

對于n個節(jié)點p1,p2,…,pn，可以任意分配每個節(jié)點的初始連接性值（例如Cpi=1/n,1 ≤i≤n）并遞歸地進行計算，以細化每次迭代中每個節(jié)點的連通性的值，這種迭代過程稱為冪方法，常用于求矩陣的主導特征向量，通過將該場景建模為馬爾可夫鏈來細化每個節(jié)點的連通性。

定義4 數(shù)據(jù)對象的相似性simpi,pj：

其中distpi,pj表示pi和pj之間的邊的距離，其中若pi和pj之間的不存在邊，則認為distpi,pj=∞。注意，對象與自身的相似性設(shè)置為零，以避免底層圖形表示中的自循環(huán)，這樣的循環(huán)應(yīng)該被忽略，因為這對每個節(jié)點都是存在且常見的，因此對于區(qū)分正常對象和異常值并不是很有用。

數(shù)據(jù)集D中所有對象之間的關(guān)系用n×n的矩陣sim(pi,pj)表示，其中n是D中數(shù)據(jù)點的個數(shù)，矩陣中的每個條目(simpi,pj)對應(yīng)于上面定義的對象i和對象j之間的相似性，將此相似矩陣作為圖的鄰接矩陣。如果兩個節(jié)點的相似性度量大于零，則兩個節(jié)點X和Y通過邊連接，并且將simpi,pj作為該邊的權(quán)值如公式（5）：

2.3 基于馬爾科夫隨機游走的離群點度量

由于W矩陣中除了對角線外，還有可能存在一些零項的行或者列，將會導致隨機游走沒有機會到達該點，也就是說使用DLS-delaunary 圖可能導致三角剖分圖被分割成幾個孤立的子圖，產(chǎn)生懸掛鏈路問題。針對該問題，本文算法引入并重新定義重啟向量，使得鄰接矩陣中每個條目都大于零，使得每個節(jié)點都有被選擇的機會，這將確保本地信息圖中的每個節(jié)點都有機會被重新選中，同時還避免引入新的孤立節(jié)點。

定義5 定義重啟向量

m=(sim(n1),sim(n2),…,sim(nn))

這種歸一化確保了轉(zhuǎn)換矩陣的每一行的元素和為1，這是馬爾可夫鏈的一個基本性質(zhì)。在利用公式（6）計算完轉(zhuǎn)移概率矩陣S(i,j)，需要使其既不可約又非周期，才能收斂到唯一的平穩(wěn)分布。在過去這個問題已經(jīng)由文獻[16]解決了，在他們的迭代過程計算中，保留一個低概率值來重新啟動隨機游走：

其中S是行歸一化過渡矩陣，d稱為阻尼因子，I是單位列向量(1,…,1)T。直觀地說，可以看作是允許隨機步行者以概率d傳輸?shù)綀D中的任何節(jié)點，即使這些節(jié)點不與當前訪問的節(jié)點相鄰。利用迭代方法，可以計算鄰域圖上馬爾科夫隨機游動過程的平穩(wěn)分布。迭代過程的形式為公式（7）：

達到平衡后節(jié)點的訪問概率。本文算法為了提高效率，本算法采用自動生成一系列DLS-delaunary 圖的方法，針對其每個Gα(0<α

根據(jù)上述定義，對象的離群點分數(shù)為其訪問概率在各個Gα圖上平穩(wěn)向量的平均偏差值，在這種情況下，由于離群點對象的數(shù)量比正常點對象的數(shù)量少得多，則導致異常點在不同圖上的偏差值會遠遠大于正常值，也就是說異常點的離群點分數(shù)會比正常點對象的離群點分數(shù)大得多。因此，具有較大離群點分數(shù)的對象表示其在不同圖上的訪問概率發(fā)生了巨大的變化，這表明它有更高的機會成為一個離群點。

3 基于馬爾科夫隨機游走的兩階段離群點檢測算法

本文算法基本過程分為兩個階段：第一階段，根據(jù)數(shù)據(jù)集以及公式（1）（2）（3）對三角剖分圖進行調(diào)整，刪除對表達相似性無效的邊，構(gòu)建DLS-delaunary圖，并得到每個點的拓撲結(jié)構(gòu)；第二步，建立相似矩陣S與轉(zhuǎn)移概率P，對該圖進行馬爾科夫隨機游走，計算各個圖平穩(wěn)分布的平均偏差值，從中選取分數(shù)最高的前n個對象作為離群點。由于用到了DLS-delaunary是本算法的特色，因此將該算法簡稱為DLS算法描述如下：

算法基于馬爾科夫隨機游走的的兩階段離群點檢測算法

現(xiàn)有的利用馬爾科夫隨機游走的算法，例如VOS算法[15]，該算法添加一個虛擬節(jié)點和2n條虛擬邊來構(gòu)造強連通圖，然后在該圖上執(zhí)行量身定做的馬爾科夫隨機游走來衡量每個數(shù)據(jù)對象的離群程度。該方法主要存在兩方面的問題：第一，利用虛擬節(jié)點和虛擬邊構(gòu)造強連通圖是極容易受到虛擬節(jié)點位置的影響，而且有可能引入新的孤立節(jié)點，從而影響算法的精確度。第二，馬爾科夫隨機游走的過程是由虛擬邊的權(quán)值決定的，為了使其不直接移動到虛擬點，該算法給定數(shù)據(jù)點到虛擬點間的權(quán)值較小，這一過程并未將數(shù)據(jù)對象周圍的實際情況考慮進來。本文所提出的兩階段離群點檢測算法，在第一階段，利用算法步驟1 到步驟6 構(gòu)造DLS-delaunary圖，避免了引入新的孤立節(jié)點，將空間上相鄰的點都賦予邊直接相連，在用戶不用輸入任何參數(shù)的情況下，為下一步的馬爾科夫隨機游走提供每個節(jié)點的鏈路結(jié)構(gòu)。在第二階段，也就是算法的步驟10到步驟15，為了使得每個數(shù)據(jù)點均有機會被訪問，在此階段引入并重新定義了重啟向量，即使出現(xiàn)數(shù)據(jù)對象較為稀疏的情況，仍然可以得到平穩(wěn)分布向量；在本階段馬爾科夫隨機游走的方式是轉(zhuǎn)移概率矩陣決定的，而轉(zhuǎn)移概率矩陣將節(jié)點的連通性考慮在內(nèi)，使得隨機游走的方式和數(shù)據(jù)點的真實分布直接相關(guān)，以此提高算法的準確性。

4 實驗分析

為了驗證基于馬爾科夫隨機游走的兩階段離群點檢測算法的有效性，4.1 節(jié)首先選取了兩個不同形狀的合成數(shù)據(jù)集，計算結(jié)果表明，本文算法可以適應(yīng)于不同的分布數(shù)據(jù)集。此外，4.2 節(jié)簡要介紹了選定的10 個UCI數(shù)據(jù)集的預處理過程以及對比算法，并利用ROC曲線、AUC以及精確度來測試算法的性能。

4.1 人工合成數(shù)據(jù)集

由于利用鄰域信息計算離群點分數(shù)的離群點檢測方法容易受到數(shù)據(jù)集分布的影響，為了測量所提出的算法在不同分布的數(shù)據(jù)集上的適應(yīng)性，構(gòu)造了兩個不同形狀的人工合成數(shù)據(jù)集如圖1 所示。其中圖（a）和（d）的橫縱坐標均為數(shù)據(jù)點的橫縱坐標。第一個數(shù)據(jù)集如圖1（a）所示，包含一個環(huán)狀簇750 個點和隨機生成的35 個離群點，其中遠離環(huán)狀區(qū)域的點稱之為離群點。第二個數(shù)據(jù)集如圖1（d）所示，是一條余弦波曲線，由501 個點作為正常點和從高斯分布中隨機采樣的42個點作為離群點組成。

首先對兩個人工合成數(shù)據(jù)分別建立DLS-delaunay三角剖分圖，結(jié)果如圖1（b）和（e）所示，其中連接點之間的灰色線條代表DLS-delaunay 圖得到的數(shù)據(jù)點間的拓撲關(guān)系，然后依據(jù)該圖進行馬爾科夫隨機

游走計算了上述兩個數(shù)據(jù)集中每個對象的離群點分數(shù)，依照Top-n以區(qū)分正常點與離群點，結(jié)果如圖1（c）和（f）所示，其中黑色和橙色分別表示正常點和離群點。由圖1可知，本文算法可為之字形數(shù)據(jù)集Zigzag和環(huán)狀數(shù)據(jù)集Ring 檢測出真正的離群點，并為孤立點對象分配了相對較小的分數(shù)，并且將人工數(shù)據(jù)集Ring 和Zigzag 應(yīng)用到經(jīng)典算法VOS、OutRannk 以及RDOS 上，如表1 所示，可以看到DLS 算法性能優(yōu)于其余3 個算法。主要原因是在獲得DLS-delaunary圖的基礎(chǔ)上得到了每個數(shù)據(jù)點的鄰接關(guān)系，并不需要人為設(shè)定參數(shù)，依此得到的相似矩陣更能代表數(shù)據(jù)點之間的關(guān)系，使得算法有了良好的基礎(chǔ)；此外，再利用連通性構(gòu)造的重啟向量，進行馬爾科夫隨機游走，使得算法的準確率大大提高，表明了所提出的算法對于不同的數(shù)據(jù)分布具有較強的適應(yīng)性。

圖1 Ring 和Zigzag數(shù)據(jù)集的DLS算法的執(zhí)行過程Fig.1 Execution process of DLS algorithm for Ring and Zigzag datasets

表1 Ring和Zigzag不同算法的AUC值Table 1 AUC values of Ring and Zigzag algorithms

4.2 真實數(shù)據(jù)集

4.2.1 數(shù)據(jù)集和評價標準

在本文研究中采用了Emmott方法構(gòu)造了來自UCI數(shù)據(jù)存儲庫10 個真實世界數(shù)據(jù)集，詳細的預處理過程參照文獻[17]，數(shù)據(jù)集的詳細信息在表2。在每個數(shù)據(jù)集中，來自小類（ES）的樣本被視為異常值，使用歸一化過程將每個屬性值縮放到一個[0，1]范圍內(nèi)，同時將重復的樣本和那些包含缺失值的樣本丟棄，其中數(shù)據(jù)的孤立點標簽信息不是用來提高算法的性能，而是僅僅用來評估結(jié)果。

表2 10個真實數(shù)據(jù)集的特征Table 2 Features of 10 real datasets

由于異常值檢測鄰域有一項具有挑戰(zhàn)性的任務(wù)是嚴格的類不平衡，也就是離群點對象的數(shù)量要遠遠小于正常點對象的數(shù)量，因此在離群點檢測鄰域，很少有研究直接使用傳統(tǒng)的度量方式。本文通過評估所有可能的決策閾值，可以得到ROC曲線，這表明正確分類的陽性樣本（離群點）的數(shù)量，稱為為真陽性，錯誤分類的陰性樣本（正常樣本）的數(shù)量稱為假陽性，并且該曲線越接近于左上角證明模型效果越好。AUC即為計算ROC曲線下的面積，其值從0到1不等，越接近于1，證明算法模型效果越好。設(shè)n是用戶期望從離群點檢測算法中得到的離群點對象的數(shù)量，TP和FP分別表示真實離群點的數(shù)量和被錯誤標記的正常點的個數(shù)，F(xiàn)N 為被錯誤標記的真實離群點的個數(shù)。TPR（true positive rate）、FPR（flase positive rate）和精度的計算如下：

特別是，一個完美的模型將得到一個接近1的AUC的分數(shù)，而隨機模型的分數(shù)將等于0.5。當模型被分配到相對較大的AUC 分數(shù)時，模型更可取。在下面的部分中，本文使用ROC 和AUC 將所提出的算法與其他3種方法進行比較。

4.2.2 真實數(shù)據(jù)集不同算法比較結(jié)果

為了驗證本文提出的基于馬爾科夫隨機游走的兩階段式離群點檢測算法優(yōu)于傳統(tǒng)的離群點檢測算法，將所提出的算法與其他3 種使用局部信息或隨機游走過程來決定離群點分數(shù)的算法進行了比較。將DLS、VOS、OutRannk 以及RDOS 算法在10 個真實的數(shù)據(jù)集上進行測試，并使用相同的實驗環(huán)境，實驗結(jié)果如表3所示。

表3 在10個數(shù)據(jù)集上最好的AUC和Precision score結(jié)果Table 3 Best AUC and Precision score results on 10 datasets

為了更直觀地證明本文算法的性能，進一步采用ROC曲線來評估檢測結(jié)果，其中本文畫出了4個數(shù)據(jù)集的ROC 曲線，如圖2 所示，圖中右下角的area 值代表ROC 曲線下的面積，由4.2.1 小節(jié)可知area 值越接近于1，代表算法性能越好，因此DLS算法在這4個數(shù)據(jù)集上是優(yōu)于其余算法的。而對于Synthetic-control 和Arrhythmia 數(shù)據(jù)集出現(xiàn)折線主要是因為數(shù)據(jù)量較小而且數(shù)據(jù)間的差距較小，導致最終計算的假陽性即FPR值有重復，為了使圖像呈現(xiàn)結(jié)果更接近真實性，沒有對折線進行平滑處理。

圖2 不同算法在4個數(shù)據(jù)集上的ROC AUC分數(shù)Fig 2 ROC AUC scores of different algorithms on four datasets

為了驗證本文提出的根據(jù)三角剖分圖自動確定閾值的方法優(yōu)于傳統(tǒng)的基于k值確定鄰域信息的方法，本節(jié)通過將k的值從2調(diào)整到100來對每個數(shù)據(jù)集進行附加實驗，如圖3。對于VOS 和RDOS，實驗結(jié)果將隨著鄰域大小k的變化而急劇變化，而DLS和OutRank不需要一個參數(shù)來指示鄰域大小，將實驗結(jié)果應(yīng)用于所有k設(shè)置的值，實驗結(jié)果如圖3 所示?，F(xiàn)將表2 中性能較為優(yōu)越的兩個數(shù)據(jù)集glass和Breast-cancer--wisc-diag進行不同k值的分析，由圖3可以看到在這兩個數(shù)據(jù)集上本文所提出的算法不論其他3 種算法取何k值都會有較高的AUC 值。在k值較小的時候，DLS 算法可自動為每個數(shù)據(jù)點分配合適的鄰域，并使用平穩(wěn)分布向量的平均偏差值可以有效的區(qū)分正常點和離群點，從而提高算法的性能，而圖中OutRank 和RDOS 的效果性能比較差，主要是因為從正常點到離群點的邊會大幅度減少，可能會導致降低隨機步行者從正常點跳到離群點的概率，使目標離群點很難得到所需的分數(shù)。另一方面，從圖中我們也可以觀察到，當k較大時，DLS 算法是基于節(jié)點的連通性來確定馬爾科夫隨機游走的轉(zhuǎn)移概率矩陣和重啟向量，可得到唯一的平穩(wěn)分布向量，這也就使算法的準確性仍然高于其余算法，其中VOS 算法和OutRank 算法的AUC 值會比較接近本算法，其原因是，即使在離群點對象之間形成簇時，k設(shè)置為一個較大的值，仍然存在連接正常點和離群點的邊緣，并確保隨機步行者可以從正常節(jié)點跳到離群點，但是往往需要較大k值才能有較高準確率，因此k值的選擇仍然不可避免的影響算法的準確性。

圖3 不同k 值的不同算法的ROC AUC分數(shù)比較Fig 3 Comparison of ROCAUC scores of different algorithms using different k values

本文算法中，為了提高效率選擇自動生成一系列的鄰域圖，而為了驗證生成鄰域圖的數(shù)目對實驗的結(jié)果的影響，選擇4個數(shù)據(jù)集在不同鄰域圖數(shù)量的前提下進行實驗，鄰域圖的數(shù)量分別為7，80，100，180，260，320，360，440，520，600，實驗結(jié)果如圖4 所示。從圖4所示的結(jié)果可以看出，隨著圖數(shù)的增加，算法的性能開始增加。當該值達到65左右時，性能趨于穩(wěn)定，具體針對每個數(shù)據(jù)集有不同的值，主要是因為每個數(shù)據(jù)集有不同的維度。此外，這一趨勢幾乎適用于所有的測試數(shù)據(jù)集，這也就意味著我們提出的DLS 算法對圖的數(shù)量并不敏感。

圖4 圖的數(shù)量對AUC值得影響Fig.4 Influence of AUC values under number of graphs

在證明了本文算法的有效性之后，使用真實數(shù)據(jù)集Waveform-noise 和Arrhythmia 對算法的性能進行實驗測試，將本文算法在最優(yōu)狀態(tài)下的時間與VOS、Out-Rank、RDOS 算法的時間相比較，實驗結(jié)果如圖5 所示。該圖顯示，本文所提出的算法，無論在哪個數(shù)據(jù)集上，其運行時間都比較短，充分說明本文提出的算法相比于對比算法有更高的效率。其主要原因一是本文算法采用均勻采樣策略，在不影響算法效率的前提下，盡可能的將算法效率優(yōu)化；二是當建立完成DLS-delaunary圖后，即可得到每個點的近鄰，也就是說本文算法在尋找每個點近鄰時不用從全局出發(fā)，也就是說避免了每次都將全部點遍歷一遍，有效的降低了時間復雜度。

圖5 不同算法效率對比Fig.5 Efficiency comparison of different algorithms

5 結(jié)束語

在分析了基于隨機游走的圖模型的特點后，提出了一種新的離群點檢測算法：基于馬爾科夫隨機游走的兩階段離群點檢測算法。該算法從DLS-delaunary圖中推導出轉(zhuǎn)移概率矩陣，由于其并不依賴于特定的閾值，因此即可確保對不同應(yīng)用場景的適應(yīng)性；為了解決懸掛鏈路問題，本文提出了基于相鄰節(jié)點的重啟向量，然后利用馬爾科夫隨機游走過程得到平穩(wěn)分布向量，而平均偏差值可以有效地區(qū)分正常點和潛在的離群點對象。最后對人工數(shù)據(jù)集和UCI數(shù)據(jù)集進行了廣泛實驗，結(jié)果表明，該方法在10 個真實世界的數(shù)據(jù)集中優(yōu)于一組基于局部信息的算法以及基于馬爾科夫隨機游走的算法。

此外借助三角剖分圖計算節(jié)點間的拓撲結(jié)構(gòu)和計算隨機游走的平穩(wěn)分布也是耗時的過程，也限制了本文算法在大規(guī)模和流數(shù)據(jù)中的應(yīng)用。因此，如何克服這一特殊問題，開發(fā)出新的算法，既可以加快過程，同時又能保持算法性能，也是未來研究的方向。