基于Fisher-FCBF的入侵特征選擇算法的研究

王浩，石研

（1.新疆大學信息科學與工程學院，烏魯木齊 830046；2.新疆大學軟件學院，烏魯木齊 830008）

基于Fisher-FCBF的入侵特征選擇算法的研究

王浩1，石研2

（1.新疆大學信息科學與工程學院，烏魯木齊 830046；2.新疆大學軟件學院，烏魯木齊 830008）

大量的冗余和噪音數據混合于網絡入侵數據中，從而影響到檢測的性能和響應。因此，提出基于Fisher-FCBF算法。通過對特征的Fisher分值排序，再使用FCBF算法去冗余，結合SVM，建立分類特征模型，在不降低準確率的前提下，選出最優特征子集，結果表明所提出的方法能夠在保證分類準確率的情況下，降低至少11%-21%的計算時間。

入侵檢測；特征選擇；Fisher分；FCBF

0 引言

高吞吐量技術的快速發展導致數據的維度和樣本大小成指數增長[1]。高維的數據使得入侵檢測將會消耗巨大的資源和時間，而如何進行快速有效的檢測，將會成為網絡入侵檢測亟待解決的問題。是以，為解決入侵檢測系統的性能和準確性，將特征選擇引入了入侵檢測中[2]。

特征選擇作為一種常見的降維方法是模式識別的研究熱點之一。它是指從原始的特征集合中，去除不相關和冗余的特征，使選擇后的特征子集為較優的特征子集。在原始數據中，每一個特征的重要程度都不相同，重要的是找到對分類器影響較大的特征，去掉影響不大或者是相關性不大的特征[3]。Fisher分是一種有效的特征選擇方法，可以很好地去除噪聲數據，有效地降低特征空間。

本文通過將特征選擇引入到入侵檢測當中，在減少了安全數據的維度的同時降低了計算時間。本文將Fisher分和FCBF相結合，提出一個新的算法Fisher-FCBF，該算法通過特征的重要度對特征進行評估，從而得到較優的特征子集。實驗將SVM（Support Vector Machine）作為分類算法，從準確度、漏報率、預測時間、誤報率等四方面對實驗數據進行評價，最終說明所提的算法有效降低了運行的時間。

1 特征選擇方法

1.1 Fisher分

Fisher分是一種基于距離度量的特征選擇方法［4］。其主要思想是按照Fisher準則計算特征的比值，并將該比值作為該特征的Fisher分，比值愈大，說明該該特征對分類器越重要，分類的能力越強，在分類時，可以使得其在類內的距離盡量的小，而類間的距離盡量的大[4]。Fisher分在文本處理、圖像識別等領域有相關的應用，但主要還是應用于預處理。Jiang L等[5]將半監督核邊界Fisher分析用于儀表誤差診斷中的特征提取，由于Fisher方法同時考慮類內和類間的散度，能夠清晰的發現數據集的內部結構。Lu JC等[6]將Fisher判別準則應用于隱藏分析特征選擇中，用于有效地減少數值特征的維度。

首先假定存在訓練集樣本 {(x1,y1),(x2,y2),(xi,yi),…(xl,yl)}，其中，l為樣本數量；xi∈Rn，i=1,2,…,l,n為特征向量維數；yi={-1,1}l為類別標號，1——正類，-1——負類。而正類樣本的集合X1，個數為l1；負類樣本集合記為X2，個數記為l2。以Fk表示Fisher分，則：

式中：Sb——類間離散度，表示不同類樣本間的距離；Sw——類內離散度，表示同類樣本間的距離，計算公式如下：

通過運行Fisher分，我們可以得到該算法的特征比值，為了進一步選出較優的特征子集，將會結合SVM算法以檢測率和誤報率為指標來選擇，因此我們定義了特征分類值[4]。

式中：i為第i維特征或第i組特征；DRi為特征的檢測率；FDi為特征的誤報率。

1.2 FCBF 算法

基于快速關聯的過濾算法（FCBF）是一種快速過濾的特征選擇算法，使用對稱的不確定行來度量兩個特征的相關性，通過度量特征-類別以及特征-特征之間的關聯，來選擇最優的特征。其主要思想是根據定義的 C-相關（SUi,c，特征與類的關系）和 F-相關（SUi,j，特征與特征的關系），從原始特征集合中去除C-相關值小于δ（由用戶定義）的特征，然后對剩余的特征進行冗余分析，最后得到一個較優的特征子集。算法的偽代碼如下所示：

FCBF通過選擇所有主要特征和刪除其余特征來進行近似相關性和冗余分析。它使用C-相關和F-相關來確定特征冗余，適用于多分類問題中。在應用方面，Gharavian D等人將FCBF和GA優化的GA優化的基于FAMNN的情感識別器，顯著地改善了語音處理系統中語音情感的識別[7]。Liu Y等將改進的FCBF和相關矢量機（RAM）相結合，有效地提取了相關但非冗余的故障特征，并準確的識別柴油機的故障類型[8]。

2 Fisher-FCBF特征選擇方法

2.1 方法模型

Fisher分可用于特征選擇與特征提取，是特征降維的一種有效的方法。其主要思想是通過對樣本的變換，將樣本投影到一條直線上，使樣本的投影能更好地分類[3]，將多維問題簡化為一維問題來解決。Fisher分需選出在同一特征下，其類內的距離盡量小，類間距離盡量大的特征，這樣的特征為強鑒別的特征，可提高類別間的區分能力。Fisher算法可以刪除不相關和辨別性能較差的特征，但是卻不能剔除數據中的冗余特征。FCBF算法更注重特征與類別、特征與特征之間的關系，能夠有效地去除冗余特征，同時在處理高維數據時該算法更加高效。因此，本文提出了Fisher-FCBF算法，選擇兩個算法的優點，從而實現了一種組合式的特征選擇方法。算法的流程圖如圖1所示。

圖1 Fisher-FCBF算法流程圖

通過Fisher分去除不相關或者相關性較小的的特征，對特征進行初選。然后使用FCBF對特征進行更進一步的篩選，剔除冗余特征，最終得到較優的特征子集。最終，采用準確率、預測時間、誤報率等作為評價指標，利用SVM分類器來評估得到的較優的特征子集。

2.2 Fisher-FCBF算法的基本定義

定義1：Fisher-FCBF的算法矩陣，可以表示為二元組D:(Fn,Cm)。其中Fn表示數據的特征維度為n維。Cm表示該數據共有m類。

定義2：Fisher-FCBF中Fisher算法的特征分類值FTRi和特征子集S。其中，N代表原始特征的維度。FTRi代表特征分類值，特征的檢測率越高，誤報率越低，其特征的分類值越大，就越重要。S即將FTRi按大小進行排序，選取FTRi值較大的對應的特征作為特征子集S。

定義3：C-相關：任何一個特征Fi與類之間的關系，記為SUi,c；F-相關：任意兩個特征Fi與Fj之間的關系，記為SUi,j。

定義4：Fisher-FCBF中FCBF的參數有：不確定性SU(X ,Y )、啟發式參數Spi，S+pi，S-pi特征子集Sbest[9]。 δ由用戶自定義，X表示為特征，Y為類別標簽，C-相關性的值越大，而F-相關的值越小，則該特征為優越特征。如果特征Fj滿足SUj,i≥SUi,c≥δ，則Fj為Fi的冗余特征，構成冗余特征集 Spi再判斷，如果SUj,i>SUi,c，則構成S+pi，剩下的特征構成S-pi。

2.3 算法描述

輸入：訓練集、原始特征集D。

輸出：特征子集S'。

（1）輸入KDD99數據集，特征個數為N，初始化的FTRi=0；

（2）根據公式計算特征集D上的每維特征Fisher值Fki，并對其進行降序排列，使用SVM，測試并計算模型的正確率和誤報率，最后計算FTRi，形成一個去相關性的特征子集S；

（3）將子集S作為FCBF的輸入，選取合適的參數值δ；

（4）計算每個特征的C-相關（即SUi,c）；

（5）根據參數Spi，S+pi，S-pi來剔除數據中的冗余特征；

（6）當{S}→?，輸出子集S'。

3 實驗

環境：6×2.6GHz CPU，32GB內存，64位Windows 8系統，算法的實現采用64位MATLAB R2012a[10]。

數據集：采用KDD CUP 1999［11］作為入侵檢測數據，其中包含一種正常數據和四種攻擊數據。

3.1 評估指標

使用IDS的常用指標漏報率[12]、正確率[12]、誤報率[12]、檢測時間[12]作為本次的評價準則。表1為混淆矩陣[12]。

表1 混淆矩陣

其中，TN表示正常數據被誤認為異常，TP表示將異常數據歸類到正常類。根據表1，給出了以下的一些計算方式：

3.2 實驗過程

將Fisher-FCBF算法與Fisher分、FCBF、SVM算法做一個對比。實驗室用KDD99數據集，并5類指標作對比，過程如下：

（1）特征選擇：采用最佳參數對KDD99[11]數據進行數據的預處理，然后將利用算法所獲得的特征權值進行結果對比與選取，從而得到較優的特征子集；不同的得到對應的特征子集。

（2）結果驗證：SVM采用5折交叉驗證的方法和同樣參數將，將獲得的不同的結果用得出的四種評估指標進行結果的對比與分析。

3.3 實驗結果與分析

（1）Fisher分的特征選擇

按照公式（1）計算各個特征的Fisher值并對其進行排序，并查看單個特征Fisher分值對分類器的影響，計算了特征的漏報率，如圖2所示。

圖2 Fisher分的漏報率情況

從圖2可以看出，隨著Fisher分值的下降，特征對分類器的影響逐漸減小，相關的特征也越來越少；并且按照Fisher比值的排序，可以看出在22個特征之后的特征對分類器的影響不大，可以視為不相關或相關性較小的特征，可以將其去掉。

根據公式（5）計算了特征集的Fisher分，并查看特征集的特征分類對分類的影響，如圖3所示。

從圖3可以看出，當特征維度為7、18、27時都達到了一個峰值，但是在維度為27時，特征測度值達到最大，因此進一步建立了特征模型，通過對7、18、27個特征進行正確率、誤報率、測試時間的比較，隨著特征數的增加，正確率和測試時間也隨之增長，而誤報率在逐漸降低，因而當特征維度為27時，這時的特征子集的正確率最高，誤報率最低，同時測試時間也最大，最后，將特征子集的特征維度定為27。

圖3 特征集的特征分類影響

（2）FCBF的參數選擇

本文通過選取不同的δ值進行多次實驗對比，從而選擇出相對較優的δ值。

表2 FCBF算法δ值得選擇

從表4中可以看出，隨著δ的增加，準確率保持恒定，再此情況下，δ選取0.01最佳，漏報率、誤報率最小。

3.4 實驗結果與分析

以下為四種評價

通過以下四種指標對四種算法進行比較，結果如表3所示。

表3 四種算法的比較

圖4 四種算法的特征數、準確率和預測時間的對比

根據圖4可知，Fisher-FCBF算法在一定程度上減少了特征選擇的數量，明顯的提高了預測時間。其中SVM的準確率最高，FCBF的最低。圖5為四種算法在漏報率和誤報率之間的對比。

實驗結果表明這4種算法的漏報率都是比較低的，而改進的Fisher-FCBF算法，在誤報率方面有一定的降低。

通過以上實驗的對比分析，可以得出Fisher-FCBF在準確率只是輕微下降的情況下，數據的特征維度有明顯的減少，在分類算法的時間上有顯著地降低，有較好的魯棒性。

圖5 四種算法的誤報率和漏報率的對比

4 總結

大量的冗余和噪音數據混合于網絡入侵的數據中，影響了系統的檢測效率和檢測速率。因此本文提出了Fisher-FCBF特征選擇方法，去除了數據集中的不相關與冗余數據，在保證準確率的情況下，不僅降低了數據的維度、計算復雜與時間復雜，同時減少了誤報率和預測時間。因次改進的Fisher-FCBF算法是一種有效的特征選擇算法。

[1]Tang J,Alelyani S,Liu H.Feature Selection for Classification:A Review[J].Documentación Administrativa,2014:313-334.

[2]楊杰明.文本分類中文本表示模型和特征選擇算法研究[D].吉林大學,2013.

[3]張潤蓮,張昭,彭小金,等.基于Fisher分和支持向量機的特征選擇算法[J].計算機工程與設計,2014（12）:4145-4148.

[4]Jiang L,Xuan JP,Shi TL.Feature Extraction Based on Semi-supervised Kernel Marginal Fisher Analysis and Its Application In Bearing Fault Diagnosis[J].Mechanical Systems and Signal Processing,2013,41（1）:113-126.

[5]Lu JC,Liu FL,Luo XY.Selection of Image for Steganalysis Based on the Fisher Criterion[J].Digital Investigation,2014,11（1）:57-66.

[6]Hossain M A,Jia X,Pickering M.Subspace Detection Using a Mutual Information Measure for Hyperspectral Image Classification[J].Geoscience&Remote Sensing Letters IEEE,2014,11（2）:424-428.

[7]Jixiang Y E,Wang C.Application of Improvement of F-score Algorithm in Speech Emotion Recognition[J].Computer Engineering&Applications,2013,49（16）:137-141.

[8]Gharavian D,Sheikhan M,Nazerieh A,et al.Speech Emotion Recognition Using FCBF Feature Selection Method and Ga-optimized Fuzzy Artmap Neural Network[J].Neural Computing and Applications,2012,21（8）:2115-2126.

[9]Liu Y,Zhang J,Ma L.A Fault Diagnosis Approach for Diesel Engines Based on Self-adaptive WVD,Improved FcBF and PECOC-RVM[J].Neurocomputing,2016,177（C）:600-611.

[10]黃春虎,努爾布力,解男男,等.基于Re—FCBF的入侵特征選擇算法研究[J].激光雜志,2016（1）:103-107.

[11]The UCI KDD Archive.KDD Cup 99 DataSet[EB/OL].http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html.

[12]郭春.基于數據挖掘的網絡入侵檢測關鍵技術研究[D].北京郵電大學,2014.

Research on Feature Selection Algorithm in Intrusion Detection Based on Fisher-FCBF

WANG Hao1，SHI Yan2

（1.School of Information Science and Technology，Xinjiang University，Urumqi 830046；2.School of Software，Xinjiang University，Urumqi 830008）

A large amount of redundancy and noise data are mixed in the network intrusion data,thus affects the performance and re?sponse of the detection.By sorting the Fisher scores of the feature,uses the FCBF algorithm to reduce the redundancy and us?es SVM to establish the classification feature model.The optimal feature subset is selected without reducing the accuracy. The results show that the proposed method can reduce at least 11%-21%of the calculation time in the case of classification accuracy to ensure.

王浩（1991-），女，湖北黃岡人，碩士研究生，研究方向為網絡安全、特征選擇

2017-03-16

2017-05-10

國家自然科學基金項目（No.61163052、No.61303231、No.61433012）、國家自然科學基金聯合基金項目（No.U1435215）

1007-1423（2017）15-0007-06

10.3969/j.issn.1007-1423.2017.15.002

石研（1991-），女，河南商丘人，碩士研究生，研究方向為無線傳感器網絡節點定位和網絡安全

Intrusion Detection;Feature Selection;Fisher Score;FCBF