張忠平，郭 鑫，張玉停，張睿博

（1.燕山大學 信息科學與工程學院，河北 秦皇島 066004；2.河北省計算機虛擬技術與系統(tǒng)集成重點實驗室（燕山大學），河北 秦皇島 066004；3.河北省軟件工程重點實驗室（燕山大學），河北 秦皇島 066004；4.武漢理工大學 國際教育學院，武漢 430070）

0 引言

離群點檢測旨在從數(shù)據(jù)集中發(fā)現(xiàn)異常數(shù)據(jù)，是數(shù)據(jù)挖掘技術領域研究的熱點問題之一。離群點的定義是指與其他數(shù)據(jù)點明顯不同的數(shù)據(jù)點或不符合預期行為的數(shù)據(jù)點［1］。離群點檢測在很多方面都有著重要的研究意義，如信用卡欺詐檢測［2］、網(wǎng)絡入侵檢測［3］、故障診斷［4］、圖像處理［5］等。目前，離群點檢測方法主要分為以下幾個大類：基于統(tǒng)計的方法［6-8］、基于距離的方法［9-11］、基于密度的方法［12-14］和基于圖的方法［15-17］。

基于統(tǒng)計的方法的基本思想是在識別離群點時取決于數(shù)據(jù)的分布模型。該方法分為兩大類：一類是參數(shù)方法，這是一種假設有底層分布模型的方法，常用的兩種檢測模型是高斯混合模型和回歸模型；另一類是非參數(shù)方法，這是一種使用核密度估計（Kernel Density Estimation，KDE）［18］的方法。

基于距離的方法的基本思想側重于數(shù)據(jù)之間的距離計算，若一個點距離其鄰居點很遠，則被視作為離群點。Knorr等［19］最早對基于距離的方法進行了研究并定義了基于距離的離群點，此方法適用于中到高維的大數(shù)據(jù)集，與基于統(tǒng)計的方法相比，此方法具有更強的健壯性、靈活性和更高的檢測效率。

基于密度的方法的基本思想是在低密度區(qū)域找到離群點，在密集鄰域內找到內部點。此方法將數(shù)據(jù)點的局部密度與其鄰域密度進行比較，刻畫數(shù)據(jù)點的離群程度，進而檢測離群點。最為經(jīng)典的基于密度的方法是Breunig 等［20］提出的局部離群因子（Local Outlier Factor，LOF）算法。該算法利用k近鄰，在每個點的k近鄰域中，利用局部可達密度與其k近鄰域內的平均可達密度進行比較得出離群點。

基于圖的方法的基本思想是使用圖技術有效地捕獲數(shù)據(jù)點間的相互依賴性，從而識別離群點?；趫D的方法能夠對各種類型的數(shù)據(jù)提供一個健壯的表示，同時還能夠有效地捕獲數(shù)據(jù)隱含的內部連接模式，因此此類方法吸引了很多學者的關注。該方法的檢測過程可以概括為兩個步驟：首先將每個數(shù)據(jù)點都看作圖中的一個節(jié)點，并將整個數(shù)據(jù)集以圖的形式表示；然后從圖中提取轉移概率矩陣進行馬爾可夫隨機游走，利用生成的平穩(wěn)分布檢測離群點。Moonesinghe 等［21］提出OutRank，這是一種基于圖的離群點檢測算法，此算法用兩種方式構建數(shù)據(jù)的圖形表示，分別是基于數(shù)據(jù)點的相似性和基于數(shù)據(jù)點共享鄰居的數(shù)量；然后在構建的圖上進行馬爾可夫隨機游走，通過最終的平穩(wěn)分布檢測離群點。此算法只考慮了數(shù)據(jù)對象的全局信息，沒有考慮數(shù)據(jù)對象的局部信息，導致它在一些數(shù)據(jù)集上檢測效果不佳。Wang等［22］考慮到大多數(shù)基于圖的方法忽略了每個數(shù)據(jù)點周圍的局部信息，提出了一種新的離群點檢測模型，將圖形表示和每個數(shù)據(jù)點周圍的局部信息相結合，構建局部信息圖，并通過在圖上進行隨機游走計算離群分數(shù)，但會出現(xiàn)隨機游走提前結束的情況，文獻中針對這種情況提出了兩種不同類型的重啟向量來解決“懸空鏈接”問題，不僅避免了隨機游走提前結束，還提高了算法的檢測性能。

基于圖的離群點檢測方法通常將重點放在構造轉移概率矩陣上，一個好的轉移概率矩陣不僅能刻畫每個數(shù)據(jù)點的全局信息，也能捕捉數(shù)據(jù)點的局部信息。傳統(tǒng)的基于圖的方法在構造轉移概率矩陣時使用數(shù)據(jù)的整體分布特征，由于忽略了數(shù)據(jù)的局部信息，導致檢測精度不高；使用數(shù)據(jù)的局部信息時，又可能出現(xiàn)“懸空鏈接”問題。針對上述問題，本文提出了基于全息圖平穩(wěn)分布因子的離群點檢測算法（Outlier Detection algorithm based on Hologram Stationary Distribution Factor，HSDFOD）。算法首先使用相似度矩陣自適應地獲取每個數(shù)據(jù)點的鄰居集合，進而構造局部信息圖；然后引入最小生成樹構造一個全局信息圖，使用全局信息圖不僅能夠考慮數(shù)據(jù)點的全局信息，同時能有效避免“懸空鏈接”的問題；最后綜合利用局部信息圖和全局信息圖融合為全息圖構造轉移概率矩陣進行馬爾可夫隨機游走，通過生成的平穩(wěn)分布檢測出離群點。

1 相關定義

馬爾可夫鏈上的隨機游走是基于圖的離群點檢測方法常用的概率學模型。

定義1 馬爾可夫鏈。給定一個隨機變量的序列X={x0，x1，…，xt，…}，其中xt表示t時刻的隨機變量且每個xt的取值集合相同。當t＞1 時，如果xt只依賴于xt-1，不依賴過去的其他隨機變量{x0，x1，…，xt-2}，即滿足條件概率分布：p(xt|xt-1，xt-2，…，x0)=p(xt|xt-1)，該性質被稱為馬爾可夫性。存在馬爾可夫性的隨機變量的序列稱為馬爾可夫鏈或馬爾可夫過程。

定義2 轉移概率矩陣P。設pi，j表示馬爾可夫鏈中從節(jié)點i轉移到節(jié)點j的概率，則對于一個包含n個數(shù)據(jù)點的馬爾可夫鏈，其轉移概率矩陣表示為P，定義如式（1）所示：

定義3 平穩(wěn)分布。馬爾可夫隨機游走最終會趨于一個穩(wěn)定的狀態(tài)，即訪問每個數(shù)據(jù)點的概率不再發(fā)生變化，這個概率向量分布稱為平穩(wěn)分布π=[π(1)，π(2)，…，π(n)]，π為一個n維的向量，每個分量表示對應節(jié)點被訪問的概率，且=1。通過不斷的迭代，最終會生成一個平穩(wěn)分布，迭代過程如式（2）所示：

為更加清晰地描述馬爾可夫隨機游走過程，下面給出一個在有向圖上進行馬爾可夫隨機游走過程的具體實例。

如圖1所示，給定一個由3個節(jié)點組成的轉移概率圖，可見每個節(jié)點不僅有轉移到其他節(jié)點的邊，還有從其他節(jié)點轉移到該節(jié)點的邊。有向圖的邊上的權重表示從一個節(jié)點轉移到另一個節(jié)點的概率，因此一個節(jié)點上所有出度邊上的權重和為1。

圖1 3個節(jié)點之間的狀態(tài)轉移Fig.1 State transfer among three nodes

根據(jù)圖1 生成對應的轉移概率矩陣P的具體定義如式（3）。利用矩陣P，進行如式（2）的迭代。其中，初始分布為π0=[0.21，0.68，0.11]，在迭代十幾次后，平穩(wěn)分布最終會收斂，得到最終的平穩(wěn)分布π=[0.286，0.489，0.225]。實際上，根據(jù)馬爾可夫鏈的特性，初始分布的概率分布不會影響最終生成的平穩(wěn)分布。

2 本文算法

基于馬爾可夫隨機游走進行離群點檢測算法的核心是構造轉移概率矩陣。一個好的轉移概率矩陣能較為準確地刻畫數(shù)據(jù)的分布特征。經(jīng)典的構造轉移概率矩陣的方法是構造一個全局連通圖，但由于忽略了數(shù)據(jù)點的局部信息，導致檢測精度不高。之后改進的方法通過構造虛擬節(jié)點或重啟向量獲取數(shù)據(jù)點的局部信息，但檢測結果容易受到k值的影響。針對上述問題，本文提出基于全息圖平穩(wěn)分布因子的離群點檢測算法（HSDFOD），綜合考慮數(shù)據(jù)點的局部和全局信息，并使用一種自適應k值的方法避免輸入?yún)?shù)，提高算法的檢測精度和增強健壯性。

2.1 HSDFOD思想

HSDFOD 首先通過一種自適應k值的方法獲取每個數(shù)據(jù)點的局部鄰域信息，使內部點的鄰居個數(shù)多于離群點的鄰居個數(shù)，根據(jù)數(shù)據(jù)點的鄰域信息構造局部信息圖；然后為獲取數(shù)據(jù)點的全局信息，利用最小生成樹生成一個全局信息圖，最小生成樹中每條邊對應全局信息圖中兩個有向邊，且兩個有向邊的轉移概率相同，該全局信息圖不僅能獲取數(shù)據(jù)的全局分布信息，而且還能避免“懸空鏈接”問題；最后融合局部信息圖和全局信息圖為全息圖構造轉移概率矩陣，利用該轉移概率矩陣進行馬爾可夫隨機游走，通過不斷迭代，將生成的平穩(wěn)分布中各個分量視為數(shù)據(jù)點的平穩(wěn)分布因子，進而刻畫數(shù)據(jù)點的離群程度。

2.2 HSDFOD定義

定義4 相似度函數(shù)。給定數(shù)據(jù)集X={x1，x2，…，xi，…，xn}，i=1，2，…，n，xi∈Rd，對于xi，xj∈X，它們的相似度函數(shù)計算如式（4）：

其中‖xi-xj‖為xi和xj之間的歐氏距離。式（4）使用的是高斯核密度公式計算兩個數(shù)據(jù)點的之間的相似性，δ為核函數(shù)的帶寬，計算方法如式（5）：

其中 |V|是數(shù)據(jù)集包含的數(shù)據(jù)點數(shù)。

定義5 相似矩陣S。使用式（4）計算數(shù)據(jù)集中每兩個點之間的相似度，進而得到整個數(shù)據(jù)集的相似矩陣ST=S，定義為式（6）：

定義6 局部鄰居集合。數(shù)據(jù)點xi的局部鄰居LN(xi)的定義如式（7）所示。由式（7）可知將相似度大于閾值εi的點視為該數(shù)據(jù)點的鄰居點。

其中εi為數(shù)據(jù)點xi的自適應閾值，定義如式（8）：

其 中：μi為集合{sim(xi，x1)，sim(xi，x2)，…，sim(xi，xn)}的期望；σi為該集合的標準差。

從式（7）（8）可見數(shù)據(jù)點的局部鄰居集合和k近鄰集合類似，都是獲取與數(shù)據(jù)點最相似點的集合，但與k近鄰集合相比，局部鄰居集合有以下兩個優(yōu)勢。

1）局部鄰居集合通過自適應k值的方式生成數(shù)據(jù)點的鄰居集合，無需輸入?yún)?shù)，從而提高算法在面對不同數(shù)據(jù)集的健壯性和穩(wěn)定性。

2）每個數(shù)據(jù)點的鄰居個數(shù)不同，但總體上內部點能獲取更多的鄰居點，而離群點獲取較少的鄰居點。

如圖2 所示，P1點位于稀疏區(qū)域，可將該點視為離群點，P2～P9點位于稠密區(qū)域，可將這些點視為內部點。使用局部鄰居的概念計算P1點的鄰居集合為LN(P1)={P2，P9}，P3點的鄰居集合為LN(P3)={P2，P4，P5，P6，P7}。可以看出P1點和P3點的鄰居個數(shù)不同，而且內部點P3有更多的鄰居點。離群點P1僅有兩個邊緣點作為鄰居點。因此，使用局部鄰居集合不僅可以避免外部輸入?yún)?shù)確定鄰居個數(shù)的問題，而且能讓稠密區(qū)域的點擁有比稀疏區(qū)域更多的鄰居個數(shù)。

圖2 局部鄰居集合示例Fig.2 Example of a local neighbor set

定義7 局部信息圖WLIG。局部信息圖刻畫數(shù)據(jù)點的局部信息，定義如式（9）：

其中：S是定義5 中的相似矩陣；運算符°為哈達瑪積，即矩陣對應元素直接相乘；N是0-1 矩陣，即矩陣元素只有0 和1。N定義如式（10）：

對于數(shù)據(jù)點xi，只有其局部鄰居集合中的點在局部信息圖中才有相應的權重。由于局部鄰居集合的特性，局部信息圖中內部點之間連接的緊密程度遠高于離群點和內部點的連接，表現(xiàn)在局部信息圖上為內部點對應行有更少的0 分量，因此，利用局部信息圖可以準確地刻畫數(shù)據(jù)的局部信息。

但僅使用局部信息圖對應的轉移概率矩陣進行馬爾可夫隨機游走會出現(xiàn)“懸空鏈接”問題，下面簡要介紹“懸空鏈接”問題產(chǎn)生的原因。如圖3 所示，B、C和D點為內部點，A點為離群點。

圖3 懸空鏈接問題Fig.3 Suspended link problem

內部點B有分別指向B、C、D和A的有向邊，而離群點A只有指向自己的有向邊。當在該圖以B點為起點進行馬爾可夫隨機游走時，下一步可以轉移到B、C、D和A中任意一個。當轉移到A點后，由于A點是離群點，沒有其他點把A點視為鄰居點，導致A點只有指向自身的一條邊。因此，在后續(xù)的隨機游走中，只會不停地在A點循環(huán)，導致A點被訪問的概率急劇增加。最后，馬爾可夫隨機游走會提前結束，A點的訪問概率接近為1，其他點的訪問概率接近為0。同時，如果轉移概率矩陣分為幾個子圖且子圖之間不連通，會同樣導致馬爾隨機游走難以有效地檢測離群點。

為此，本文提出利用最小生成樹構建的全局信息圖解決“懸空鏈接”問題，下面將對全局信息圖進行闡述。

定義8 矩陣R。該矩陣表示在全局連通圖上的權重矩陣，主要用于生成最小生成樹，其定義為式（11）：

定義9 最小生成樹T。在數(shù)據(jù)集X上建立一個全連接的有向完全圖，其邊上的權重矩陣為R，則使用Kruskal 算法或Prim 算法生成最小生成樹T=(V，E)。

其中：頂點集V={x1，x2，…，xn}，邊集E={e1，e2，…，en-1}。從矩陣R的定義可以看出，生成的樹結構不僅將整個數(shù)據(jù)集中的節(jié)點連接起來，同時任意一條邊上的兩個節(jié)點都是其鄰域內相似性最大的節(jié)點，因此利用最小生成樹能精準地刻畫數(shù)據(jù)的全局信息。

定義10 最小連通矩陣（Minimum Connected Matrix，MCM）。MCM 描述了最小生成樹中數(shù)據(jù)點的連通信息，定義如式（12）所示：

其中E是最小生成樹的邊集。由式（12）可以看出，最小生成樹的每條邊對應最小連通矩陣兩個分量，即MMC(i，j)=MMC(j，i)。

定義11 全局信息圖WGIG。全局信息圖刻畫了通過最小生成樹獲取的數(shù)據(jù)點的全局信息，定義如式（13）：

其中：S為相似度矩陣；MMC為最小連通矩陣，通過哈達瑪積運算得到全局信息圖。全局信息圖不僅通過最小生成樹將整個數(shù)據(jù)點連接起來，同時利用相似矩陣精確刻畫了數(shù)據(jù)點的全局分布信息。

定義12 全息圖WHG。全息圖將局部信息和全局信息進行融合，更全面地刻畫了數(shù)據(jù)信息，定義如式（14）：

定義13 轉移概率矩陣PHG。轉移概率矩陣綜合考慮了數(shù)據(jù)點的全局和局部的數(shù)據(jù)分布，定義如式（15）：

其中：D為對角矩陣，對角線上的元素為局部信息圖和全局信息圖對應分量之和，作用是在于保證轉移概率矩陣中每一行的概率和為1。因此，本文構造的轉移概率矩陣能全面地考慮數(shù)據(jù)的全局和局部分布特征，即全息圖特征；同時還能避免“懸空鏈接”問題，確保順利進行馬爾可夫隨機游走過程。

最后，在構造好的轉移概率矩陣上進行馬爾可夫隨機游走，其迭代過程如式（17）所示：

其中π為n維的平穩(wěn)分布。

定義14 平穩(wěn)分布因子（Stationary Distribution Factor，SDF）。SDF 描述的數(shù)據(jù)點離群程度，定義如式（18）：

由式（18）可以看出，數(shù)據(jù)點xi的SDF為馬爾可夫隨機游走產(chǎn)生的平穩(wěn)分布對應分量。由于內部點之間的連接緊密程度高于離群點和內部點之間的連接緊密程度，因此平穩(wěn)分布中內部點的對應的分量較大，則其SDF較大，數(shù)據(jù)點離群程度低；平穩(wěn)分布中離群點對應的分量較小，則其SDF較小，數(shù)據(jù)點離群程度高。

2.3 HSDFOD描述

本節(jié)主要描述基于全息圖平穩(wěn)分布因子的離群點檢測算法HSDFOD 的執(zhí)行過程。HSDFOD 需要輸入數(shù)據(jù)集D，算法輸出top-n離群點。本文算法首先構建數(shù)據(jù)點的局部鄰居集合，利用一種自適應k值的方式確定數(shù)據(jù)點的鄰居個數(shù)，使得內部點的鄰居點個數(shù)多于離群點的鄰居個數(shù)；然后利用局部鄰居集合構建局部信息圖，使用最小生成樹構造出的全局信息圖解決“懸空鏈接”問題；最后融合局部信息圖和全局信息圖為全息圖，構造轉移概率矩陣，再利用轉移概率矩陣進行馬爾可夫隨機游走，利用SDF 衡量數(shù)據(jù)點的離群程度進而檢測出離群點。

根據(jù)上述算法思想及相關定義，HSDFOD 描述如下。

算法1 HSDFOD。

HSDFOD的時間復雜度主要來源于以下兩個部分：1）為構建局部信息圖，需要獲取每個數(shù)據(jù)點的鄰域信息所需的時間復雜度為O(n2)，n為數(shù)據(jù)集中數(shù)據(jù)點的個數(shù)；2）為構建全局信息圖，需要使用Kruskal算法或Prim算法生成最小生成樹，時間復雜度為O(n2)。因此HSDFOD的總體時間復雜度為O(n2)。

3 實驗與結果分析

為評估HSDFOD 的性能，使用SOD（Outlier Detection in axis-parallel Subspaces of high dimensional data）［23］、SUOD（accelerating large-Scale Unsupervised heterogeneous Outlier Detection）［24］、IForest（Isolation Forest）［25］和HBOS（Histogram-Based Outlier Score）［26］算法在人工數(shù)據(jù)集和真實數(shù)據(jù)集上進行實驗驗證，比較分析本文算法的性能。以上算法都是基于top-n思想檢測離群點。實驗環(huán)境配置如表1所示，主要分為軟件配置和硬件配置。

表1 實驗環(huán)境Tab.1 Experimental environment

3.1 實驗評估指標

為了全面、有效地檢測本文所提算法的性能，本節(jié)將使用精確率Pr、曲線下面積（Area Under Curve，AUC）和離群點發(fā)現(xiàn)曲線作為離群點檢測算法性能的評價指標。精確率Pr是傳統(tǒng)離群點檢測算法常用的指標，定義如式（19）所示：

其中：TP表示算法正確檢測出的數(shù)據(jù)集中真實離群點的數(shù)量；FN表示算法錯誤地把真實離群點識別為內部點的數(shù)量；FP表示算法錯誤地把內部點識別為離群點的數(shù)量。AUC 是受試者工作特征曲線（Receiver Operating characteristic Curve，ROC）下方的面積，取值范圍為［0，1］。AUC 值大的離群點檢測算法意味著有更大的概率將離群點排在內部點之前，因此，AUC 值越大，算法表現(xiàn)越好。

離群點發(fā)現(xiàn)曲線是一種新的展現(xiàn)離群點檢測算法性能的指標，計算過程為：在離群點檢測算法為數(shù)據(jù)集中每個數(shù)據(jù)點計算離群得分后，將數(shù)據(jù)點的離群分數(shù)倒序排列，然后分段統(tǒng)計離群點檢測算法檢測出真實離群點的總數(shù)，最后以增量的形式進行展示。離群點發(fā)現(xiàn)曲線上升越快，表明算法能更加準確有效地檢測出離群點。離群點發(fā)現(xiàn)曲線最優(yōu)表現(xiàn)為一條斜率為0.5 的線段。

3.2 人工數(shù)據(jù)集實驗

本文使用圖4 所示的4 種人工數(shù)據(jù)集。

圖4 4種人工數(shù)據(jù)集分布Fig.4 Distribution of four synthetic datasets

表2 是人工數(shù)據(jù)集A1～A4 的詳細數(shù)據(jù)特征。根據(jù)圖4 和表2可以看出，選用的人工數(shù)據(jù)集A1～A4分布較為復雜，離群點個數(shù)占比合理。因此，使用A1～A4 的數(shù)據(jù)集能較為全面地驗證本文算法在各種復雜數(shù)據(jù)分布下離群點的檢測效果。

表2 人工數(shù)據(jù)集的數(shù)據(jù)特征Tab.2 Data characteristics of synthetic datasets

圖5 展示了HSDFOD 和對比算法在4 個人工數(shù)據(jù)集下精確率對比。從圖5 可見，HSDFOD 在每個人工數(shù)據(jù)集下的檢測精度都是最高的，尤其在A3數(shù)據(jù)集中精確率達到100%，最差的檢測精度也有70%以上。人工數(shù)據(jù)集A4 的數(shù)據(jù)分布構成較為復雜，可以看出相比其他數(shù)據(jù)集，該數(shù)據(jù)集下的各算法的精確率都存在不同程度的下降，SUOD 算法在A4 數(shù)據(jù)集中甚至未能檢測出離群點，但HSDFOD 依然能達到超70%的精確率。綜合上述分析，可以看出，HSDFOD 在各個人工數(shù)據(jù)集中的檢測精度最高且算法較為穩(wěn)定。因此，驗證了HSDFOD能高效地檢測離群點。

圖5 人工數(shù)據(jù)集上不同算法的精確率對比Fig.5 Comparison of precision for different algorithms on synthetic datasets

圖6 為HSDFOD 和對比算法在4 個人工數(shù)據(jù)集下AUC值的對比。從圖6 可以清晰地看出HSDFOD 在A1～A3 數(shù)據(jù)集上的AUC 值都是最高的。由于實驗時選取top-n數(shù)據(jù)點計算AUC 值，因此在A3 數(shù)據(jù)集中HSDFOD 的AUC 值和精確率一樣都是1。人工數(shù)據(jù)集A3 和A4 下的各算法AUC 值都較為接近，但HSDFOD 的AUC 值排名靠前。綜合上述的分析可以看出，HSDFOD 在4 個人工數(shù)據(jù)集下AUC 值表現(xiàn)依然很出色，雖然在A4 數(shù)據(jù)集下AUC 值稍低于SOD 算法，但整體來看HSDFOD 的AUC 值表現(xiàn)是優(yōu)秀的，從而進一步驗證了HSDFOD 能準確有效地檢測離群點。

圖6 人工數(shù)據(jù)集上不同算法的AUC對比Fig.6 Comparison of AUC for different algorithms on synthetic datasets

圖7 為HSDFOD 和對比算法在4 個人工數(shù)據(jù)集下的離群點發(fā)現(xiàn)曲線。從圖7 可以看出，HSDFOD 的離群點發(fā)現(xiàn)曲線均在對比算法的離群點發(fā)現(xiàn)曲線之上，表明HSDFOD 在指定查詢數(shù)據(jù)點的前提下比其他對比算法更能有效檢測出潛在的離群點。尤其在A3 數(shù)據(jù)集上，HSDFOD 的離群點發(fā)現(xiàn)曲線是一條斜率為0.5 的直線，表明HSDFOD 檢測出的前40 個數(shù)據(jù)點均為離群點。綜合上述的分析可以看出，在4 種復雜分布的人工數(shù)據(jù)集下，HSDFOD 的離群點發(fā)現(xiàn)曲線表現(xiàn)都為最優(yōu)，驗證了HSDFOD 使用局部信息圖和全局信息圖能有效提高算法的離群點檢測性能。算法能很好地適用各種有復雜分布的數(shù)據(jù)集，并且有較好的檢測精度和穩(wěn)定性。

圖7 人工數(shù)據(jù)集上不同算法的離群點發(fā)現(xiàn)曲線對比Fig.7 Comparison of outlier discovery curve for different algorithms on synthetic datasets

圖8 是HSDFOD 和對比算法在人工數(shù)據(jù)集上運行時間的對比。通過圖8 可見，HSDFOD 在人工數(shù)據(jù)集A1、A2 和A4 上的運行時間都是最少的，在A3數(shù)據(jù)集上比SOD算法運行時間長，與IForest 算法和HBOS 算法運行時間相近。綜合上述的分析可以看出，HSDFOD 在4 個人工數(shù)據(jù)集上運行時間整體上少于其他4 個對比算法。因此可以得出HSDFOD 雖然時間復雜度為O(n2)，但在人工數(shù)據(jù)集上的運行效率整體較好。

圖8 人工數(shù)據(jù)集上不同算法的效率對比Fig.8 Comparison of efficiency for different algorithms on synthetic datasets

3.3 真實數(shù)據(jù)集實驗

本文選用的4 個真實數(shù)據(jù)集均來自UCI 數(shù)據(jù)集，數(shù)據(jù)集的維度在7～32，離群點占比在4.0%～35.8%。表3 展示了真實數(shù)據(jù)集的數(shù)據(jù)特征，由表3 可見，本文選用的真實數(shù)據(jù)集擁有較廣泛離群點比例和數(shù)據(jù)點維度，使用這些數(shù)據(jù)集能更加全面且真實地展示各種離群點檢測算法的實際檢測能力。

表3 真實數(shù)據(jù)集的數(shù)據(jù)特征Tab.3 Data characteristics of real datasets

圖9 給出了HSDFOD 和對比算法在真實數(shù)據(jù)集下精確率的比較。從圖9 可見，在WDBC 數(shù)據(jù)集上HSDFOD 的精確率達到了90%以上，而對比算法的精確率均在50%左右，HSDFOD 在該數(shù)據(jù)集的精確率遠超對比算法的精確率。HSDFOD 在Ionosphere 數(shù)據(jù)集上的精確率為84.1%，精確率優(yōu)于對比算法。在Ecoli 數(shù)據(jù)集上，HSDFOD、SUOD 算法和IForest 算法的精確率均為80%。HSDFOD 在WBC 數(shù)據(jù)集上的精確率略低于SUOD 算法，但仍然有80%的精確率。綜上分析，可以看出HSDFOD 在4 個真實數(shù)據(jù)集上整體精確率的表現(xiàn)優(yōu)于對比算法，而且算法性能較為穩(wěn)定，精確率均能保持在80%以上。因此，通過精確率的比較分析，驗證了HSDFOD通過利用全息圖能正確有效地檢測離群點，精確率較高。

圖9 真實數(shù)據(jù)集上不同算法的精確率對比Fig.9 Comparison of precision for different algorithms on real datasets

圖10是HSDFOD 和對比算法在真實數(shù)據(jù)集下的AUC值。由圖10 可以看出，HSDFOD 在4 個數(shù)據(jù)集上的AUC 值均超過0.9，并且AUC 值均優(yōu)于對比算法。因此，通過對4 個真實數(shù)據(jù)集上的AUC 值的比較，發(fā)現(xiàn)HSDFOD 具有較高的穩(wěn)定性，驗證了HSDFOD能正確檢測離群點，有較好的檢測性能。

圖10 真實數(shù)據(jù)集上不同算法的AUC對比Fig.10 Comparison of AUC for different algorithms on real datasets

圖11 是HSDFOD 和對比算法在真實數(shù)據(jù)集下離群點發(fā)現(xiàn)曲線的比較。通過圖11 可看出HSDFOD 在WDBC 數(shù)據(jù)集和Ionosphere 數(shù)據(jù)集的離群點發(fā)現(xiàn)曲線明顯處于對比算法的離群點發(fā)現(xiàn)曲線上方。在WBC 數(shù)據(jù)集上，HSDFOD 在查詢數(shù)據(jù)點數(shù)為6～12 時，查詢出的離群點數(shù)比SUOD 算法、IForest 算法和HBOS 算法少，但當查詢數(shù)據(jù)點數(shù)達到14 時，檢測出和對比算法同樣多的離群點。HSDFOD 在Ecoli 數(shù)據(jù)集上和對比算法的表現(xiàn)類似，但整體好于SOD 算法的離群點發(fā)現(xiàn)曲線。綜上所述可以發(fā)現(xiàn)，HSDFOD 的離群點發(fā)現(xiàn)曲線雖然不是在4 個真實數(shù)據(jù)集中都優(yōu)于對比算法，但整體的離群點發(fā)現(xiàn)曲線遠優(yōu)于對比算法，而且HSDFOD 的穩(wěn)定性好于對比算法。因此，通過在離群點發(fā)現(xiàn)曲線指標上的比較，驗證了HSDFOD 在真實數(shù)據(jù)集上不僅能正確檢測離群點，并且算法有較好穩(wěn)定性。

圖11 真實數(shù)據(jù)集上不同算法的離群點發(fā)現(xiàn)曲線對比Fig.11 Comparison of outlier discovery curve for different algorithms on real datasets

圖12是HSDFOD和對比算法在真實數(shù)據(jù)集上運行時間的對比。

圖12 真實數(shù)據(jù)集上不同算法的效率對比Fig.12 Comparison of efficiency for different algorithms on real datasets

通過圖12 可以看出，HSDFOD 在真實數(shù)據(jù)集WBC、Ecoli上的運行時間都是最少的。在真實數(shù)據(jù)集WDBC、Ionosphere上，HSDFOD和SOD算法的運行時間均少于SUOD算法、Iforest算法和HBOS算法，HSDFOD的運行時間僅多于SOD算法。綜上可以看出，HSDFOD在4個真實數(shù)據(jù)集上運行時間整體上少于其他4 個對比算法。因此可以得出HSDFOD 在真實數(shù)據(jù)集上的運行效率整體上是好于對比算法的。

綜上，由于本文算法既考慮了基于圖的離群點檢測方法中僅使用數(shù)據(jù)的全局分布信息會導致忽略局部離群點的問題，也考慮了只使用數(shù)據(jù)的局部信息會造成“懸空鏈接”問題，因此本文提出的基于全息圖平穩(wěn)分布因子的離群點檢測算法能更有效全面地檢測離群點。

4 結語

本文提出了基于全息圖平穩(wěn)分布因子的離群點檢測算法。首先為獲取數(shù)據(jù)點的局部信息，提出了一種自適應k值的生成方法獲取數(shù)據(jù)點的局部鄰居；然后通過獲取的局部鄰域信息，生成局部信息圖，再通過最小生成樹和相似矩陣生成全局信息圖；最后綜合局部信息圖和全局信息圖為全息圖生成轉移概率矩陣，利用該轉移概率矩陣進行馬爾可夫隨機游走以完成離群點的檢測。實驗結果表明，通過同時考慮局部信息圖和全局信息圖的全息圖能很好地提高離群點的檢測精度。由于本文在構建局部信息圖和全局信息圖時都需要較高的時間復雜度，因此未來的工作方向是在保證準確率的條件下降低時間的復雜度。