基于聚類和距離的大數據集離群點檢測算法

王 欣

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

基于聚類和距離的大數據集離群點檢測算法

王 欣

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

0 引言

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

基于距離的方法大致分為嵌套循環的算法、基于索引的算法和基于單元的算法。但這些方法在處理大規模數據集時都存在性能上的不足。嵌套循環算法通過循環掃描數據集為各樣本尋找近鄰，復雜度為O（N2×d）（其中N為數據集中對象個數，d為數據的維數）[3]。基于索引的算法通過建立多維索引結構為各樣本尋找近鄰，最壞情況下的復雜度為O（N2×d）。但在大數據集上建立索引的開銷很大，而且隨著維數的增大，索引的性能急劇下降，性能不如簡單的順序掃描[4]。基于單元的算法的復雜度與N呈線性關系，但與d呈指數關系，因此很難處理高維數據。

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

1 相關概念與定義

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

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

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

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

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

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

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

2 CDOD算法

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

1）第一階段

這一階段的目的是對數據集進行快速的大致聚類，不尋求最優聚類效果，算法的效率是關鍵因素。

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

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

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

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

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

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

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

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

2）第二階段

這一階段改進了傳統的嵌套循環算法，在其基礎之上增加了兩個剪枝規則[8]。

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

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

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

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

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

根據式（5）和（6）得到：

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

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

算法1 改進的嵌套循環離群點檢測算法

輸入：排序后的簇集合LC，最近鄰個數k，離群點個數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

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

3 算法分析與實驗結果

3.1 算法復雜度分析

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

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

3.2 實驗結果

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

圖1 不同數據集大小下的執行時間對比（k＝5）

圖2 不同數據集大小下的執行時間對比（k＝10）

實驗結果說明了CDOD算法在執行效率上優于傳統的嵌套循環算法，并且隨著數據集的增大，挖掘性能更優。

4 結束語

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

[1]Han JW, Kamber M. 范明, 孟小峰, 譯. 數據挖掘概念與技術[M]. 北京: 機械工業出版社, 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

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

離群點；聚類；嵌套循環；k近鄰搜索

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

TP311

A

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

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

2010-12-13

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