基于ReliefF算法的核主成分特征提取

摘要：入侵檢測中特征選擇和特征提取是解決特征降維的方法之一。本文采用基于ReliefF算法的核主成分方法解決特征降維問題，先采用ReliefF算法去除原始特征中與分類不相關的特征，再采用核主成分分析法進行特征提取。實驗數據表明：將41個特征變量降維成9個主成分，大大減輕了后續的分類器的工作量，同時也有助于提高分類器的分類精度。

關鍵詞：特征選擇 ReliefF算法 KPCA 特征提取

為了能獲得理想的入侵檢測效果，需要在兩個方面進行努力：一是建造一個好的分類器，二是尋找對問題的一個好的表示，即選用的輸入特征能為分類器提供最有用的信息。對于前者，人們嘗試利用各種基于不同原理的方法來檢測入侵。對于后者，一般有兩種方法從原始的輸入特征中獲得問題更好的表達：特征選擇和特征提取。

1、特征選擇和特征提取技術

采用模式識別方法進行入侵檢測首先要解決特征降維問題。現存的特征降維主要采用特征選擇和特征再構造(也就是特征提取)兩種方法。

特征選擇是模式識別領域的重要問題。在一個學習算法通過訓練樣本對未知樣本進行預測之前，必須決定哪些特征應該采用，哪些特征應該忽略。特征選擇已廣泛應用到文本分類、圖像檢索、入侵檢測和基因分析等方面。特征提取是提升分類器性能的另一類方法。它通過對高維的輸入特征進行變換從而獲得新的低維特征。

入侵檢測系統中特征的選擇和提取如圖1所示。其中不相關的特征是指那些與分類過程沒有關系的特征。去不相關特征本文采用ReliefF算法。特征提取本文采用核主成分分析(KPCA)方法。

2、ReliefF算法及其實現

Kira等1992年提出了Relief算法。該算法僅適用于訓練樣本是兩類的情況。Kononenko[31]擴展了Relief算法得到ReliefF算法，ReliefF則可以應用于多類樣本情況。ReliefF算法在處理多類問題時，不是從所有不同類樣本集合中統一選擇最近鄰樣本，而是從每個不同類別的樣本集合中選擇最近鄰樣本，并且不是選擇一個最近鄰樣本，而是選擇k個最近鄰樣本。

ReliefF的算法描述如下：

輸入：訓練實例的特征向量集合及類別標號； /* N-特征維數，m-迭代次數，k-最近鄰樣本個數 * /

輸出：對應于特征向量各個分量的權值向量W；

1.初始化權值向量為0.W[A]: =0. 0；

2.for :i =1 to m

3.隨機選擇實例Ri；

4.計算k個nearest hits Hj；

5.對于每一類C≠class (Ri)

6.從類C中求得k nearest misses Mj(C)；

7.for A: =1 to N

9．結束；

需要說明的參數: diff(A，Ri，H)代表樣本Ri和H關于特征A的差異，初始值定義如公式(1)：

(1)

迭代計算為公式(2)

(2)

其中，H與M分別代表訓練集合中與實例Ri距離最近的同類(nearest hit)樣本與不同類樣本(nearest miss)。

ReliefF每次隨機從訓練樣本集中取出一個樣本Ri，然后從和Ri同類的樣本集中找出樣本Ri的k個近鄰樣本(nearest hits)，從每個Ri的不同類的樣本中找出k個近鄰樣本(nearest misses)，然后更新每個特征的權值。以上過程重復m次。

ReliefF算法的優點是：運行效率高，對數據類型沒有限制，對特征間的關系不敏感(相對很多特征評估方法的特征間獨立的建設)。ReliefF算法的缺點是：和很多特征評估算法，如信息增益等一樣，ReliefF算法不能去除冗余特征，算法會賦予所有和類別相關性高的特征較高的權值，而不管該特征是否和其余特征冗余。

3、核主成分分析算法

PCA是一種常見的、強大的特征提取方法，但它是一種線性映射算法，只能提取數據中的線性特征。核主成分分析(KPCA，Kernel principal component analysis)的提出被認為是PCA的一個非線性擴展。它是在PCA中引入核方法，首先將原始輸入向量xt映射到高維特征空間并在其上用PCA方法計算。在空間上的線性PCA方法對應于在空間xt上的非線性PCA方法。由于從xt到的映射，空間的維數假定比訓練樣本維數大。因此，KPCA解決如下的特征值問題：

(3)

其中是的樣本方差矩陣，的一個非零特征值，ui是對應的特征向量。

公式(3)被轉換為如下特征值問題：

(4)

其中核矩陣。中每個元素的值都等于向量在高維特征空間和上的內積，即

(5)

因為完全被核函數取代了，所以說映射是很有意思的。任意維而不需要精確計算這一問題通過運用核函數巧妙的解決了。任意滿足Mercer’s條件的函數都可以用核方法。是的一個特征值，滿足；是對應的特征向量，滿足 。

此外，為了確保特征向量滿足單位長度。每一個必需被標準化，通過利用對應的特征值。

因此，基于的估計，主成分通過如下公式計算：

(6)

其中，樣本輸入向量由一些中心化數據構成，即

在訓練集和測試集上的核矩陣也分別通過如下公式被修改：

(7)

(8)

其中，是n維單位矩陣，是測試數據的數量，代表長度為和的全1向量，代表由測試數據組成的的核矩陣。

4、實驗及結論

KDDCUP99數據集是目前入侵檢測領域比較權威的測試數據集，該數據集把入侵檢測數據特征分為三類，分別是基本特征、內容特征和流量特征。可將網絡入侵特征分為5類：Normal、DOS、R2L、U2R和Probing。

本文用到KDDCUP99的10%數據集中的1000個記錄，對前41個特征屬性分別進行ReliefF和KPCA分析。實驗結果如表1所示。

由表1可以看出，經過ReliefF算法和KPCA核主成分分析

算法對數據集進行特征選擇和特征提取后，前4個主成分的方差貢獻率總和為86%，前9個已經達到98.5%。也就是說，基本可以用4個主成分的數據來描述出原始的41維的特征數據的變化狀態。將41個特征變量降維成4個主成分，大大減輕了后續的分類器的工作量，同時也有助于提高分類器的分類精度。

參考文獻：

[1] Kononenko I. Estimation attributes: Analysis and extensions of RELIEF [A]. In: Bergadano F，De Raedt L，eds. Proceedings of the 1994 European Conference on Machine Learning [C]. Catania， Italy: Springer Verlag，1994.171-182.

[2] Wenming Zheng，Cairong Zou，Li Zhao. An Improved Algorithm for Kernel Principal Component Analysis[J].Neural Processing Letters，2005，22(1):49-56.