劉財(cái)輝，劉地金

贛南師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，江西 贛州 341000

數(shù)據(jù)的鄰近性度量可以分為相似性和相異性兩個(gè)方面，它們相互構(gòu)成負(fù)相關(guān)關(guān)系。在數(shù)據(jù)挖掘應(yīng)用中，通常用數(shù)據(jù)矩陣和相異性矩陣來(lái)表達(dá)這兩種特性，以此來(lái)評(píng)估對(duì)象之間的相似程度或相異程度[1]。

在離群點(diǎn)檢測(cè)中，鄰近性包括距離和密度兩種典型的近鄰方式。所以，基于鄰近性的離群點(diǎn)檢測(cè)方法包括基于距離的方法和基于密度的方法。前者是利用距離計(jì)算方法來(lái)衡量數(shù)據(jù)樣本的離群程度，后者則是對(duì)局部數(shù)據(jù)簇的密度情況來(lái)判斷數(shù)據(jù)局部離群程度[2]。

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

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

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

1 基于距離的檢測(cè)方法

基于距離的方法是通過(guò)計(jì)算數(shù)據(jù)點(diǎn)之間的距離來(lái)檢測(cè)離群值的，通常離最近的相鄰點(diǎn)很遠(yuǎn)的數(shù)據(jù)點(diǎn)被認(rèn)為是離群值。最常用的基于距離的離群點(diǎn)檢測(cè)定義集中于局部鄰域、k-最近鄰（KNN）[14]和傳統(tǒng)的距離閾值概念。Knorr 和Ng[15]最早對(duì)基于距離的異常值計(jì)算進(jìn)行了研究。在接下來(lái)的章節(jié)中，將基于距離的方法分為以下幾類——使用k近鄰計(jì)算的基于距離的方法、基于求解集的方法、基于角度的方法、近鄰方法、修剪方法和與在數(shù)據(jù)流中的方法以及各方法的優(yōu)缺點(diǎn)進(jìn)行總結(jié)歸納。

1.1 k 近鄰法

使用k近鄰方法來(lái)檢測(cè)離群點(diǎn)與k近鄰分類不同，這些方法主要用于檢測(cè)全局離群點(diǎn)和局部離群點(diǎn)。首先，搜索每個(gè)記錄的k近鄰，然后使用這些近鄰計(jì)算離群值。其關(guān)鍵思想是利用鄰域信息來(lái)檢測(cè)離群值。

1.1.1 全局離群點(diǎn)檢測(cè)

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

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

Angiulli 等[21]的方法與傳統(tǒng)的方法有所不同，傳統(tǒng)的方法是開(kāi)發(fā)技術(shù)來(lái)檢測(cè)輸入數(shù)據(jù)集中的異常值，而他們的方法可以學(xué)習(xí)模型并預(yù)測(cè)輸入數(shù)據(jù)集中的異常值。他們?cè)O(shè)計(jì)了一種基于距離的算法，可以從給定的未標(biāo)記數(shù)據(jù)集中檢測(cè)頂級(jí)異常值，并預(yù)測(cè)一個(gè)未檢測(cè)到的數(shù)據(jù)點(diǎn)是否為異常值。該方法的局限性是將異常值看作是二元屬性，對(duì)檢測(cè)出的每個(gè)異常值不能給出異常的程度。

1.1.2 局部離群點(diǎn)檢測(cè)

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

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

1.2 基于求解集（solving set）的離群點(diǎn)檢測(cè)方法

基于求解集的方法由Angiulli 等[27]提出，主要思想是利用一個(gè)求解集來(lái)求解離群點(diǎn)檢測(cè)問(wèn)題?？紤]圖1所示的例子，圖1（a）顯示了整個(gè)數(shù)據(jù)集，那么在圖1（b）中定義了一個(gè)求解集S={a,b,c}，用黑點(diǎn)表示。圖1（c）顯示了鄰域關(guān)系，其中實(shí)線箭頭表示數(shù)據(jù)集中對(duì)象的第一個(gè)和第二個(gè)鄰域，虛線箭頭表示求解集對(duì)象的第二種鄰域。

為了計(jì)算離群點(diǎn)檢測(cè)問(wèn)題的求解集，相繼提出了三種算法：Solving Set 算法、Robust Solving Set 算法和Minimal Robust Solving Set 算法，以適用于不同情形。這個(gè)方法的主要優(yōu)點(diǎn)是計(jì)算時(shí)間短，因?yàn)樗挥?jì)算到求解集合對(duì)象的鄰域距離，而不是整個(gè)數(shù)據(jù)集。

1.3 基于角度的離群點(diǎn)檢測(cè)ABOD方法

數(shù)據(jù)維數(shù)的增加導(dǎo)致了所謂的“維數(shù)災(zāi)難”，這意味著比較距離變得十分困難。文獻(xiàn)[28]提出了一種新的方法，稱為基于角度的離群點(diǎn)檢測(cè)ABOD 方法，該方法仍然使用距離，但也考慮了所有數(shù)據(jù)對(duì)象的角度方差。該方法觀察每個(gè)對(duì)象的角度方差，并計(jì)算一個(gè)名為CBOF 的離群因子，對(duì)象離聚類越遠(yuǎn)，CBOF 越小，角度方差越?。ㄒ?jiàn)圖2）。

圖2顯示了ABOD方法檢測(cè)異常值的過(guò)程，p為異常值，可以清楚地觀察到內(nèi)露層的角度比異常值的角度要寬，即γ的角度要大于α和β的角度。實(shí)驗(yàn)結(jié)果表明，該方法具有較高的查全率和查準(zhǔn)率。

1.4 反向近鄰方法

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

文獻(xiàn)[33]針對(duì)分布復(fù)雜且離群類型多樣的數(shù)據(jù)集進(jìn)行離群檢測(cè)困難的問(wèn)題，提出基于相對(duì)距離的反k近鄰樹(shù)離群檢測(cè)方法RK-NMOD（reversedK-nearest neighborhood）。該方法定義了對(duì)象的相對(duì)距離，能同時(shí)有效檢出全局和局部離群點(diǎn)。該方法結(jié)合了經(jīng)典距離、對(duì)象局部密度、對(duì)象鄰域關(guān)系。

1.5 其他近鄰方法

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

文獻(xiàn)[38]提出一種基于隨機(jī)距離方法的排名模型框架（RAMODO），利用很少的標(biāo)記數(shù)據(jù)作為先驗(yàn)知識(shí)來(lái)學(xué)習(xí)，可以非常低維地表示超高維數(shù)據(jù)。這種基于隨機(jī)距離的學(xué)習(xí)方法讓離群值檢測(cè)器獲得更好的性能和速度，所需的標(biāo)記數(shù)據(jù)也更少，在內(nèi)存上，至少獲得了兩個(gè)數(shù)量級(jí)的加速，降低了空間復(fù)雜度。

文獻(xiàn)[39]針對(duì)k近鄰的標(biāo)簽噪聲過(guò)濾對(duì)近鄰參數(shù)k的選取較敏感的問(wèn)題，提出了近鄰感知（perception of nearest neighbors，PNN）的標(biāo)簽噪聲過(guò)濾算法，可有效解決二分類數(shù)據(jù)集的類內(nèi)標(biāo)簽噪聲的問(wèn)題。相比經(jīng)典過(guò)濾算法，PNN獲得更優(yōu)的噪聲識(shí)別效果，顯著提升模型的泛化能力。PNN 對(duì)于多分類數(shù)據(jù)的噪聲過(guò)濾具有一定借鑒意義。

1.6 修剪方法

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

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

1.7 在數(shù)據(jù)流中的方法

隨著大數(shù)據(jù)的到來(lái)，許多傳入的數(shù)據(jù)是連續(xù)流的形式。對(duì)于基于距離的方法，面臨著重大的挑戰(zhàn)，如時(shí)間概念、多維度、概念漂移和不確定性問(wèn)題[44]。這類數(shù)據(jù)的挖掘高度依賴于時(shí)間間隔。兩個(gè)著名的數(shù)據(jù)流窗口模型是邊界和滑動(dòng)窗口[45]。前一種方法，首先確定數(shù)據(jù)流中的一個(gè)時(shí)間點(diǎn)，然后分析最后一個(gè)時(shí)間點(diǎn)和當(dāng)前時(shí)間點(diǎn)之間的時(shí)間點(diǎn)；后者方法，窗口由兩個(gè)滑動(dòng)端點(diǎn)標(biāo)記。

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

Kontaki 等[50]提出的算法解決了數(shù)據(jù)流事件檢測(cè)中的一些問(wèn)題[51]和數(shù)據(jù)流上滑動(dòng)窗口場(chǎng)景中的事件檢測(cè)[48]。在Angiulli等的技術(shù)[51]中，在檢測(cè)離群值的過(guò)程，有兩種算法使用滑動(dòng)窗口與階躍函數(shù)并行。文獻(xiàn)[50]的主要目標(biāo)是最小化存儲(chǔ)消耗，提高算法效率，并使其更加靈活。Cao 等[52]提出一種稱為T(mén)hreshLEAP 的算法。它是一種試圖減輕昂貴的范圍查詢的技術(shù)，通過(guò)不相同的窗口中存儲(chǔ)數(shù)據(jù)點(diǎn)來(lái)實(shí)現(xiàn)的。利用現(xiàn)代分布式多核集群來(lái)提高可伸縮性的異常值檢測(cè)是未來(lái)研究的一個(gè)感興趣方向。

1.8 與粗糙集結(jié)合的方法

文獻(xiàn)[53]將傳統(tǒng)的基于距離的離群點(diǎn)檢測(cè)方法[15]與基于粗糙集邊界的離群點(diǎn)檢測(cè)方法[54]結(jié)合在一起，提出了一種基于邊界和距離的離群點(diǎn)檢測(cè)方法。該方法借助粗糙集在處理不確定與不完備數(shù)據(jù)方面的優(yōu)勢(shì)，能夠從不確定與不完整的數(shù)據(jù)中高效地檢測(cè)出離群點(diǎn)，設(shè)計(jì)了相應(yīng)的離群點(diǎn)檢測(cè)算法BDOD，該方法創(chuàng)新性比較高，是原有方法的有機(jī)結(jié)合和擴(kuò)展。

文獻(xiàn)[55]設(shè)計(jì)并實(shí)現(xiàn)了基于鄰域值差異度量的離群點(diǎn)檢測(cè)（NVDMOD）算法，該方法利用鄰域粗糙集的?；卣魈岢隽烁倪M(jìn)的鄰域值差異度量（NVDM）方法進(jìn)行離群點(diǎn)檢測(cè)。N-VDMOD 算法具有更好的適應(yīng)性和有效性，為混合型屬性數(shù)據(jù)集的離群點(diǎn)檢測(cè)提供了一條更有效的新途徑。

2 基于距離的方法

2.1 優(yōu)點(diǎn)

（1）它們是直接和容易理解的，因?yàn)樗鼈兇蠖嗖灰蕾嚰僭O(shè)的分布來(lái)擬合數(shù)據(jù)。

（2）在可伸縮性方面，它們?cè)诙嗑S空間中的可伸縮性更好，因?yàn)樗鼈冇幸粋€(gè)健壯的理論基礎(chǔ)，而且與統(tǒng)計(jì)方法相比，它們的計(jì)算效率更高。

2.2 缺點(diǎn)、挑戰(zhàn)和差距

（1）在高維空間上，因?yàn)樗鼈兊男阅苡捎凇熬S數(shù)災(zāi)難”而下降。數(shù)據(jù)中的對(duì)象通常具有離散屬性，這使得定義這些對(duì)象之間的距離具有挑戰(zhàn)性。

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

（3）現(xiàn)有的基于距離的方法大多處理數(shù)據(jù)流都比較困難，原因是難以保持?jǐn)?shù)據(jù)在局部鄰域的分布，以及難以找到數(shù)據(jù)流中的KNN。專門(mén)為處理數(shù)據(jù)流而設(shè)計(jì)的方法例外。

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

在表1中，提出了一系列典型的基于距離的離群點(diǎn)檢測(cè)算法。從計(jì)算復(fù)雜度（運(yùn)行時(shí)間和內(nèi)存消耗）、解決問(wèn)題和缺點(diǎn)等方面對(duì)不同的技術(shù)進(jìn)行了總結(jié)?；诰嚯x的方法由于具有較強(qiáng)的理論基礎(chǔ)和計(jì)算效率而被廣泛采用。

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

3 基于密度的檢測(cè)方法

將基于密度的方法應(yīng)用于離群點(diǎn)檢測(cè)是已知的最早的離群點(diǎn)檢測(cè)方法之一?；诿芏鹊碾x群點(diǎn)檢測(cè)方法的核心原理是在低密度區(qū)域可以找到一個(gè)離群點(diǎn)，而非離群點(diǎn)（inliers）則假設(shè)出現(xiàn)在密集的鄰域。在基于密度的離群點(diǎn)檢測(cè)方法中，與基于距離的方法相比，應(yīng)用了更復(fù)雜的機(jī)制來(lái)建模離群點(diǎn)。盡管如此，基于密度的方法的簡(jiǎn)單和有效性使它們被廣泛地采用來(lái)檢測(cè)離群點(diǎn)。

3.1 經(jīng)典LOF算法

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

數(shù)據(jù)對(duì)象p的局部離群因子計(jì)算為其局部密度與其k近鄰的密度之比。LOF是局部的，因?yàn)樗豢紤]對(duì)象的受限制的鄰居。以圖3為例，可以看到兩個(gè)簇“C1”和“C2”有不同的密度分布。使用基于距離的方法，不能將點(diǎn)“o2”識(shí)別為離群值。這就是LOF 通過(guò)使用局部離群值的概念而優(yōu)于使用距離概念方法的地方。與其他異常值檢測(cè)方法相比，LOF能夠識(shí)別出更有意義的局部異常值。

3.2 LOF算法的改進(jìn)方法

由于LOF 沒(méi)有有效索引的缺點(diǎn)，Schubert 等[60]發(fā)現(xiàn)LOF 密度估計(jì)可以簡(jiǎn)化，他們提出了一種簡(jiǎn)化的LOF，用KNN距離代替LOF的可達(dá)距離。盡管簡(jiǎn)化了的LOF表現(xiàn)出了改進(jìn)的性能，但其計(jì)算復(fù)雜度與LOF相似。

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

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

3.3 處理多粒度問(wèn)題

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

Ren 等[67]提出了LOF[59]和LOCI[66]結(jié)合的方法，與現(xiàn)有的方法相比，LOF[59]和LOCI 結(jié)合對(duì)聚類中深度的數(shù)據(jù)點(diǎn)具有剪枝能力，因此效率更高。提出了一種稱為相對(duì)密度因子（RDF）的方法，RDF 是離群值的程度度量，離群點(diǎn)是具有高RDF 值的點(diǎn)。文獻(xiàn)[68]針對(duì)不確定數(shù)據(jù)集的離群點(diǎn)檢測(cè)問(wèn)題，提出了基于密度的不確定數(shù)據(jù)的局部離群因子ULOF（uncertain local outlier factor）算法。結(jié)合傳統(tǒng)的LOF算法推導(dǎo)出ULOF算法，優(yōu)化后的方法有效地提高了異常檢測(cè)準(zhǔn)確率，降低了時(shí)間復(fù)雜度，改善了不確定數(shù)據(jù)的異常檢測(cè)性能。

3.4 結(jié)合k 近鄰方法

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

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

文獻(xiàn)[71]針對(duì)INFLO 算法[69]存在需要對(duì)所有數(shù)據(jù)不加區(qū)分的計(jì)算其k近鄰和反向k近鄰點(diǎn)集的不足，提出了局部密度離群點(diǎn)檢測(cè)算法LDBO，引入強(qiáng)k近鄰點(diǎn)和弱k近鄰點(diǎn)概念。在準(zhǔn)確率不低于INFLO 算法的前提下，LDBO 算法的檢測(cè)時(shí)間是相較LOF 和INFLO 算法中最少的。該方法的執(zhí)行時(shí)間在一定范圍內(nèi)受μ值選取的影響較大，但總體上看算法執(zhí)行時(shí)間還是優(yōu)于前兩種算法。

Keller 等[72]提出了一種高對(duì)比子空間方法（HiCS），改進(jìn)了離群值得分密切相關(guān)的離群值的評(píng)估和排序。基于隔離機(jī)制的靈感，Bandaragoda 等[73]提出一種基于最近鄰隔離的異常檢測(cè)方法iNNE（nearest neighbour ensemble），另一種用于子抽樣構(gòu)建模型的離群點(diǎn)檢測(cè)方法LeSiNN[74]，iNNE 和LeSiNN 都使用了一個(gè)集成來(lái)保證離群點(diǎn)檢測(cè)器的穩(wěn)定性。在具有數(shù)千維或數(shù)百萬(wàn)實(shí)例的數(shù)據(jù)集中，iNNE 的運(yùn)行速度比之前基于最近鄰的方法（如LOF）快得多，主要因?yàn)樵摲椒ň哂芯€性時(shí)間復(fù)雜度和常數(shù)空間復(fù)雜度。該方法的優(yōu)勢(shì)是彌補(bǔ)了之前方法的三個(gè)缺陷，即無(wú)法檢測(cè)局部異常、相關(guān)屬性較少的異常以及異常被正常實(shí)例包圍。

Campello 等[75]將關(guān)注點(diǎn)從局部離群值擴(kuò)展到全局離群值，提出了一種稱為全局-局部層次離群值得分（GLOSH）的算法。它基于一個(gè)完整的統(tǒng)計(jì)解釋，能夠同時(shí)檢測(cè)全局和局部離群值類型。它對(duì)不同的任務(wù)都具有良好的擴(kuò)展性，但該研究是基于特定的k近鄰密度估計(jì)，存在一定的局限性。

3.5 數(shù)據(jù)流中的檢測(cè)方法

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

Na 等[80]對(duì)現(xiàn)有LOF 的數(shù)據(jù)流算法存在的兩個(gè)限制：需要大量?jī)?nèi)存和不能檢測(cè)到長(zhǎng)序列的離群點(diǎn)。提出了一種新的數(shù)據(jù)流離群點(diǎn)檢測(cè)算法DILOF。DILOF 在準(zhǔn)確性和執(zhí)行時(shí)間方面顯著優(yōu)于現(xiàn)有的算法。Qin等[81]提出了局部離群值語(yǔ)義的概念，通過(guò)利用內(nèi)核密度估計(jì)（aKDE）來(lái)有效地從流數(shù)據(jù)中檢測(cè)局部離群值。KELOS 是基于抽象核心中心的aKDE 策略，aKDE 可以準(zhǔn)確而有效地估計(jì)每個(gè)點(diǎn)上的數(shù)據(jù)密度。aKDE和內(nèi)部剪枝策略共同消除了流局部離群點(diǎn)檢測(cè)的性能瓶頸。

文獻(xiàn)[82]針對(duì)現(xiàn)有數(shù)據(jù)流離群點(diǎn)檢測(cè)算法在面對(duì)海量高維數(shù)據(jù)流時(shí)普遍存在運(yùn)算時(shí)間過(guò)長(zhǎng)的問(wèn)題，提出一種引入局部向量點(diǎn)積密度的高維數(shù)據(jù)流離群點(diǎn)快速檢測(cè)算法。以保存少量中間結(jié)果的方式只對(duì)窗口內(nèi)受影響的數(shù)據(jù)點(diǎn)進(jìn)行增量計(jì)算。該算法可以在保證檢測(cè)準(zhǔn)確性的情況下有效提高數(shù)據(jù)流的離群點(diǎn)檢測(cè)效率，并且可擴(kuò)展至并行環(huán)境進(jìn)行并行加速。

3.6 基于相對(duì)密度的方法

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

文獻(xiàn)[86]將依據(jù)正常點(diǎn)與離群點(diǎn)相對(duì)密度的差異性計(jì)算每個(gè)對(duì)象的離群值，將離群值高的對(duì)象判定為離群點(diǎn)的方法引入并提出了一種生成對(duì)抗網(wǎng)絡(luò)（generative adversarial network，GAN）與變分自編碼器（variational auto-encoder，VAE）結(jié)合的GAN-VAE 算法。模型的判別器能學(xué)習(xí)正常點(diǎn)與離群點(diǎn)的分類邊界，生成更多潛在離群點(diǎn)。該算法在準(zhǔn)確率和F1值上均有較大提高。

3.7 高維數(shù)據(jù)的檢測(cè)方法

文獻(xiàn)[87]提出了基于鄰域密度的高維異構(gòu)數(shù)據(jù)局部離群點(diǎn)挖掘算法，首先對(duì)高維數(shù)據(jù)進(jìn)行區(qū)域分割，然后采取核密度來(lái)描述局部密度，計(jì)算出數(shù)據(jù)鄰域密度，從而判斷異構(gòu)數(shù)據(jù)中的離群點(diǎn)。該方法幾乎不受數(shù)據(jù)量和數(shù)據(jù)維數(shù)改變的影響，其挖掘時(shí)間和覆蓋率指標(biāo)也較優(yōu)。文獻(xiàn)[88]針對(duì)離群點(diǎn)檢測(cè)算法LOF 在高維離散分布數(shù)據(jù)集中檢測(cè)精度較低及參數(shù)敏感性較高的問(wèn)題，提出了基于鄰域系統(tǒng)密度差異度量的離群點(diǎn)檢測(cè)NSD（neighborhood system density difference）算法。NSD算法簡(jiǎn)單易用，在檢測(cè)偏離程度較大的目標(biāo)對(duì)象時(shí)會(huì)大幅降低計(jì)算開(kāi)銷。

文獻(xiàn)[89]在LOF的基礎(chǔ)上結(jié)合粗糙集理論，引入屬性權(quán)值概念，提出了一種基于粗約簡(jiǎn)和網(wǎng)格的離群點(diǎn)檢測(cè)算法RRGOD（outliers detecting based on rough reduction and grid）。通過(guò)淘汰屬性權(quán)值低于重要度閾值的屬性來(lái)降低維度，從而減少了后續(xù)的計(jì)算量。文獻(xiàn)[90]提出一種基于局部線性嵌入的離群點(diǎn)檢測(cè)方法（OLLE），是針對(duì)高維數(shù)據(jù)的降維方法。算法使數(shù)據(jù)集的下近似中的點(diǎn)保持局部線性結(jié)構(gòu)，保證在降維的過(guò)程中使離群點(diǎn)遠(yuǎn)離正常點(diǎn)。該方法的優(yōu)勢(shì)是將數(shù)據(jù)集從高維空間降至低維空間的過(guò)程能很好地保持?jǐn)?shù)據(jù)的局部幾何結(jié)構(gòu)，且在檢測(cè)離群點(diǎn)時(shí)，一定范圍內(nèi)對(duì)k不敏感。

在表2中對(duì)經(jīng)典算法進(jìn)行了整理，展示了在上述一些關(guān)鍵算法的進(jìn)展。

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

4 基于密度的方法

4.1 優(yōu)點(diǎn)

（1）在基于密度的方法中，使用的密度估計(jì)是非參數(shù)的，它們不依賴于假設(shè)的分布來(lái)擬合數(shù)據(jù)。

（2）一些基于密度的技術(shù)[59，62，66，69]已經(jīng)成為許多后續(xù)算法的基本算法。它們的衍生算法通常優(yōu)于它們的競(jìng)爭(zhēng)對(duì)手，如一些基于統(tǒng)計(jì)和基于距離的方法[91-93]。這些方法中的離群值通常是通過(guò)對(duì)象的鄰域密度[59]來(lái)分析的[66]，其在識(shí)別其他大多數(shù)基于離群值檢測(cè)的方法所遺漏的關(guān)鍵離群值方面更有優(yōu)勢(shì)。它們只需要最小的先驗(yàn)知識(shí)，如概率分布和只需要一個(gè)參數(shù)調(diào)整。它們還以高效計(jì)算局部離群值的能力而聞名。

4.2 缺點(diǎn)、挑戰(zhàn)和差距

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

（2）由于其固有的復(fù)雜性和缺乏對(duì)離群值度量的更新，如INFLO 和MDEF 算法，不能靈活地處理數(shù)據(jù)流。當(dāng)離群值之間的關(guān)系非常密切時(shí)，這對(duì)于高維數(shù)據(jù)也是一個(gè)挑戰(zhàn)。

（3）由于大多數(shù)基于密度的方法依賴于最近鄰計(jì)算，這使得k的選擇對(duì)于這些算法的評(píng)估非常重要。

（4）基于密度的方法雖然檢測(cè)的精準(zhǔn)度比較高，但其復(fù)雜程度也更高，所以接下來(lái)將該方法的復(fù)雜性降低和在高維大數(shù)據(jù)集中，能有效降低計(jì)算復(fù)雜度，將是研究的重點(diǎn)和挑戰(zhàn)。

5 結(jié)語(yǔ)

基于鄰近性的離群點(diǎn)檢測(cè)方法思想基本上貫穿于整個(gè)離群點(diǎn)檢測(cè)過(guò)程中，依靠鄰近性的思維能挖掘發(fā)現(xiàn)很多相似與相異的關(guān)系。本文將鄰近性劃分為基于距離和基于密度的兩個(gè)分支，主要從鄰近性角度對(duì)現(xiàn)有的離群點(diǎn)檢測(cè)技術(shù)進(jìn)行了歸納和分析。在離群點(diǎn)檢測(cè)鄰域，大量的方法針對(duì)不同的問(wèn)題被提出，無(wú)論是基于統(tǒng)計(jì)的，基于聚類的，還是基于鄰近性的方法，在面對(duì)現(xiàn)在大規(guī)模高維度數(shù)據(jù)集，檢測(cè)都還存在一定局限性，隨著大數(shù)據(jù)、云計(jì)算和分布式的發(fā)展，相信這些檢測(cè)方法還能有更大突破?；卩徑缘碾x群點(diǎn)檢測(cè)算法，最大的優(yōu)點(diǎn)就是直觀，易于理解，缺點(diǎn)是考慮的鄰近性中的數(shù)據(jù)都要進(jìn)行考慮。算法的計(jì)算復(fù)雜度如何降低、如何有效地處理高維大數(shù)據(jù)集等方向?qū)⒊蔀橐院笱芯康闹攸c(diǎn)和熱點(diǎn)。