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

王浩，石研

（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ò)入侵?jǐn)?shù)據(jù)中，從而影響到檢測(cè)的性能和響應(yīng)。因此，提出基于Fisher-FCBF算法。通過(guò)對(duì)特征的Fisher分值排序，再使用FCBF算法去冗余，結(jié)合SVM，建立分類特征模型，在不降低準(zhǔn)確率的前提下，選出最優(yōu)特征子集，結(jié)果表明所提出的方法能夠在保證分類準(zhǔn)確率的情況下，降低至少11%-21%的計(jì)算時(shí)間。

入侵檢測(cè)；特征選擇；Fisher分；FCBF

0 引言

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

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

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

1 特征選擇方法

1.1 Fisher分

Fisher分是一種基于距離度量的特征選擇方法［4］。其主要思想是按照Fisher準(zhǔn)則計(jì)算特征的比值，并將該比值作為該特征的Fisher分，比值愈大，說(shuō)明該該特征對(duì)分類器越重要，分類的能力越強(qiáng)，在分類時(shí)，可以使得其在類內(nèi)的距離盡量的小，而類間的距離盡量的大[4]。Fisher分在文本處理、圖像識(shí)別等領(lǐng)域有相關(guān)的應(yīng)用，但主要還是應(yīng)用于預(yù)處理。Jiang L等[5]將半監(jiān)督核邊界Fisher分析用于儀表誤差診斷中的特征提取，由于Fisher方法同時(shí)考慮類內(nèi)和類間的散度，能夠清晰的發(fā)現(xiàn)數(shù)據(jù)集的內(nèi)部結(jié)構(gòu)。Lu JC等[6]將Fisher判別準(zhǔn)則應(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為類別標(biāo)號(hào)，1——正類，-1——負(fù)類。而正類樣本的集合X1，個(gè)數(shù)為l1；負(fù)類樣本集合記為X2，個(gè)數(shù)記為l2。以Fk表示Fisher分，則：

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

通過(guò)運(yùn)行Fisher分，我們可以得到該算法的特征比值，為了進(jìn)一步選出較優(yōu)的特征子集，將會(huì)結(jié)合SVM算法以檢測(cè)率和誤報(bào)率為指標(biāo)來(lái)選擇，因此我們定義了特征分類值[4]。

式中：i為第i維特征或第i組特征；DRi為特征的檢測(cè)率；FDi為特征的誤報(bào)率。

1.2 FCBF 算法

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

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

2 Fisher-FCBF特征選擇方法

2.1 方法模型

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

圖1 Fisher-FCBF算法流程圖

通過(guò)Fisher分去除不相關(guān)或者相關(guān)性較小的的特征，對(duì)特征進(jìn)行初選。然后使用FCBF對(duì)特征進(jìn)行更進(jìn)一步的篩選，剔除冗余特征，最終得到較優(yōu)的特征子集。最終，采用準(zhǔn)確率、預(yù)測(cè)時(shí)間、誤報(bào)率等作為評(píng)價(jià)指標(biāo)，利用SVM分類器來(lái)評(píng)估得到的較優(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代表特征分類值，特征的檢測(cè)率越高，誤報(bào)率越低，其特征的分類值越大，就越重要。S即將FTRi按大小進(jìn)行排序，選取FTRi值較大的對(duì)應(yīng)的特征作為特征子集S。

定義3：C-相關(guān)：任何一個(gè)特征Fi與類之間的關(guān)系，記為SUi,c；F-相關(guān)：任意兩個(gè)特征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為類別標(biāo)簽，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ù)集，特征個(gè)數(shù)為N，初始化的FTRi=0；

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

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

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

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

（6）當(dāng){S}→?，輸出子集S'。

3 實(shí)驗(yàn)

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

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

3.1 評(píng)估指標(biāo)

使用IDS的常用指標(biāo)漏報(bào)率[12]、正確率[12]、誤報(bào)率[12]、檢測(cè)時(shí)間[12]作為本次的評(píng)價(jià)準(zhǔn)則。表1為混淆矩陣[12]。

表1 混淆矩陣

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

3.2 實(shí)驗(yàn)過(guò)程

將Fisher-FCBF算法與Fisher分、FCBF、SVM算法做一個(gè)對(duì)比。實(shí)驗(yàn)室用KDD99數(shù)據(jù)集，并5類指標(biāo)作對(duì)比，過(guò)程如下：

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

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

3.3 實(shí)驗(yàn)結(jié)果與分析

（1）Fisher分的特征選擇

按照公式（1）計(jì)算各個(gè)特征的Fisher值并對(duì)其進(jìn)行排序，并查看單個(gè)特征Fisher分值對(duì)分類器的影響，計(jì)算了特征的漏報(bào)率，如圖2所示。

圖2 Fisher分的漏報(bào)率情況

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

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

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

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

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

本文通過(guò)選取不同的δ值進(jìn)行多次實(shí)驗(yàn)對(duì)比，從而選擇出相對(duì)較優(yōu)的δ值。

表2 FCBF算法δ值得選擇

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

3.4 實(shí)驗(yàn)結(jié)果與分析

以下為四種評(píng)價(jià)

通過(guò)以下四種指標(biāo)對(duì)四種算法進(jìn)行比較，結(jié)果如表3所示。

表3 四種算法的比較

圖4 四種算法的特征數(shù)、準(zhǔn)確率和預(yù)測(cè)時(shí)間的對(duì)比

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

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

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

圖5 四種算法的誤報(bào)率和漏報(bào)率的對(duì)比

4 總結(jié)

大量的冗余和噪音數(shù)據(jù)混合于網(wǎng)絡(luò)入侵的數(shù)據(jù)中，影響了系統(tǒng)的檢測(cè)效率和檢測(cè)速率。因此本文提出了Fisher-FCBF特征選擇方法，去除了數(shù)據(jù)集中的不相關(guān)與冗余數(shù)據(jù)，在保證準(zhǔn)確率的情況下，不僅降低了數(shù)據(jù)的維度、計(jì)算復(fù)雜與時(shí)間復(fù)雜，同時(shí)減少了誤報(bào)率和預(yù)測(cè)時(shí)間。因次改進(jìn)的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]張潤(rùn)蓮,張昭,彭小金,等.基于Fisher分和支持向量機(jī)的特征選擇算法[J].計(jì)算機(jī)工程與設(shè)計(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]郭春.基于數(shù)據(jù)挖掘的網(wǎng)絡(luò)入侵檢測(cè)關(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-），女，湖北黃岡人，碩士研究生，研究方向?yàn)榫W(wǎng)絡(luò)安全、特征選擇

2017-03-16

2017-05-10

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

1007-1423（2017）15-0007-06

10.3969/j.issn.1007-1423.2017.15.002

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

Intrusion Detection;Feature Selection;Fisher Score;FCBF