聚類算法在網絡入侵檢測技術中的作用

摘要：該文探討了聚類算法作為一種無監督的異常檢測技術，在網絡入侵檢測技術中的作用，并通過具體分析K-means算法和迭代最優化算法的優劣，把兩種算法結合起來，提出一種新的分類算法。

關鍵詞：模式識別；無監督的異常檢測技術；聚類算法K-means算法；迭代最優化算法

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)32-1194-03

The Role of the Clustering Algorithm in the Network Intrusion Detection Technology

ZHANG Pei-shuai

(The PLA 71977 Unit， Rizhao 276800， China)

Abstract: The paper studies the role of the clustering algorithm in the network intrusion detection technology， and create a new algorithm by analysising the Pros and Cons of K-means algorithm and Iterative optimization algorithms.

Key words: pattern recognition; anomaly detection technology without supervision; clustering algorithm; K-means algorithm; iterative optimization algorithms

1 引言

我們知道，在一個多因素問題中，結果即目標與各因素即指標之間難以找出直接的聯系，很難用理論的途徑去解決。在各指標之間一時也尋找不到明顯的關聯，所能得到的只是些模糊的認識、由長期的經驗所形成的感知和由測量所積累的數據。因此，若能用計算機技術對以往的經驗、觀察、數據進行總結，尋找目標與各指標之間的某種聯系或目標的優化區域、優化方向，則對實際問題的解決是具有指導意義和應用價值的。

在無監督情況下，我們可以嘗試以多種方式重新描述問題，其中之一是將問題陳述為對數據分組或聚類的處理。盡管得到的聚類算法沒有很明顯的理論性，但它們確實是模式識別研究中非常有用的一類技術。

聚類算法是一個將數據集劃分成若干個聚類的過程，使得同一聚類內的數據具有較高的相似性，而不同聚類中的數據不具有相似性。相似或者不相似根據描述數據的屬性值來度量，通常使用基于距離的方法。通過聚類，可以發現數據的密集和稀疏的區域，從而發現數據整體的分布模式，以及數據屬性間有意義的關聯。

我們首先從模式識別的思想入手進行探討。

2 模式識別的概念

模式識別方法（Pattern Recognition Method）是一種借助于計算機對信息進行處理、判決分類的數學統計方法。在日常生產實踐和社會研究中，往往所需處理的問題影響因素非常多且復雜，給問題的研究和解決增加了困難。模式識別方法可使人們在影響因素眾多的情況下仍能對問題進行方便的處理，進而發現問題的解決途徑和事物發展的潛在規律性。

應用模式識別方法的首要步驟是建立模式空間。所謂模式空間是指在考察一客觀現象時，影響目標的眾多指標構成的多維空間。每個指標代表一個模式參量。

假設一現象有幾個事件（樣本）組成，每一個事件都有P個特征參量（X1，X2，…，Xp），則它就構成P維模式空間，每一個事件的特征參量代表一個模式。模式識別就是對多維空間中各種模式的分布特點進行分析，對模式空間進行劃分，識別各種模式的聚類情況，從而作出判斷或決策。

3 模式分類

模式分類的方法有很多種，比如貝葉斯決策論，最大似然估計和貝葉斯參數估計，分參數技術，線性判別函數法，獨立于算法的機器學習，利用這些方法，我們一直假設在設計分類器時，訓練樣本集中每個樣本的類別歸屬是“被標記了” 的，這種利用已標記樣本集的方法稱為“有監督”或“有教師”方法。

下面我們將介紹“無監督”或“無教師”方法，用來處理未被標記的樣本集。

有許多理由使我們相信“無監督”方法是非常有用的：

1) 收集并標記大型樣本集是個非常費時費力的工作，若能在一個較小的樣本空間上粗略地訓練一個分類器，隨后，允許它以自適應的方式處理大量的無監督的樣本，我們就能節省大量的時間和精力。

2) 存在很多應用，待分類模式的性質會隨著時間發生緩慢的變化。如果這種性質的變化能在無監督的情況下捕捉到，分類器的性能就會大幅提升。

3) 可以用無監督的方法提取一些基本特征，這些特征對進一步分類會很有用。

4) 在任何一項探索性的工作中，無監督的方法都可以向我們揭示觀測數據的一些內部結構和規律。

4 基于異常的入侵檢測技術

基于異常的入侵檢測技術可以分為有監督的異常檢測技術和無監督的異常檢測技術，有監督的異常檢測技術通過觀察得到的正常數據建立正常數據模型，然后檢測技術那些偏離正常模型的異常數據，一個比較典型的使用這種技術的系統是美國喬治梅森大學的MADAM/ID系統。這種方法能夠檢測技術新的攻擊類型，因為這些新的攻擊數據也會偏離正常的數據模型。有監督的異常檢測技術的一個缺陷是需要一組完全正常的數據來訓練獲得模型，如果訓練數據中包含攻擊數據的話，這些攻擊就很難檢測技術到，因為該方法把這些攻擊數據認為是正常數據，另一方面，要獲取這些訓練數據也是很困難的。

目前入侵檢測技術研究的重點轉移到了無監督的異常檢測技術上，這種技術用一組沒有標記的數據作為輸入，發現其中存在的攻擊數據，即試圖從一組不知道什么是正常，什么是異常的數據集中發現那些異常的數據。無監督的異常檢測技術與有監督的異常檢測技術相比，它不需要完全正常的訓練數據，只需要未加工的網絡原始數據。無監督的異常檢測技術技術有一個基本的假設，就是正常數據和異常數據有定性的不同，這樣才可以將它們區分開來，例如通過一般的分析，可以知道拒絕服務攻擊的數據在屬性取值和模式上與正常的數據有很大的不同，所以可以利用無需指導的異常檢測技術技術來有效地檢測技術出拒絕服務攻擊。

5 聚類算法簡介

聚類算法涉及很多個領域，包括數據挖掘、統計、機器學習、空間數據庫技術，目前研究重點是基于距離的聚類算法。聚類算法也是一種無指導的學習，它不像分類算法那樣需要事先標記好的訓練數據。聚類算法的輸入是一個包含多個數據的數據集，每個數據通常用一個屬性向量(x1，x2，...，xp)來表示，其中xi是一個連續的或離散的變量，代表數據的一個屬性的取值。

聚類算法的輸出是若干個聚類，每個聚類中至少包含一個數據，而且同一個聚類中的數據具有相似性，不同聚類的數據不具有相似性。

為了使用聚類算法，需要計算數據之間的差異，數據間的差異通常用距離來表示，距離計算方法包括歐幾里德距離、Manhattan距離、Minkowski距離。其中最常用的是歐幾里德距離，它的計算方法如下：

其中i，j分別代表數據集中的兩個數據，它們都有P個屬性。

可以給不同的屬性賦以不同的權值，這樣計算出來的距離稱為加權的歐幾里德距離，定義如下：

聚類算法有很多種，可以劃分為幾種類別：劃分方法，層次方法，基于密度的方法，基于網格的方法和基于模型的方法，同時聚類也可以用于異常值(outlier)檢測技術。

6 兩種聚類算法的優劣分析

6.1 K-means算法

最常用的聚類算法是K-means算法，它是一種劃分方法。給定一個包含n個數據的數據集，和產生的聚類的個數，K-means算法將個數據劃分成k個子集，每個子集代表一個聚類，同一個聚類中的數據之間距離較近，而不同聚類的數據間距離較遠。每個聚類由其中心值來表示，通過計算聚類中所有數據的平均值可以得到它的中心值。

1) K-means算法描述如下：

算法：K-means

輸入：聚類的個數k和一個包含n個數據的數據集

輸出：k個聚類

方法：任意選取k個數據作為初始的聚類中心

Do

將每個數據劃分到一個聚類，依據數據與聚類中心值的距離最近為標準

更新聚類的中心值，即重新計算每個聚類中所有數據平均值

While劃分沒有發生變化時輸出K個聚類

2) K-means算法在入侵檢測技術中的應用原理

基于無監督聚類的入侵檢測技術算法建立在兩個假設上：第一個假設是正常行為的數目遠遠大于入侵行為的數目。第二個假設是入侵的行為和正常的行為差異非常大。該方法的基本思想就是由于入侵行為是和正常行為不同的并且數目相對很少，因此它們在能夠檢測技術到的數據中呈現出比較特殊的特性。比如可以首先假定輸出10個聚類，從數據集中任選10個數據作為這個聚類初始的中心值，然后將每10個數據劃分到其中的一個聚類，方法是判斷該數據到哪一個聚類的中心值的距離最近，則將該數據劃分到這個聚類。劃分完成后，重新計算每個聚類的中心值，方法是計算聚類中所有數據的平均值，把這個平均值作為新的聚類的中心值。接下來重新將每個數據劃分到其中的一個聚類，如此反復地進行若干次劃分和計算中心值的操作，直到數據的劃分沒有變化。

3) 算法的優點和缺陷

算法的優點是不需要用人工的或其他的方法來對訓練集進行分類，并且能夠比較有效地檢測技術未知入侵攻擊。而且算法有良好擴展性，被廣泛應用于各領域。

但是像K-means算法經常在聚類開始前就獲得了全部數據（即離線的），但時常會有些對“在線聚類”的需求。比如存儲空間不夠記錄所有的數據模式，或者系統對時間要求很高，以至于數據還沒有全部出現算法就必須開始。

怎么解決這個問題呢？大家都知道，算法設計要求中有一點就是效率與低存儲量需求，所以衡量算法的復雜度有時間復雜度和空間復雜度兩個方面。K-means算法的效率較高，但是得付出較大的存儲空間。下面介紹一下迭代最優化算法。

6.2 迭代最優化算法

輸入：聚類的個數k，一個包含n個數據的數據集，每個聚類的均值mi

輸出：k個聚類

方法：隨機選取一個樣本Xi （存在于某個均值為mi的聚類中）

While Xi離mj 的距離比離 mi 更近

Do

將Xi轉移到均值為mj的這個聚類中

更新這個聚類的中心值，即重新計算這個聚類中所有數據平均值

While劃分沒有發生變化時輸出K個聚類

算法分析：對這個算法稍作考慮就會發現它其實是K-means算法的一種變形。K-means算法在每次更新前都要對所有的數據點重新分類，而這個方法每次對一個樣本重新分類后就進行更新。

但是這種算法更易陷入局部極小值，對全局入侵檢測技術效率有影響。然而它畢竟是一種逐步求精的算法，對存儲空間要求不高，而且很容易作些改動使得它能處理順序數據流或需要在線聚類的場合，這也正符合入侵檢測技術的環境。當然，在其他在許多領域也有廣泛的應用。

7 結束語

衡量一個算法的效率有時間和空間兩方面的要求，而且時空不可能同時達到最優，但是可以適當地將時空兩方面兼顧一下，使對聚類分析時的存儲空間要求不太高，同時分析過程也不太長。

所以，如果能把有監督和無監督方法的結合，即把是K-means算法和迭代最優化算法的結合，從而生成一種更加優化的算法，并據此思路設計成入侵檢測技術系統，各部分的性能和整體效率必然會大大提高。

參考文獻：

[1] 蔣建春，馮登國.網絡入侵檢測技術原理與技術[M].北京:國防工業出版社，2001.

[2] 戴連英，連一峰，王航.系統安全與入侵檢測技術[M].北京:清華大學出版社，2002.

[3] 唐正軍.網絡入侵檢測系統的設計與實現[M].北京:電子工業出版社，2002.

[4] 戴英俠.系統安全與入侵檢測[M].北京:清華大學出版社，2002.

[5] 張杰，戴英俠.入侵檢測系統技術現狀及其發展趨勢[J].計算機與通信，2002(6):28-32.