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

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

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

離群點(diǎn)是聚類的副產(chǎn)品，因此對(duì)常見(jiàn)的聚類算法，如K-means、DBSCAN[2]、CHAMELEON[3]、CLIQUE[4]等加以修改都可將其用于離群點(diǎn)檢測(cè)，這些方法大多通過(guò)考慮數(shù)據(jù)對(duì)象與簇之間的關(guān)系檢測(cè)離群點(diǎn)。離群點(diǎn)檢測(cè)是數(shù)據(jù)預(yù)處理中的一項(xiàng)重要任務(wù)，它的目的是發(fā)現(xiàn)數(shù)據(jù)集中與大多數(shù)數(shù)據(jù)偏離較遠(yuǎn)的對(duì)象[5]。離群點(diǎn)不一定是錯(cuò)誤的數(shù)據(jù)，它們往往包含著重要信息，能夠表征數(shù)據(jù)集的某些特點(diǎn)，具有重要研究意義。離群點(diǎn)檢測(cè)技術(shù)在欺詐檢測(cè)[6-7]、入侵檢測(cè)[8-9]、環(huán)境監(jiān)測(cè)[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í)行聚類的同時(shí)就能進(jìn)行檢測(cè)離群點(diǎn)的任務(wù)，這是基于聚類的離群點(diǎn)檢測(cè)的最大優(yōu)點(diǎn)。目前，沒(méi)有任何一種聚類方法都適用于所有數(shù)據(jù)集，不同數(shù)據(jù)集需要采用不同的聚類方法，這是聚類方法的最大缺點(diǎn)，同時(shí)，也是基于聚類的離群點(diǎn)檢測(cè)的最大缺點(diǎn)。

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

1 基于聚類的離群點(diǎn)檢測(cè)方法分類

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

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

1.1.1 定量分析方法

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

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

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

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

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

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

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

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

各種離群因子計(jì)算公式如下：

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

對(duì)象p的局部離群因子表示為L(zhǎng)A(p)與它的k個(gè)鄰居局部密度均值比值的倒數(shù)[27]：

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

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

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

1.1.2 定性分析方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4 其他檢測(cè)方法

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

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

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

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

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

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

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

同時(shí)，它的不足與劣勢(shì)也十分明顯：

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

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

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

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

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

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

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

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

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

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

表1 典型檢測(cè)方法描述與優(yōu)缺點(diǎn)

3 結(jié)語(yǔ)

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