主成分分析法和K-均值聚類算法在入侵檢測系統中的運用

盧永祥，李巧蘭

（武夷學院 信息技術與實驗室管理中心，福建 武夷山 354300）

隨著信息時代的到來，計算機網絡得到飛速發展，給人們帶來便利的同時也遭受越來越嚴重的網絡攻擊。網絡安全變得尤為重要，國內外廣大學者對網絡安全防護技術的研究也越來越深入，網絡安全防護技術中防火墻技術和數據加/解密技術僅僅是靜態防護，在錯綜復雜網絡環境中，單單靠靜態的防護是完全不夠的。入侵檢測系統是對防火墻技術的有效補充，不僅對系統提供實時的防御，而且能主動對穿越防火墻的攻擊進行有效的響應，但一般的入侵檢測技術，具有效率低、誤差率高的特點。針對大數據網絡的特征以及目前存在的問題，入侵檢測系統自身存在著很多不適宜大數據網絡的缺點，容易給外來入侵者機會，對來自網絡內部的非法訪問也容易誤報。這就要求我們研究出一種新的網絡數據檢測的方法來彌補入侵檢測系統的不足。

本文研究集成主成分分析法和K-均值聚類算法相結合的入侵檢測系統，主成份分析法是從多元的事物中解析出具有代表性的特征，簡化復雜數據,K-均值聚類算法能夠減少因高維數據所帶來的計算量和計算時間。將這2種算法結合起來對網絡流量的數據進行數據預處理，利用主成分分析法提取能代表每一類數據集合的主成分作為入侵檢測系統的輸入數據，一方面實現了降低數據集合的維數、數量級以及數量，另一方面去除了冗余、非主要特性的特征屬性，有效提高了輸入數據集合的有效性。再利用K-均值聚類算法對數據集合進行重分類，一方面提高分類的準確性另一方面使得數據集合具有一定的簡潔性。并通過實驗進行驗證，采用檢測入侵檢測系統性能的標準數據集KDD CUP 99中的部分子集作為仿真實驗數據集合，經過對比實驗驗證基于這兩種算法的入侵檢測系統具有較高的檢測效率和低的誤報率。

1 主成分分析法對數據進行降維

主成分分析法(principal component analysis，PCA)是一種用數學推導的方法來實現高緯度數據的降維處理，用主成分分析法PCA來實現數據降維比較簡單。PCA算法的步驟有六步。

第一步，計算樣本的協方差矩陣

第二步，記特征空間X的協方差矩陣為Σx，并且記該特征空間的協方差矩陣的特征值為λ，前p個特征值分別記為λ1，λ2，…，λp，并假設λ1≥λ2≥…≥λp≥0。

第三步，記每個特征值對應的特征向量為a1，a2，…，ap，則特征向量ai可表示為：

第四步，計算累計方差貢獻率，達到85%及其以上時，計算主成分的個數。

第五步，計算所選出的K個主成分的貢獻率。

第六步，根據方差貢獻率排序，統計出累積方差的貢獻率，當累積方差的貢獻率達到85%以上時，計算K值，即可計算出能代表原數據特征屬性的主成分的個數。

經國內外學者實驗證明，當累計方差貢獻率超過85%就表示可以代表原特征空間的屬性了[1]。我們可以根據這個累計方差的貢獻率來求出K，那么這K個主成分就可以用來代表原數據集的主要特征，已達到對高維數據進行降維的目的。

2 K-均值聚類算法對數據進行重分類

K均值聚類算法是一種應用非常廣泛的聚類算法，K可以由用戶指定，給定一個數據點集合和需要的聚類數目K將各個聚類子集內的所有的數據樣本的均值看作是這個聚類的代表點。這個算法的主要的思想是通過一系列的迭代過程把數據集劃分成為不同的類別[2]，并且每個聚類內部緊湊，聚類間相互獨立。目前是應用于工業領域的一種非常有影響的技術。

K均值聚類算法的工作原理是首先確定初始聚類中心，這個聚類中心的確定是從數據集合中隨機選取的K個點，然后分別計算除了作為聚類中心的這些點以外的數據集合的其他點到這個聚類中心的距離，并且計算這個距離的大小，最后根據判斷距離的大小把數據樣本歸類到距離它最近的類別中，并形成新的聚類中心[3]。具體算法描述如下：

設數據集合為X，其中X=（x1，x2，…，xd），執行第一步得到分組特征子集記為Xi，其中i=1,2,…,d。

在大數據網絡時代背景下，網絡數據呈現復雜、冗余、龐大、高維等特性，網絡數據集的特性不僅多而且存在著不相干特征屬性，特征屬性集之間的關系也很復雜，對網絡數據集進行重聚類分析，主要應用K-均值聚類算法的聚類過程對網絡數據特征屬性進行計算。

可以設定不同的K值和聚類中心對網絡數據集進行分類，經過研究可通過設置k=2,3,…,u，其中u=，并每次執行時設置隨機初始中心，執行u次K均值聚類算法得到u個聚類結果，每個聚類中都被標記為一個特征組合，從而簡化了數據量。

3 集合主成分分析法和K-均值聚類分析法的入侵檢測系統

基于主成分分析法和K-均值聚類算法對入侵檢測系統的輸入數據進行預處理的的過程包括，首先進行網絡數據集的提取，用主成分分析法對網絡數據進行降維處理，最后用K-均值聚類算法對數據進行重聚類。

將主成分分析法和K-均值聚類算法結合起來對網絡數據進行預先處理，并將處理后的網絡數據集導入到入侵檢測系統里，會很大程度上提升入侵檢測系統的檢測效率，降低誤/漏報率。其模型如圖（1）所示。

圖4-1 集合主成分分析法和K均值聚類算法網絡數據預處理模型Fig.1 Network data pre-processing model that assembled principal component analysis method and K-means clustering algorithm

1)提取網絡數據集

入侵檢測系統以旁路的方式部署在網絡中，實時檢測流經網絡接口的數據包，主要是監測網絡中的數據鏈路層的數據幀、IP數據包等。

2)數據降維處理

對網絡數據進行主成分分析實現數據降維并特征值提取，進行數據規范化、標準化，方便后續K-均值聚類算法進行重聚類。

3)對數據進行分類處理

網絡數據集經過主成分處理階段后，再利用K-均值聚類算法對這些網絡數據集進行聚類分析，建立聚類中心，并進行標記。

4)輸出

對預處理后輸出的網絡數據集進行入侵檢測操作，標記出哪些是正常的網絡數據，哪些是異常的網絡數據，并對異常網絡數據進行處理。

采用集成K-均值聚類算法和主成分分析法的入侵檢測系統，一方面監測并預警來自互聯網的黑客攻擊行為，另一方面也阻擊了來自用戶群體的誤操作、IP地址濫用、非法下載以及違反安全策略的用戶行為等。下面通過實驗驗證得知，這種方法具有高的檢測效率和較低的誤報率。

4 仿真實驗驗證及分析

通過主成分分析法提取出數據集的主要成分，再采用均值的方法來對數據聚類，經過這樣一系列處理后得到的數據更純凈，特征之間的屬性相對更獨立，作為入侵檢測系統的輸入數據更高效和更低的誤碼率。實驗采取數據集KDD CUP 99的10%的特征子集進行仿真實驗。

4.1 采用數據集簡介

KDD CUP 99數據集是公認比較實用的網絡安全審計數據集，分為訓練數據集和測試數據集兩部分[4]。數據集里每一行代表一條記錄，每條記錄有42個屬性。其中，前面41個屬性有41維特征，這些特征又有4種類型，基于TCP連接基本特征（共9種,1～9）、基于TCP連接的內容特征（共13種,10～22）、基于時間的網絡流量統計特征（共9種，23～31）、基于主機的網絡流量統計特征[5]（共10種，32～41）這42個屬性中最后一個是標識屬性，用來表示該條記錄是否正常，如果不正常，將標記出是哪種網絡攻擊，下面介紹網絡攻擊的一般種類，一般分為四種類型，表1介紹了該數據集的四種網絡攻擊類型的分類標識類型。

表1 KDD Cup99數據集的標識類型Tab.1 Identification types of KDD CUP99 dataset

4.2 入侵檢測系統的評測標準

評測入侵檢測系統性能好壞的最主要的標準之一是檢測率和誤報率[6]，檢測率和誤報率并給出其公式定義。

定義1檢測率 定義檢測率為DR，表示入侵檢測系統檢測出網絡數據集合中的數據異常的效率。

其中：TP表示入侵檢測系統檢測出網絡數據中非法數據的數量；FN表示未能識別到的網絡數據中非法數據的數量。TP+FN表示入侵檢測系統需要處理的總得網絡數據量。

定義2誤報率 我們定義誤報率為FR，誤報率表示入侵檢測系統對于正常數據流量的誤判斷占總數據流量的比率。

其中：FP表示入侵檢測系統在工作過程中出現錯誤的判斷正常網絡數據量的比率；TN表示入侵檢測系統能夠識別出正常網絡數據的數量。

4.3 KDDCUP 99數據集的10%的子集降維處理過程

本文進行仿真實驗，為了簡化實驗數據，利用特征值提取方法提取KDD CUP 99數據集的10%子集的部分屬性，如下圖2所示為該數據集部分集合截圖。

圖2 KDD CUP 99數據集10%子集部分記錄Fig.2 Partial records of 10%subset of KDD CUP 99 data set

我們利用特征提取的方法，提取該數據集合中屬性為的記錄，如下圖3所示為截取的該數據集合中屬性值為的部分記錄。

圖3 提取特征屬性后的數據子集的部分記錄Fig.3 Partial records of the data subset after has extracted the feature attributes

對提取特征值的網絡數據子集中的部分屬性進行主成分分析操作，我們提取了該數據子集的10個屬性，組成10維特征向量，可當做1×10維的特征矩陣，提取的數據子集可當做10×1 391的特征矩陣，執行主成分分析后，可以得到網絡數據集中代表不同的方差貢獻率和累積方差的貢獻率。如表2所示。

表2 方差貢獻率Tab.2 The contribution rate of variance

由上表可明顯看出：k=4時，累計貢獻率超過85%。即特征值的屬性分別為protocol_type、duration、count、srv_diff_host_rat所對應的特征值可以代表我們仿真所選擇數據子集的幾乎全部特征屬性。

我們可以用這4個特征屬性的數據代表原提取的10維的特征向量，為后續的分類工作既減少了計算量同時又降低了相關的維數，提高了分類的準確性。下面我們介紹用均值聚類方法對這些數據集合進行分類。

4.4 用K-均值聚類方法進行分類

利用主分分析法對數據進行降維處理以后，接下來就可以進行分類了。從KDD CUP 99數據集合的10%子集的訓練集中選出一組，同時從該數據集的測試集中選出三組。其中，訓練數據集有21 500條，包括315條是非法入侵網絡數據，選取這些非法入侵網絡數據時把四類攻擊類型的數據都包括進來；測試數據集中每一組包括5 250條，包括65條是非法入侵數據。訓練集和測試集中的非法數據占總數據量的比例[0.9%,1.5%]，符合聚類的條件。

經過計算，K-均值中聚類的個數K分別為14、18、22、28、36，我們首先標識訓練數據類別，用測試網絡數據進行測試，得出入侵檢測系統的檢測率和誤報率的結果如表3所示。

表3 K-均值聚類算法檢測率和誤報率Tab.3 The detection rate and false positive rate of K-means clustering algorithm

從表3可以看出，在對檢測網絡數據的檢測率上集合PCA和均值算法比傳統的均值算法檢測效率更高，從誤報率上來看集合PCA和均值算法比傳統的均值算法有明顯的降低。

4.5 入侵檢測系統檢測率和誤報率分析

由公式(6)和公式(7)可以計算出采用主成分分析法PCA、信息增益法IG和相關系數法進行比較，基于不同特征提取方法下的均值聚類算法處理后作為入侵檢測系統輸入數據的檢測效率和誤報率，結果如表4所示。

表4 3種方法效率比較Tab.4 Efficiency comparison of three methods

從表4可以得出結論，采用主成分分析法和K-均值聚類算法相結合處理對入侵檢測系統的輸入數據進行預處理具有高檢測率和低誤/漏報率。下面我們通過圖示比較三種方法得出的結果，如圖4、5所示。

圖4 三種特征提取方法得到的入侵檢測系統的檢測率（%）比較Fig.4 Comparison of detection rates(%)of the intrusion detection systems obtained by three feature extraction methods

圖5 三種特征提取方法得到的入侵檢測系統的誤報率%比較Fig.5 Comparison of false positive rates of the intrusion detection systems obtained by the three feature extraction methods

5 結論

對基于主成分分析法PCA對網絡數據進行降維處理，經過數據降維后再用K-均值聚類算法對網絡數據進行分類處理。并且通過仿真實驗進行驗證，實驗數據采用KDD CUP 99數據集，經過實驗驗證本文提出的集合這2種方法來對網絡數據進行預處理后應用到入侵檢測系統中具有較高的檢測率和較低的誤報率。