周 玉，朱文豪，房 倩，白 磊

華北水利水電大學(xué) 電力學(xué)院，鄭州450011

聚類在數(shù)據(jù)處理中占有重要地位，它利用相似性對數(shù)據(jù)進(jìn)行分組，同組數(shù)據(jù)的相似性盡可能大，不同組數(shù)據(jù)的相似性要盡可能小。聚類分析技術(shù)已廣泛應(yīng)用于各種領(lǐng)域，如計算機(jī)科學(xué)、生命和醫(yī)學(xué)科學(xué)、社會科學(xué)及經(jīng)濟(jì)學(xué)等[1]。

離群點是聚類的副產(chǎn)品，因此對常見的聚類算法，如K-means、DBSCAN[2]、CHAMELEON[3]、CLIQUE[4]等加以修改都可將其用于離群點檢測，這些方法大多通過考慮數(shù)據(jù)對象與簇之間的關(guān)系檢測離群點。離群點檢測是數(shù)據(jù)預(yù)處理中的一項重要任務(wù)，它的目的是發(fā)現(xiàn)數(shù)據(jù)集中與大多數(shù)數(shù)據(jù)偏離較遠(yuǎn)的對象[5]。離群點不一定是錯誤的數(shù)據(jù)，它們往往包含著重要信息，能夠表征數(shù)據(jù)集的某些特點，具有重要研究意義。離群點檢測技術(shù)在欺詐檢測[6-7]、入侵檢測[8-9]、環(huán)境監(jiān)測[10]、定位[11-12]和目標(biāo)跟蹤[13-14]等方面已經(jīng)有了廣泛應(yīng)用。Gan等提出的KMOR（K-measn with outlier removol）[15]算 法 以 及Ahemd等提出的ODC（Outlier Detection and Clustering）[16]算法都在執(zhí)行聚類的同時就能進(jìn)行檢測離群點的任務(wù)，這是基于聚類的離群點檢測的最大優(yōu)點。目前，沒有任何一種聚類方法都適用于所有數(shù)據(jù)集，不同數(shù)據(jù)集需要采用不同的聚類方法，這是聚類方法的最大缺點，同時，也是基于聚類的離群點檢測的最大缺點。

文獻(xiàn)[17]從有監(jiān)督和無監(jiān)督的角度入手概述了基于深度學(xué)習(xí)的離群點檢測方法，文獻(xiàn)[18-19]綜述了傳統(tǒng)的和前沿主流的檢測方法，其中都對基于聚類的檢測方法有所提及。但是之前的綜述研究均沒有對基于聚類的檢測方法做出系統(tǒng)總結(jié)與分析。為了及時掌握當(dāng)前基于聚類技術(shù)的離群點檢測方法的研究現(xiàn)狀，本文通過歸納與整理，將具有代表性的基于聚類的離群點檢測方法進(jìn)行了介紹和歸類，將其主要分為靜態(tài)數(shù)據(jù)集中的檢測方法、數(shù)據(jù)流中的檢測方法、大規(guī)模數(shù)據(jù)中的檢測方法和其他方法等四大類。對每類方法所解決的問題、算法思想、應(yīng)用場景以及各自的優(yōu)缺點進(jìn)行了詳細(xì)地歸納和分析，并分析目前存在的問題以及提出未來發(fā)展方向。

1 基于聚類的離群點檢測方法分類

1.1 靜態(tài)數(shù)據(jù)集中的檢測方法

靜態(tài)數(shù)據(jù)是指在運行過程中主要作為控制或參考用的數(shù)據(jù)，它們在很長的一段時間內(nèi)不會變化，一般不隨運行而改變。聚類技術(shù)在靜態(tài)數(shù)據(jù)集中離群點檢測方法可以分為定量分析法和定性分析法。定量分析法主要包括采用離群因子、熵等來檢測離群點的方法，它們對數(shù)據(jù)點具有明確的離群程度度量，即離群因子或者熵越大，離群程度就越大。而采用距離與概率等的方法中，只能判別數(shù)據(jù)點是否是離群點，這些方法是定性分析的，定性分析法對離群程度沒有明確的度量。

1.1.1 定量分析方法

在數(shù)據(jù)處理中，離群點往往包含重要的信息，一個數(shù)據(jù)點具有多大的離群程度需要根據(jù)不同的應(yīng)用環(huán)境獲得，有些離群點可以被“容忍”。

Zhang等人[20]引入了一種稱為基于局部距離的離群因子LDOF（Local Distance-based Outlier Factor）來度量散亂數(shù)據(jù)集中的離群點。

文獻(xiàn)[21]使用K-means算法對聚類中心周圍的一些點進(jìn)行剪枝，并使用LDOF從剩余的數(shù)據(jù)點中識別離群點。文獻(xiàn)[22]提出了一種基于聚類的離群點檢測（Clurstering Based Outlier Dectection，CBOD）的兩階段算法來檢測數(shù)據(jù)集中的離群點。在第一階段，采用one-pass聚類算法將數(shù)據(jù)集劃分為半徑幾乎相同的超球體。在第二階段，計算第一階段得到的所有數(shù)據(jù)的離群因子，并根據(jù)其離群因子對數(shù)據(jù)點進(jìn)行排序，具有高離群因子的數(shù)據(jù)點被視為離群點。

Li等人[23]基于FCM里面隸屬度和信息論里面熵的概念提出了一種基于信息熵的離群點檢測方法，他們把聚類之后得到的隸屬度看作數(shù)據(jù)點屬于對應(yīng)類別的概率，通過熵來度量數(shù)據(jù)點的離群程度，計算得到每一個數(shù)據(jù)點的熵值，將其按從大到小的順序排列，找到數(shù)據(jù)集中的離群點。

Breunig等人同樣提出了局部離群因子的概念[24-25]，這是一種基于密度的方法，這種方法不再將離群點看做一個二值屬性，而是量化地描述數(shù)據(jù)對象的離群程度，其能在數(shù)據(jù)分布不均的情況下準(zhǔn)確發(fā)現(xiàn)離群點，但由于離群點在數(shù)據(jù)集中所占的比重較小，直接計算數(shù)據(jù)對象的離群度會增大計算量。Chen等人[26]提出了基于粗糙集理論的混合數(shù)據(jù)離群點檢測算法，首先指定數(shù)據(jù)對象每個屬性的粗糙鄰域，再利用屬性值的差異性計算對象的離群程度，但該算法的檢測結(jié)果對人工指定的屬性粗糙鄰域范圍參數(shù)十分敏感，針對上述缺點，文獻(xiàn)[27]提出了改進(jìn)的DBSCAN聚類和LAOF兩階段混合數(shù)據(jù)的離群點檢測算法，在第一階段，通過輸入K近鄰的個數(shù)代替Minpts并通過K近鄰確定聚類半徑，從而減少參數(shù)輸入進(jìn)而提高聚類質(zhì)量，通過改進(jìn)的DBSCAN對混合數(shù)據(jù)進(jìn)行初步篩選，然后利用新構(gòu)造的LAOF計算篩選后數(shù)據(jù)的離群程度，在混合數(shù)據(jù)進(jìn)行距離度量的過程中采用除一化信息熵差值確定屬性權(quán)重，并在第二階段進(jìn)行二次權(quán)重確定。最后利用真實數(shù)據(jù)對提出的算法進(jìn)行了驗證，結(jié)果顯示該算法能夠提高離群點檢測的精度，降低計算復(fù)雜度，但該算法中參數(shù)K值的選取直接影響聚類結(jié)果。

文獻(xiàn)[28]從定義出發(fā)，提出基于聚類的局部離群點的概念。他們解釋了局部的定義，即小聚類在宏觀上可以看作離它最近的大聚類的局部，給出倍數(shù)β來作為大小聚類的判別。通過新的局部概念，提出了CBLOF（Cluster-Based Local Outlier Factor）的計算公式，計算得到每一個數(shù)據(jù)點的局部離群因子來表征離群程度。

Jiang等人[29]利用離群點檢測技術(shù)初始化K-modes聚類，避免離群點被選作聚類中心，影響聚類結(jié)果。他們根據(jù)數(shù)據(jù)集中的簡單距離提出了屬性加權(quán)距離，即不同的屬性對數(shù)據(jù)的影響不同。在這個定義下，提出兩種表征離群程度的方法。第一種是傳統(tǒng)的基于距離的方法，用DOF衡量離群度。第二種是基于屬性熵的檢測方法，根據(jù)提出的屬性加權(quán)距離得到每一個數(shù)據(jù)的屬性熵，計算得到其基于熵的離群因子PEOF來表征離群程度。

文獻(xiàn)[30-34]提出了類似的用信息熵或離群因子來表征離群程度的方法。這些方法的優(yōu)點十分明顯，它們能夠表征離群點的離群程度，給研究者很重要的參考來判斷哪些離群點可以被“容忍”。

各種離群因子計算公式如下：

u ij表示數(shù)據(jù)x的隸屬度，c是聚類個數(shù)[23]：

對象p的局部離群因子表示為LA(p)與它的k個鄰居局部密度均值比值的倒數(shù)[27]：

|Ci|*表示數(shù)據(jù)集C i的大小，SC、LC分別表示小、大數(shù)據(jù)集，C j為離C i最近的大數(shù)據(jù)集[28]：

數(shù)據(jù)點x的離群因子表示為加權(quán)距離w d(x,y)大于參數(shù)dis的點的個數(shù)與數(shù)據(jù)集大小的比值[29]：

然而，這些方法的缺點也顯而易見，從計算公式（1）～（4）中可以看出，無論是信息熵還是離群因子的計算，都要首先得到數(shù)據(jù)點與其他所有點的距離或者數(shù)據(jù)點周圍其他點的密度，這對于大型高維數(shù)據(jù)集，計算復(fù)雜度會大大增加。

1.1.2 定性分析方法

定性分析方法與定量分析方法的區(qū)別是有相應(yīng)的閾值來判別離群點。

文獻(xiàn)[35]提出了基于K均值和層次聚類的離群點檢測與去除方法，先執(zhí)行任意一種聚類方法，直接將小簇當(dāng)作離群簇去除，然后計算每一對數(shù)據(jù)點之間的距離，提出一個閾值，該閾值是最大距離與最小距離和的一半，如果數(shù)據(jù)點與聚類中心的距離大于這個閾值，則該點視為離群點，把離群點去除后，聚類效果得到提升。這個閾值是噪聲距離的原型。Rehm等人[36]提出了更為復(fù)雜精確的方法，他們引入了單獨的離群簇，將所有的離群點歸類到這一簇中，基于特征空間中超體積的概念給出了新的噪聲距離的計算公式，通過實驗證明，這個閾值更加精確。

Saha等[37]采用了一種綜合的方法檢測離群點，他們的亮點在于提出了硬聚類中隸屬度的概念，先使用Kmeans、K-mean++和FCM對數(shù)據(jù)集分別進(jìn)行聚類，得到相應(yīng)的隸屬度，把隸屬度當(dāng)作數(shù)據(jù)點屬于相應(yīng)類別的概率，然后根據(jù)加權(quán)概率公式，算出總概率。最終給出閾值的計算過程，如果加權(quán)概率中最大的概率小于此閾值，該點就被視為離群點。如公式（6）中，K為聚類個數(shù)，θ為所設(shè)置的閾值，需通過多次實驗獲得，當(dāng)閾值減小時，被檢測到的離群點個數(shù)隨之減少，反之增加。

Dan等[38]發(fā)現(xiàn)通過傳統(tǒng)的FCM算法能巧妙地檢測離群點。他們根據(jù)FCM的目標(biāo)函數(shù)發(fā)現(xiàn)離群點的存在會使其值顯著變大，也就是說，把離群點去除后，目標(biāo)函數(shù)值會顯著減小，他們通過實驗證明了把每一個數(shù)據(jù)依次剔除，觀察目標(biāo)函數(shù)值的變化量能很好地判別離群點。對于“顯著”的判斷，他們同樣提出了閾值——目標(biāo)函數(shù)值平均變化量的T倍，T是研究者自己確定的。如公式（7）中，T通常情況下取1.5得到的檢測效果最佳，若T減小，則檢測到的離群點個數(shù)增加，反之減少。

相關(guān)的判別公式：

u cj表示第j個點對應(yīng)于第c類的隸屬度，μ、σ為噪聲聚類隸屬度的均值和標(biāo)準(zhǔn)差，β為提出的閾值[36]：

P[i][j]為三種聚類執(zhí)行后得到的綜合概率，k為聚類個數(shù)，θ為提出的閾值[37]：

DOFi為去除第i個點得到的目標(biāo)函數(shù)值變化量，AvgDOF為平均變化量，T為提出的閾值[38]：

文獻(xiàn)[39-41]同樣提出了類似的定性分析方法，都是通過一個界限即閾值來判別離群點，如公式（5）～（7），表述起來十分清晰方便，這是區(qū)別于定量分析的最大優(yōu)點，然而，閾值（β,θ,T等）的確定是一項復(fù)雜的工作，需要大量實驗的支撐，并且涉及到大量參數(shù)，上述方法幾乎都是在閾值的確定方面做出了創(chuàng)新。

定量分析方法和定性分析方法都有同樣的缺點，即計算復(fù)雜度過高，對于大型高維數(shù)據(jù)集的處理十分困難。在基于K近鄰的離群檢測方法中，文獻(xiàn)[42]提出了在Hadoop平臺上采用分布式計算的方法來解決計算太過復(fù)雜的問題。但是，在基于聚類的領(lǐng)域，大型高維數(shù)據(jù)仍然是一個棘手的問題。

1.2 數(shù)據(jù)流中的檢測方法

在前一節(jié)中提出的檢測方法大多只適用靜態(tài)數(shù)據(jù)集，然而，數(shù)據(jù)流在許多應(yīng)用中越來越常見。由于數(shù)據(jù)流的輸入是動態(tài)變化的，這使得有監(jiān)督的方法基本無從下手，所以無監(jiān)督的聚類方法更適合數(shù)據(jù)流的離群檢測。

文獻(xiàn)[43]中基于距離的數(shù)據(jù)流離群點挖掘算法DSOBD主要是通過計算各個數(shù)據(jù)塊中每個數(shù)據(jù)點與其他所有數(shù)據(jù)點的距離計算離群度的方式判斷是否為離群點。在閾值合適時，此算法檢測的精確度比大多數(shù)算法高，但對于大數(shù)據(jù)集，由于該算法對每個數(shù)據(jù)都需要計算離群度導(dǎo)致運行效率低。文獻(xiàn)[44]把檢測過程分為兩個階段，首先將滑動窗口固定大小，第一階段對滑動窗口中的數(shù)據(jù)進(jìn)行聚類，第二階段負(fù)責(zé)把小規(guī)模的遠(yuǎn)離其他簇的小簇挑選出來作為離群點集。這個算法實現(xiàn)了無監(jiān)督的檢測，但它單一地認(rèn)為離群點就是小簇，這是不合理的。針對以上缺點，文獻(xiàn)[45]提出了動態(tài)離群點檢測算法（Dynamic Outlier detection based onKMeans，DOKM），同樣先使用K-means算法對初始滑動窗口聚類找出小簇并視為離群點集，然后計算剩下的數(shù)據(jù)點的相對距離，如果此距離大于一定閾值，則該點被視為離群點，同時在滑動窗口中刪除此點。該方法完善了前一個方法檢測到的離群點的類型，改善了檢測結(jié)果，并減少了運行時間。

文獻(xiàn)[46]采用頻繁項集的方法處理流數(shù)據(jù)，Zeng等人[47]提出通過對流數(shù)據(jù)進(jìn)行劃分先進(jìn)行K-means聚類，然后進(jìn)行聚合聚類的流數(shù)據(jù)噪聲檢測算法。文獻(xiàn)[48-49]提出一種基于K均值的數(shù)據(jù)流聚類方法，算法將數(shù)據(jù)流中數(shù)據(jù)進(jìn)行分區(qū)，順序的s個數(shù)據(jù)點構(gòu)成一個區(qū)域，輸入s個數(shù)據(jù)點，按照K-Means聚類算法從中找出K個均指點，每個點的權(quán)重為隸屬于該均指點的數(shù)據(jù)點數(shù)目，重復(fù)這一步驟，直到內(nèi)存中生成s個均值點，對應(yīng)層次聚類算法的第1層聚類效果；對生成的s個均值點按照K-Means聚類算法從中找出2K個中心點，同時更新這些均值點的權(quán)重；繼續(xù)讀入s個數(shù)據(jù)點，進(jìn)入下一層聚類。借鑒這一方法，倪巍偉等人[50]提出基于K均值分區(qū)的流數(shù)據(jù)離群點發(fā)現(xiàn)算法（Data Stream Outliers detection alogorithm based onK-means Partioning，DSOKP）算法，該算法通過對流數(shù)據(jù)進(jìn)行分區(qū)，在每個分區(qū)內(nèi)基于K-means聚類獲得均值點集，然后識別出異常數(shù)據(jù)，此算法可以有效解決數(shù)據(jù)流離群點檢測問題，但參數(shù)K的選取依然對算法效能存在較大影響。

文獻(xiàn)[51]提出了一種無監(jiān)督的快速準(zhǔn)確多維序列異常檢測方法（unsupervised Fast and Accurate Anomaly Detection，F(xiàn)AAD）來檢測數(shù)據(jù)流中的離群點，首先，采用信息計算和最小生成樹聚類的方法減少冗余維數(shù)；其次，為了適應(yīng)數(shù)據(jù)流的動態(tài)特性，加快模型的構(gòu)建，提出了基于RSIPST（Random Sampling and subsequence partitioning based on the Index Probabilistic Suffix Tree）的隨機(jī)采樣和子序列劃分方法；最后，用ABMDA（Anomaly buffer Based on the Model Dynamic Adjustment）降低概念漂移的影響。同樣，為了能夠及時發(fā)現(xiàn)異?，F(xiàn)象，Yogita等[52]利用加權(quán)屬性矩陣來檢測離群點，通過計算當(dāng)前和以前的方差矩陣來更新權(quán)重和聚類中心。文獻(xiàn)[53]提出了基于離群點檢測的不確定數(shù)據(jù)流聚類算法，先把數(shù)據(jù)集劃分成若干個微聚類;然后，根據(jù)過濾機(jī)制獲取全局離群點，在離群點微聚類中使用基于距離的方法挖掘出局部離群點；最后，采用不確定數(shù)據(jù)流子空間聚類算法完成全局離群點以及局部離群點兩種不確定數(shù)據(jù)流聚類。這種方法在數(shù)據(jù)維度和數(shù)據(jù)規(guī)模增加時，不會對算法結(jié)果產(chǎn)生太大影響，因此穩(wěn)當(dāng)性較好。

文獻(xiàn)[54-56]也提出了類似的數(shù)據(jù)流中的檢測方法，但是數(shù)據(jù)流中的離群檢測與靜態(tài)數(shù)據(jù)相比面臨更大的挑戰(zhàn)，首先，數(shù)據(jù)流中的冗余維數(shù)和較大的狀態(tài)空間會導(dǎo)致對數(shù)據(jù)的建模能力差；其次，數(shù)據(jù)流是連續(xù)的，速度很快，這就需要離群檢測方法具有實時性；最后，與靜態(tài)數(shù)據(jù)相比會出現(xiàn)概念漂移的現(xiàn)象，新的數(shù)據(jù)可能與歷史數(shù)據(jù)的特征完全不一致，從而影響檢測性能。

1.3 大規(guī)模數(shù)據(jù)集中的檢測方法

隨著數(shù)據(jù)規(guī)模的不斷增長，傳統(tǒng)的集中式算法計算復(fù)雜，處理效率受限，無法滿足用戶日益增長的需求?；诰垲惖臋z測方法對于大規(guī)模數(shù)據(jù)處理起來十分困難，也是亟待研究的領(lǐng)域，但也有少量的學(xué)者在這個方面做出了研究，大多以分布式計算作為解決問題的手段。

文獻(xiàn)[57]提出了一種多步異常檢測方法，他們基于互信息和廣義熵的特征選擇技術(shù)來選擇相關(guān)的非冗余特征子集，基于生成樹的聚類技術(shù)生成一組參考點和一個離群值函數(shù)來對傳入的網(wǎng)絡(luò)流量進(jìn)行排序以識別異常，設(shè)計了一個快速的分布式特征提取和數(shù)據(jù)準(zhǔn)備框架，從原始網(wǎng)絡(luò)流量中提取特征。張?zhí)煊覽58]提出基于網(wǎng)格劃分的高維大數(shù)據(jù)集離群點檢測算法，先對高維空間進(jìn)行網(wǎng)格劃分，之后對剩余離群點集進(jìn)行檢測，但在網(wǎng)格劃分時，時效將成指數(shù)增長。

王習(xí)特等人在大規(guī)模數(shù)據(jù)檢測方面具有代表性。文獻(xiàn)[31]提出了一種基于網(wǎng)格的劃分算法（Gird-Based Partition algorithm，GBP）作為數(shù)據(jù)預(yù)處理的方法，該方法把數(shù)據(jù)集分成幾個網(wǎng)格，然后將這些網(wǎng)格分配給分布式環(huán)境中的數(shù)據(jù)節(jié)點，其次，提出了一種分布式LOF計算方法（Distributed LOF Computing，DLC），它只需要少量的網(wǎng)絡(luò)通信就可以并行檢測基于密度的離群值。文獻(xiàn)[59]提出了一種新型的分布式離群點檢測算法，在預(yù)處理階段，設(shè)計了新的BDSP（Balance Driven Spatial Partitioning）數(shù)據(jù)劃分算法，實現(xiàn)了良好的過濾效果，降低了網(wǎng)絡(luò)開銷。在這種劃分算法的基礎(chǔ)上，提出了BOD（BDSP-based Outlier Detection）檢測算法，第一步，利用R樹索引進(jìn)行批量過濾，快速地計算離群點并得到本地候選集，第二步，利用BDSP中提供的塊編碼確定需要相互通信的節(jié)點，使用少量的網(wǎng)絡(luò)開銷得到最終的結(jié)果。文獻(xiàn)[60]提出了更為高效的DACB（Distributed Algorithm for the Cluster-Based outlier detection）算法檢測離群點，主節(jié)點根據(jù)每個從節(jié)點上權(quán)重較大的點計算閾值，在每個從節(jié)點上設(shè)計了一種剪枝方法加快KNN的搜索速度，并利用閾值過濾掉大量冗余節(jié)點，最后通過一系列的仿真實驗證明這個方法能有效地減少分布式異常點檢測的運行時間和網(wǎng)絡(luò)傳輸量。

Google提出的MapReduce是一種用于大規(guī)模數(shù)據(jù)集的并行運算編程模型，能夠處理T級別以上巨量數(shù)據(jù)的業(yè)務(wù)[61]，Apache基金會開發(fā)的Hadoop分布式系統(tǒng)能夠很好地處理巨量數(shù)據(jù)，劉亞梅等[62]發(fā)現(xiàn)王習(xí)特等人提出的BOD算法對全局離群點具有良好的檢測率，但不適用于局部離群點。于是，將傳統(tǒng)的檢測方法LOF和Hadoop分布式平臺下的MapReduce框架結(jié)合，實現(xiàn)了并行化策略，并通過密度聚類算法DBSCAN對其進(jìn)行了改進(jìn)，但在進(jìn)行并行化操作時聚類效果會受到影響，并且這種方法對參數(shù)(ε,MinPts)和K距離參數(shù)比較敏感。

文獻(xiàn)[63]在LDOF算法的基礎(chǔ)上，提出了一種基于多重聚類的離群點檢測算法PMLDOF，該算法針對局部離群度量計算量大的缺點，采用聚類剪枝技術(shù)作為減少計算量的方法，同時，為了避免將位于簇邊緣的離群點錯剪，算法利用多重聚類的差異性對簇的邊緣點進(jìn)行篩選。在對數(shù)據(jù)集進(jìn)行剪枝后，計算剩余數(shù)據(jù)的局部離群度LDOF，并找出符合條件的離群數(shù)據(jù)點，此算法在時間復(fù)雜度和檢測精度上具有良好的優(yōu)越性。

文獻(xiàn)[64-66]同樣給出了在大規(guī)模數(shù)據(jù)集上的處理方法，由于聚類算法在大規(guī)模數(shù)據(jù)集處理上的局限性，其檢測方法同樣不多。目前對大規(guī)模數(shù)據(jù)集的處理主要集中在兩個方面：首先，在數(shù)據(jù)預(yù)處理方面，對數(shù)據(jù)集進(jìn)行剪枝[67]、降維[68]，或如文獻(xiàn)[59]中提出新的數(shù)據(jù)劃分方法，平均化每個節(jié)點上的工作負(fù)載，提高并行性，降低網(wǎng)絡(luò)開銷。其次，采用Hadoop平臺上的MapReduce模型框架，解決數(shù)據(jù)規(guī)模過大的問題。

1.4 其他檢測方法

除了以上三類主要檢測方法外，依然有一些其他檢測方法。文獻(xiàn)[69]提出了三階段K-means算法，對數(shù)值型數(shù)據(jù)進(jìn)行聚類和離群點檢測。文獻(xiàn)[70]提出了一種用于離群點檢測的兩階段聚類算法。在第一階段，對K-means算法進(jìn)行了改進(jìn)，當(dāng)數(shù)據(jù)點遠(yuǎn)離所有聚類時，將這個數(shù)據(jù)點指定為一個新的聚類中心。在第二階段，根據(jù)第一階段得到的聚類中心構(gòu)造最小生成樹，在小子樹中的簇被視為離群點。文獻(xiàn)[71]提出了一種同時從數(shù)據(jù)集中聚類和識別離群點的ORC（Outlier Removal Clustering）算法。ORC算法由兩個連續(xù)的階段組成：第一階段是純K-means算法；第二階段迭代地刪除遠(yuǎn)離聚類中心的數(shù)據(jù)點。文獻(xiàn)[72]提出了一種基于馬氏距離的離群點檢測方法。文獻(xiàn)[73]提出了K-means-L算法，它需要兩個參數(shù)：K和L，分別指定所需的聚類數(shù)和期望的最大離群點數(shù)量。

針對傳統(tǒng)的基于最小生成樹的聚類算法時空復(fù)雜度過高且容易漏檢較大簇中局部離群點的問題，文獻(xiàn)[74]將基于K近鄰與基于聚類方法的優(yōu)勢相結(jié)合，提出了一種快速K-NN的最小生成樹聚類離群檢測方法，減小了時空復(fù)雜度。該方法首先在數(shù)據(jù)集上構(gòu)建平分樹，計算數(shù)據(jù)點的K近鄰，然后減枝確定全局離群點，通過計算局部離群因子來檢測局部離群點，該方法能夠自適應(yīng)的識別聚類數(shù)目并且能夠檢測出多種類型的離群點。

基于密度的聚類通常需要輸入大量的參數(shù)，這時參數(shù)的選擇在很大程度上會影響聚類以及檢測的效果。邱華等[75]以用電數(shù)據(jù)上傳過程中的掉線問題為對象，研究一種基于極限學(xué)習(xí)機(jī)的密度聚類離群點檢測方法，他們發(fā)現(xiàn)傳統(tǒng)的LOF算法對于智能電表的報文數(shù)據(jù)掉線分析效果不理想，于是在此基礎(chǔ)上，提出了基于權(quán)值的局部離群因子（WLOF）算法，把預(yù)處理后的歷史報文數(shù)據(jù)放入ELM進(jìn)行訓(xùn)練，預(yù)測得到判別離群點的WLOF閾值，再用密度聚類算法對實時數(shù)據(jù)進(jìn)行離群點檢測。這種算法不用知道離群檢測的閾值，拓寬了算法的應(yīng)用范圍。

同樣，為了解決參數(shù)輸入過多的問題，文獻(xiàn)[76]將自然鄰居搜索算法和密度聚類算法相結(jié)合，提出了基于聚類離群因子和相互密度的離群點檢測方法，他們使用相互密度和γ密度構(gòu)造決策圖，將γ密度異常大的樣本點作為聚類中心進(jìn)行聚類，最后根據(jù)聚類的離群因子找出離群聚類邊界檢測離群點。OPTICS也是常用的基于密度的聚類方法，文獻(xiàn)[77]提出了OD-OPTICS算法，為了過濾無效半徑，選擇合適的半徑，在覆蓋空間（coverspace）中提出了半徑過濾策略（RFS），重新定義了核距離（core-distance），更加突出了離群點與正常點之間的不同。

離群點檢測的方法很多，應(yīng)用場景也多種多樣，例如在文獻(xiàn)[78]中，利用離群檢測提出了OEDP-K-means方法來保護(hù)數(shù)據(jù)挖掘過程中暴露的個人隱私，文獻(xiàn)[79]采用兩步無監(jiān)督的聚類方法應(yīng)用于醫(yī)療欺詐的檢測。不管是哪種方法，他們都以聚類為背景檢測離群點，在不同領(lǐng)域做出了貢獻(xiàn)。

2 方法總結(jié)及存在的主要問題和進(jìn)一步研究方向

靜態(tài)數(shù)據(jù)集與數(shù)據(jù)流是相互對立的，因此在檢測離群點時所應(yīng)用的方法和所要解決的問題截然不同，然而大規(guī)模數(shù)據(jù)集中的檢測方法與上述兩種稍有重合，只不過它的重點在于如何解決計算復(fù)雜度過高這個難題，比如對其進(jìn)行剪枝、降維等?；诰垲惖碾x群點檢測方法方便高效，在進(jìn)行聚類的同時，就能完成檢測離群點的任務(wù)，由于無監(jiān)督學(xué)習(xí)的特點決定了數(shù)據(jù)無需類標(biāo)簽，因此適用于大多數(shù)數(shù)據(jù)，這是其他方法不可比擬的。

同時，它的不足與劣勢也十分明顯：

（1）基于聚類的離群點檢測方法檢測結(jié)果的好壞受到聚類方法本身的制約，對于不同的數(shù)據(jù)集沒有普遍適用的聚類方法，因此，對于不同的應(yīng)用場景和數(shù)據(jù)特征，需要對算法進(jìn)行調(diào)整，這就增加了應(yīng)用的難度。

（2）在靜態(tài)數(shù)據(jù)集中，定量與定性分析從兩種截然不同的角度判別離群點，定量分析中離群因子與熵值大小能夠明確衡量離群程度，它們的得出往往需要計算每個數(shù)據(jù)點與其他所有數(shù)據(jù)點之間的距離或者與周圍點的密度，當(dāng)數(shù)據(jù)維數(shù)比較高，數(shù)據(jù)集比較龐大的時候，這種方法運行起來就十分困難，計算就比較復(fù)雜，在文獻(xiàn)[27]中，由于傳統(tǒng)的LOF算法計算可達(dá)距離和可達(dá)密度的時間復(fù)雜度較高為o(Nk2)，所以對該算法的相關(guān)定義進(jìn)行了改進(jìn)，采用數(shù)據(jù)對象的K距離作為可達(dá)距離并用區(qū)域半徑求得區(qū)域面積代替距離和，這樣就降低了時間復(fù)雜度變?yōu)榱薿(Nk)，定性分析中根據(jù)閾值來判別離群點簡潔明了，但閾值的確定是個十分復(fù)雜的問題，文獻(xiàn)[36]提出了基于特征空間超體積概念的噪聲距離確定方法，對于其中參數(shù)α的確定需要大量實驗，在文獻(xiàn)[38]中，通過大量實驗提出了將目標(biāo)函數(shù)值的平均變化量的T倍作為閾值，其中T的確定同樣需要重復(fù)實驗多次。

（3）在數(shù)據(jù)流中，無監(jiān)督的方法更加適用動態(tài)變化的數(shù)據(jù)，但冗余維數(shù)和較大的狀態(tài)空間導(dǎo)致數(shù)據(jù)建模能力差，不斷變化的數(shù)據(jù)需要算法具有很強的及時性。文獻(xiàn)[45]提出的DOKM算法在檢測離群點的同時也優(yōu)化了聚類，但是此算法只能檢測數(shù)值型數(shù)據(jù)，并且質(zhì)心的初始值隨機(jī)性比較大。文獻(xiàn)[50]提出的基于K均值分區(qū)的檢測算法需要對數(shù)據(jù)流先進(jìn)行聚類生成均值參考點，而K-均值聚類效果受K的影響較大，因此參數(shù)K的選取對該算法效能具有很大影響。

（4）在大規(guī)模數(shù)據(jù)中，基于聚類的檢測方法面臨巨大挑戰(zhàn)，離群因子、熵、閾值等的計算復(fù)雜度過高是急需解決的問題。文獻(xiàn)[59]研究了分布式環(huán)境下的離群點檢測方法，在數(shù)據(jù)預(yù)處理階段，他們提出了新型的數(shù)據(jù)劃分方法BDSP來均衡每個計算節(jié)點的工作負(fù)載并具有良好的過濾效果，基于BDSP算法提出了BOD分布式離群點檢測方法，提高了計算效率并大幅降低了網(wǎng)絡(luò)開銷。劉亞梅等[62]采用Hadoop平臺上的MapReduce模型框架，以Hbase作為數(shù)據(jù)庫，解決了數(shù)據(jù)規(guī)模過大的問題，但是由于對數(shù)據(jù)進(jìn)行并行化操作時導(dǎo)致數(shù)據(jù)集聚類效果受到影響，并且此算法同樣對參數(shù)(ε,MinPts)和K距離參數(shù)比較敏感。

在基于聚類的離群檢測領(lǐng)域，未來應(yīng)該針對上述問題提出相應(yīng)解決方法：

（1）研究一種或幾種具有普適性的且運行穩(wěn)定的針對離群點檢測的聚類算法，在該算法的指導(dǎo)下使離群檢測能夠適用大部分?jǐn)?shù)據(jù)集以及更多的應(yīng)用場景。

（2）針對靜態(tài)數(shù)據(jù)集中的離群點檢測，需要對閾值的計算方法進(jìn)行創(chuàng)新，因此需要研究新的離群因子模型，給出更為精確的閾值計算公式是當(dāng)下研究的關(guān)鍵。

（3）針對數(shù)據(jù)流中的離群點檢測，需要解決對流數(shù)據(jù)的及時適應(yīng)的問題，如何減少數(shù)據(jù)的冗余維數(shù)以及提高時效性是未來需要研究的方向。

（4）針對大規(guī)模數(shù)據(jù)集中的離群點檢測，需要研究數(shù)據(jù)預(yù)處理方法，進(jìn)而減小數(shù)據(jù)量，同時，與并行計算相結(jié)合是未來研究的趨勢。

最后，把本文涉及到的文獻(xiàn)與對應(yīng)的檢測方法類別進(jìn)行了整理，如表1所示。

表1 典型檢測方法描述與優(yōu)缺點

3 結(jié)語

基于聚類的離群檢測方法在眾多方法中具有明顯優(yōu)勢，本文主要從數(shù)據(jù)類型的角度對其進(jìn)行了分類，在靜態(tài)數(shù)據(jù)集中又從定性定量的角度進(jìn)行了劃分。在離群檢測領(lǐng)域，大量的方法已被研究者提出，無論是基于統(tǒng)計的，基于密度的，基于距離的還是基于聚類的方法，它們在大規(guī)模高維數(shù)據(jù)集方面都存在一定的局限性，隨著大數(shù)據(jù)和分布式計算時代的到來，相信這些檢測方法會迎來新的突破。