基于譜聚類的離群檢測(cè)

馮超　羅杰

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

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

1引言

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

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

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

3仿真結(jié)果

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

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

4結(jié)束語(yǔ)

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

作者簡(jiǎn)介：

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

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