離群點檢測的鄰近性方法綜述

劉財輝，劉地金

贛南師范大學 數學與計算機科學學院，江西 贛州 341000

數據的鄰近性度量可以分為相似性和相異性兩個方面，它們相互構成負相關關系。在數據挖掘應用中，通常用數據矩陣和相異性矩陣來表達這兩種特性，以此來評估對象之間的相似程度或相異程度[1]。

在離群點檢測中，鄰近性包括距離和密度兩種典型的近鄰方式。所以，基于鄰近性的離群點檢測方法包括基于距離的方法和基于密度的方法。前者是利用距離計算方法來衡量數據樣本的離群程度，后者則是對局部數據簇的密度情況來判斷數據局部離群程度[2]。

離群點被定義為一個顯著不同于其他數據分布的數據對象，通過分析離群點數據分布特征，可以從海量數據中挖掘異常信息、提取興趣模式等。因此離群點檢測（outlier detection）成為數據挖掘領域的研究熱點之一[3]。離群點檢測目的是通過數據挖掘方法找出不同于大規模數據中的異常點，并發現潛在的、有意義的知識。目前其廣泛應用于欺詐檢測[4-5]、醫療處理[6]、公共安全[7]、環境衛生[8]、圖像處理[9]、異常行為模式檢測[10]、軌跡異常檢測[11]等領域。傳統離群點的檢測方法眾多，一般經典的離群點檢測方法通常分為基于統計學的、基于聚類的、基于分類的和基于鄰近性的方法四大類[3]。

鄰近性方法的核心思想是定義出數據之間的鄰近性度量，并根據此度量的值判定離群點。其中比較典型的方法是基于距離的方法以及基于密度的方法，前者以距離體現鄰近性，后者以密度體現鄰近性[12]。

本文通過綜述基于鄰近性的離群點檢測方法，包括基于距離的檢測方法和基于密度的檢測方法。目前，梅林等[12]對傳統的離群點檢測方法和目前主流的檢測技術進行了系統化的綜述，但由于介紹的面比較廣，缺乏對某一小領域的精細研究。針對這個問題，文獻[13]對基于聚類領域的離群點檢測方法進行了綜述。為了完善離群點檢測方法在更加精細化鄰域的研究，本文提出了基于鄰近性的離群點檢測方法的綜述，目的是為后續科研人員從鄰近性方面進行離群點檢測研究做一個鋪墊，讓研究新人對鄰近性的離群點檢測方法有個快速的了解。

1 基于距離的檢測方法

基于距離的方法是通過計算數據點之間的距離來檢測離群值的，通常離最近的相鄰點很遠的數據點被認為是離群值。最常用的基于距離的離群點檢測定義集中于局部鄰域、k-最近鄰（KNN）[14]和傳統的距離閾值概念。Knorr 和Ng[15]最早對基于距離的異常值計算進行了研究。在接下來的章節中，將基于距離的方法分為以下幾類——使用k近鄰計算的基于距離的方法、基于求解集的方法、基于角度的方法、近鄰方法、修剪方法和與在數據流中的方法以及各方法的優缺點進行總結歸納。

1.1 k 近鄰法

使用k近鄰方法來檢測離群點與k近鄰分類不同，這些方法主要用于檢測全局離群點和局部離群點。首先，搜索每個記錄的k近鄰，然后使用這些近鄰計算離群值。其關鍵思想是利用鄰域信息來檢測離群值。

1.1.1 全局離群點檢測

在1998 年，Knorr 和Ng[15]提出了一種非參數方法，基于索引的算法和基于嵌套循環的算法，兩種算法的計算復雜度都為O(kN2)，前者，在數據集的維數增加時具有較好的擴展性，但是時間復雜度的估算僅考慮了搜素時間。后者，它不需要構造索引結構，把數據集劃分為邏輯塊，通過選擇每個邏輯塊裝入緩沖區的順序，實現輸入、輸出效率的改善。這與一些統計技術[16-17]形成了對比。但這兩種算法的局限性是用戶缺乏關于底層分布的知識。

后來Ramaswamy 等[18]提出了一種基于網格單元的對N線性、對K指數的算法，對之前的算法[15]進行了優化。與前兩種方法相比，其計算復雜度較低，適用于大規模數據集的異常值檢測，但當數據集的維數增加時，它的可擴展性較差。在文獻[15]的擴展版本中，使用了KD-tree、X-tree 和R-tree[19]。Ghoting 等[20]提出了一種名為RBRP（recursive binning and reprojection）的算法，提高了高維數據集的計算速度，并改進了以往方法[15，18]的缺點。使用了近似近鄰，這使得計算量更少，計算速度更快，但是此方法的局限性是只適用于小數據集，對大數據集的擴展性不行。

Angiulli 等[21]的方法與傳統的方法有所不同，傳統的方法是開發技術來檢測輸入數據集中的異常值，而他們的方法可以學習模型并預測輸入數據集中的異常值。他們設計了一種基于距離的算法，可以從給定的未標記數據集中檢測頂級異常值，并預測一個未檢測到的數據點是否為異常值。該方法的局限性是將異常值看作是二元屬性，對檢測出的每個異常值不能給出異常的程度。

1.1.2 局部離群點檢測

2009年，研究人員將研究的方向轉向了局部距離的離群值檢測。Zhang等[22]提出了一種基于局部距離的離群值檢測方法，稱為基于局部距離的離群值因子（local distance-based outlier factor，LDOF）。與LOF[23]相比，在鄰居大小范圍內的性能有所提高。兩兩距離計算的需求為(O(k2) )，類似于COF[24]。在性能上可與k近鄰離群點檢測技術相媲美。但是，它對參數值不太敏感。Liu等[25]在后來的研究中，將傳統的LOF擴展到不確定數據。

文獻[26]給每個對象分配一個孤立程度，通過將孤立程度進行排序判定離群點。提出了一種基于近鄰傳播的離群點檢測算法，引入放大因子。與top-nLDOF算法[22]相比，增大了算法對離群點的敏感性，以此提高算法的準確性。該方法放大離群點的離群因子，擴大與正常點的差異，很好地提高了檢測的準確性與效率，但是該算法對離群點的敏感度不太理想，針對此方法的靈敏度改進將成為后續研究的有意義方向。

1.2 基于求解集（solving set）的離群點檢測方法

基于求解集的方法由Angiulli 等[27]提出，主要思想是利用一個求解集來求解離群點檢測問題。考慮圖1所示的例子，圖1（a）顯示了整個數據集，那么在圖1（b）中定義了一個求解集S={a,b,c}，用黑點表示。圖1（c）顯示了鄰域關系，其中實線箭頭表示數據集中對象的第一個和第二個鄰域，虛線箭頭表示求解集對象的第二種鄰域。

為了計算離群點檢測問題的求解集，相繼提出了三種算法：Solving Set 算法、Robust Solving Set 算法和Minimal Robust Solving Set 算法，以適用于不同情形。這個方法的主要優點是計算時間短，因為它只計算到求解集合對象的鄰域距離，而不是整個數據集。

1.3 基于角度的離群點檢測ABOD方法

數據維數的增加導致了所謂的“維數災難”，這意味著比較距離變得十分困難。文獻[28]提出了一種新的方法，稱為基于角度的離群點檢測ABOD 方法，該方法仍然使用距離，但也考慮了所有數據對象的角度方差。該方法觀察每個對象的角度方差，并計算一個名為CBOF 的離群因子，對象離聚類越遠，CBOF 越小，角度方差越小（見圖2）。

圖2顯示了ABOD方法檢測異常值的過程，p為異常值，可以清楚地觀察到內露層的角度比異常值的角度要寬，即γ的角度要大于α和β的角度。實驗結果表明，該方法具有較高的查全率和查準率。

1.4 反向近鄰方法

Radovanovic 等[29]提出了一種反向最近鄰方法來解決計算高維數據集異常值檢測的問題，可以有效地應用于低維度和高維環境。Huang等[30]采用自然鄰域的概念來獲取鄰域的信息。Ha等[31]提出了一種利用迭代隨機抽樣確定k合適值的啟發式方法。Tang 等[32]提出了一種在局部KDE中確定離群值的方法。他們研究了反向最近鄰、共享最近鄰和k個最近鄰。基于鄰域的檢測方法獨立于數據分布模型，易于理解和解釋。然而，它們對參數設置很敏感，有時還存在性能缺陷。

文獻[33]針對分布復雜且離群類型多樣的數據集進行離群檢測困難的問題，提出基于相對距離的反k近鄰樹離群檢測方法RK-NMOD（reversedK-nearest neighborhood）。該方法定義了對象的相對距離，能同時有效檢出全局和局部離群點。該方法結合了經典距離、對象局部密度、對象鄰域關系。

1.5 其他近鄰方法

Huang 等[34]提出了一種名為基于秩的檢測算法（RBDA）的方法來對鄰居進行排序，確保了高維數據的本質變得有意義。在文獻[35]中說明，當物體從相同的機制中產生時，它們會彼此靠近或共享相似的鄰居。后來，Bhattacharya 等[36]提出了一種進一步使用最近鄰秩和反向最近鄰秩的方法，確保能有效地測量每個候選對象的離群值。為了提高搜索效率，Wang 等[37]增加了使用最小生成樹。

文獻[38]提出一種基于隨機距離方法的排名模型框架（RAMODO），利用很少的標記數據作為先驗知識來學習，可以非常低維地表示超高維數據。這種基于隨機距離的學習方法讓離群值檢測器獲得更好的性能和速度，所需的標記數據也更少，在內存上，至少獲得了兩個數量級的加速，降低了空間復雜度。

文獻[39]針對k近鄰的標簽噪聲過濾對近鄰參數k的選取較敏感的問題，提出了近鄰感知（perception of nearest neighbors，PNN）的標簽噪聲過濾算法，可有效解決二分類數據集的類內標簽噪聲的問題。相比經典過濾算法，PNN獲得更優的噪聲識別效果，顯著提升模型的泛化能力。PNN 對于多分類數據的噪聲過濾具有一定借鑒意義。

1.6 修剪方法

Bay 等[40]提出了一種基于嵌套循環的算法，該算法使用了隨機化和剪枝規則，能夠在之前方法中顯示二次性能的數據集上獲得接近線性的時間[15]。然而，算法做了大量的假設，從而導致性能較差。針對文獻[15，18-19]都無法同時滿足CPU 成本和最小化I/O 成本的需求，Angiulli等[41]提出了一種名為將離群值將數據推入索引（DOLPHIN）的新算法來解決這些問題，只對數據集進行兩次順序掃描。

Ren等[42]提出了Ramaswamy等技術[18]的改進版本，這是一種基于垂直距離的離群點檢測方法，該方法通過p-樹兩階段（帶剪枝和不帶剪枝）進行離群點檢測。Vu等[43]引入了MIRO（multirule outlier），MIRO采用了與文獻[42]相似的技術，使用剪枝技術來加快異常值的檢測過程。

1.7 在數據流中的方法

隨著大數據的到來，許多傳入的數據是連續流的形式。對于基于距離的方法，面臨著重大的挑戰，如時間概念、多維度、概念漂移和不確定性問題[44]。這類數據的挖掘高度依賴于時間間隔。兩個著名的數據流窗口模型是邊界和滑動窗口[45]。前一種方法，首先確定數據流中的一個時間點，然后分析最后一個時間點和當前時間點之間的時間點；后者方法，窗口由兩個滑動端點標記。

Angiulli等[45]提出了一種對數據流中離群值進行一次性查詢的新思路，不同于文獻[46-47]提出的連續查詢方法。他們提出了三種stream outlier miner（STORM）算法。第一種是精確算法（exact-storm），使用流管理器和合適的數據結構，缺點是存儲所有窗口對象的開銷且它不能裝入內存。后兩種算法側重于檢測近似結果，目標是通過只保留安全內層的受控部分來最小化內存使用。Yang等[48]提出了一些方法（Abstract-C、Abstract-M、Exact-N、Extra-N）來處理數據流上滑動窗口場景中基于鄰接模式的增量檢測。該方法解決了處理滑動窗口的問題，這是早期基于增量DBSCAN 算法[49]不支持的問題。它顯示了更少的CPU 使用，并且它保持了窗口中對象數量的線性內存使用。

Kontaki 等[50]提出的算法解決了數據流事件檢測中的一些問題[51]和數據流上滑動窗口場景中的事件檢測[48]。在Angiulli等的技術[51]中，在檢測離群值的過程，有兩種算法使用滑動窗口與階躍函數并行。文獻[50]的主要目標是最小化存儲消耗，提高算法效率，并使其更加靈活。Cao 等[52]提出一種稱為ThreshLEAP 的算法。它是一種試圖減輕昂貴的范圍查詢的技術，通過不相同的窗口中存儲數據點來實現的。利用現代分布式多核集群來提高可伸縮性的異常值檢測是未來研究的一個感興趣方向。

1.8 與粗糙集結合的方法

文獻[53]將傳統的基于距離的離群點檢測方法[15]與基于粗糙集邊界的離群點檢測方法[54]結合在一起，提出了一種基于邊界和距離的離群點檢測方法。該方法借助粗糙集在處理不確定與不完備數據方面的優勢，能夠從不確定與不完整的數據中高效地檢測出離群點，設計了相應的離群點檢測算法BDOD，該方法創新性比較高，是原有方法的有機結合和擴展。

文獻[55]設計并實現了基于鄰域值差異度量的離群點檢測（NVDMOD）算法，該方法利用鄰域粗糙集的粒化特征提出了改進的鄰域值差異度量（NVDM）方法進行離群點檢測。N-VDMOD 算法具有更好的適應性和有效性，為混合型屬性數據集的離群點檢測提供了一條更有效的新途徑。

2 基于距離的方法

2.1 優點

（1）它們是直接和容易理解的，因為它們大多不依賴假設的分布來擬合數據。

（2）在可伸縮性方面，它們在多維空間中的可伸縮性更好，因為它們有一個健壯的理論基礎，而且與統計方法相比，它們的計算效率更高。

2.2 缺點、挑戰和差距

（1）在高維空間上，因為它們的性能由于“維數災難”而下降。數據中的對象通常具有離散屬性，這使得定義這些對象之間的距離具有挑戰性。

（2）使用基于距離的方法時，在高維空間中的鄰域搜索和KNN搜索等搜索技術是一項開銷大的任務。在大型數據集中，可伸縮性也不具有成本效益。

（3）現有的基于距離的方法大多處理數據流都比較困難，原因是難以保持數據在局部鄰域的分布，以及難以找到數據流中的KNN。專門為處理數據流而設計的方法例外。

同時，面臨著一些挑戰。大多數基于距離的方法的一個重要缺點是，它們不能很好地適應非常高維的數據集[56]。當數據維數增長時，這將影響距離度量的描述能力，在多元數據集中，計算數據實例之間的距離可能需要大量的計算，從而導致缺乏可伸縮性。未來面臨的挑戰是：如何同時解決低內存成本和計算時間的問題。為了解決二次復雜性的問題，提出了幾種優化方法，如應用緊湊的數據結構[20，57]，使用剪枝和隨機化[40]等。對于k-最近鄰方法，數據集在確定最佳KNN 分數方面起著至關重要的作用，在需要閾值時選擇合適的閾值是最復雜的任務之一。

在表1中，提出了一系列典型的基于距離的離群點檢測算法。從計算復雜度（運行時間和內存消耗）、解決問題和缺點等方面對不同的技術進行了總結。基于距離的方法由于具有較強的理論基礎和計算效率而被廣泛采用。

表1 基于距離的算法綜述Table 1 Overview of distance-based algorithms

3 基于密度的檢測方法

將基于密度的方法應用于離群點檢測是已知的最早的離群點檢測方法之一。基于密度的離群點檢測方法的核心原理是在低密度區域可以找到一個離群點，而非離群點（inliers）則假設出現在密集的鄰域。在基于密度的離群點檢測方法中，與基于距離的方法相比，應用了更復雜的機制來建模離群點。盡管如此，基于密度的方法的簡單和有效性使它們被廣泛地采用來檢測離群點。

3.1 經典LOF算法

Breunig 等[59]提出了局部離群因子（local outlier factor，LOF）方法，這是最早的基于基本松散相關密度的聚類離群值檢測方法之一。該技術利用了k近鄰，LOF 的目的是為多維數據集中的每個數據對象分配一個離群值（見圖3）。

數據對象p的局部離群因子計算為其局部密度與其k近鄰的密度之比。LOF是局部的，因為它只考慮對象的受限制的鄰居。以圖3為例，可以看到兩個簇“C1”和“C2”有不同的密度分布。使用基于距離的方法，不能將點“o2”識別為離群值。這就是LOF 通過使用局部離群值的概念而優于使用距離概念方法的地方。與其他異常值檢測方法相比，LOF能夠識別出更有意義的局部異常值。

3.2 LOF算法的改進方法

由于LOF 沒有有效索引的缺點，Schubert 等[60]發現LOF 密度估計可以簡化，他們提出了一種簡化的LOF，用KNN距離代替LOF的可達距離。盡管簡化了的LOF表現出了改進的性能，但其計算復雜度與LOF相似。

Tang 等[61]提出了對LOF[59]的改進和簡化的LOF[60]，稱之為基于連接的離群值因子（COF）。COF 使用鏈距離作為估計鄰居的局部密度的最短路徑，這種方法的缺點是對數據分布作了間接的假設，從而導致不正確的密度估計。然而，在LOF中哪個閾值可以被認為是離群值仍然是令人困惑的。Kriegel等[62]隨后為一種被稱為“局部離群值概率”（LoOP）的離群值檢測方法制定了一種更穩健的局部密度估計，試圖解決LOF輸出異常值而不是異常概率的問題。使用LoOP 的概率評分的優點是，可以更好地比較不同數據集的離群值記錄。

文獻[63]提出了一種基于譜嵌入和局部密度的離群點檢測算法。該算法采用迭代策略對不重要的特征向量進行高效篩查。該算法對參數的設置不敏感。提出了一種可廣泛應用于局部非線性子空間中離群點檢測的譜嵌入方法（LODES）。Momtaz等[64]在計算局部離群值時，通過為每個對象提供一個稱為動態窗口離群值因子（DWOF）的分數來檢測前n個離群值。該算法是Fan 等[65]基于分辨率的離群因子（ROF）算法的改進版本。ROF 克服了精度低和對數據集參數的高靈敏度等缺點。

3.3 處理多粒度問題

在LOF[59]和COF[61]中，這些方法都不能正確處理多粒度問題。Papadimitriou 等[66]提出了一種名為LOCI 的局部相關積分技術及其離群值度量多粒度偏差因子（MDEF）來處理這一缺陷。該方法能很好地處理特征空間中的局部密度變化，同時也能檢測出遙遠的聚類和隱蔽的離群點。雖然LOCI 表現出良好的性能，但運行時間較長。Papadimitriou 等[66]提出了LOCI 的近似版本aLOCI。對四叉樹進行了約束，來提高兩個鄰域的計數速度。

Ren 等[67]提出了LOF[59]和LOCI[66]結合的方法，與現有的方法相比，LOF[59]和LOCI 結合對聚類中深度的數據點具有剪枝能力，因此效率更高。提出了一種稱為相對密度因子（RDF）的方法，RDF 是離群值的程度度量，離群點是具有高RDF 值的點。文獻[68]針對不確定數據集的離群點檢測問題，提出了基于密度的不確定數據的局部離群因子ULOF（uncertain local outlier factor）算法。結合傳統的LOF算法推導出ULOF算法，優化后的方法有效地提高了異常檢測準確率，降低了時間復雜度，改善了不確定數據的異常檢測性能。

3.4 結合k 近鄰方法

Jin等[69]提出了受影響離群度（INFLO）的方法，利用對稱鄰域關系來挖掘離群值。在LOF中，沒有給出正確計算集群邊界實例的得分的方法。INFLO 解決了這一缺點。INFLO對引用集和背景集使用不同的鄰域描述，使用k近鄰和反向近鄰計算INFLO 得分。圖4 顯示了一個對象p的INFLO 影響空間(kIS(p))如何包括它的KNN(p)和它的反向RKNN(p)。

INFLO 值越高，該對象屬于異常值的概率越高。Cao 等[70]提出了一種新的基于密度的局部離群點檢測（UDLO）概念，該概念針對具有離散實例特征的不確定性數據，建議使用一種精確的算法來計算實例的密度。然而，只應用了歐幾里德距離度量。利用其他距離計算方法來優化算法可以作為未來的研究方向。

文獻[71]針對INFLO 算法[69]存在需要對所有數據不加區分的計算其k近鄰和反向k近鄰點集的不足，提出了局部密度離群點檢測算法LDBO，引入強k近鄰點和弱k近鄰點概念。在準確率不低于INFLO 算法的前提下，LDBO 算法的檢測時間是相較LOF 和INFLO 算法中最少的。該方法的執行時間在一定范圍內受μ值選取的影響較大，但總體上看算法執行時間還是優于前兩種算法。

Keller 等[72]提出了一種高對比子空間方法（HiCS），改進了離群值得分密切相關的離群值的評估和排序。基于隔離機制的靈感，Bandaragoda 等[73]提出一種基于最近鄰隔離的異常檢測方法iNNE（nearest neighbour ensemble），另一種用于子抽樣構建模型的離群點檢測方法LeSiNN[74]，iNNE 和LeSiNN 都使用了一個集成來保證離群點檢測器的穩定性。在具有數千維或數百萬實例的數據集中，iNNE 的運行速度比之前基于最近鄰的方法（如LOF）快得多，主要因為該方法具有線性時間復雜度和常數空間復雜度。該方法的優勢是彌補了之前方法的三個缺陷，即無法檢測局部異常、相關屬性較少的異常以及異常被正常實例包圍。

Campello 等[75]將關注點從局部離群值擴展到全局離群值，提出了一種稱為全局-局部層次離群值得分（GLOSH）的算法。它基于一個完整的統計解釋，能夠同時檢測全局和局部離群值類型。它對不同的任務都具有良好的擴展性，但該研究是基于特定的k近鄰密度估計，存在一定的局限性。

3.5 數據流中的檢測方法

Wu 等[76]提出了一種檢測大數據流中離群點的算法。他們使用了一種稱為RS-Forest的快速而準確的密度估計器和一種半監督類機器學習算法。Bai等[77]考慮了大數據中基于密度的離群點檢測，提出了分布式LOF計算（DLC）方法，并行檢測離群點。然而，盡管性能有所提高，但與Lozano等[78]的PLOFA算法相比，它的可伸縮性仍然不佳。文獻[79]將局部離群點檢測的靜態數據擴展到流形數據的離群點檢測，提出了基于局部相關維度的流形離群點檢測算法LCDO（local-correlationdimension-based outlier detection），實驗觀察發現在1維和2維的流形上做了論證，為之后處理流形數據的離群點檢測問題提供了良好的理論基礎。

Na 等[80]對現有LOF 的數據流算法存在的兩個限制：需要大量內存和不能檢測到長序列的離群點。提出了一種新的數據流離群點檢測算法DILOF。DILOF 在準確性和執行時間方面顯著優于現有的算法。Qin等[81]提出了局部離群值語義的概念，通過利用內核密度估計（aKDE）來有效地從流數據中檢測局部離群值。KELOS 是基于抽象核心中心的aKDE 策略，aKDE 可以準確而有效地估計每個點上的數據密度。aKDE和內部剪枝策略共同消除了流局部離群點檢測的性能瓶頸。

文獻[82]針對現有數據流離群點檢測算法在面對海量高維數據流時普遍存在運算時間過長的問題，提出一種引入局部向量點積密度的高維數據流離群點快速檢測算法。以保存少量中間結果的方式只對窗口內受影響的數據點進行增量計算。該算法可以在保證檢測準確性的情況下有效提高數據流的離群點檢測效率，并且可擴展至并行環境進行并行加速。

3.6 基于相對密度的方法

Vázquez 等[83]提出了一種新的基于數據低密度模型的異常點檢測算法，稱為稀疏數據觀察者（SDO）。SDO 降低了大多數懶惰學習者OD 算法的二次復雜度。Ning等[84]提出了一種基于相對密度的OD方法，該方法使用一種新技術來測量物體的鄰域密度。Su等[85]提出了一種高效的基于密度的方案，該方案基于局部OD法，用于處理分散的數據，稱為E2DLOS。將局部離群因子重新命名為局部偏離系數（LDC）。該方法在LDC和RCMLQ的基礎上，在檢測精度和時間效率上對現有的局部離群點檢測方法進行了改進。

文獻[86]將依據正常點與離群點相對密度的差異性計算每個對象的離群值，將離群值高的對象判定為離群點的方法引入并提出了一種生成對抗網絡（generative adversarial network，GAN）與變分自編碼器（variational auto-encoder，VAE）結合的GAN-VAE 算法。模型的判別器能學習正常點與離群點的分類邊界，生成更多潛在離群點。該算法在準確率和F1值上均有較大提高。

3.7 高維數據的檢測方法

文獻[87]提出了基于鄰域密度的高維異構數據局部離群點挖掘算法，首先對高維數據進行區域分割，然后采取核密度來描述局部密度，計算出數據鄰域密度，從而判斷異構數據中的離群點。該方法幾乎不受數據量和數據維數改變的影響，其挖掘時間和覆蓋率指標也較優。文獻[88]針對離群點檢測算法LOF 在高維離散分布數據集中檢測精度較低及參數敏感性較高的問題，提出了基于鄰域系統密度差異度量的離群點檢測NSD（neighborhood system density difference）算法。NSD算法簡單易用，在檢測偏離程度較大的目標對象時會大幅降低計算開銷。

文獻[89]在LOF的基礎上結合粗糙集理論，引入屬性權值概念，提出了一種基于粗約簡和網格的離群點檢測算法RRGOD（outliers detecting based on rough reduction and grid）。通過淘汰屬性權值低于重要度閾值的屬性來降低維度，從而減少了后續的計算量。文獻[90]提出一種基于局部線性嵌入的離群點檢測方法（OLLE），是針對高維數據的降維方法。算法使數據集的下近似中的點保持局部線性結構，保證在降維的過程中使離群點遠離正常點。該方法的優勢是將數據集從高維空間降至低維空間的過程能很好地保持數據的局部幾何結構，且在檢測離群點時，一定范圍內對k不敏感。

在表2中對經典算法進行了整理，展示了在上述一些關鍵算法的進展。

表2 基于密度的算法綜述Table 2 Overview of density-based algorithms

4 基于密度的方法

4.1 優點

（1）在基于密度的方法中，使用的密度估計是非參數的，它們不依賴于假設的分布來擬合數據。

（2）一些基于密度的技術[59，62，66，69]已經成為許多后續算法的基本算法。它們的衍生算法通常優于它們的競爭對手，如一些基于統計和基于距離的方法[91-93]。這些方法中的離群值通常是通過對象的鄰域密度[59]來分析的[66]，其在識別其他大多數基于離群值檢測的方法所遺漏的關鍵離群值方面更有優勢。它們只需要最小的先驗知識，如概率分布和只需要一個參數調整。它們還以高效計算局部離群值的能力而聞名。

4.2 缺點、挑戰和差距

（1）雖然一些基于密度的方法顯示出了更好的性能，但與統計方法相比，它們更加復雜，計算成本更高[94]。它們對參數設置很敏感，比如確定鄰居的大小。它們需要謹慎地考慮幾個因素，這導致了昂貴的計算。對于不同密度的區域，它使性能變得更復雜并導致性能低下。

（2）由于其固有的復雜性和缺乏對離群值度量的更新，如INFLO 和MDEF 算法，不能靈活地處理數據流。當離群值之間的關系非常密切時，這對于高維數據也是一個挑戰。

（3）由于大多數基于密度的方法依賴于最近鄰計算，這使得k的選擇對于這些算法的評估非常重要。

（4）基于密度的方法雖然檢測的精準度比較高，但其復雜程度也更高，所以接下來將該方法的復雜性降低和在高維大數據集中，能有效降低計算復雜度，將是研究的重點和挑戰。

5 結語

基于鄰近性的離群點檢測方法思想基本上貫穿于整個離群點檢測過程中，依靠鄰近性的思維能挖掘發現很多相似與相異的關系。本文將鄰近性劃分為基于距離和基于密度的兩個分支，主要從鄰近性角度對現有的離群點檢測技術進行了歸納和分析。在離群點檢測鄰域，大量的方法針對不同的問題被提出，無論是基于統計的，基于聚類的，還是基于鄰近性的方法，在面對現在大規模高維度數據集，檢測都還存在一定局限性，隨著大數據、云計算和分布式的發展，相信這些檢測方法還能有更大突破。基于鄰近性的離群點檢測算法，最大的優點就是直觀，易于理解，缺點是考慮的鄰近性中的數據都要進行考慮。算法的計算復雜度如何降低、如何有效地處理高維大數據集等方向將成為以后研究的重點和熱點。