馮超　羅杰

關(guān)鍵詞：譜聚類；候選離群因子；離群點檢測；kNN

中圖法分類號：TP311 文獻(xiàn)標(biāo)識碼：A

1引言

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

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

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

3仿真結(jié)果

以人工合成數(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譜聚類求出的特征值和特征向量進(jìn)行了分析，圖1表示所有點譜聚類后第二小特征值與該點的kNN譜聚類后第二小特征值組的平均值的偏離程度。

圖1中橫線表示偏離閾值的分割線，橫線以上部分是偏離值大于0.05的數(shù)據(jù)點，總數(shù)為24，橫線以下部分是偏離值小于0.05的數(shù)據(jù)點，總數(shù)為116。之所以選擇閾值為0.05，從統(tǒng)計學(xué)角度考慮，離群點一般是在數(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結(jié)束語

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

作者簡介：

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

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