王 欣

（中國民航飛行學院 計算機學院，廣漢 618307）

基于聚類和距離的大數(shù)據(jù)集離群點檢測算法

王 欣

（中國民航飛行學院 計算機學院，廣漢 618307）

0 引言

離群點檢測是數(shù)據(jù)挖掘技術(shù)的重要研究領(lǐng)域之一，用來發(fā)現(xiàn)數(shù)據(jù)集中明顯偏離于其他數(shù)據(jù)、不滿足數(shù)據(jù)的一般行為或模式的數(shù)據(jù)[1]。這些數(shù)據(jù)對象叫做離群點，也叫做孤立點。離群點檢測算法分為基于統(tǒng)計、深度、聚類、距離和密度的方法[2]。其中，基于距離的方法由于算法思想直觀，易于實現(xiàn)而得到了廣泛的研究和應用。

基于距離的方法大致分為嵌套循環(huán)的算法、基于索引的算法和基于單元的算法。但這些方法在處理大規(guī)模數(shù)據(jù)集時都存在性能上的不足。嵌套循環(huán)算法通過循環(huán)掃描數(shù)據(jù)集為各樣本尋找近鄰，復雜度為O（N2×d）（其中N為數(shù)據(jù)集中對象個數(shù)，d為數(shù)據(jù)的維數(shù)）[3]?；谒饕乃惴ㄍㄟ^建立多維索引結(jié)構(gòu)為各樣本尋找近鄰，最壞情況下的復雜度為O（N2×d）。但在大數(shù)據(jù)集上建立索引的開銷很大，而且隨著維數(shù)的增大，索引的性能急劇下降，性能不如簡單的順序掃描[4]?；趩卧乃惴ǖ膹碗s度與N呈線性關(guān)系，但與d呈指數(shù)關(guān)系，因此很難處理高維數(shù)據(jù)。

利用嵌套循環(huán)算法對維數(shù)不敏感，針對其在大數(shù)據(jù)集上效率低下的問題，本文提出基于聚類和距離的混合離群檢測算法（Clustering and Distance-based Outlier Detection，CDOD）。算法首先對數(shù)據(jù)集進行聚類，將得到的簇按照包含離群點的可能性大小排序，然后對排序后的簇中的數(shù)據(jù)進行基于距離的離群點檢測。實驗結(jié)果驗證了算法的可行性和有效性。

1 相關(guān)概念與定義

對于d維空間中的數(shù)據(jù)點p＝（p1，p2，…，pd）和q＝（q1，q2，…，qd），通常采用歐式距離度量它們之間的相似性。

Ramaswamy用點p和它的第k個最近鄰的距離來度量p的離群程度，記為Dk（p）[5]。Angiulli用權(quán)重wk（p）表示對象p與其k個最近鄰居的距離之和[6]。顯然wk（p）比Dk（p）更精確地度量了p的鄰域的稀疏程度。本文在wk（p）的基礎(chǔ)之上定義了度量數(shù)據(jù)點離群程度的離群因子。

定義1（點p的離群因子）對于數(shù)據(jù)集D，給定參數(shù)k和p ∈ D，則點p的離群因子定義為p與其k個最近鄰對象的平均距離：

其中，kNN（p）表示p在D中的k個最近鄰元素的集合。Da（p）越大，表示p越遠離k-鄰域內(nèi)的近鄰，成為離群點的可能性越大。

離群點檢測算法可以描述為：計算數(shù)據(jù)集D中每個數(shù)據(jù)點的離群因子Da，將其按從大到小降序排列，離群因子最高的前n個點就是所求的離群點，即Top-n離群點。

要得到Top-n離群點，需要計算每個點的離群因子Da（p），相應地需要計算每個點與數(shù)據(jù)集中其它點之間的距離以搜索該點的k個最近鄰，導致O（N2）的時間復雜度。因此提高算法效率的關(guān)鍵在于減少k近鄰搜索時數(shù)據(jù)點之間距離計算的次數(shù)。

減少距離計算的主要思想是：對于占數(shù)據(jù)集絕大多數(shù)的正常數(shù)據(jù)，在搜索每個數(shù)據(jù)的k個最近鄰的過程中，如果能盡可能早地確定其為非離群點，就可以立即中斷最近鄰搜索，節(jié)省距離計算。這一過程稱為近似最近鄰搜索。其實現(xiàn)方法是：取當前已得到的n個離群點中的Da值的最小值作為剪枝閾值，記為Omin。該值隨著已檢查數(shù)據(jù)集的增大而單調(diào)遞增。而根據(jù)點p當前的k個最近鄰計算得到的Da（p）值隨著新的近鄰點的發(fā)現(xiàn)而單調(diào)遞減。因此如果當前的Da（p）＜Omin，就可以斷定p不是離群點，而略去p與數(shù)據(jù)集中剩余點之間的距離計算。在嵌套循環(huán)的執(zhí)行過程中，如果剪枝閾值Omin能夠快速增大，就能實現(xiàn)對正常數(shù)據(jù)的高效剪枝，減少k近鄰搜索時距離計算的次數(shù)。

2 CDOD算法

CDOD算法綜合了基于聚類和基于距離的方法的特點，并使用一個啟發(fā)式規(guī)則和兩個剪枝規(guī)則來提高算法的效率。該算法第一階段對數(shù)據(jù)集進行聚類，然后采用啟發(fā)式規(guī)則估計每個簇包含離群點的可能性，按可能性從大到小進行排序。第二階段在聚類的結(jié)果上采用嵌套循環(huán)算法實現(xiàn)離群點檢測，并通過兩個剪枝規(guī)則進行高效剪枝，提高了算法的效率。

1）第一階段

這一階段的目的是對數(shù)據(jù)集進行快速的大致聚類，不尋求最優(yōu)聚類效果，算法的效率是關(guān)鍵因素。

本文采用層次聚類和k-means混合的層次k-means算法。該算法整體上是自頂向下的分裂層次聚類，在每一層次的簇的分裂過程中，采用k-means算法將選定的簇劃分為2個子簇（k取值為2）。其具體算法為：

（1） 首先從數(shù)據(jù)集中隨機選取2個點，每個點作為一個簇的初始均值或中心。對于剩余的每一個數(shù)據(jù)點，根據(jù)其與各個簇均值的距離，將其指派到最近的簇。然后重新計算每個簇的均值。這個過程不斷重復，直到簇中心不再發(fā)生變化，這樣就將數(shù)據(jù)集分解成2個簇，加入簇表中；

（2） 從簇表中選出一個包含成員個數(shù)最多的簇C；

（3） 利用k-means方法二分簇C為C1和C2；

（4） 將C1和C2加入簇表中；

（5） 重復步驟（2）～（4），直到簇表中簇的個數(shù)達到指定的個數(shù)Nc為止。以N表示數(shù)據(jù)集大小，則分裂停止時的簇個數(shù)Nc通過以下經(jīng)驗公式指定：

對于得到的簇集合LC＝{C1，C2，…，CNc}，用|Ci|表示簇中元素的個數(shù)。簇在特征空間中的尺寸，用簇半徑RCi大致表示。簇半徑是簇的中心到該簇中最遠的點之間的距離?；诰垲惖碾x群點檢測算法通常將小簇（即|Ci|小的簇）指定為離群簇[7]，直觀的想法是離群點極可能包含在元素個數(shù)少的簇中。另一方面，尺寸大的簇有可能密度較低，導致其中元素的k-鄰域較為稀疏，包含離群點的可能性較大。將這兩個因素綜合起來，用一個指標來估計一個簇包含離群點的可能性大小（Outlying Degree of a Cluster），表示為ODC＝RCi/ |Ci|。

對于后續(xù)的基于距離的離群點檢測，如果先取ODC值最大的簇中的點計算離群因子，就會使得剪枝閾值Omin快速增大，提高剪枝效率。因此，這一階段應用如下的啟發(fā)式規(guī)則：聚類算法將數(shù)據(jù)集劃分為Nc個簇后，按ODC值從大到小進行排序。假設(shè)排序后的結(jié)果為ODC（C1）≥ODC（C2）≥…≥ODC（CNc），排序后的簇傳遞給第二階段。

2）第二階段

這一階段改進了傳統(tǒng)的嵌套循環(huán)算法，在其基礎(chǔ)之上增加了兩個剪枝規(guī)則[8]。

規(guī)則1：如果Da（p）＜Omin，點p被修剪而無需進行k近鄰搜索。

規(guī)則2：對p進行k近鄰搜索過程中，假設(shè)取q與p計算距離以檢查是否為近鄰，又假設(shè)q已經(jīng)計算過Da（q）值，則可以利用Da（q）和三角不等式計算Da（p）的上界。如果該上界值小于Omin，則對象p被修剪而無需進行k近鄰搜索。

規(guī)則2推導如下：假設(shè)已計算對象q的離群因子Da（q）。對p進行k近鄰搜索時，取q與p計算距離以檢查是否為近鄰。點p，q和q的k個最近鄰之間形成k個三角形。根據(jù)三角不等式有：

（4）式兩邊同除k，得到：

q的k個最近鄰不一定是p的k個最近鄰，因此有：

根據(jù)式（5）和（6）得到：

這樣就得到Da（p）值的上界。如果該上界小于剪枝閾值Omin，即式（8）成立，說明p不可能是離群點而無需再進k近鄰搜索。

按第一階段的啟發(fā)式規(guī)則排序后的簇傳遞給這一階段。嵌套循環(huán)算法依次從C1到CNc檢測離群點。因為首先檢測ODC值大的簇中的點，導致剪枝閾值Omin迅速增大，因此對于占數(shù)據(jù)集絕大多數(shù)的正常數(shù)據(jù)，就會因為剪枝規(guī)則1和2的作用，不必精確獲得對象的k個最近鄰，就可以確定其為非離群點而中斷k近鄰搜索，減少對象間距離計算的次數(shù)。閾值Omin增大越快，內(nèi)循環(huán)k近鄰搜索時的剪枝效率越高。

算法1 改進的嵌套循環(huán)離群點檢測算法

輸入：排序后的簇集合LC，最近鄰個數(shù)k，離群點個數(shù)n

輸出：離群點集合Outliers

（1）初始化剪枝閾值Omin←0，Outliers←

（2）for each C in LC

（3）for each p in C

（4）p的最近鄰集合NN（p）←

（5）for each C in LC

（6）for each q in C，q≠p

（7）if dist (p, q)＜Omin－Da (q)

（8）goto (3)

（10）if |NN (p) |＜k or dist (p, q)＜Maxdist (p,NN (p))

（11）NN (p)＝Neighbors (p, NN (p)∪q, k)

（13）if |NN (p) |＝k and Da(p)＜Omin

（14）goto (3)

（16）end for

（17）end for

（18）Outliers＝ TopOutliers (Outliers∪p, n)

（19）Omin＝Min (Da(s) for all s in Outliers)

（20）end for

（21）end for

其中，函數(shù)Maxdist（x, S）返回x與集合S中的對象之間的最大距離。函數(shù)Neighbors（x,S, k）返回集合S中關(guān)于x的k個最近鄰。函數(shù)TopOutliers（S, n）返回集合S中Da值最大的前n個對象。

3 算法分析與實驗結(jié)果

3.1 算法復雜度分析

k-means算法的時間復雜度為O（Nkt），其中N是數(shù)據(jù)的總數(shù)，k是簇的個數(shù)，t是迭代次數(shù)，通常有k，t?N，因此算法的效率很高。CDOD算法第一階段的層次k-means算法的步驟（1）～（4）實質(zhì)是k值為2的k-means算法。在決定將數(shù)據(jù)劃分到某個簇時，只需要與2個均值點計算距離。在步驟（5）中迭代調(diào)用前面的步驟（2）～（4）直到簇分解到指定個數(shù)為止，時間復雜度是O（NNct）。因此第一階段具有線性的時間復雜度。

在第二階段，對于占數(shù)據(jù)集絕大多數(shù)的正常數(shù)據(jù)，在搜索對象的k個最近鄰時，通過高效的剪枝而盡可能早地中斷最近鄰搜索，大大減少了對象間距離計算的次數(shù)，因此第二階段具有近似線性的時間復雜度O（N×d）。綜合離群檢測的兩個階段，CDOD算法的時間復雜度與數(shù)據(jù)集大小成近似線性關(guān)系。

3.2 實驗結(jié)果

通過實驗對算法的效率進行測試分析。實驗平臺為P4 1.8GHz的CPU，1G內(nèi)存的計算機，操作系統(tǒng)為Windows XP。實驗數(shù)據(jù)集取自UCI KDD Archive的KDD Cup 1999數(shù)據(jù)集[9]。該數(shù)據(jù)集采用1998 DARPA入侵檢測數(shù)據(jù)集來構(gòu)造連接記錄和提取特征。每個連接共有42個變量，其中8個是離散型變量，其余是連續(xù)型數(shù)字變量。從全部變量中選取了20個連續(xù)型變量，并對數(shù)據(jù)記錄進行了歸一化處理。為了測試算法對數(shù)據(jù)集大小的伸縮性，取離群點個數(shù)n＝30，最近鄰個數(shù)k分別為5和10，數(shù)據(jù)集記錄個數(shù)從100K增加到700K，執(zhí)行CDOD算法和嵌套循環(huán)算法所花費的時間對比如圖1和圖2所示。

圖1 不同數(shù)據(jù)集大小下的執(zhí)行時間對比（k＝5）

圖2 不同數(shù)據(jù)集大小下的執(zhí)行時間對比（k＝10）

實驗結(jié)果說明了CDOD算法在執(zhí)行效率上優(yōu)于傳統(tǒng)的嵌套循環(huán)算法，并且隨著數(shù)據(jù)集的增大，挖掘性能更優(yōu)。

4 結(jié)束語

本文研究了大規(guī)模數(shù)據(jù)集上的離群檢測問題，提出了CDOD算法。算法綜合了基于聚類和基于距離的方法的特點。第一階段采用層次聚類和k-means的混合聚類算法對數(shù)據(jù)集進行大致聚類，并用一個啟發(fā)式規(guī)則估計每個簇包含離群點的可能性，按可能性從大到小進行排序。這一方法使得第二階段進行離群檢測時剪枝閾值可以快速增大，提高剪枝效率。第二階段在嵌套循環(huán)算法的基礎(chǔ)上增加了兩個剪枝規(guī)則，可以有效地減少對象間距離計算的次數(shù)，實現(xiàn)近似線性的時間復雜度。理論分析與實驗結(jié)果都表明了算法的可行性和效率。

[1]Han JW, Kamber M. 范明, 孟小峰, 譯. 數(shù)據(jù)挖掘概念與技術(shù)[M]. 北京: 機械工業(yè)出版社, 2004.

[2]陸聲鏈, 林士敏. 基于距離的孤立點檢測研究[J]. 計算機工程與應用, 2004, 40(33):73-75.

[3]Knorr EM, Ng RT. Algorithms for mining distance-based outliers in large datasets[C]//Proc. of the 24th VLDB Conference. New York, USA: ACM Press, 1998.

[4]Weber R, Schek H-J, Blott S. A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces[C]//Proc. of the 24th VLDB Conference. New York, USA: ACM Press, 1998.

[5]Ramaswamy S, Rastogi R, Shim K. Efficient algorithms for mining outliers from large data sets[C]//Proc. of the 2000 ACM SIGMOD Int’l Conf. on Management of Data. New York, 2000.

[6]Angiulli F, Pizzuti C. Outlier mining in large highdimensional data sets[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(2):203–215.

[7]Jiang MF, Tseng SS, Su CM. Two-phase clustering process for outlier detection[J]. Pattern Recognition Letters, 2001,22(6-7): 691-700.

[8]Vu NH, Gopalkrishnan V. Efficient pruning schemes for distance-based outlier detection[C]. Proc. of the European Conference on Machine Learning and Knowledge Discovery in Databases. 2009:160-175.

[9]Bay SD, Kibler DF. KDD Cup 1999 data[EB/OL]. http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html, 1999.

Clustering and distance-based outlier detection in large datasets

WANG Xin

針對已有的基于距離的離群點檢測算法在大數(shù)據(jù)集上擴展性差的問題，提出了基于聚類和距離混合的大數(shù)據(jù)集離群檢測算法。算法第一階段采用層次聚類和k-means混合的層次k-means算法對數(shù)據(jù)進行聚類，并按照一個啟發(fā)式規(guī)則對其進行排序。第二階段在聚類的結(jié)果上采用嵌套循環(huán)算法進行離群檢測，并通過兩個剪枝規(guī)則進行高效剪枝，減少了離群檢測時數(shù)據(jù)點之間距離計算的次數(shù)。理論分析和實驗結(jié)果證明了算法的可行性和效率。

離群點；聚類；嵌套循環(huán)；k近鄰搜索

王欣（1973－），男，四川綿陽人，副教授，博士，研究方向為數(shù)據(jù)挖掘。

TP311

A

1009-0134(2011)4(下)-0101-04

10.3969/j.issn.1009-0134.2011.4(下).29

2010-12-13

國家自然科學基金資助項目（60879022）