基于擴(kuò)展Jarvis-Patrick聚類(lèi)的異常檢測(cè)算法優(yōu)化及檢測(cè)仿真

張利劍，陳晉鵬

（西安工程大學(xué)電子信息學(xué)院，陜西西安 710048）

異常檢測(cè)方法主要對(duì)已知數(shù)據(jù)的整體進(jìn)行建模分析，從中識(shí)別和記錄異常數(shù)據(jù)。但是，隨著現(xiàn)代社會(huì)的發(fā)展，從高維數(shù)據(jù)中提取和識(shí)別威脅并應(yīng)對(duì)未知的攻擊類(lèi)型是當(dāng)前亟待解決的問(wèn)題[1-2]。在異常檢測(cè)領(lǐng)域，有兩個(gè)被廣泛接受的假設(shè)：①大多數(shù)數(shù)據(jù)行為是正常行為，只有少數(shù)行為是惡意行為；②攻擊行為與正常行為有顯著差異。在這兩個(gè)假設(shè)條件下，目前，許多專(zhuān)家學(xué)者將多種類(lèi)型的數(shù)據(jù)挖掘技術(shù)引入該研究領(lǐng)域，成為目前的熱門(mén)研究[3-5]。近年來(lái)，許多專(zhuān)家在異常檢測(cè)領(lǐng)域采用了一些聚類(lèi)方法[6-9]。K-means是一種聚類(lèi)方法，較早用于異常檢測(cè)領(lǐng)域，但有其自身的局限性，例如聚類(lèi)依賴(lài)性和簡(jiǎn)并性[10-12]。Y 均值法通過(guò)替換該方法生成的空聚類(lèi)，消除離群值的影響以及合并相似的聚類(lèi)以進(jìn)一步優(yōu)化聚類(lèi)中心來(lái)改進(jìn)k均值方法[13-16]。文中算法基于圖的聚類(lèi)算法，通常不需要考慮聚類(lèi)中心的問(wèn)題，具有處理大小、形狀和密度不同的聚類(lèi)的優(yōu)勢(shì)，并且對(duì)高維數(shù)據(jù)具有良好的效果。通過(guò)擴(kuò)展共享的k最近鄰的條件，提出了一種擴(kuò)展的Jarvis-Patrick 聚類(lèi)算法（Extended-Jarvis-Patrick，EJP），與其他聚類(lèi)方法相比，文中算法更擅于發(fā)現(xiàn)強(qiáng)相關(guān)點(diǎn)的聚類(lèi)。使用KDD Cup99 數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，結(jié)果表明，與傳統(tǒng)Jarvis-Patrick 聚類(lèi)相比，該算法提高了檢測(cè)率（Jarvis-Patrick的最佳檢測(cè)率僅為78.7%，而EJP可以達(dá)到97.10%）。

1 Jarvis-Patrick聚類(lèi)算法

Jarvis-Patrick 聚類(lèi)算法的主要思想是首先找到每個(gè)數(shù)據(jù)點(diǎn)的k最近鄰；其次，找到圖中具有共享k最近鄰關(guān)系的所有點(diǎn)。如果兩個(gè)點(diǎn)具有共享的k最近鄰關(guān)系，則這兩個(gè)點(diǎn)之間可以有一條線(xiàn)，因此最終將獲得一系列簇，其中每個(gè)簇中的點(diǎn)之間具有共享的k最近鄰關(guān)系。該算法具有處理不同大小、形狀和密度的簇的能力，并且對(duì)高維數(shù)據(jù)具有良好的效果。但是，在將算法應(yīng)用于一些實(shí)際數(shù)據(jù)集之后，可以發(fā)現(xiàn)它仍然存在一些缺點(diǎn)。

通過(guò)將該算法應(yīng)用于KDD Cup 1999 數(shù)據(jù)集，考慮到數(shù)據(jù)量較大，從數(shù)據(jù)集中隨機(jī)抽取1 000、2 000和5 000 個(gè)數(shù)據(jù)點(diǎn)進(jìn)行測(cè)試。根據(jù)前面提到的兩個(gè)異常檢測(cè)假設(shè)，α(累計(jì)值)應(yīng)與標(biāo)記為正常的點(diǎn)數(shù)一致，遠(yuǎn)大于聚類(lèi)后的異常點(diǎn)數(shù)，因此取α=0.8。在α=0.8 處提取1 000、2 000 和5 000 個(gè)數(shù)據(jù)點(diǎn)時(shí)，使用Jarvis-Patrick 的最佳結(jié)果如表1 所示?？梢钥吹?，最好的檢測(cè)率為78.7%。

表1 差異化數(shù)據(jù)點(diǎn)Jarvis-Patrick算法最佳結(jié)果

在對(duì)2 000 個(gè)提取的數(shù)據(jù)點(diǎn)進(jìn)行測(cè)試時(shí)，檢測(cè)率（Detection Rate，DR）和誤報(bào)率（False positive Rate，F(xiàn)R）結(jié)果如圖1 所示。圖2 顯示了在用不同的k值標(biāo)記之前每個(gè)集群中的元素?cái)?shù)量。

圖1 Jarvis-Patrick聚類(lèi)提取2 000個(gè)數(shù)據(jù)點(diǎn)時(shí)差異化k值的檢測(cè)率（DR）和誤報(bào)率（FR）（α=0.8）

圖2 Jarvis-Patrick聚類(lèi)提取2 000個(gè)數(shù)據(jù)點(diǎn)時(shí)標(biāo)記前聚類(lèi)大小分布（α=0.8）

圖1 表明，當(dāng)k=20時(shí)，檢出率的最大值為0.787，并且可以看到，如果選擇較小的k，則檢出率要好于較大的k值，但最佳檢出率為0.787。結(jié)合圖2 可以發(fā)現(xiàn)，當(dāng)k值較小時(shí)，每個(gè)群集中的點(diǎn)數(shù)是相對(duì)平均的，意味著大型群集和小型群集之間的大小差異不是很明顯。隨著k值的增加，大型群集的大小增加，太多的異常數(shù)據(jù)點(diǎn)將合并到大型群集中，并且在標(biāo)記時(shí)可能會(huì)誤判很多異常數(shù)據(jù)點(diǎn)為正常數(shù)據(jù)點(diǎn)，從而降低了檢測(cè)率。

所以Jarvis-Patrick 聚類(lèi)算法還存在以下缺點(diǎn)：

1）與其他基于圖的聚類(lèi)算法相比，Jarvis-Patrick算法本身的條件相對(duì)苛刻，只有兩點(diǎn)之間具有共享的最近鄰關(guān)系時(shí)，才能在它們之間存在一條邊，因此聚類(lèi)的結(jié)果似乎是零散的。也就是說(shuō)，聚類(lèi)結(jié)果中出現(xiàn)了太多的小型聚類(lèi)。根據(jù)入侵檢測(cè)的兩個(gè)假設(shè)，只有一小部分?jǐn)?shù)據(jù)被標(biāo)記為異常點(diǎn)，因此，太多的小簇將對(duì)貼標(biāo)過(guò)程的準(zhǔn)確性產(chǎn)生負(fù)面影響；

2）當(dāng)將Jarvis-Patrick 聚類(lèi)算法應(yīng)用于真實(shí)世界的入侵檢測(cè)數(shù)據(jù)集時(shí)，其檢測(cè)率和誤報(bào)率均不令人滿(mǎn)意。

為了解決這個(gè)問(wèn)題，在傳統(tǒng)的Jarvis-Patrick 聚類(lèi)算法基礎(chǔ)上，適當(dāng)?shù)乜刂屏思捍笮〉脑鲩L(zhǎng)，降低大型集群的增長(zhǎng)速率，避免在沒(méi)有太多小型集群的情況下出現(xiàn)誤報(bào)率較低的結(jié)果，以便于獲得合理的標(biāo)記結(jié)果，從而提高檢出率。因此，提出一種可以改善這些缺陷的改進(jìn)的Jarvis-Patrick 聚類(lèi)算法。

2 擴(kuò)展Jarvis-Patrick聚類(lèi)算法

通過(guò)上述實(shí)驗(yàn)得出，當(dāng)k值較小時(shí)，Jarvis-Patrick算法具有較高的檢測(cè)率，但是小聚類(lèi)和離群值的數(shù)量太大，因此考慮擴(kuò)展共享k最近鄰條件。

定義1：擴(kuò)展共享k最近鄰

對(duì)于有向圖G中的任意兩點(diǎn)wp和wq，如果wp是wq的k最近鄰，并且wq是(k+m)最近鄰（其中m是任意整數(shù)），則在wp和wq之間存在一條邊epq=，這意味著wp和wq是擴(kuò)展的共享k最近鄰關(guān)系。

定義2：擴(kuò)展共享k最近鄰聚類(lèi)圖

由一組節(jié)點(diǎn)W={w1,w2,…wn}和邊集E={e1,e2,…em}組成的有向圖G稱(chēng)為擴(kuò)展共享k最近鄰聚類(lèi)圖，其中ei=wp，wq∈W，i=1,2,3,…,n。如果wp和wq是擴(kuò)展的共享k最近鄰關(guān)系，則存在邊ei。

根據(jù)上面的定義，將共享k最近鄰的概念擴(kuò)展到Jarvis-Patrick 聚類(lèi)算法。在完成聚類(lèi)過(guò)程之后，能夠獲得擴(kuò)展的共享k最近鄰聚類(lèi)子圖。圖3 所示為擴(kuò)展的共享k最近鄰關(guān)系的兩個(gè)點(diǎn)P3和P4的示例。從圖中可以看到，當(dāng)k=4 且m=1時(shí)，P3具有4 個(gè)最近鄰A、B、C和D，而P4具有4 個(gè)最近鄰A、B、C和E，因此，當(dāng)k=4時(shí)，設(shè)置m=1，則P4（k+m）的最近鄰是A、B、C、D和E，因此，當(dāng)k=4時(shí)，P3和P4可以在一個(gè)簇中。由此還可以看到，在相同的k值下，擬擴(kuò)展共享k最近鄰關(guān)系可以合并Jarvis-Patrick 原本分割的部分聚類(lèi)，以減少最終聚類(lèi)結(jié)果中的聚類(lèi)數(shù)量。

圖3 k=4,m=1時(shí)，P3和P4的擴(kuò)展共享k最近鄰關(guān)系

在擴(kuò)展Jarvis-Patrick 聚類(lèi)算法（EJP）的步驟中，首先通過(guò)在每個(gè)點(diǎn)之間設(shè)置邊來(lái)構(gòu)造每個(gè)聚類(lèi)，然后按升序累積每個(gè)聚類(lèi)的大小。如果總累加值大于α%，則已經(jīng)累加的群集將被標(biāo)記為正常數(shù)據(jù)，而其他群集則被標(biāo)記為異常數(shù)據(jù)。

3 仿真實(shí)驗(yàn)與分析

KDD Cup99 數(shù)據(jù)集包含連續(xù)數(shù)據(jù)和離散數(shù)據(jù)兩種數(shù)據(jù)屬性，不同的屬性類(lèi)型有很大的差異，因此，有必要在使用算法之前對(duì)數(shù)據(jù)的屬性值進(jìn)行歸一化。歸一化方法如下所示：

對(duì)于連續(xù)數(shù)據(jù)，使用式（1）進(jìn)行歸一化，首先，計(jì)算每個(gè)屬性值的平均值和平均絕對(duì)偏移量：

其中，n表示數(shù)據(jù)集中數(shù)據(jù)元素的總數(shù)，xij表示第i個(gè)數(shù)據(jù)的第j個(gè)屬性值。因此，對(duì)應(yīng)于該屬性的歸一化值為：

在某些情況下，從數(shù)據(jù)集中提取數(shù)據(jù)后，發(fā)現(xiàn)異常數(shù)據(jù)點(diǎn)過(guò)多，無(wú)法匹配上文提到的異常檢測(cè)領(lǐng)域中的兩個(gè)假設(shè)。因此，在這種情況下，如果需要，將會(huì)用從數(shù)據(jù)集中隨機(jī)提取的正常數(shù)據(jù)替換一些異常數(shù)據(jù)。

實(shí)驗(yàn)中隨機(jī)提取1 000、2 000 和5 000 個(gè)數(shù)據(jù)點(diǎn)，對(duì)擴(kuò)展的Jarvis-Patrick 聚類(lèi)算法進(jìn)行測(cè)試。值得注意的是：①當(dāng)m=0時(shí)，EJP算法就是Jarvis-Patrick算法本身；②根據(jù)前面提到的兩個(gè)異常檢測(cè)假設(shè)，α值應(yīng)與標(biāo)記為法線(xiàn)的點(diǎn)數(shù)一致，遠(yuǎn)大于聚類(lèi)后的異常點(diǎn)數(shù)，因此取α=0.8。經(jīng)過(guò)聚類(lèi)和標(biāo)記過(guò)程后，記錄不同k值的每個(gè)聚類(lèi)中的元素?cái)?shù)量，以說(shuō)明算法的效果。在此，選擇了從數(shù)據(jù)集中提取的相同的3組數(shù)據(jù)。表2 顯示了對(duì)這3 組數(shù)據(jù)進(jìn)行實(shí)驗(yàn)后的最大檢測(cè)率。值得注意的是，m可能為負(fù)數(shù)，因此計(jì)算（k+m）的值而不是k的值，并且使用正整數(shù)有助于研究準(zhǔn)確率，從而減少統(tǒng)計(jì)量容易出錯(cuò)的問(wèn)題。因此，在實(shí)驗(yàn)過(guò)程中，使用（k+m）的值，從而保留原始數(shù)據(jù)記錄。

從表2可以看到，檢測(cè)率有了很大提高。提取5 000個(gè)數(shù)據(jù)點(diǎn)時(shí)，最佳檢測(cè)率高達(dá)97.1%。對(duì)于表2 中不同的m，EJP 不僅可以達(dá)到比傳統(tǒng)Jarvis-Patrick 更高的檢測(cè)率，而且對(duì)于其他k值，EJP 的檢測(cè)率也高于傳統(tǒng)Jarvis-Patrick 算法。對(duì)給定的k值選擇不同的m值時(shí)，檢測(cè)率變化如圖4、5 所示。從圖4 可以看出，k=20時(shí)，在m取不同值的情況下，最大檢測(cè)率出現(xiàn)在m=20 或30處，檢測(cè)率(DR)高達(dá)95%，遠(yuǎn)高于m=0 的檢測(cè)率。當(dāng)m=20（或m=30 或40）時(shí)，最大簇包含的點(diǎn)數(shù)大于m=0 時(shí)最大簇的點(diǎn)數(shù)。當(dāng)k為其他較大的整數(shù)時(shí)，也可以得到同樣的結(jié)果。圖5 顯示，當(dāng)m=-50 或m=-10時(shí)，檢測(cè)率(DR)達(dá)到最大值（95.7%），而當(dāng)m=0時(shí)，檢測(cè)率(DR)略高于60%。

圖4 k=20和α=0.8時(shí)的檢測(cè)率(DR)和誤報(bào)率(FR)結(jié)果

圖5 k=70和α=0.8時(shí)的檢測(cè)率(DR)和誤報(bào)率(FR)結(jié)果

表2 擴(kuò)展Jarvis-Patrick算法與傳統(tǒng)Jarvis-Patrick算法結(jié)果對(duì)比

圖6 顯示了標(biāo)記前EJP 聚類(lèi)結(jié)果中聚類(lèi)大小的分布（k=20，α=0.8）。在m=20（取最大檢測(cè)率）時(shí)，大簇和小簇的大小具有顯著差異，表明EJP 算法可以通過(guò)增加聚類(lèi)大小差異來(lái)提高檢測(cè)率。

圖6 標(biāo)記前EJP聚類(lèi)結(jié)果中聚類(lèi)大小的分布（k=20，α=0.8）

同樣，當(dāng)k為大值時(shí)，如圖7 所示，當(dāng)m為-10時(shí)，最大簇和最小簇之間的差異與m=0 相比有所降低，主要由于最大聚類(lèi)和最小聚類(lèi)之間的差異太大或聚類(lèi)總數(shù)太小，從而導(dǎo)致檢測(cè)率不足。盡管簇的大小差異并不明顯，但是簇的總數(shù)增加，表明EJP 可以在較低誤報(bào)率的情況下拆分Jarvis-Patrick 算法的某些簇，以實(shí)現(xiàn)較高的檢測(cè)率。

圖7 標(biāo)記前EJP聚類(lèi)結(jié)果中聚類(lèi)大小的分布（k=70，α=0.8）

4 結(jié)論

該文將數(shù)據(jù)抽象為點(diǎn)，并確定兩點(diǎn)之間的相似性，通過(guò)引入共享k 最近鄰關(guān)系獲得擴(kuò)展的共享k 最近鄰聚類(lèi)簇，減少最終聚類(lèi)結(jié)果中的聚類(lèi)數(shù)量，降低數(shù)據(jù)量。通過(guò)在KDD Cup99 數(shù)據(jù)集進(jìn)行驗(yàn)證，結(jié)果表明，該文優(yōu)化算法可以很好地確定相似點(diǎn)屬性，得到最佳聚類(lèi)數(shù)并有效減少數(shù)據(jù)量。后續(xù)將為進(jìn)一步提高算法的誤報(bào)率進(jìn)行研究。