席婷婷，趙旭俊，蘇建花

太原科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024

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

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

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

1 相關(guān)工作

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

1.1 基于鄰域的離群點(diǎn)檢測方法

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

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

1.2 基于圖形的離群點(diǎn)檢測算法

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

2 基于馬爾科夫隨機(jī)游走的離群點(diǎn)檢測

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 基于馬爾科夫隨機(jī)游走的離群點(diǎn)度量

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

定義5 定義重啟向量

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

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

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

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

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

3 基于馬爾科夫隨機(jī)游走的兩階段離群點(diǎn)檢測算法

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

算法基于馬爾科夫隨機(jī)游走的的兩階段離群點(diǎn)檢測算法

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

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

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

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

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

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

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

4.2.1 數(shù)據(jù)集和評價(jià)標(biāo)準(zhǔn)

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

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

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

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

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

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

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

為了更直觀地證明本文算法的性能，進(jìn)一步采用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)折線主要是因?yàn)閿?shù)據(jù)量較小而且數(shù)據(jù)間的差距較小，導(dǎo)致最終計(jì)算的假陽性即FPR值有重復(fù)，為了使圖像呈現(xiàn)結(jié)果更接近真實(shí)性，沒有對折線進(jìn)行平滑處理。

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

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

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

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

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

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

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

5 結(jié)束語

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

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