一種基于支持向量的二進制粒子群網絡故障特征選擇算法

夏愛民 溫祥西 張宏志

(1.后勤學院研究生管理大隊北京 100036；2.空軍工程大學空管領航學院陜西西安 710077；3.61139部隊北京 100091)

一種基于支持向量的二進制粒子群網絡故障特征選擇算法

夏愛民1溫祥西2張宏志3

(1.后勤學院研究生管理大隊北京 100036；2.空軍工程大學空管領航學院陜西西安 710077；3.61139部隊北京 100091)

網絡故障診斷中大量無關或冗余的特征會降低診斷的精度，需要對初始特征進行選擇。Wrapper模式特征選擇方法分類算法計算量大，為了降低計算量，本文提出了基于支持向量的二進制粒子群(SVB-BPSO)的故障特征選擇方法。該算法以SVM為分類器，首先通過對所有樣本的SVM訓練選出SV集，在封裝的分類訓練中僅使用SV集，然后采用異類支持向量之間的平均距離作為SVM的參數進行訓練，最后根據分類結果，利用BPSO在特征空間中進行全局搜索選出最優特征集。在DARPA數據集上的實驗表明本文提出的方法能夠降低封裝模式特征選擇的計算量且獲得了較高的分類精度以及較明顯的降維效果。

網絡故障 特征選擇 二進制粒子群 支持向量

1 引言

網絡故障的診斷本質上是一個模式識別問題，現有的網絡故障診斷方法往往直接將收集的網絡故障數據送入分類器進行訓練和識別。但是原始特征中往往含有冗余特征甚至噪聲特征，這些冗余特征不僅會增加訓練的復雜度，還可能降低分類精度。在最終的診斷應用中，還會影響診斷速度。可見從采集的初始故障集中選出最能代表故障特性的穩定特征子集對診斷具有十分重要的意義。

近年來，特征選擇問題得到了廣泛的研究，根據是否依賴機器學習算法，特征選擇算法可以分為兩大類：一類為Wrapper型算法，另一類為Filter型算法[1-3]。Filter型特征選擇算法獨立于機器學習算法，計算代價小，效率高但效果一般，典型的算法包括采用類間距離作為親和度函數的AICSA算法[4]；而Wrapper型特征選擇算法則需要依賴某種或多種機器學習算法，計算代價大，效率低但選擇效果好，例如文獻[5-6]提出的BPSO-SVM特征選擇算法。本文選擇Wrapper型算法，Wrapper首先要考慮的是采用哪種機器學習方法進行分類。支持向量機（SVM）建立在結構風險最小化原則基礎之上，具有很強的學習能力和泛化性能，本文選擇SVM作為Wrapper的機器學習算法。但是，前面已經提到Wrapper最大的缺點是計算代價特別高：BPSO-SVM需要進行大量的SVM訓練，阻礙了這些方法的實用性。因此，如何降低Wrapper型特征選擇的計算代價成為亟待解決的問題。而這些計算主要是由SVM訓練引起，需要從SVM訓練過程中去尋求解決方法。

本文分析了典型的基于SVM的Wrapper型特征選擇算法，從提高訓練參數的優化速度以及減少訓練規模這兩個方面降低整個選擇算法的計算代價。并結合二進制粒子群（BPSO）算法尋找最優的特征組合，提出一種新穎的基于支持向量的二進制粒子群（SVB-BPSO）特征選擇算法。SVB-BPSO僅使用支持向量集作為BPSO尋優時SVM的訓練集，且在參數尋優時通過固定RBF核帶寬僅尋找最優的懲罰因子的方式快速確定最終的最優分類精度，降低了整個選擇過程的計算代價。

2 相關研究工作分析

本節分析現有的典型特征選擇算法的計算代價，從中找出減少計算量的途徑和方法。首先分析BPSO-SVM，它是一種典型的Wrapper特征選擇模型。特征選擇實際上是一個組合優化問題，可以采用一些啟發式的搜索算法求解，關鍵是如何設置優化目標。在該算法中，優化的目標函數綜合考慮分類準確性（accuracy）和特征維數（feature_dim）：

其中，SVM的accuracy是通過交叉驗證的方式得到的。計算accuracy過程中，如文獻[5]所提的采用5折交叉驗證，則對于每個選取的參數均需要進行5次SVM訓練才能確定最終的accuracy；考慮交叉驗證獲得最優的參數過程，無論采用網格搜索還是啟發式算法都需進行多次SVM訓練。若不考慮參數的尋優，如文獻[6]中，采用LIBSVM的缺省設置，則得到的accuracy無法保證是最佳的，也就影響了目標函數的準確性。因此，如果能夠快速找到最優的SVM訓練參數將能降低算法的計算量。

另一個方面，SVM的訓練過程是一個求解二次規劃的過程，它的計算代價與訓練樣本的個數相關。在不降低分類準確度的情況下減少參與訓練的樣本個數也能夠降低算法的計算量。文獻[7]提出一種基于SVM的遞歸特征約簡算法（SVM-recursive feature elimination，SVM-RFE），通過定義的評價函數來評估每一個特征維對分類的敏感度（貢獻度），最終為每個特征按照敏感度進行排序，最終通過排序表定義若干個嵌套的特征子集訓練并評估這些子集的優劣，選出最優的特征。它的評價函數為：

3 SVB-BPSO算法描述

通過第二部分的分析，本文提出的SVB-BPSO特征選擇算法框圖如圖1所示。首先對訓練樣本進行SVM訓練（包括通過5折交叉進行參數尋優），獲得最終的SV集；對選擇的SV集通過BPSO算法進行尋優找到最終的最優特征集；最后將測試樣本代入最優特征集中進行測試得到最終的分類結果。圖中，New SV集代表的是當前粒子編碼對應的SV集。

圖1 SVB-BPSO特征選擇算法框圖

下面就框圖中的參數尋優以及BPSO特征選擇進行詳細介紹。

3.1 SVM參數快速確定

SVM訓練需要確定的參數包括核參數和懲罰因子，這些參數的選取對最終的分類結果會產生較大的影響進而影響特征選擇結果[9-10]。在文獻[6]中并未考慮SVM訓練參數的尋優問題，雖然SVM具有較大的最優區域，但是僅通過簡單設定往往不是最優的參數。SVM的訓練參數的尋優問題是一直是SVM學習中的一個熱點問題，效果比較好的包括交叉驗證和網格搜索以及一些智能搜索算法相結合的方法，但是這些方法需要大量的SVM訓練。快速找到一個較優的參數能夠較大的降低算法的計算量。常用的核函數包括線性核函數、多項式核函數（Polynomial Function）、徑向基核函數（Radial Basic Funtion，RBF）以及感知核函數（Sigmoid Function）。文獻[11]評估結果顯示，徑向基核函數（Radial Basic Function，RBF）的無窮維映射特性使之具有很強的學習能力且只需優化核帶寬一個參數，故本文選擇RBF作為SVM的核函數。下面對RBF核函數進行分析，首先給出RBF核函數的數學表達式：

圖2顯示了不同核寬度值對RBF核函數的影響。

圖2 不同參數的徑向基核函數

3.2 BPSO算法

粒子群算法是Kennedy和Eberhart模仿鳥類群體行為的智能優化算法，可解決連續函數的優化問題[12]。在算法中，群體中的每個粒子都是一個潛在的解，通過學習歷史中自身的最優位置Pb和群體最優位置Pg來更新位置和速度，并根據粒子的位置計算適應度函數來判斷解的優劣，不斷迭代找到最優解。

其中，t為迭代次數，c1和c2為學習因子，r1和r2為[0,1]之間的隨機數。

為解決粒子群在離散問題中的應用，Kennedy和Eberhart又在標準粒子群的基礎之上提出了二進制粒子群優化算法[10]。其原理和速度的更新方式不變，只是將粒子位置的每一維分量限制為0或1，并根據速度的sigmoid函數變換來控制粒子的位置更新：

本文提出的SV-BPSO算法采用wrapper特征選擇模型，利用BPSO的自動尋優能力在特征空間中進行全局搜索，得到不同特征組合。根據SVM分類結果判斷這些特征組合的分類性能，并不斷更新選取的特征集，直至搜索到取得最佳分類結果的特征組合。與神經網絡、遺傳算法等優化算法相比，PSO具有所需確定的參數較少，收斂速度更快等優點；與順序選擇算法等常用特征選擇方法相比，PSO不易陷入局部極值，能得到全局最優解。

3.3 基于SVB-BPSO的特征選擇

如果將整個特征空間看作解空間，不同特征組合看作解空間中不同位置處的粒子，粒子中各位置分量取值對應特征組合中各特征分量的狀態。在BPSO尋優中，首先需要根據問題對候選解進行編碼：把每一個特征定義為粒子的二進制變量，粒子空間維數D由原始特征集維數決定。如果第i位為1，那么第i個特征就被選中，否則這個特征就被丟棄。

BPSO算法中，某個粒子的位置矢量決定了某種特征子集的組合方式，而整個群體最優點Pg確定了系統的最優特征組合，適應度函數Fit指導粒子群搜索方向。特性選擇的目的是使用盡可能少的特征得到相同或更優的分類性能，因此，適應度函數需要綜合考慮分類準確性(accuracy)和特征維數(feature_dim)。式(1)給出的適應度函數將這兩部分視作同等重要，但是當accuracy較小時（如0.6），若feature_dim為1，則F=0.3+0.5=0.8，此時的F高于當accuracy達到1而feature_dim為2（F=0.5+0.25=0.75），我們顯然不能認為第一種情況好于第二種情況。其它文獻給出的目標函數同樣沒有很好的解決這兩部分的權值關系。若原始樣本集訓練獲得的分類精度（accuracy_1），在以下假設的前提下：

假設1：經過特征選擇后獲得的最終accuracy同accuracy_1相差不大。

從文獻[5-8]中對大量數據集的實驗可以看出經過特征選擇得到的最終accuracy一般略高于或者略低于accuracy_1，這說明假設是可以成立的。另外，考慮在目標函數中，我們更注重最終的accuracy，且認為當feature_dim對目標函數的影響較accuracy低一個數量級時由accuracy主導目標函數值。我們給出的最終的目標函數為：

結合3.2，給出BPSO進行特征選擇的步驟：輸入：初始樣本集為類別數，lsv為支持向量個數），種群規模np，最大迭代次數iter，適應度函數Fit，閾值Th。

步驟1：初始化粒子位置和速度，設定粒子規模np，最小和最大飛行速度vmin和vmax，最大迭代次數iter，適應度函數閾值Th，計算每個粒子適應度函數Fit，初始化pb、pg以及迭代次數n=1。

根據式(8)和(9)更新每個粒子的速度vid和位置xid

返回2

else停止迭代，輸出群體最佳位置Pg和Fit(Pg)。

步驟5：選擇當前種群中最優個體Pg中為1的基因位對應S中的樣本特征，構成約簡樣本集

4 實驗與分析

4.1 數據處理

目前網絡中各種攻擊事件和病毒越來越多，導致網絡中產生大量的"軟故障"，如網絡服務異常、操作系統崩潰、鏈路擁塞甚至中斷等。本文選擇了DARPA評估數據集[13]，以攻擊下的網絡狀態模擬網絡故障。該數據集包含四類網絡攻擊，分別是DoS、Probe、R2L和U2R，每條記錄均有41個特征值。為了確保數據的普適性，從原始數據集中以等間隔采集法選取訓練集樣本和測試樣本，具體情況如表1所示：

表1 實驗樣本集結構

此外樣本特征屬性值之間的不同度量，使得樣本向量在計算距離時取值范圍偏大的屬性占據了主導地位，大大弱化了取值范圍偏小的特征的貢獻，無法正確反映樣本間的真實差異。設特征集合中的第i個特征的最大最小值分別為，則通過式(12)的歸一化處理將訓練和測試集中的樣本特征值映射到[0,1]區間：

4.2 實驗結果與分析

對以上經過預處理的樣本數據集，分別使用文獻[4]提出的AICSA方法、文獻[5]提出的BPSO-SVM方法和文獻[6]的BPSO-SVM方法，文獻[7]的SVM-RFE、文獻[8]的SV-RFE以及本文的SVB-BPSO方法進行特征選擇，并對測試樣本進行分類，分別比較選擇的時間、得到的特征維數、測試的診斷精度。其中，BPSO的種群規模取20，最大迭代次數取100，SVM的訓練工具采用LIBSVM[14]（注意：LIBSVM中的參數核函數的表示形式為：，這里即為訓練中的參數g，其表達式與式(3)不同，因此設置參數時）。得到是實驗結果如表2所示：

表2 實驗結果

其中，時間比是其它方法同本文方法所用時間的比值。從實驗結果可以發現基于Filter思想的AICSA特征選擇方法能夠獲得最低的選擇時間，遠遠快于其它算法。這是因為在Filter的選擇中僅分析數據之間的關系，不考慮分類，但是它獲得的分類精度也低于其它方法。經過文獻[5]提出的BPSO-SVM方法選擇出來的特征得到了最高的分類精度，但是它所花的時間遠遠高于其它方法，這主要是因為它在訓練中采用5折交叉驗證方式確定參數并訓練，這中間需要進行大量的SVM訓練，因此它需要較長的時間。另外由于它考慮了訓練參數且訓練使用的是所有數據，它最終得到的選擇結果也是最好的。文獻[6]中并未考慮參數設置問題，本文由于在前期進行了歸一化處理，在使用缺省設置參數時能夠獲得較好的訓練效果。在其它一些數據集實驗時還是表現出了訓練參數對最終提取結果還是有較大影響的。在訓練時間上，即使不需要參數設置，但是每次計算目標函數過程中的訓練集仍為所有數據，因此它的尋優時間高于本文方法。SVM-RFE通過SVM得到Lagrange乘數，通過式(2)判斷每一維的分類敏感性，式(2)的計算不涉及SVM訓練，因此它的尋優時間較短。SV-RFE SVM方法減少了參與尋優的樣本，但是每次均要進行SVM訓練計算判別函數，時間上較SVM-RFE略長，但是這兩種方法得到的最終分類精度低于本文方法以及文獻[5]中的BPSO-SVM，且選擇的特征維數較多。實驗結果很明顯的體現出本文方法的優勢：用了一個較短的尋優時間獲得了相對較高的分類精度以及較明顯的維數降低效果。

5 結束語

特征選擇在網絡故障診斷領域能夠提高診斷的精度和速度，作為目前特征提取效果較好的Wrapper模式選擇算法由于計算目標函數時需要進行分類訓練，帶來大量的計算。為了降低Wrapper模式中的計算量，本文從SVM分類器的訓練出發，通過對SVM訓練參數確定以及參與訓練樣本個數兩個方面考慮降低SVM的訓練代價。并對分類結果和選擇出的樣本維數的綜合考慮，利用BPSO在特征空間中進行全局搜索選出最優特征集。最后，在DARPA數據集上的特征提取實驗表明本文提出的方法能夠折中的獲得較優的分類精度較好的降維效果以及較低的運算代價。本文提出的方法能夠為網絡故障診斷中的特征選擇問題提供一種新的較優的途徑。

[1]Zhu Z,Ong Y,Dash M.Wrapper-filter feature selection algorithm using a memetic framework[J].IEEE Transactions on Systems,Man,and Cybernetics-Part B:Cybernetics, 2007,37(1):70-76.

[2]Zhao Mingyuan,Fu Chong,Ji Luping,Tang Ke,Zhou Mingtian.Feature selection and parameter optimization for support vector machines:A new approach based on genetic algorithm with feature chromosomes[J].Expert Systems with Applications 2011,38(5):5197-5204.

[3]Kim S.,Oommen B.On using prototype reduction scheme to optimize kernel-based Fisher discriminant analysis.IEEETransactions on Systems,Man,and Cybernetics-Part B: Cybernetics,2008,38(2):564-570.

[4]Zhang Li,Meng Xiangru,Wu Weijia,Zhou Hua.Network Fault Feature Selection Based on Adaptive Immune Clonal Selection Algorithm[A].2009 International Joint Conference on Computation Sciences and Optimization[C].Hainan, China:2009,969-973.

[5]潘泓,李曉兵,金立左,夏良正.一種基于二值粒子群優化和支持向量機的目標檢測算法[J].電子與信息學報,2011,33 (1):117-121.

[6]喬立巖,彭喜元,彭宇.基于微粒群算法和支持向量機的特征子集選擇方法[J].電子學報,2006,34(3):496-498.

[7]Guyon,I.,Weston,J.,Barnhill,S.,Vapnik,V..Gene selection for cancer classification using support vector machines[J].Machine Learning,2012,46(1/3):389-422.

[8]Eunseog Youn,Lars Koenig,Myong K.Jeong,Seung H. Baek.Support vector-based feature selection using Fisher's linear discriminant and Support Vector Machine[J].Expert Systems with Applications 2010,37(9):6148-6156.

[9]Vapnik.An Overview of Statistical Learning Theory[J].IEEE Transaction on Neural Network,2009,10(5):998-999.

[10]Chapelle O,Vapnik V,Bousquet O,et al.Choosing multiple parameters for support vector machine[J].Machine Learning,2012,46:131-159.

[11]王泳，胡包鋼.應用統計方法綜合評估核函數分類能力的研究[J].計算機學報,2008,31(6):942-952.

[12]Kennedy J,Eberhart R C,Shi Y H.Swarm intelligence[M].北京:人民郵電出版社,2009.

[13]University of California Irvine.UCI KDD Archive [DB/OL].http://kdd.ics.uci.edu/

[14]Chih-Chung Chang,Chih-Jen Lin.LIBSVM:A library for support vector machines[EB/OL].http://www.csie. ntu.edu.tw/～cjlin/libsvm.

A Support Vector Based Binary Particle Swarm Optimization Feature Selection Algorithm

XIA Ai-min1，WEN Xiang-xi2，ZhANG Hong-zhi3
（1.Graduate Management Unit of The Logistics College,PLA,Beijing 100036,China; 2.Institute of Air Traffic Control and Navigation,Air Force Engineering University,Xi'an Shanxi 710077,China；3.61139 PLA Troops,Beijing 100091,China）

In network fault diagnosis,many irrelevant and redundant features lessen the performance of diagnosis,feature selection is introduced on this condition.The wrapper feature selection algorithms get large calculation cost,a support vector based binary particle swarm optimization(SVB-BPSO)feature selection algorithm was proposed in this paper.The support vectors(SVs)are selected from the whole datasets by SVM training,the following wrapper classification focus only on these SVs.The training parameter is decided by average distance between different class SVs.Based on the SVM classifiers,the BPSO is used for searching the whole feature space to find the best feature subset.Experiments on DARPA datasets show the proposed method can reduce the wrapper feature selection's calculation cost while gets good performance on diagnosis accuracy and dimensional decrease.

network fault;feature selection;BPSO;support vector

TP391.4

A

1008-1739（2014）23-68-6

定稿日期：2014-11-12