一種改進(jìn)的K-means入侵檢測算法?

張珂嘉 黃樹成

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212003）

1 引言

隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展和廣泛應(yīng)用，網(wǎng)絡(luò)安全問題越來越受到人們的關(guān)注。入侵檢測作為一項(xiàng)網(wǎng)絡(luò)與信息安全領(lǐng)域的重要技術(shù)，已經(jīng)成為了網(wǎng)絡(luò)安全體系中一個(gè)重要組成部分。入侵檢測系統(tǒng)常用的檢測方法有誤用檢測和異常檢測［1］。誤用檢測是一種檢測計(jì)算機(jī)攻擊的方法，它可以模式匹配已知的攻擊行為，所以具有較低的誤報(bào)率，但由于網(wǎng)絡(luò)環(huán)境不斷變化，新類型的攻擊層出不窮，導(dǎo)致誤用檢測方法具有較低的檢測率；異常檢測是檢測入侵者異于正常主體的活動(dòng)，具有較高的檢測率，局限在于并非所有的入侵都表現(xiàn)為異常，因此誤報(bào)率偏高。

大數(shù)據(jù)時(shí)代，隨著信息技術(shù)的快速發(fā)展，數(shù)據(jù)量急速增長。從海量的數(shù)據(jù)中挖掘出有效的信息和知識(shí)是數(shù)據(jù)挖掘技術(shù)的特征。聚類分析是數(shù)據(jù)挖掘中的一個(gè)重要的研究領(lǐng)域領(lǐng)域［2］。它將對象的集合按照一定規(guī)則進(jìn)行分組，這滿足了入侵檢測中異常檢測的需求：將入侵的異常行為同正?；顒?dòng)進(jìn)行區(qū)別，從而達(dá)到入侵警告的目的。因此人們將聚類分析引入到入侵檢測研究中。

2 Canopy-K-means算法

本章節(jié)將介紹傳統(tǒng)K-means算法和Cano?py-K-means算法的基本原理與優(yōu)缺點(diǎn)。

2.1 K-means算法原理

K-means算法是一種基于劃分的無監(jiān)督的聚類算法，利用數(shù)據(jù)對象間的距離作為相似性的評(píng)價(jià)指標(biāo)［3］。聚類過程是一個(gè)不斷迭代的過程，對數(shù)據(jù)點(diǎn)進(jìn)行簇劃分和對簇的中心點(diǎn)不斷調(diào)整交替進(jìn)行，從而實(shí)現(xiàn)不同簇間相似度低，簇內(nèi)數(shù)據(jù)相似度高的效果。

K-means算法的執(zhí)行步驟：

假設(shè)一個(gè)數(shù)據(jù)集D，其中有n個(gè)數(shù)據(jù)對象，每個(gè)數(shù)據(jù)對象含有p個(gè)特征屬性，即Di=(Di1，Di2，Di3，…，Dip)，Di∈D，1≤i≤n，需要聚類的個(gè)數(shù)為K，且

K＜n。

1）根據(jù)實(shí)際應(yīng)用場景，用戶輸入需要聚類的個(gè)數(shù)K。隨機(jī)選擇K個(gè)數(shù)據(jù)對象作為初始聚類中心；

2）對于每個(gè)數(shù)據(jù)對象Di，計(jì)算其到各個(gè)聚類中心的歐式距離，將Di劃分到聚類中心的歐式距離最小值的聚類中，據(jù)此得到k個(gè)聚類C1，C2，C3，…，Ck；

3）對于每個(gè)聚類Ci（1≤i≤k），根據(jù)式（1）重新計(jì)算K個(gè)聚類的聚類中心；

4）若重新計(jì)算的K個(gè)質(zhì)心位置變化，則重復(fù)2）、3）步驟直至聚類中心不再變化。

因其算法簡潔、易于實(shí)現(xiàn)、聚類效果較好，被大量應(yīng)用在入侵檢測領(lǐng)域。但它在實(shí)際應(yīng)用過程也存在不足之處：

1）K-means算法的聚類簇?cái)?shù)量需要人為指定，不同的k值對聚類結(jié)果會(huì)產(chǎn)生非常大的影響；

2）由于每個(gè)簇的初始質(zhì)心都是隨機(jī)產(chǎn)生的，易受噪聲點(diǎn)干擾，易導(dǎo)致聚類結(jié)果不穩(wěn)定和聚類質(zhì)量不高，陷入局部最優(yōu)解等問題。

2.2 Canopy-K-means算法原理

Canopy-K-means算法是一種改進(jìn)的K-means算法。它是在K-means算法的基礎(chǔ)上，先對數(shù)據(jù)進(jìn)行“粗聚類”，再由K-means算法進(jìn)行“細(xì)聚類”，從而達(dá)到聚類更精確的目的［4］。

Canopy算法的執(zhí)行步驟：

1）將原數(shù)據(jù)集集合化為一個(gè)List，并設(shè)置T1、T2（T1>T2）；

2）從List集合中隨機(jī)選出一個(gè)數(shù)據(jù)對象p，若當(dāng)前沒有Canopy，則p直接作為一個(gè)新的Canopy；若存在Canopy，則計(jì)算p到Canopy的歐式距離d；

3）當(dāng)d

4）重復(fù)2）、3），直至List為空；

5）將Canopy的數(shù)量和Canopy的中心質(zhì)心作為K-means算法的初始質(zhì)心數(shù)量k和初始質(zhì)心進(jìn)行聚類。

圖1 Canopy聚類示意圖

Canopy-K-means算法的優(yōu)點(diǎn)在于：

2）每一個(gè)數(shù)據(jù)對象都至少被劃分到了一個(gè)Conapy中；

3）一定程度上緩解了初始質(zhì)心敏感的問題。

但是Canopy-K-means算法仍然存在不足之處：

1）數(shù)據(jù)集中噪聲點(diǎn)也會(huì)被劃分入Canopy，會(huì)對最終的聚類結(jié)果產(chǎn)生較大的影響；

2）每個(gè)Canopy的中心點(diǎn)依然為隨機(jī)選取，仍然會(huì)對聚類結(jié)果產(chǎn)生較大的影響；

3）T1、T2的大小難以確定；

4）由于在K-means算法的基礎(chǔ)上多進(jìn)行了一次“粗聚類”，在實(shí)際應(yīng)用中耗時(shí)會(huì)增加。

通過分析電子郵件的語言特征、結(jié)構(gòu)特征與格式特征，利用支持向量機(jī)做分類算法，分析出作者的寫作風(fēng)格，從而建立作者身份識(shí)別模型，當(dāng)需要識(shí)別某一封電子郵件時(shí)，將待識(shí)別的電子郵件通過建立的作者識(shí)別模型即可得到結(jié)果。通過測試集的電子郵件結(jié)果顯示，此方法用于中文電子郵件作者身份識(shí)別，具有較高的可行性與可靠性。本文與之前學(xué)術(shù)界相關(guān)研究比較，具有以下特點(diǎn)：

3 改進(jìn)Canopy-K-means算法

本章節(jié)將從抗噪性、初始質(zhì)心選擇、算法運(yùn)算過程三個(gè)方面對Canopy-K-means算法進(jìn)行改進(jìn)。

3.1 優(yōu)化噪聲處理能力

Canopy-K-means算法，在執(zhí)行過程中，會(huì)因?yàn)檫x擇噪聲點(diǎn)作為Canopy的中心點(diǎn)，導(dǎo)致聚類結(jié)果產(chǎn)生較大的差異，所以增強(qiáng)Canopy-K-means算法的抗噪能力十分必要。本文在選取Canopy之前，對數(shù)據(jù)集進(jìn)行劃分，從而增強(qiáng)算法的抗噪能力［5～6］。

定義1設(shè)數(shù)據(jù)集D，Di=(D1，D2，D3，…，Dn)，Di∈D，定義數(shù)據(jù)對象Di到其他數(shù)據(jù)對象的歐式距離和為

其中‖‖2表示歐式距離的平方。

定義2設(shè)數(shù)據(jù)集D，Di=(D1，D2，D3，…，Dn)，Di∈D，

定義數(shù)據(jù)集中數(shù)據(jù)對象到其他數(shù)據(jù)對象的平均距離和為

計(jì)算數(shù)據(jù)集中每個(gè)數(shù)據(jù)對象到其他數(shù)據(jù)對象的歐式距離平方Sum（Di）和數(shù)據(jù)集的距離和的均值A(chǔ)vg（D）；去除Sum（Di）>Avg（D）的數(shù)據(jù)對象，即去除數(shù)據(jù)集中的噪聲點(diǎn)，由此得到一個(gè)新的數(shù)據(jù)集D'，并用D'進(jìn)行后續(xù)聚類操作。

3.2 優(yōu)化初始質(zhì)心

在Canopy-K-means算法執(zhí)行過程中，每一個(gè)Canopy的中心點(diǎn)都為隨機(jī)生成。為了避免聚類陷入局部最優(yōu)解，初始中心點(diǎn)隨機(jī)性問題，本文引入“最大最小原則”對Canopy-K-means進(jìn)行優(yōu)化，提高聚類的準(zhǔn)確性。

“最大最小原則”的基本思想［7］是：確保任意兩個(gè)Canopy中心點(diǎn)的距離足夠遠(yuǎn)。即假設(shè)計(jì)算m+1個(gè)Canopy中心點(diǎn)，除已知的m個(gè)質(zhì)心外，計(jì)算其余每個(gè)數(shù)據(jù)對象到已知質(zhì)心的最短距離，取其最小值；然后取最短距離中的最大值對應(yīng)的數(shù)據(jù)對象作為第m+1個(gè)初始質(zhì)心［8～9］。則Cm+1個(gè)質(zhì)心可用公式表示為

在實(shí)際應(yīng)用過程中，選取的Canopy中心點(diǎn)并不是最終K-means的聚類中心，所以為了避免全局求解，節(jié)省運(yùn)算開銷，本文取距離坐標(biāo)原點(diǎn)最近、最遠(yuǎn)的兩個(gè)數(shù)據(jù)對象為初始質(zhì)心。

根據(jù)“最大最小原則”的規(guī)律：當(dāng)Canopy個(gè)數(shù)小于或大于最優(yōu)聚類個(gè)數(shù)時(shí)，Cm+1變化幅度較小；當(dāng)Canopy個(gè)數(shù)接近或等于最優(yōu)聚類個(gè)數(shù)時(shí)，Cm+1變化幅度明顯；因此定義深度D（m）來描述Cm變化幅度。

當(dāng)式（6）取最大值時(shí)，此時(shí)m即為最優(yōu)聚類個(gè)數(shù)。有研究表明，聚類個(gè)數(shù)（N為數(shù)據(jù)規(guī)模）［10］。同時(shí)為了保證聚類中心點(diǎn)都落在Canopy范圍內(nèi)，將T1設(shè)置為Cm［11］。

3.3 優(yōu)化K-means運(yùn)算過程

在將由Canopy算法得出的初始質(zhì)心和K代入K-means算法的過程中，由于Canopy算法特性，每一個(gè)數(shù)據(jù)對象至少在一個(gè)Canopy中，可能會(huì)存在多個(gè)Canopy中并且Canopy具有簇間相似度低，簇內(nèi)相似度高的特性，所以在進(jìn)行K-means算法的聚類過程中，不需要計(jì)算不同Canopy間的相似度，只需要計(jì)算數(shù)據(jù)對象所在Canopy的相似度，將其歸入相似度高的Canopy中即可。在Canopy重疊較少的環(huán)境下，可明顯地減少K-means算法的迭代次數(shù)。

3.4 基于Canopy-K-means的改進(jìn)算法

將上述優(yōu)化處理有機(jī)結(jié)合得到一種新的Cano?py-K-means算法。具體算法流程為

1）對原始數(shù)據(jù)集D進(jìn)行抗噪處理，得到新數(shù)據(jù)集D'，并放入集合List中；

2）若集合Q為空，則選取List中距離坐標(biāo)原點(diǎn)最近的數(shù)據(jù)對象，放入Q中；

3）若集合Q不為空，則選取距離Q中所有數(shù)據(jù)對象距離最短中的最大者，放入Q中；

5）計(jì)算深度D（m），得出最優(yōu)聚類個(gè)數(shù)K和T1，并截取Q中前K個(gè)數(shù)據(jù)對象作為初始質(zhì)心；

6）根據(jù)T1，將非中心點(diǎn)的數(shù)據(jù)對象作上標(biāo)記；

7）將得到的初始中心點(diǎn)、K、Canopy集合代入優(yōu)化的K-means算法進(jìn)行聚類。

4 實(shí)驗(yàn)研究與結(jié)果分析

本章節(jié)將介紹仿真實(shí)驗(yàn)過程涉及到的實(shí)驗(yàn)?zāi)Ｐ?、?shù)據(jù)集、算法評(píng)價(jià)指標(biāo)以及實(shí)驗(yàn)結(jié)果分析。

4.1 實(shí)驗(yàn)?zāi)Ｐ图皵?shù)據(jù)集選擇

本文采用的入侵檢測模型如圖2。

圖2 入侵檢測模型示意圖

本文選取Snort入侵檢測系統(tǒng)進(jìn)行仿真實(shí)驗(yàn)，采用kddcup.data_10_percent數(shù)據(jù)集作為網(wǎng)絡(luò)數(shù)據(jù)［12～13］。該數(shù)據(jù)集為KDD Cup99的10%抽樣，其中包含正常數(shù)據(jù)和攻擊數(shù)據(jù)。攻擊數(shù)據(jù)中分為DOS攻擊、Probing攻擊、U2R攻擊和R2L攻擊［14～15］。實(shí)驗(yàn)前，先對數(shù)據(jù)集進(jìn)行標(biāo)準(zhǔn)化、歸一化處理［16］，然后從中隨機(jī)選取7428條正常數(shù)據(jù)和1560條異常數(shù)據(jù)（含21類攻擊行為）作為數(shù)據(jù)集D，進(jìn)行多次實(shí)驗(yàn)取均值。

4.2 實(shí)驗(yàn)結(jié)果評(píng)估指標(biāo)

運(yùn)用檢測率、誤報(bào)率，兩個(gè)常用的入侵檢測評(píng)判指標(biāo)來判斷K-means算法改進(jìn)前后的性能。

1）檢測率

檢測率是用來評(píng)價(jià)算法對入侵攻擊檢測程度的指標(biāo)，可以有效的反應(yīng)出該算法對入侵攻擊的檢測情況。通常情況，檢測率越高，算法對入侵攻擊的識(shí)別效果越好。具體公式如下：

2）誤報(bào)率

誤報(bào)率是用來評(píng)價(jià)算法對正?；顒?dòng)誤判的指標(biāo)，通常情況，誤報(bào)率越低，說明算法對區(qū)分正?；顒?dòng)和異?；顒?dòng)更精準(zhǔn)。具體公式如下：

4.3 結(jié)果分析

經(jīng)式（7）和（8）可得三種算法的誤報(bào)率和檢測率，如表2所示。

表2 實(shí)驗(yàn)測試對照表

從表1和表2可以看出改進(jìn)后的Canopy-Kmeans算法相比于傳統(tǒng)的K-means算法和Cano?py-K-means算法均具有更低的誤報(bào)率和更高的檢測率，改進(jìn)后的Canopy-K-means算法性能更優(yōu)。

表1 入侵檢測結(jié)果

5 結(jié)語

本文針對傳統(tǒng)K-means算法需要初始質(zhì)心敏感、需要人為指定K、抗噪能力差，提出了改進(jìn)的Canopy-K-means算法。通過實(shí)驗(yàn)結(jié)果可知，改進(jìn)后的Canopy-K-means算法性能明顯優(yōu)于傳統(tǒng)K-means算法和Canopy-K-means算法，因此可將改進(jìn)的Canopy-K-means算法應(yīng)用于入侵檢測，以提高入侵檢測的性能。下一步研究將針對改進(jìn)的Canopy-K-means算法的時(shí)間復(fù)雜度、耗時(shí)進(jìn)行深入探索。