季賽花 黃樹成

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

1 引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展與快速普及，網(wǎng)絡(luò)已經(jīng)成為人們?cè)谏钪胁豢扇鄙俚牟糠??；ヂ?lián)網(wǎng)固有的開放性與共享性在給人們帶來便利的同時(shí)，伴隨而來的是現(xiàn)今人們極為關(guān)注的相關(guān)網(wǎng)絡(luò)信息安全問題［1］?；谛畔⒓用芗夹g(shù)、防火墻等靜態(tài)安全防御技術(shù)已經(jīng)無法適應(yīng)動(dòng)態(tài)變化的網(wǎng)絡(luò)，入侵檢測(cè)作為一種積極主動(dòng)的安全防護(hù)技術(shù)，彌補(bǔ)了靜態(tài)安全技術(shù)的缺陷［2］，提供了對(duì)內(nèi)部攻擊、外部攻擊和誤操作的實(shí)時(shí)保護(hù)。

數(shù)據(jù)挖掘技術(shù)能從海量數(shù)據(jù)中挖掘出有用的知識(shí)，進(jìn)而應(yīng)用于入侵檢測(cè)中，識(shí)別正?；虍惓Ｐ袨?，能有效提高入侵檢測(cè)效率。而聚類分析是數(shù)據(jù)挖掘重要的一部分。它能通過分析數(shù)據(jù)的屬性特征，將特征相近或相似的數(shù)據(jù)劃分到同一個(gè)類中。K-means算法是一種典型的聚類算法，具有快速簡(jiǎn)單，具有較高的大數(shù)據(jù)集運(yùn)算效率［3］。將K-means算法運(yùn)用于入侵檢測(cè)中，在數(shù)據(jù)處理和分析方面有明顯的優(yōu)勢(shì)，但是K-means算法也有一些缺點(diǎn)，比如聚類數(shù)目需要事先給定，聚類結(jié)果對(duì)初始中心點(diǎn)和數(shù)據(jù)集中的噪聲點(diǎn)以及孤立點(diǎn)敏感，且聚類結(jié)果易陷入局部最優(yōu)［4］。近年來，很多學(xué)者對(duì)傳統(tǒng)的K-means算法進(jìn)行改進(jìn)，并將其應(yīng)用于入侵檢測(cè)中。徐超［5］等在基于最大最小距離算法的思想和有效性指標(biāo)基礎(chǔ)上，迭代計(jì)算出最優(yōu)聚類數(shù)和其對(duì)應(yīng)的聚類中心，并用于構(gòu)建正常行為模式庫，入侵檢測(cè)性能有所改善。李鵬［6］等將K-means與決策樹結(jié)合，根據(jù)信息增益比差異將樣本數(shù)據(jù)先分類再建立決策樹，提升了算法的檢測(cè)率，但對(duì)未知攻擊的檢測(cè)能力較低，因此，傳統(tǒng)K-means算法在入侵檢測(cè)應(yīng)用上仍存在不足。

為此，文中提出了一種改進(jìn)的K-means算法，基于類內(nèi)和類間的聚類有效性指標(biāo)的確定聚類數(shù)目，在聚類過程中對(duì)距離進(jìn)行特征加權(quán)，并結(jié)合三支決策聚類思想，擴(kuò)展了K-means算法使之適用于不確定性聚類，進(jìn)而提高入侵檢測(cè)的檢測(cè)率，降低誤檢率。

2 傳統(tǒng)K-means聚類算法

2.1 算法過程

K-means算法是1967年由J.B.MacQueen首先提出的一種無監(jiān)督聚類算法［7］。其算法思想比較簡(jiǎn)單，即在無類標(biāo)簽的數(shù)據(jù)集中，將N個(gè)對(duì)象劃分到K個(gè)簇中，使得相似度較高的在一個(gè)類中，差異較大的在不同的類中，其算法流程［8］如下：

1）從給定的數(shù)據(jù)集中選擇K個(gè)點(diǎn)作為初始聚類中心點(diǎn)；

2）對(duì)每個(gè)樣本點(diǎn)，計(jì)算樣本點(diǎn)到各個(gè)聚類中心點(diǎn)的距離，選出最小距離對(duì)應(yīng)的聚類中心點(diǎn)，并將其劃分到該聚類中心點(diǎn)對(duì)應(yīng)的聚類中；

3）計(jì)算每個(gè)聚類中所有點(diǎn)的均值，將此均值點(diǎn)作為新的聚類中心；

4）循環(huán)2）、3），直到每個(gè)聚類的中心點(diǎn)不再發(fā)生變化，目標(biāo)函數(shù)收斂，算法結(jié)束。

其中，一般采用歐式距離去計(jì)算樣本點(diǎn)到各個(gè)聚類中心點(diǎn)的距離，見式（1）；采用均方差作為目標(biāo)函數(shù)，見式（2）。

2.2 算法在入侵檢測(cè)應(yīng)用中的不足

K-means算法操作簡(jiǎn)單、運(yùn)算速度快，將其應(yīng)用于入侵檢測(cè)中具有重要的研究?jī)r(jià)值。但同時(shí)也存在一些不足之處。其中，聚類的數(shù)目難以估計(jì)，不確定的K值會(huì)導(dǎo)致聚類質(zhì)量下降［9］。入侵檢測(cè)中從網(wǎng)絡(luò)中抓取的數(shù)據(jù)包都是實(shí)時(shí)的，所以難以確定聚類數(shù)，致使聚類效果不穩(wěn)定，從而影響入侵檢測(cè)的性能［10］。

3 算法的改進(jìn)

3.1 特征加權(quán)

網(wǎng)絡(luò)數(shù)據(jù)呈現(xiàn)多維性，而每條數(shù)據(jù)的每個(gè)特征對(duì)聚類的作用都不盡相同，所以需要對(duì)不同特征進(jìn)行權(quán)值分配［11］。本文兼顧類內(nèi)和類間對(duì)象的關(guān)系，利用前次迭代中產(chǎn)生的均值、方差等確定權(quán)重。

設(shè)數(shù)據(jù)集X中有N個(gè)D維數(shù)據(jù)為第k類的第d維上的均值為當(dāng)前第k類的方差在第d維上的取值，如式（3）所示。

整個(gè)數(shù)據(jù)集X在第d維特征上所有的聚類均值總和（式（4））與方差總和（式（5））為表示第d維特征在各類別中心的間距表示第d維特征的類內(nèi)離散度大小。為了達(dá)到理想的聚類效果，類間距離越大越好，類內(nèi)離散度越小越好。所以，可以設(shè)一個(gè)第d維特征類間距離與類內(nèi)離散度的比值作為第d維特征的聚類效果的指標(biāo)，如式（6）所示。

那么第d維特征在聚類過程中的權(quán)重，即為第d維特征的聚類效果指標(biāo)與各維特征聚類效果指標(biāo)之和的比值。如式（7）所示。

即求得各維特征的權(quán)重。繼而得到數(shù)據(jù)集中任意xi至聚類中心uj的距離特征加權(quán)公式，如式（8）所示。

3.2 K值有效性指標(biāo)

本文算法K值有效性指標(biāo)利用上述的特征加權(quán)距離綜合考慮類內(nèi)緊密性與類間分離性。

設(shè)在數(shù)據(jù)集U中，Ci表示其中被劃分的一個(gè)類，定義類內(nèi)距離Intra（Ci）為類Ci中任意兩個(gè)數(shù)據(jù)x，y的距離平方和，如式（9）所示；定義類間距離Inter（Ci，Cj）為類Ci到其他類Cj的距離，如式（10）所示。其中，k、p分別是類Ci和類Cj中數(shù)據(jù)樣本點(diǎn)的個(gè)數(shù)。

3.3 三支決策聚類

三支決策（Three-way Decisions）最早由Yao［12］在粗糙集理論的基礎(chǔ)上提出的。在人們實(shí)際決策中，由于對(duì)事件信息了解程度不同，往往會(huì)做出三種類型的決策：接受、拒絕和延遲。對(duì)于那些有充分把握的事件，人們很容易做出接受或拒絕的決策，但是對(duì)不確定事件，人們往往不能立馬做出決策，需要延遲決策［13］。該理論與傳統(tǒng)的二支決策相比，更有實(shí)際意義?；诖耍瑢⑷Q策引入到聚類分析中，考察對(duì)象與類之間的關(guān)系，可劃分為對(duì)象屬于這個(gè)類，對(duì)象不屬于這個(gè)類以及對(duì)象可能屬于這個(gè)類。

結(jié)合三支決策思想，在一個(gè)數(shù)據(jù)集U中，針對(duì)一個(gè)類C，與其有關(guān)聯(lián)的有三個(gè)互不相交的區(qū)域：CI、CB和CO，又稱I域，B域和O域［14］。I域中的對(duì)象確定屬于這個(gè)類，O域中的對(duì)象確定不屬于這個(gè)類，B域中的對(duì)象可能屬于也可能不屬于這個(gè)類，即類C的構(gòu)成為C={CI，CB}。為保證有實(shí)際的意義，需 滿 足1）

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

圖1 改進(jìn)的算法流程圖

具體的步驟如下：

輸入：數(shù)據(jù)集X=｛x1，x2，…，xn｝，初始聚類數(shù)目k=2。

輸出：聚類結(jié)果C。

1）在數(shù)據(jù)集中，隨機(jī)選取k個(gè)初始聚類中心點(diǎn)U=｛u1，u2，…，uk｝；

2）計(jì)算數(shù)據(jù)集中除了聚類中心點(diǎn)外剩余數(shù)據(jù)對(duì)象xi到每個(gè)聚類中心uj的特征加權(quán)距離dist(xi，uj)，并把他們劃分到距離最近的簇Cj中；

4）如果聚類中心不發(fā)生變化，轉(zhuǎn)至5），否則轉(zhuǎn)至2）；

5）計(jì)算k=arg［S］，如果，那么，轉(zhuǎn)至1），否則轉(zhuǎn)至6）；

6）k'=argmin［S］，最終輸出新的二支聚類結(jié)果集C'；

7）遍歷C'，對(duì)于每一個(gè)類若則若，且，則，否則

4 仿真實(shí)驗(yàn)及分析

4.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)說明

本文實(shí)驗(yàn)借助的硬件平臺(tái)是Intel（R）Core（TM）i5-3230 CPU@2.60Hz，4GBRAM的計(jì)算機(jī)，并在Win7系統(tǒng)上采用在Python編譯器上實(shí)現(xiàn)程序設(shè)計(jì)。

本實(shí)驗(yàn)使用KDD Cup99數(shù)據(jù)集中的corrected.data作為訓(xùn)練集，使用10%的數(shù)據(jù)樣本作為測(cè)試集。KDD Cup99數(shù)據(jù)集中的每條數(shù)據(jù)由41個(gè)特征屬性和1個(gè)決策標(biāo)簽組成［16］。其中決策標(biāo)簽分為正常（Normal）和攻擊類型，攻擊類型有四大類：DOS，R2L，U2R，Probe。數(shù)據(jù)格式如下例所示：2，tcp，smtp，SF，1684，363，0，0，0，0，0，1，0，0，0，0，0，0，0，0，0，0，1，1，0.00，0.00，0.00，0.00，1.00，0.00，0.00，104，66，0.63，0.03，0.01，0.00，0.00，0.00，0.00，0.00，normal。

由于數(shù)據(jù)集中含有符號(hào)型數(shù)據(jù)屬性，不適合聚類測(cè)試，同時(shí)也為了避免“大數(shù)吃小數(shù)”現(xiàn)象，故對(duì)先要對(duì)數(shù)據(jù)進(jìn)行數(shù)值化和歸一化處理。

4.2 結(jié)果分析

本改進(jìn)模型的實(shí)驗(yàn)結(jié)果評(píng)估指標(biāo)主要有兩項(xiàng)：檢測(cè)率（Detection Rate，DR）和誤報(bào)率（False Posi?tive Rate，F(xiàn)PR）。

檢測(cè)率DR的公式如式（12）所示：

誤報(bào)率FPR的公式見式（13）：

由上述公式可以看出，誤報(bào)率越小，檢測(cè)率越大，入侵檢測(cè)性能越好。

改進(jìn)前后的算法應(yīng)用到入侵檢測(cè)中所得到的檢測(cè)率和誤報(bào)率見表1。

表1 實(shí)驗(yàn)測(cè)試結(jié)果對(duì)比

如圖2所示，以誤報(bào)率為橫坐標(biāo)，以檢測(cè)率為縱坐標(biāo)畫出改進(jìn)前后的入侵檢測(cè)算法的ROC曲線對(duì)比圖，由此可以很直觀地看出本文的入侵檢測(cè)算法的面積大于未改進(jìn)的K-means算法的面積，可以說明本文的入侵檢測(cè)算法性能更好，檢測(cè)效率更佳。

圖2 ROC曲線

5 結(jié)語

針對(duì)傳統(tǒng)的K-means算法無法準(zhǔn)確確定聚類數(shù)目而導(dǎo)致聚類質(zhì)量下降的問題，本文提出了基于改進(jìn)的K-means入侵檢測(cè)算法，一方面考慮數(shù)據(jù)的各維特征屬性對(duì)聚類作用不一，提出對(duì)聚類過程中所涉及的數(shù)據(jù)點(diǎn)到聚類中心點(diǎn)的距離進(jìn)行特征加權(quán)；另一方面，基于類內(nèi)和類間的聚類效果有效性指標(biāo)來確定聚類數(shù)目；最后結(jié)合三支決策聚類思想，劃分確定域和模糊域，對(duì)模糊域中的數(shù)據(jù)延遲決策，進(jìn)而提高了聚類的檢測(cè)率，降低了誤報(bào)率。