基于譜聚類的離群檢測

馮超　羅杰

關鍵詞：譜聚類；候選離群因子；離群點檢測；kNN

中圖法分類號：TP311 文獻標識碼：A

1引言

目前，數據挖掘技術大多集中于挖掘數據集中數據對象的常規數據模式，然而并不是所有的數據對象都符合這種常規模式。數據集中一些新穎、不符合常規的少部分異常模式通常被視為噪聲或異常而被拋棄，然而在很多應用中，這些小眾的數據模式可能蘊涵重要的隱藏信息，如入侵行為、欺詐行為、醫學上疾病前期的征兆等。這些稀有的異常模式通常被稱為離群點，目前關于離群點并沒有一個廣泛認可的定義，按照Hawkins的觀點：“離群點是偏離其他觀察點非常大的觀察點，以至于懷疑它是由不同的機制所產生的”。離群點挖掘的目的是在大量復雜的數據集中發現這些小部分的異常模式。

近年來，基于數據挖掘概念的離群點檢測技術已經取得一定的研究成果，大致可分為基于分布的離群點檢測方法、基于密度的離群點檢測方法、基于距離的離群點檢測方法和基于深度的離群點檢測方法。譜聚類是近年來新出現的一種極具競爭力的聚類算法，它建立在譜圖理論基礎上，實質是將原始數據點映射到它的譜特征空間上，然后用K-means，C -means等方法對譜特征空間聚類實現原始數據集的聚類。與傳統的K-means，EM聚類算法相比，譜聚類的優勢在于聚類可以在任何形狀的樣本空間上進行并且能夠收斂于全局最優解，因此逐漸受到廣大數據挖掘研究者的重視。由于譜聚類算法只與數據的點數有關，而與維數無關，因此可以避免由高維特征向量造成的奇異性問題。另外，譜聚類可用于大規模數據集。離群點代表的是一種不同于主體結構特征的結構，鑒于譜聚類算法的諸多優勢，將譜聚類方法引入離群數據挖掘中顯得尤為重要，這將有利于從結構特征分析數據對象，并發現離群點與主體結構特征的相異之處，最終實現離群數據的挖掘。

本文在研究了離群數據挖掘和譜聚類相關理論的基礎上，提出一種新型的基于譜聚類算法的離群點檢測方法。仿真驗證了該方法不僅在低維數據上有很好的效果，并且對高維及高維空間上的離群點檢測具有更好的效果，這為目前基于距離和密度的離群點檢測方法在高維數據空間上存在維數災難等問題提供了重要的參考價值。

3仿真結果

以人工合成數據集為例，數據總數為140，其中索引號為0，80，81，82，106，116，124的數據點為離群點，索引號為0，106，116的數據點為局部離群點，索引號為80，81，82的點組成了離群簇，索引號為124的點為全局離群點。我們對所有數據點的kNN譜聚類求出的特征值和特征向量進行了分析，圖1表示所有點譜聚類后第二小特征值與該點的kNN譜聚類后第二小特征值組的平均值的偏離程度。

圖1中橫線表示偏離閾值的分割線，橫線以上部分是偏離值大于0.05的數據點，總數為24，橫線以下部分是偏離值小于0.05的數據點，總數為116。之所以選擇閾值為0.05，從統計學角度考慮，離群點一般是在數據集中出現概率小于某一閾值的數據點，在整個數據集中只占一小部分，為了得到包含所有離群點的最小候選離群點集，一般將偏離值選擇為大于該值的數據點個數占整個數據集規模的15%～20%。從圖1中可以看到，偏離程度大于0.05的數據點中包含所有的離群點。因此，我們受到啟發：對于數據集中每個數據點的k個鄰近點組成的數據集通過譜聚類算法求出的第二小特征值，以及該點每個k鄰近點的kNN組經過譜聚類后得到的第二小特征值組的平均值，這2個值的差值越大的那些點意味著離群。

4結束語

通過譜聚類算法求解的特征值和特征向量，包含關于離群點和正常數據點譜的豐富信息。為了彌補傳統方法的不足和充分利用特征空間的信息，本文提出了一種基于譜聚類的離群點檢測的新思路。該算法的優點在于對大規模和高維數據集上的離群點檢測具有很高的參考價值。

作者簡介：

馮超（1986—），本科，工程師，研究方向：網絡安全、個人信息保護。

羅杰（1985—），碩士，工程師，研究方向：網絡安全、數據安全。