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

席婷婷，趙旭俊，蘇建花

太原科技大學計算機科學與技術學院，太原 030024

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

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

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

1 相關工作

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

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

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

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

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

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

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

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

2.1 構建DLS-delaunary圖

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

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

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

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

定義2 DLS-delaunary 圖。設有無向圖G(V,E)為delaunary 三角剖分圖，其中V表示三角剖分圖中各個三角形頂點集，E表示三角剖分圖中各個三角形的邊的集合，圖中數據點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即為空間相鄰點，而數據點pi所有的空間相鄰點的集合稱為的pi空間鄰域DN(Pi)。

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

步驟1 計算數據集D的樣本期望。

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

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

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

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

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

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

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

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

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

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

定義4 數據對象的相似性simpi,pj：

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

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

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

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

定義5 定義重啟向量

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

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

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

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

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

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

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

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

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

4 實驗分析

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

4.1 人工合成數據集

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

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

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

圖1 Ring 和Zigzag數據集的DLS算法的執行過程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 真實數據集

4.2.1 數據集和評價標準

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

表2 10個真實數據集的特征Table 2 Features of 10 real datasets

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

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

4.2.2 真實數據集不同算法比較結果

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

表3 在10個數據集上最好的AUC和Precision score結果Table 3 Best AUC and Precision score results on 10 datasets

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

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

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

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

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

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

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

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

5 結束語

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

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