王浩，石研

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

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

王浩1，石研2

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

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

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

0 引言

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

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

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

1 特征選擇方法

1.1 Fisher分

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

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

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

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

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

1.2 FCBF 算法

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

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

2 Fisher-FCBF特征選擇方法

2.1 方法模型

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

圖1 Fisher-FCBF算法流程圖

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

2.2 Fisher-FCBF算法的基本定義

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

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

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

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

2.3 算法描述

輸入：訓(xùn)練集、原始特征集D。

輸出：特征子集S'。

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

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

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

（4）計算每個特征的C-相關(guān)（即SUi,c）；

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

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

3 實驗

環(huán)境：6×2.6GHz CPU，32GB內(nèi)存，64位Windows 8系統(tǒng)，算法的實現(xiàn)采用64位MATLAB R2012a[10]。

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

3.1 評估指標

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

表1 混淆矩陣

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

3.2 實驗過程

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

（1）特征選擇：采用最佳參數(shù)對KDD99[11]數(shù)據(jù)進行數(shù)據(jù)的預(yù)處理，然后將利用算法所獲得的特征權(quán)值進行結(jié)果對比與選取，從而得到較優(yōu)的特征子集；不同的得到對應(yīng)的特征子集。

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

3.3 實驗結(jié)果與分析

（1）Fisher分的特征選擇

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

圖2 Fisher分的漏報率情況

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

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

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

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

（2）FCBF的參數(shù)選擇

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

表2 FCBF算法δ值得選擇

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

3.4 實驗結(jié)果與分析

以下為四種評價

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

表3 四種算法的比較

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

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

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

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

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

4 總結(jié)

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

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

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

[3]張潤蓮,張昭,彭小金,等.基于Fisher分和支持向量機的特征選擇算法[J].計算機工程與設(shè)計,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]郭春.基于數(shù)據(jù)挖掘的網(wǎng)絡(luò)入侵檢測關(guān)鍵技術(shù)研究[D].北京郵電大學(xué),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-），女，湖北黃岡人，碩士研究生，研究方向為網(wǎng)絡(luò)安全、特征選擇

2017-03-16

2017-05-10

國家自然科學(xué)基金項目（No.61163052、No.61303231、No.61433012）、國家自然科學(xué)基金聯(lián)合基金項目（No.U1435215）

1007-1423（2017）15-0007-06

10.3969/j.issn.1007-1423.2017.15.002

石研（1991-），女，河南商丘人，碩士研究生，研究方向為無線傳感器網(wǎng)絡(luò)節(jié)點定位和網(wǎng)絡(luò)安全

Intrusion Detection;Feature Selection;Fisher Score;FCBF