張珂嘉 黃樹成

（江蘇科技大學計算機學院 鎮(zhèn)江 212003）

1 引言

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

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

2 Canopy-K-means算法

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

2.1 K-means算法原理

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

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

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

K＜n。

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

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

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

4）若重新計算的K個質心位置變化，則重復2）、3）步驟直至聚類中心不再變化。

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

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

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

2.2 Canopy-K-means算法原理

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

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

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

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

3）當d

4）重復2）、3），直至List為空；

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

圖1 Canopy聚類示意圖

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

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

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

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

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

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

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

4）由于在K-means算法的基礎上多進行了一次“粗聚類”，在實際應用中耗時會增加。

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

3 改進Canopy-K-means算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4 基于Canopy-K-means的改進算法

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

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

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

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

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

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

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

4 實驗研究與結果分析

本章節(jié)將介紹仿真實驗過程涉及到的實驗模型、數(shù)據(jù)集、算法評價指標以及實驗結果分析。

4.1 實驗模型及數(shù)據(jù)集選擇

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

圖2 入侵檢測模型示意圖

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

4.2 實驗結果評估指標

運用檢測率、誤報率，兩個常用的入侵檢測評判指標來判斷K-means算法改進前后的性能。

1）檢測率

檢測率是用來評價算法對入侵攻擊檢測程度的指標，可以有效的反應出該算法對入侵攻擊的檢測情況。通常情況，檢測率越高，算法對入侵攻擊的識別效果越好。具體公式如下：

2）誤報率

誤報率是用來評價算法對正?；顒诱`判的指標，通常情況，誤報率越低，說明算法對區(qū)分正?；顒雍彤惓；顒痈珳?。具體公式如下：

4.3 結果分析

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

表2 實驗測試對照表

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

表1 入侵檢測結果

5 結語

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