離群點(diǎn)識別方法研究

黃強(qiáng) 葉青 聶斌

摘 要：離群點(diǎn)又稱特異點(diǎn)、興趣點(diǎn)、偏離點(diǎn)、新穎點(diǎn)、異常點(diǎn)等。通過離群點(diǎn)識別可發(fā)現(xiàn)異常事件與新現(xiàn)象。隨著信息技術(shù)的發(fā)展和信息量爆炸式增長，通過識別數(shù)據(jù)中的離群點(diǎn)獲得潛在信息成為研究熱點(diǎn)。首先簡要介紹幾種主要的離群點(diǎn)識別方法，并分析各種方法的優(yōu)缺點(diǎn)，為相關(guān)使用者學(xué)習(xí)、選擇和改進(jìn)算法提供參考。闡述離群點(diǎn)識別的研究熱點(diǎn)和應(yīng)用鄰域，并分析現(xiàn)有算法在識別高維、空間和時序數(shù)據(jù)離群點(diǎn)的難點(diǎn)，便于研究者提出新的相關(guān)離群點(diǎn)識別方法。

關(guān)鍵詞：離群點(diǎn)識別;離群點(diǎn);分析數(shù)據(jù);數(shù)據(jù)挖掘;異常點(diǎn)

DOI：10. 11907/rjdk. 182475

中圖分類號：TP301

文獻(xiàn)標(biāo)識碼：A文章編號：1672-7800（2019）006-0035-07

Abstract： Outliers are also called special points， interest points， deviations， novelty points， outliers， etc. Outlier identification can detect abnormal events and new phenomena. With the development of information technology and the explosive growth of information， potential information by identifying outliers in the data has become the research hotspot and it has attracted more and more attention. This paper briefly introduces several main outlier recognition methods， and concisely analyzes the advantages and disadvantages of each method， providing a reference for later users to learn， select and improve the algorithm. At the same time， the research hotspots and application neighborhoods of outlier recognition are described， and the difficulties of existing algorithms in identifying outliers in high-dimensional， spatial and temporal data are analyzed， which is convenient for relevant researchers to propose new outlier recognition methods.

Key Words： outlier identification; outliers; analysis data; data mining; outlier

0 引言

對于離群點(diǎn)的概念目前還沒有一個通用定義，Hawkins[1]第一次提出離群點(diǎn)定義：“某個數(shù)據(jù)點(diǎn)與數(shù)據(jù)集中其它的數(shù)據(jù)點(diǎn)偏離的太多，像是產(chǎn)生于不同的機(jī)制，這樣的數(shù)據(jù)點(diǎn)我們把它稱為離群點(diǎn)?！盉arnet等[2]認(rèn)為離群點(diǎn)是與樣本中其它數(shù)據(jù)點(diǎn)顯著不同的數(shù)據(jù)點(diǎn)。Johnson[3]認(rèn)為與數(shù)據(jù)集中其它數(shù)據(jù)點(diǎn)的行為、表現(xiàn)不一致的數(shù)據(jù)點(diǎn)是離群點(diǎn)。離群點(diǎn)出現(xiàn)的原因有很多，大致可以分為兩種：一種是數(shù)據(jù)異常（離群點(diǎn)），常為人為干涉的結(jié)果，比如藥理實(shí)驗(yàn)出現(xiàn)新結(jié)果（之前實(shí)驗(yàn)沒有出現(xiàn)過的結(jié)果），可能是人們期望出現(xiàn)的“異?！?第二種是自然發(fā)生的，比如異常天氣的出現(xiàn)。

離群點(diǎn)有多種叫法，國外有學(xué)者把離群點(diǎn)稱為outlier、exception、 abnormal point等，國內(nèi)翻譯為特異點(diǎn)、興趣點(diǎn)、新穎點(diǎn)、偏離點(diǎn)、異常點(diǎn)等。為方便描述，本文一律用離群點(diǎn)代替。根據(jù)其特點(diǎn)，離群點(diǎn)大致可以分為如圖1所示的幾種類別。其中，數(shù)據(jù)點(diǎn)范圍是指離群點(diǎn)偏離的對象位置。若離群點(diǎn)顯著偏離于其所在局部區(qū)域數(shù)據(jù)點(diǎn)，則該離群點(diǎn)是局部離群點(diǎn);若離群點(diǎn)顯著偏離于全部數(shù)據(jù)點(diǎn)，則該離群點(diǎn)是全局離群點(diǎn)?，F(xiàn)實(shí)世界中超過三維（屬性）的數(shù)據(jù)均稱為高維數(shù)據(jù)。不同離群點(diǎn)有相應(yīng)方法識別，比如基于距離的離群點(diǎn)識別方法可以識別全局離群點(diǎn)，局部離群點(diǎn)需要應(yīng)用基于密度的識別方法。

現(xiàn)有數(shù)據(jù)分析嘗試通過建立一個能夠擬合數(shù)據(jù)分布規(guī)律的模型對輸入數(shù)據(jù)進(jìn)行分類或者預(yù)測。在建模過程中，離群點(diǎn)導(dǎo)致擬合結(jié)果不準(zhǔn)確，因此需去除數(shù)據(jù)集中的離群點(diǎn)。實(shí)際上，離群點(diǎn)在某些情景下包含豐富的有用信息，比如藥理實(shí)驗(yàn)出現(xiàn)的新結(jié)果。因此離群點(diǎn)研究有重要的意義，不能簡單地丟棄。

1 離群點(diǎn)識別方法

KNORREM 等[4]提出，知識發(fā)現(xiàn)可分為4類：依賴性檢測、類識別、類描述、異常檢測。前3項(xiàng)任務(wù)側(cè)重于數(shù)據(jù)集中的大多數(shù)對象。數(shù)據(jù)挖掘中的大部分研究，比如關(guān)聯(lián)規(guī)則、分類、數(shù)據(jù)聚類和概念泛化都屬于前3項(xiàng)任務(wù)。然而第4項(xiàng)任務(wù)則側(cè)重于經(jīng)常被當(dāng)作噪聲丟棄的小部分?jǐn)?shù)據(jù)對象。事實(shí)上，有時小部分?jǐn)?shù)據(jù)對象攜帶的信息比大部分?jǐn)?shù)據(jù)對象攜帶的信息更有研究意義，例如前文所指的藥物實(shí)驗(yàn)的“異常點(diǎn)”，所以離群點(diǎn)識別的作用是挖掘一些異常數(shù)據(jù)對象，并發(fā)現(xiàn)其隱藏的信息。

隨著對離群點(diǎn)識別的深入研究，離群點(diǎn)識別方法愈加豐富，其方法分類如圖2所示?？梢园凑諗?shù)據(jù)是否標(biāo)記分為監(jiān)督、半監(jiān)督、無監(jiān)督3類;也可以按照對離群點(diǎn)的假定分為基于統(tǒng)計、鄰近、聚類3種。由于兩種分類下的方法有交叉，本文重點(diǎn)從離群點(diǎn)假設(shè)角度介紹離群點(diǎn)識別方法，并概述各種方法的優(yōu)劣。

1.1 監(jiān)督、半監(jiān)督、無監(jiān)督方法

使用標(biāo)記為正常和離群點(diǎn)的數(shù)據(jù)樣本可建立離群點(diǎn)識別模型，其中離群點(diǎn)識別方法可分為監(jiān)督、半監(jiān)督和無監(jiān)督三大類方法：①監(jiān)督方法主要針對數(shù)據(jù)點(diǎn)正常性和離群性建模，通過學(xué)習(xí)給定的標(biāo)記數(shù)據(jù)（正常數(shù)據(jù)或者離群數(shù)據(jù)）間存在的潛在聯(lián)系識別離群點(diǎn)。比如通過學(xué)習(xí)標(biāo)記為正常數(shù)據(jù)建模，與該模型不匹配的數(shù)據(jù)均被識別為離群點(diǎn);②半監(jiān)督方法。在現(xiàn)實(shí)應(yīng)用中，小部分?jǐn)?shù)據(jù)樣本被標(biāo)記，大部分未被標(biāo)記，無法直接通過監(jiān)督方法建模，因而提出半監(jiān)督方法。半監(jiān)督方法指通過標(biāo)記數(shù)據(jù)和其鄰近的未標(biāo)記數(shù)據(jù)建模，不符合該模型的數(shù)據(jù)被標(biāo)記為離群點(diǎn);③無監(jiān)督方法指針對難以處理的無標(biāo)記數(shù)據(jù)，只能通過某種方法自主學(xué)習(xí)數(shù)據(jù)間的潛在聯(lián)系。

分類方法是典型的監(jiān)督方法，通過學(xué)習(xí)標(biāo)記為某類別的數(shù)據(jù)建模，再使用該模型對數(shù)據(jù)進(jìn)行分類，不屬于該類別（不符合該模型）的數(shù)據(jù)即為離群點(diǎn)。比如支持向量機(jī)（SVM）通過學(xué)習(xí)數(shù)據(jù)（通常是正常數(shù)據(jù)）的決策邊界識別離群點(diǎn)。給定一個新數(shù)據(jù)點(diǎn)，如果該數(shù)據(jù)點(diǎn)在決策邊界外則被標(biāo)記為離群點(diǎn)。半監(jiān)督和無監(jiān)督的方法有聚類、神經(jīng)網(wǎng)絡(luò)算法等。

1.2 基于統(tǒng)計的離群點(diǎn)

該概念的前提是數(shù)據(jù)對象是由某個統(tǒng)計模型產(chǎn)生的，如果數(shù)據(jù)對象不符合該模型或出現(xiàn)概率小于給定的閾值，則該對象被視作基于統(tǒng)計的離群點(diǎn)。

基于統(tǒng)計的離群點(diǎn)識別方法可以分為應(yīng)用于多變量和單變量兩大類。

在正態(tài)分布的假定下，卡方檢驗(yàn)也可識別多變量離群點(diǎn)，數(shù)據(jù)對象卡方分布統(tǒng)計量值越大，則越可能是離群點(diǎn)。

基于統(tǒng)計的離群點(diǎn)識別方法的優(yōu)點(diǎn)是所挖掘的離群點(diǎn)具有具體現(xiàn)實(shí)意義和統(tǒng)計學(xué)理論支撐。但這些方法均基于數(shù)據(jù)對象符合某個統(tǒng)計模型的假設(shè)，而現(xiàn)實(shí)世界中的數(shù)據(jù)大都不符合該假定?；诮y(tǒng)計的離群點(diǎn)識別方法大多適用于低維數(shù)據(jù)集，同時時間復(fù)雜度與數(shù)據(jù)集大小有關(guān)，數(shù)據(jù)集越大，算法時間復(fù)雜度越大，因此遇到高維數(shù)據(jù)集則無法有效應(yīng)對。

1.3 基于鄰近的離群點(diǎn)

如果一個數(shù)據(jù)對象與它最近鄰之間的鄰近性顯著地不同于其它對象與它最近鄰的鄰近性，則該數(shù)據(jù)對象為基于鄰近的離群點(diǎn)。

如果數(shù)據(jù)對象集D中至少有P部分與數(shù)據(jù)對象O的距離大于D，則該對象O是以P和D為參數(shù)的基于鄰近的離群點(diǎn)，記作DB（P，D），即如果在以D為半徑的對象O的鄰域內(nèi)少于P（是一個分?jǐn)?shù)）部分的數(shù)據(jù)對象，該對象可被定義為基于鄰近的離群點(diǎn)，其中D確定鄰域，P確定離群點(diǎn)。

基于鄰近的離群點(diǎn)識別方法可以再細(xì)分為兩種類型，一種是基于距離的，另一種是基于密度的?；诰嚯x的離群點(diǎn)識別方法主要考慮對象鄰域，如果一個對象在給定半徑的鄰域內(nèi)沒有足夠數(shù)目（用戶指定）的數(shù)據(jù)對象，則該數(shù)據(jù)對象為基于距離的離群點(diǎn)?；诿芏鹊碾x群點(diǎn)識別主要考慮近鄰的密度，如果對象的密度相對于近鄰的密度很小，則該對象為基于密度的離群點(diǎn)。

（1）基于距離的離群點(diǎn)識別方法可以分為基于索引、基于嵌套和基于網(wǎng)格3種類別：①基于索引的方法[8-9]核心思想是在查找對象O鄰域內(nèi)數(shù)據(jù)對象數(shù)目的過程中，使用查詢索引結(jié)構(gòu)。根據(jù)給定數(shù)據(jù)對象集S建立多維索引（比如R樹），之后根據(jù)索引查找對象鄰域內(nèi)的對象個數(shù)，如果n為使對象O成為離群點(diǎn)的臨界值，在對象O鄰域內(nèi)搜索到第n+1個對象時，則判定該對象不是離群點(diǎn)并開始搜索下一個對象的鄰域。基于索引的方法時間復(fù)雜度是 ? ? ?O（DN2），D是數(shù)據(jù)對象的維度，N是數(shù)據(jù)集的對象總數(shù)，但是沒有囊括初始化索引結(jié)構(gòu)的時間;②基于嵌套循環(huán)的方法[8，10]主要通過遍歷對象集中的每個對象鄰域確定該對象是否為離群點(diǎn)。嵌套循環(huán)算法有內(nèi)外兩個循環(huán)。外循環(huán)是遍歷數(shù)據(jù)集中的每個對象，內(nèi)循環(huán)遍歷所有對象時，計算屬于O鄰域內(nèi)的對象個數(shù)（n），一旦n超過給定閾值，則確定對象O不是離群點(diǎn)，跳出內(nèi)循環(huán)，繼續(xù)外循環(huán)直到遍歷所有對象，算法時間復(fù)雜度為O（n2）。由于遍歷所有數(shù)據(jù)對象時需計算對象間距離，所以該方法不適用于高維稀疏數(shù)據(jù)集;③基于網(wǎng)格的方法。由于基于嵌套循環(huán)的方法為確定一個對象是否為離群點(diǎn)，需遍歷所有對象，為改進(jìn)算法性能，提出基于網(wǎng)格[8，10-11]的方法。基于網(wǎng)格的方法是把對象集劃分成由許多單元組成的多維網(wǎng)格，其中每個單元的邊長為[r2k] ，k是數(shù)據(jù)對象的維度，r是用戶指定的閾值參數(shù)。單元c鄰近的單元被分成兩層，直接與c相接的單元格構(gòu)成第一層，在任意方向遠(yuǎn)離c單元一個或者兩個單元的單元組成第二層?；诰W(wǎng)格的方法根據(jù)這兩個層對數(shù)據(jù)進(jìn)行剪枝，從而提高了離群點(diǎn)檢測效率，時間復(fù)雜度為O（ck + n），c為劃分的單元格個數(shù)，k為數(shù)據(jù)維度，n為數(shù)據(jù)集大小。當(dāng)數(shù)據(jù)對象數(shù)量很大時，基于網(wǎng)格的方法會導(dǎo)致大量對磁盤數(shù)據(jù)的隨機(jī)訪問。為解決該問題，朱慶生等[12]提出基于粗粒度單元的離群點(diǎn)識別方法，與傳統(tǒng)基于單元格的算法相比，補(bǔ)充了初始化參數(shù)參考值的計算方法;其次對單元格劃分方式稍作改進(jìn)，使效率有所提高。陸聲鏈[13]提出基于距離和的方法，在對數(shù)據(jù)集標(biāo)準(zhǔn)化后，計算每個對象與數(shù)據(jù)集剩下所有對象的距離和，并按距離和從小到大排序，前M個距離和最大的對象為離群點(diǎn)。

綜上所述，本文首先從數(shù)據(jù)集中抽取一個樣本集s，s的每一個對象均作為一個簇的形心，然后第一次掃描數(shù)據(jù)對象集，根據(jù)對象間距離把數(shù)據(jù)對象劃分到各個簇中，第二次掃描數(shù)據(jù)集時，確定候選離群點(diǎn)（可能是離群點(diǎn)的對象），第三次掃描后找出所有基于DB（P，D）的離群點(diǎn)。該方法空間復(fù)雜度小，約為數(shù)據(jù)對象集的1%。

對于高維數(shù)據(jù)，有學(xué)者提出了新方法。Angiulli[10]通過比較數(shù)據(jù)對象與其k近鄰的平均距離對數(shù)據(jù)集中的對象排序，平均距離大的前M個數(shù)據(jù)對象被識別為離群點(diǎn)。Ghoting[11]提出基于距離的兩階段算法——RBRP算法，該算法主要在識別離群點(diǎn)之前，先對數(shù)據(jù)對象進(jìn)行聚類處理，形成若干數(shù)量的小類，再在小類中識別離群點(diǎn)，減少計算距離的量，提高算法效率，但在聚類處理階段需用戶指定類別數(shù)，且聚類效果取決于所用聚類算法。

在數(shù)據(jù)流的離群點(diǎn)識別方面，Kontaki[15]提出基于滑動窗口的離群點(diǎn)識別算法。當(dāng)在給定半徑R中鄰居數(shù)少于K時，數(shù)據(jù)對象可視為離群點(diǎn)。雖然該方法不能保證存儲開銷比相關(guān)算法更小，但比相關(guān)算法效率更高，并且在輸入?yún)?shù)方面有較高的靈活性。

基于距離的離群點(diǎn)識別方法無須知道數(shù)據(jù)符合的分布模型，可以較廣泛地應(yīng)用于距離度量的離群點(diǎn)識別。但該類方法對參數(shù)要求敏感，參數(shù)不同會導(dǎo)致不同的識別結(jié)果，而且不能識別出局部離群點(diǎn)。

（2）基于密度的離群點(diǎn)識別方法。該方法檢測離群點(diǎn)時的參數(shù)是基于全局的，識別出的離群點(diǎn)被稱為全局離群點(diǎn)。但是實(shí)際生活中的數(shù)據(jù)集往往復(fù)雜多樣，其中存在一種離群點(diǎn)相對于自己鄰近的數(shù)據(jù)對象是離群的，但是基于全局識別會被識別為正常對象，這樣的對象被稱為局部離群點(diǎn)。如圖4所示，點(diǎn)O1為局部離群點(diǎn)。

在LOF方法中數(shù)據(jù)對象不再是非此即彼的關(guān)系，每個數(shù)據(jù)對象都有大小不一的LOF值，LOF值越大，越有可能是離群點(diǎn)。

LOF算法雖然能夠識別出局部離群點(diǎn)，但計算可達(dá)距離和可達(dá)密度代價較大。Agyemang[17]對此作出改進(jìn)并提出LSC-Mine算法。該方法先通過剪枝把不可能是離群點(diǎn)的對象去除，減少候選對象數(shù)，削減了計算量;然后通過計算局部稀疏率（Local Sparsity Ratio，LSR）確定離群點(diǎn)。LSR是對象O的k近鄰數(shù)與其k近鄰距離和的比值，LSR越小，是離群點(diǎn)的可能性越大。通過降低計算復(fù)雜度的改進(jìn)算法還有MDEF算法[18]。其它改進(jìn)算法有COF算法[19]，常用于序列數(shù)據(jù)集中的離群點(diǎn)識別，INFLO算法[20]在數(shù)據(jù)分布模型復(fù)雜的數(shù)據(jù)集中能有效識別離群點(diǎn)。

LOF算法無法有效應(yīng)對數(shù)據(jù)分布異常的情況，INLOF不加區(qū)分地分析K近鄰和反向K近鄰導(dǎo)致效率低下。因此鄒云峰等[21]提出LDBO算法，通過引入強(qiáng)K近鄰點(diǎn)和弱K近鄰概念分析數(shù)據(jù)間相關(guān)性，盡可能避免不必要的反向K近鄰分析，提高算法效率。

胡彩平[22]提出DLOF算法，該算法通過引入信息熵確定離群屬性，并在計算對象間距離時為離群屬性增加權(quán)重，提高離群點(diǎn)識別準(zhǔn)確度，然后計算經(jīng)過優(yōu)化的LOF值以識別離群點(diǎn)。DLOF算法雖然提高了離群點(diǎn)識別準(zhǔn)確度，但是在優(yōu)化過程中需提前計算各對象之間的距離，增加了額外空間花銷。

王敬華[23]提出的NLOF算法首先使用DBSCAN算法對數(shù)據(jù)進(jìn)行預(yù)處理得到初步異常數(shù)據(jù)集，再計算各個數(shù)據(jù)對象的信息熵增量作為后續(xù)LOF計算中加權(quán)距離的權(quán)重，以此計算出LOF值識別出離群點(diǎn)。文獻(xiàn)[24-26]也提出一些改進(jìn)的LOF算法。

基于密度的離群點(diǎn)識別方法能夠識別出局部離群點(diǎn)，但是由于也涉及到距離計算，時間復(fù)雜度通常為O（n2），在高維數(shù)據(jù)下效率不是很理想。

1.4 基于聚類的離群點(diǎn)

基于聚類的離群點(diǎn)識別方法主要思想是通過聚類算法把數(shù)據(jù)對象集自動分成若干個簇，不屬于任何一簇的數(shù)據(jù)對象即為離群點(diǎn)。如果一個對象不屬于任何一個簇或者屬于一個微小簇，則該數(shù)據(jù)對象為基于聚類的離群點(diǎn)。

基于聚類的離群點(diǎn)識別方法有很多，下文分別介紹基于劃分的、基于層次的、基于網(wǎng)格的、基于密度的聚類方法。

（1）基于劃分的聚類方法主要思想是在給定常數(shù)k下，根據(jù)數(shù)據(jù)對象之間的相似性把數(shù)據(jù)對象分別劃分到k個簇中，每個簇中至少有一個數(shù)據(jù)對象。

K-means[27]是劃分方法中經(jīng)典的聚類算法之一，該算法效率高，適用于大規(guī)模數(shù)據(jù)聚類，現(xiàn)在很多算法均是基于該算法改進(jìn)而來的。

K-means算法首先從數(shù)據(jù)對象集中隨機(jī)地選擇k個對象，每個對象初始地代表了一個簇的平均值或中心，對剩余的每個對象，根據(jù)其與各個簇中心的距離，將它劃分給最近的簇;然后重新計算每個簇的平均值。這個過程不斷重復(fù)，直到準(zhǔn)則函數(shù)（比如平方誤差準(zhǔn)則）收斂或者達(dá)到期望閾值。

文獻(xiàn)[28]提出基于遺傳算法的K-means聚類方法，該方法通過遺傳算法確定初始聚類中心，存在前期過早收斂和后期收斂過慢的缺點(diǎn)，但可以解決傳統(tǒng)遺傳聚類算法聚類結(jié)果不穩(wěn)定性問題。

K-means算法對高維數(shù)據(jù)聚類效率不是很理想，并且只適用于數(shù)值類數(shù)據(jù);其次需設(shè)定希望得到的聚類數(shù)k，需求研究者對數(shù)據(jù)有很好的理解度。在K-means的基礎(chǔ)上，很多學(xué)者提出新的改進(jìn)方法，如文獻(xiàn) [29-34]中的改進(jìn)方法。

（2）基于層次的方法是將數(shù)據(jù)對象組成有層次的結(jié)構(gòu)，比如學(xué)生類可以細(xì)分為小學(xué)生、中學(xué)生和大學(xué)生。學(xué)生為一個層次，下面的子類為一個層次。把低層次聚類成高層次或者高層次拆分為低層次的聚類即為基于層次的聚類。

根據(jù)層次分解順序是自下向上或自上向下，層次聚類算法分為凝聚的層次聚類算法和分裂的層次聚類算法。

凝聚型層次聚類的策略是先將每個對象作為一個簇，然后合并這些原子簇為越來越大的簇，直到所有對象都在一個簇中，或者某個終結(jié)條件被滿足。與此相反，分裂的層次聚類是把整個數(shù)據(jù)對象形成的簇迭代地分裂為較小的簇群。凝聚層次聚類算法AGNES[35]首先把數(shù)據(jù)對象集中的每個對象劃分成一個簇，之后根據(jù)各個簇之間的相似度（最小距離等）合并簇，重復(fù)此過程直到達(dá)到期望的簇數(shù)目，或使兩個最近簇之間的距離超過某個閾值。分裂層次聚類算法DIANAN[36]的過程則和AGNES算法相反。

層次聚類的缺點(diǎn)是合并或分裂點(diǎn)選擇困難，因此后來出現(xiàn)了將層級聚類和其它聚類技術(shù)進(jìn)行集成、形成多階段聚類的方法。比如BIRCH算法和Chameleon算法[37]等。

（3）基于網(wǎng)格的方法將數(shù)據(jù)對象空間劃分為若干的單元格，每個對象都落入相應(yīng)網(wǎng)格中，形成一個網(wǎng)格結(jié)構(gòu)，所有數(shù)據(jù)操作均在網(wǎng)格層次進(jìn)行?；诰W(wǎng)格的聚類算法在處理大數(shù)據(jù)集合高維的數(shù)據(jù)集時比較有效。

STING算法[8，38]是一種基于網(wǎng)格的多分辨率聚類，數(shù)據(jù)空間按照分層和遞歸的方法進(jìn)行劃分，首先所有數(shù)據(jù)被劃分若干個最低層次的網(wǎng)格，上一層次的網(wǎng)格由若干個低層次的網(wǎng)格組成，以此類推，形成多層次網(wǎng)格聚類。每個網(wǎng)格單元的統(tǒng)計信息被當(dāng)作參數(shù)提前被存儲，更高的單元網(wǎng)格參數(shù)信息可由低層次網(wǎng)格單元計算得出，所以STING算法可獨(dú)立于查詢，而且網(wǎng)格結(jié)構(gòu)有利于增量更新和并行處理;但是由于STING是多分辨率的方法，低層次網(wǎng)格單元聚類成高層次網(wǎng)格單元時的效率取決于底層網(wǎng)格單元粒度，即分得越細(xì)，效率越低，若粒度粗糙，則聚類效果不佳。

CLIQUE[8]方法包括兩階段聚類：第一步先把數(shù)據(jù)對象空間按照不同的屬性組合劃分成不重疊的單元，在此基礎(chǔ)上找到稠密單元（需要指定稠密閾值）;第二步合并互相可以鄰接的稠密單元，形成更高維單元，直到遍歷所有單元。該方法需要依賴給定的稠密閾值。

（4）基于密度的方法。大部分聚類方法只能發(fā)現(xiàn)球狀簇，對于其它形狀的數(shù)據(jù)因無法識別會出現(xiàn)誤判。而基于密度的聚類方法可以發(fā)現(xiàn)任意形狀的簇群。

DBSCAN[39]基于一組鄰域描述樣本集緊密程度，參數(shù)（∈，MP）描述鄰域樣本分布緊密程度。其中，∈描述某一樣本鄰域距離閾值，MP描述某一樣本距離為∈的鄰域中樣本個數(shù)的閾值。其主要思想是：對于給定的數(shù)據(jù)集合中每個數(shù)據(jù)對象在給定領(lǐng)域內(nèi)必須包含有規(guī)定的最少數(shù)據(jù)對象，這樣的對象稱為核心對象;核心對象通過密度相連等關(guān)系被聚類成一個簇，如此便可以識別出任意形狀的數(shù)據(jù)對象簇。該方法也需要人為地指定參數(shù)（∈，MP），參數(shù)設(shè)置的不同會導(dǎo)致不同的聚類結(jié)果。

為避免使用一組全局參數(shù)，Ankerst等[40]提出OPTICS方法。OPTICS方法并不顯式地產(chǎn)生聚類，而是輸出一個簇排序，這個簇排序可反映各個數(shù)據(jù)對象基于密度的聚類結(jié)構(gòu)。該方法可用圖形表示簇排序，只需設(shè)定一個閾值，即可輕易找出滿足閾值條件下基于密度聚類的離群點(diǎn)。最壞情況下算法時間復(fù)雜度為O（n2），n為數(shù)據(jù)對象數(shù)。

Rodriguez[41]提出新的基于密度的聚類方法DPCA。該方法假定高密度的聚類中心被局部密度低的對象包圍，且距離另一個聚類中心較遠(yuǎn)，計算局部密度[ρ]和對象與高密度對象間距離d，具有較大的d和[ρ]的對象即為聚類中心，具有較大d和較小[ρ]的即為離群點(diǎn)。魏龍等[42]提出的DD-DBSCAN算法通過運(yùn)用最小生成樹，對DBSCAN進(jìn)行改進(jìn)，使算法無需輸入?yún)?shù)即可同時識別全局和局部離群點(diǎn)。

一直以來不斷有學(xué)者提出新的聚類算法識別離群點(diǎn)，Levent Ertoz[43]提出基于共享鄰居的聚類方法SNN，通過構(gòu)造相似矩陣，計算數(shù)據(jù)對象之間的鏈接強(qiáng)度，并以此為依據(jù)確立聚類中心和離群數(shù)據(jù)，輸出離群數(shù)據(jù)。但是SNN對離群點(diǎn)的處理力度有限，必須建立SNN圖和計算各個數(shù)據(jù)對象的鏈接強(qiáng)度后才開始確定數(shù)據(jù)對象是否離群點(diǎn)。耿技[44]對此提出改進(jìn)的SNN算法。

聚類方法的目的是發(fā)現(xiàn)簇，離群點(diǎn)是聚類副產(chǎn)品。雖然有學(xué)者直接通過聚類方法識別離群點(diǎn)，但識別效率較低，所以聚類方法常結(jié)合其它方法識別離群點(diǎn)。

古平等[45]提出多重聚類的算法—PMLDOF。該方法的思想是通過不同的聚類方法或者以同一聚類方法、不同參數(shù)剪枝數(shù)據(jù)，數(shù)據(jù)對象在均被劃分到某一簇中才被確定為非離群點(diǎn)，否則被確定為候選離群點(diǎn)。最后計算候選離群點(diǎn)的LOF確定離群點(diǎn)。PMLDOF算法通過剪枝處理可減少時間復(fù)雜度，提高識別準(zhǔn)確度。

為識別動態(tài)數(shù)據(jù)集中的離群點(diǎn)，孟靜[46]在DBSCAN原有的基礎(chǔ)上進(jìn)行改進(jìn)。對于新增的數(shù)據(jù)對象，計算該對象到各個簇中心的距離，若到最近簇中心的距離小于給定閾值，則將對象劃分到最近簇中，否則放入異常數(shù)據(jù)集中;再計算異常數(shù)據(jù)集的對象LOF值以確定離群點(diǎn)。該方法能有效識別增量數(shù)據(jù)中的離群點(diǎn)，時間復(fù)雜度也較低。

Christy[47]利用K-means聚類得到候選離群點(diǎn)集，然后根據(jù)離群點(diǎn)到最近簇簇心的歐式距離排序，top-n被識別為離群點(diǎn)。

石鴻雁等[49]提出DBSCAN和LAOF算法結(jié)合的兩階段離群點(diǎn)識別方法，通過優(yōu)化參數(shù)的DBSCAN和新構(gòu)造的LAOF（基于區(qū)域密度的局部異常因子）計算篩選數(shù)據(jù)對象的離群程度，并引用去一化信息熵確定數(shù)據(jù)屬性權(quán)重，提高離群點(diǎn)識別精度。文獻(xiàn)[48]提出互鄰圖概念以及基于互鄰圖的聚類算法ROCF，該算法可自動算出數(shù)據(jù)對象離群度，不用給定top-n參數(shù)即可識別出離群點(diǎn)。

任建華等[50]提出基于聚類的兩段式識別算法，先通過聚類算法得到候選離群點(diǎn)集合，之后對離群點(diǎn)排序得到有序的離群點(diǎn)集合，最終由兩集合的交集確定離群點(diǎn)。該算法無需預(yù)設(shè)離群點(diǎn)個數(shù)，具有較高準(zhǔn)確率和效率，且對數(shù)據(jù)分布不敏感，能有效識別離群點(diǎn)。

1.5 方法總結(jié)

綜上所述，各類方法的情況總結(jié)見表1。

2 離群點(diǎn)識別熱點(diǎn)與應(yīng)用

2.1 離群點(diǎn)識別熱點(diǎn)

（1）高維數(shù)據(jù)離群點(diǎn)識別。高維數(shù)據(jù)是指維數(shù)超過三維的數(shù)據(jù)。該類數(shù)據(jù)屬性眾多，數(shù)據(jù)間距離難以定義，但是真正可以標(biāo)識一個數(shù)據(jù)樣本的屬性只占其中一部分。對于該類數(shù)據(jù)一般先對數(shù)據(jù)降維，之后再使用相應(yīng)離群點(diǎn)識別方法識別離群點(diǎn)。缺點(diǎn)是降維之后，數(shù)據(jù)信息會損失一部分?，F(xiàn)有方法對該類數(shù)據(jù)的識別效率較低，還需克服以下問題：①對高維離群點(diǎn)的解釋;②高維數(shù)據(jù)稀疏性;③如何表示高維數(shù)據(jù)點(diǎn)間的差異。

（2）空間數(shù)據(jù)離群點(diǎn)識別。隨著全球定位系統(tǒng)（GPS）和各種空間數(shù)據(jù)傳感器的出現(xiàn)，空間數(shù)據(jù)復(fù)雜性和量級不斷增加，空間數(shù)據(jù)離群點(diǎn)識別成為難題?？臻g數(shù)據(jù)離群點(diǎn)識別的難處在于其包含非空間屬性和空間屬性，同時空間數(shù)據(jù)具有自相關(guān)性和異質(zhì)性，空間數(shù)據(jù)受到鄰近數(shù)據(jù)影響，因此空間數(shù)據(jù)離群點(diǎn)局部不穩(wěn)定。常用方法有變差云圖、Z-Score，用于低維空間數(shù)據(jù)，對于高維空間數(shù)據(jù)，有學(xué)者提出相應(yīng)方法。文獻(xiàn)[51]提出一個空間局部異常度量（SLOM），借助SLOM可夠識別出局部空間離群點(diǎn);文獻(xiàn)[52]提出一種無參數(shù)的自適應(yīng)空間離群點(diǎn)檢測算法，該算法能夠計算空間鄰居個數(shù)，并能夠自動找到離群點(diǎn)檢測閾值;文獻(xiàn)[53]提出基于地統(tǒng)計學(xué)的檢測算法，算法應(yīng)用空間自相關(guān)理論，利用德洛內(nèi)三角網(wǎng)構(gòu)建空間鄰域，用鄰域節(jié)點(diǎn)均值代替離群點(diǎn)。隨著數(shù)據(jù)采集設(shè)備的更新，空間數(shù)據(jù)越來越復(fù)雜，提高算法有效性是空間離群點(diǎn)識別的重點(diǎn)。

（3）時序數(shù)據(jù)離群點(diǎn)識別。時序數(shù)據(jù)是與時間有關(guān)的一系列數(shù)據(jù)，比如每個月的用水量、某個時期降雨量、直播期間網(wǎng)絡(luò)流量等。因?yàn)闀r序數(shù)據(jù)周期性影響，使時序數(shù)據(jù)離群點(diǎn)難以識別。常見方法是將時序數(shù)據(jù)的時間劃分成等長子序列，然后使用基于距離的識別方法識別離群點(diǎn)，缺點(diǎn)是計算花費(fèi)大;另一種方法是從序列數(shù)據(jù)中抽取特征，通過計算特征數(shù)據(jù)的距離識別離群點(diǎn)[54-56]。

2.2 離群點(diǎn)識別應(yīng)用

離群點(diǎn)識別有助于剝離復(fù)雜的表象，挖掘隱含的重要信息，因此具有重要意義。

（1）去除干擾數(shù)據(jù)。實(shí)驗(yàn)數(shù)據(jù)采集或傳感器數(shù)據(jù)傳輸可能出現(xiàn)不可抗原因?qū)е碌臄?shù)據(jù)缺失，增加錯誤數(shù)據(jù)，使實(shí)驗(yàn)結(jié)果不準(zhǔn)確或出現(xiàn)不實(shí)信息。識別并去除數(shù)據(jù)中的干擾數(shù)據(jù)（離群點(diǎn)）是數(shù)據(jù)挖掘重要環(huán)節(jié)。

（2）欺詐檢測。銀行卡或者儲蓄賬號被盜取后，購買模式會不同于原有購買模式。銀行或者金融機(jī)構(gòu)通過原有購買模式建立的模型可識別出反常購物行為，及時凍結(jié)賬號并告知持有者，大幅降低用戶被盜刷的可能性。

（3）入侵監(jiān)測。如BAT等公司的數(shù)據(jù)庫中存放大量寶貴的數(shù)據(jù)，為以防不法分子運(yùn)用技術(shù)手段入侵?jǐn)?shù)據(jù)庫，相關(guān)機(jī)構(gòu)可通過離群點(diǎn)識別等方法使網(wǎng)絡(luò)入侵監(jiān)測系統(tǒng)時刻檢測入侵行為。

（4）異常氣候監(jiān)測。自然氣候變化多端，離群點(diǎn)識別可提高異常天氣預(yù)測準(zhǔn)確率，提醒公眾注意防害防災(zāi)。

（5）交通狀況監(jiān)測。交通異常監(jiān)測系統(tǒng)通過監(jiān)測道路探頭傳回的視頻識別交通流量，發(fā)現(xiàn)車流量異常，判別是否交通堵塞或發(fā)生事故，能協(xié)助交警及時處理交通事件。

離群點(diǎn)識別還可以應(yīng)用于醫(yī)療狀況監(jiān)測、股票市場異常的大量買入賣出行為、網(wǎng)絡(luò)狀況監(jiān)測、機(jī)器故障監(jiān)測、藥物研究中新實(shí)驗(yàn)結(jié)果識別、直播平臺突發(fā)大流量檢測等。

3 結(jié)語

隨著信息技術(shù)的發(fā)展和信息量爆炸式增長，離群點(diǎn)識別的重要性日益凸顯。離群點(diǎn)識別的熱點(diǎn)分布于圖與網(wǎng)絡(luò)數(shù)據(jù)集、時序數(shù)據(jù)集、空間數(shù)據(jù)集、數(shù)據(jù)流等領(lǐng)域。

在離群點(diǎn)識別方法方面，隨著深度學(xué)習(xí)的興起，基于神經(jīng)網(wǎng)絡(luò)的離群點(diǎn)識別方法將是未來重點(diǎn)研究方向。如文獻(xiàn)[57-60]提到運(yùn)用神經(jīng)網(wǎng)絡(luò)方法識別離群點(diǎn)，文獻(xiàn)[57-58]利用基于能量函數(shù)的神經(jīng)網(wǎng)絡(luò)算法RBM識別離群點(diǎn)。文獻(xiàn)[59-60]提出使用DBN算法檢測離群點(diǎn)。

離群點(diǎn)識別方法還存在一些不足，如何形式化和量化數(shù)據(jù)之間的差異，提高識別方法的效率是下一步離群點(diǎn)識別研究的重點(diǎn)。

參考文獻(xiàn)：

[1] HAWKINS D. Identification of outliers [M]. London： Chapman and Hall，1980.

[2] BARNETT V，LEWIS T. Outliers in statistical data[M]. 3rd edition. New York： John Wiley and Sons， 1994.

[3] JOHNSON R. Applied multivariate statistical analysis. New Jersey： Prentice Hall，1992.

[4] KNORR E M，NG R T. Algorithms for mining distance-based outliers in large datasets 1998 [C]. Proceedings of VLDB， 1998：392-403.

[5] GRUBBS F E. Procedures for detecting outlying observations in samples[J]. Techno Metrics1969 （11）： 1-21.

[6] LAURIKKALA J， JUHOLA M， KENTALA E. Informal identification of outliers in medical data[C]. Berlin： Fifth International Workshop on Intelligent Data Analysis in Medicine and Pharmacology，2000.

[7] BEN-GAL I. Outlier detection[M]. Data Mining and Knowledge Discovery Handbook， 2005.

[8] HAN J W，KAMBER M. 數(shù)據(jù)挖掘：概念與技術(shù)[M]. 范明，孟曉峰，譯. 機(jī)械工業(yè)出版社， 2007.

[9] BAY S D. Mining distance-based outliers in near linear time with randomization and a simple pruning rule[C]. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， 2003：29-38.

[10] ANGIULLI F， PIZZUTI C. Fast outlier detection in high dimensional spaces[C]. European Conference on Principles of Data Mining and Knowledge Discovery， 2002：15-26.

[11] GHOTING A，PARTHASARATHY S，OTEY M E. Fast mining of distance-based outliers in high-dimensional datasets[J]. Data Mining & Knowledge Discovery，2008，16（3）：349-364.

[12] 朱慶生，王震. 基于粗粒度單元的離群點(diǎn)檢測算法研究[J]. 世界科技研究與發(fā)展，2011，33（6）：1045-1048.

[13] 陸聲鏈，林士敏. 基于距離的孤立點(diǎn)檢測研究[J]. 計算機(jī)工程與應(yīng)用，2004，40（33）：73-75.

[14] 張宏翔. 使用RNN的基于距離的孤立點(diǎn)檢測[J].信息與電腦，2017（8）：81-82.

[15] KONTAKI M，GOUNARIS A，PAPADOPOULOS A N，et al. Efficient and flexible algorithms for monitoring distance-based outliers over data streams[J]. Information Systems， 2016， 55（C）：37-53.

[16] BREUNIG M. LOF： identifying density-based local outliers[C]. ACM SIGMOD International Conference on Management of ?Data， 2000：93-104.

[17] AGYEMANG M， EZEIFE C I. Lsc-Mine： algorithm for mining local outliers[C]. 2004.

[18] PAPADIMITRIOU S， KITAGAWA H， GIBBONS P B， et al. LOCI： Fast Outlier Detection Using the Local Correlation Integral[C]. International Conference on Data Engineering， 2003. Proceedings. IEEE， 2003：315-326.

[19] TANG J， CHEN Z， FU W C， et al. Enhancing effectiveness of outlier detections for low density patterns[C]. Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer， Berlin， Heidelberg， 2002：535-548.

[20] JIN W， TUNG A K H， HAN J， et al. Ranking outliers using symmetric neighborhood relationship[C]. Pacific-Asia Conference on Knowledge Discovery and Data Mining， 2006：577-593.

[21] 鄒云峰，張昕，宋世淵，等. 基于局部密度的快速離群點(diǎn)檢測算法[J]. 計算機(jī)應(yīng)用，2017，37（10）：2932-2937.

[22] 胡彩平， 秦小麟. 一種基于密度的局部離群點(diǎn)檢測算法DLOF[J]. 計算機(jī)研究與發(fā)展，2010， 47（12）：2110-2116.

[23] 王敬華，趙新想，張國燕，等. NLOF：一種新的基于密度的局部離群點(diǎn)檢測算法[J]. 計算機(jī)科學(xué)，2013，40（8）：181-185.

[24] 王敬華，金鵬.基于粗約簡和網(wǎng)格的離群點(diǎn)檢測[J].計算機(jī)工程與應(yīng)用，2015，51（3）：133-137+180.

[25] 王茜，劉書志.基于密度的局部離群數(shù)據(jù)挖掘方法的改進(jìn)[J].計算機(jī)應(yīng)用研究，2014，31（6）：1693-1696+1701.

[26] 周鵬，程艷云.一種改進(jìn)的LOF異常點(diǎn)檢測算法[J].計算機(jī)技術(shù)與發(fā)展，2017，27（12）：115-118

[27] HARTIGAN J A. A K-means clustering algorithm[J]. Appl Stat， 1979， 28（1）：100-108.

[28] 左倪娜. 基于改進(jìn)遺傳算法的K-means聚類方法[J].軟件導(dǎo)刊，2016，15（4）：32-34.

[29] 華輝有，陳啟買，劉海，等. 一種融合Kmeans和KNN的網(wǎng)絡(luò)入侵檢測算法[J]. 計算機(jī)科學(xué)，2016，43（3）：158-162.

[30] 李小川，劉媛華. 基于Hadoop的多核果蠅-Kmeans聚類算法[J]. 軟件導(dǎo)刊，2018，17（4）：51-53+57.

[31] YING S， ZHU Q， CHEN Z. An iterative initial-points refinement algorithm for categorical data clustering[J]. Pattern Recognition Letters， 2002， 23（7）：875-884.

[32] JIANG F， LIU G， DU J， et al. Initialization of K-modes clustering using outlier detection techniques[J]. Information Sciences， 2016， 332（11）：167-183.

[33] 韓崇，袁穎珊，梅燾，等. 基于K-means的數(shù)據(jù)流離群點(diǎn)檢測算法[J]. 計算機(jī)工程與應(yīng)用，2017，53（3）：58-63.

[34] 蔣麗，薛善良. 優(yōu)化初始聚類中心及確定K值的K-means算法[J]. 計算機(jī)與數(shù)字工程，2018，46（1）：21-24+113.

[35] KAUFMAN L， ROUSSEEUW P J. Finding groups in data： an introduction to cluster analysis [M]. New York： John Wiley & Sons， Inc. 1990.

[36] KAUFMAN L， ROUSSEEUW P J. Finding groups in data： an introduction to cluster analysis [M]. New York： John Wiley & Sons， Inc. 2008.

[37] KARYPIS G， HAN E H， KUMAR V. Chameleon： hierarchical clustering using dynamic modeling[J]. Computer， 2002， 32（8）：68-75.

[38] WANG W， YANG J， MUNTZ R R. STING： a statistical information grid approach to spatial data mining[J]. 1997：186-195.

[39] UNCU O， GRUVER W A， KOTAK D B， et al. GRIDBSCAN： Grid density-based spatial clustering of applications with noise[C]. IEEE International Conference on Systems， Man and Cybernetics， 2007：2976-2981.

[40] ANKERST M，BREUNIG M M，KRIEGEL H P，et al. Ordering points to identify the clustering structure[C]. International Conference on Management of ?Data. 1999.

[41] RODRIGUEZ A， LAIO A. Clustering by fast search and find of density peaks[J]. Science， 2014， 344（6191）：1492.

[42] 魏龍，王勇. 基于密度劃分的離群點(diǎn)檢測算法[J]. 計算機(jī)與現(xiàn)代化，2015（3）：26-32.

[43] LEVENT E， STEINBACH M， VIPIN K. A new shared nearest neighbor clustering algorithm and its applications[C]. The Workshop on Clustering High Dimensional Data & ITS Applications at SIAM International Conference on Data Mining， 2002.

[44] 耿技，印鑒. 改進(jìn)的共享型最近鄰居聚類算法[J]. 電子科技大學(xué)學(xué)報，2006，35（1）：70-72.

[45] 古平，劉海波，羅志恒. 一種基于多重聚類的離群點(diǎn)檢測算法[J]. 計算機(jī)應(yīng)用研究， 2013， 30（3）：751-753.

[46] 孟靜，吳錫生. 一種基于聚類和快速計算的異常數(shù)據(jù)挖掘算法[J]. 計算機(jī)工程， 2013， 39（8）：60-63.

[47] CHRISTY A，GANDHI G M，VAITHYASUBRAMANIAN S. Cluster based outlier detection algorithm for healthcare data[J]. Procedia Computer Science， 2015， 50（12）：209-215.

[48] HUANG J， ZHU Q， YANG L， et al. A novel outlier cluster detection algorithm without Top-n parameter[J]. Knowledge-Based Systems， 2017， 121（1）：32-40.

[49] 石鴻雁，馬曉娟. 改進(jìn)的DBSCAN聚類和LAOF兩階段混合數(shù)據(jù)離群點(diǎn)檢測方法[J]. 小型微型計算機(jī)系統(tǒng)，2018，39（1）：74-77.

[50] 任建華，高立明. 基于聚類的兩段式孤立點(diǎn)檢測算法[J]. 計算機(jī)工程與應(yīng)用，2016，52（20）：98-102+176.

[51] SUN P， CHAWLA S. On local spatial outliers[C]. IEEE International Conference on Data Mining， 2004：209-216.

[52] XU W， GAO H， LIU Y， et al. An adaptive spatial outlier detection algorithm with no parameter for WSN[C]. International Conference on Information Fusion， 2017：1-8.

[53] 劉莘，張紹良，王飛，等. 基于地統(tǒng)計學(xué)的空間離群點(diǎn)檢測算法的研究[J]. 計算機(jī)應(yīng)用研究，2016，33（12）：3700-3704.

[54] CHOY K. Outlier detection for stationary time series[J]. Journal of ?Statistical Planning & Inference， 2001， 99（2）：111-127.

[55] MA J， PERKINS S. Time-series novelty detection using one-class support vector machines[C]. International Joint Conference on Neural Networks， 2003：1741-1745 .

[56] MARCZAK M， PROIETTI T. Outlier detection in structural time series models： The indicator saturation approach[J]. International Journal of Forecasting， 2016， 32（1）：180-202.

[57] WAN Y， BIAN F. Cell-based outlier detection algorithm： A fast outlier detection algorithm for large datasets[C]. Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining， 2008：1042-1048.

[58] ZHAI S，CHENG Y，LU W，et al. Deep structured energy based models for anomaly detection[C]. New York： Proceedings of the 33rd International Conference on Machine Learning， 2016.

[59] DO K， TRAN T， PHUNG D， et al. Outlier detection on mixed-type data： an energy-based approach[C]. 12th International Conference on Advanced Data Mining and Applications， 2016：111-125.

[60] SHARMA M K， SHEET D， BISWAS P K. Abnormality detecting deep belief network[C]. International Conference on Advances in Information Communication Technology & Computing， 2016：11.

（責(zé)任編輯：江 艷）