馮超　羅杰

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

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

1引言

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

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

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

3仿真結果

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

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

4結束語

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

作者簡介：

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

羅杰（1985—），碩士，工程師，研究方向：網(wǎng)絡安全、數(shù)據(jù)安全。