文獻(xiàn)標(biāo)識(shí)碼: A
文章編號(hào): 0258-7998(2010)10-0132-04
1980年4月Anderson第一次闡述了入侵檢測(cè)的概念,,指出可以使用審計(jì)網(wǎng)絡(luò)數(shù)據(jù)的方式判斷非法入侵的發(fā)生[1]。在網(wǎng)絡(luò)數(shù)據(jù)的審計(jì)中,,沒(méi)有一種確定的函數(shù)關(guān)系可以鑒別非法入侵,。因此引入機(jī)器學(xué)習(xí)的方法,作為入侵行為和網(wǎng)絡(luò)數(shù)據(jù)特征之間模型進(jìn)行函數(shù)逼近。
機(jī)器學(xué)習(xí)的方法在入侵檢測(cè)領(lǐng)域應(yīng)用廣泛,,并有較好的檢測(cè)效果,。傳統(tǒng)的機(jī)器學(xué)習(xí)算法需要大量的網(wǎng)絡(luò)數(shù)據(jù),而正常的網(wǎng)絡(luò)數(shù)據(jù)特征有著小樣本,、高維數(shù)、多變性的特點(diǎn),。支持向量機(jī)(SVM)對(duì)小樣本,、高維數(shù)的數(shù)據(jù)有著較好的訓(xùn)練能力,已經(jīng)被應(yīng)用于入侵檢測(cè)[2],。最小二乘向量機(jī)(LSSVM)是SVM中的一種,,相比SVM有著更快的運(yùn)行速度。LSSVM懲罰因子C和核函數(shù)參數(shù)?滓的選擇使用網(wǎng)格搜索,,耗時(shí)且分類精度不高,。而粒子群優(yōu)化(PSO)算法的尋優(yōu)求解能力較為突出,可以利用PSO算法對(duì)LSSVM的相應(yīng)參數(shù)進(jìn)行選擇[3],。
PSO算法中一個(gè)重要的參數(shù)就是慣性權(quán)重w,。w較大時(shí),全局搜索能力較強(qiáng);w較小時(shí),局部搜索能力較強(qiáng)?;綪SO算法采用固定w,,搜索的性能和效率不高。參考文獻(xiàn)[4]提出了讓w隨著進(jìn)化的進(jìn)行而線性減少的策略,,相應(yīng)的PSO算法稱為線性權(quán)重下降PSO(LWDPSO)算法,。該P(yáng)SO算法在提高搜索效率的同時(shí)有著早熟收斂、陷于局部最優(yōu)的缺點(diǎn),。本文提出一種改進(jìn)的PSO算法,,即并行PSO算法。該算法將粒子群分成兩組[5]進(jìn)行協(xié)同搜索,,兩組粒子具有不同的w,,其中w較大的粒子組側(cè)重全局搜索;w較小的粒子組側(cè)重在w大的粒子組找到全局最優(yōu)位置的附近區(qū)域進(jìn)行精細(xì)搜索,。每組都有一部分固定的粒子,,其余的粒子根據(jù)進(jìn)化階段動(dòng)態(tài)分配給兩組,通過(guò)動(dòng)態(tài)分配粒子保證算法初期以全局搜索為主,,后期以局部搜索為主,。通過(guò)適應(yīng)度函數(shù)的仿真實(shí)驗(yàn),證明了并行PSO算法的尋優(yōu)性能更優(yōu),。
選用RBF函數(shù)作為核函數(shù):
2 PSO算法
PSO算法源于對(duì)鳥類覓食行為的模擬,,通過(guò)鳥群之間的集體協(xié)作使群體達(dá)到最優(yōu)。標(biāo)準(zhǔn)PSO算法初始化產(chǎn)生一群粒子,每個(gè)粒子以一定的速度在n維空間里飛行,飛行速度由個(gè)體的飛行經(jīng)歷和群體的飛行經(jīng)歷動(dòng)態(tài)調(diào)整,。X1=(Xi1,Xi2,…,Xin)是粒子i當(dāng)前的位置,,V1=(Vi1,Vi2,…,Vin)是粒子當(dāng)前的速度,P1=(Pi1,Pi2,…,Pin)是粒子i所經(jīng)歷過(guò)的最好位置,在這個(gè)位置粒子i擁有最佳適應(yīng)度,。設(shè)f(x)為最小化的目標(biāo)函數(shù),,則粒子i的最好位置由下
3 改進(jìn)PSO算法
粒子群進(jìn)化前期應(yīng)該以全局搜索為主,搜索整個(gè)空間,,但不能放棄局部搜索,,因?yàn)槿炙阉鞯牧W铀俣容^快,發(fā)現(xiàn)的位置的范圍雖然廣泛,,但精度不高,,容易錯(cuò)過(guò)全局最優(yōu)位置;進(jìn)化后期應(yīng)該以局部搜索為主,,但不能放棄全局搜索,,因?yàn)榫植克阉麟m然精細(xì),但搜索的范圍較小,,無(wú)法搜索到較遠(yuǎn)的更優(yōu)位置,。
本文提出一種改進(jìn)PSO算法,即并行PSO算法,。設(shè)粒子的數(shù)量為S,,總進(jìn)化代數(shù)為G,當(dāng)前進(jìn)化代數(shù)為i,。該算法將粒子群分成兩組,,運(yùn)行PSO算法時(shí)慣性權(quán)重w分別設(shè)置為0.95和0.4,其中w為0.95的粒子組側(cè)重全局搜索,,w為0.4的粒子組側(cè)重在w為0.95的粒子組找到全局最優(yōu)位置的區(qū)域進(jìn)行精細(xì)搜索,。每組粒子都有一定基本的粒子數(shù)量,均為S/4,。剩余S/2粒子根據(jù)進(jìn)化階段動(dòng)態(tài)分配給兩組,,分配給w為0.95的粒子組為S×(G-i)/2G(朝負(fù)無(wú)窮方向取整);分配給w為0.4的粒子組為S×i)/2G(朝正無(wú)窮方向取整)。
進(jìn)化初始,,w為0.95的粒子組粒子數(shù)目最多,,達(dá)到3S/4,進(jìn)行全局搜索,,余下的S/4 w為0.4的粒子組對(duì)全局搜索到的當(dāng)前最優(yōu)位置的小范圍區(qū)域進(jìn)行局部搜索,,期望在該區(qū)域中搜索到更優(yōu)位置;進(jìn)化后期,,動(dòng)態(tài)粒子逐漸從w為0.95的粒子組調(diào)整到w為0.4的粒子組,,空間已被w為0.95的粒子組多次搜索,,w為0.4的粒子組針對(duì)當(dāng)前最優(yōu)位置的相關(guān)小范圍區(qū)域進(jìn)行局部搜索,w為0.95的粒子組在對(duì)空間中當(dāng)前全局最優(yōu)位置的相關(guān)大范圍區(qū)域進(jìn)行搜索,,不放棄任何尋找到全局最優(yōu)位置的機(jī)會(huì),。
4 仿真實(shí)驗(yàn)及分析
使用四種典型的測(cè)試函數(shù)[6]: Sphere函數(shù)、 Rastrigrin函數(shù),、Rosenbrock函數(shù)和Griewank函數(shù)作為適應(yīng)度函數(shù)進(jìn)行測(cè)試,。各算法最大進(jìn)化代數(shù)為500代,種群規(guī)模為80,優(yōu)化方程的維數(shù)為30,c1,、c2等于2,,搜索的空間為[-100,100]。為避免實(shí)驗(yàn)中偶然性現(xiàn)象,,現(xiàn)將PSO三種算法針對(duì)這四種函數(shù)同時(shí)進(jìn)行了10次實(shí)驗(yàn)。圖1~圖4分別是四種測(cè)試函數(shù)對(duì)三種算法的適應(yīng)度變化與進(jìn)化代數(shù)比較曲線圖,。表1是三種算法在10次實(shí)驗(yàn)次數(shù)中取得的適應(yīng)度的平均值,、最大值和最小值。
基本PSO算法粒子一直進(jìn)行全局搜索,,沒(méi)有進(jìn)行局部精細(xì)搜索,,因此無(wú)法找到較優(yōu)位置,適應(yīng)度值一直較大,尋優(yōu)效果較差,;LWDPSO算法在前期有較好的搜索效果,,但是在中后期收斂之后對(duì)最優(yōu)位置的搜索沒(méi)有任何突破,早熟的跡象非常明顯,;并行PSO算法有著較好的全局搜索能力以及局部收斂能力,,對(duì)最優(yōu)位置的搜索較為穩(wěn)定,避免了局部最優(yōu),,沒(méi)有早熟的缺點(diǎn),,同時(shí)搜索到了最優(yōu)位置。同時(shí)從表1可以得出:基本PSO算法的尋優(yōu)較差,,得到的適應(yīng)度遠(yuǎn)遠(yuǎn)高于其他兩種算法,;LWDPSO算法的尋優(yōu)結(jié)果優(yōu)于基本PSO算法,次于并行PSO算法,;并行PSO算法的尋優(yōu)結(jié)果優(yōu)于基本PSO算法和LWDPSO算法,,實(shí)驗(yàn)得到的適應(yīng)度平均值、最大值和最小值在三種算法中都是最低的,。
5 基于并行PSO算法的LSSVM建模方法
將LSSVM的懲罰因子C和δ核參數(shù)映射成粒子,,根據(jù)并行PSO算法進(jìn)行優(yōu)化選擇,最終使得建立的模型估計(jì)值與期望值的逼近程度達(dá)到預(yù)期目標(biāo),。其算法流程如下:
(1) 并行PSO算法參數(shù)初始化,將粒子群分成兩組,,慣性權(quán)重w分別設(shè)置為0.95和0.4,。
(2) 根據(jù)設(shè)定的適應(yīng)度函數(shù),計(jì)算每個(gè)粒子的位置,。
(3) 將粒子的位置與自身最優(yōu)位置進(jìn)行比較,如果當(dāng)前位置相應(yīng)適應(yīng)度小,,則更新自身最優(yōu)位置。
(4)比較每個(gè)粒子的自身最優(yōu)位置適應(yīng)度求出全局最優(yōu)位置,。
(5) 根據(jù)當(dāng)前進(jìn)化代數(shù)動(dòng)態(tài)調(diào)整兩組粒子的數(shù)目,,進(jìn)行下一代進(jìn)化。
(6) 所有進(jìn)化次數(shù)結(jié)束,,將此時(shí)全局最優(yōu)粒子分別映射為懲罰因子C和核參數(shù)?滓,并以此為優(yōu)化結(jié)果,,建立模型。
6 實(shí)驗(yàn)過(guò)程及結(jié)果
6.1實(shí)驗(yàn)數(shù)據(jù)預(yù)處理
實(shí)驗(yàn)中采用的數(shù)據(jù)取自1999年DARPA為KDD競(jìng)賽提供的一個(gè)異常檢測(cè)的標(biāo)準(zhǔn)數(shù)據(jù)集,,它是由美國(guó)麻省理工學(xué)院的Liconln實(shí)驗(yàn)室通過(guò)模擬一個(gè)典型的美國(guó)空軍網(wǎng)絡(luò)而獲得原始的TCP/IP網(wǎng)絡(luò)通信數(shù)據(jù),對(duì)于每一個(gè)TCP/IP連接,,提取了41個(gè)屬性。數(shù)據(jù)中有四種類型的攻擊:未經(jīng)授權(quán)的遠(yuǎn)程訪問(wèn)(R2L),、拒絕服務(wù)攻擊(DoS),、對(duì)本地超級(jí)用戶的非法訪問(wèn)(U2R)和掃描與探測(cè)(Probing)。標(biāo)識(shí)為正常的數(shù)據(jù)占19.6%,攻擊數(shù)據(jù)占80.4%,。
實(shí)驗(yàn)中的訓(xùn)練數(shù)據(jù)取自于原始數(shù)據(jù)集中kddcup數(shù)據(jù),,測(cè)試數(shù)據(jù)取自于corrected數(shù)據(jù),訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)采用等間隔的選取方式。測(cè)試數(shù)據(jù)共選取54 220條,,其中正常數(shù)據(jù)12 140條,、攻擊數(shù)據(jù)42 080條,訓(xùn)練數(shù)據(jù)共33 520條,按類型和間隔平均分成10組,分別使用10組訓(xùn)練數(shù)據(jù)建立模型對(duì)測(cè)試數(shù)據(jù)進(jìn)行測(cè)試,,實(shí)驗(yàn)結(jié)果取10次實(shí)驗(yàn)的平均值,。
實(shí)驗(yàn)中,需要對(duì)數(shù)據(jù)進(jìn)行處理,實(shí)驗(yàn)數(shù)據(jù)的protocol-type,、sevice和flag屬性使用字符串表示,對(duì)其進(jìn)行數(shù)字替換處理,,對(duì)屬性中不同的類型使用不同的數(shù)字表示。另外,,必須要對(duì)所有屬性進(jìn)行歸一化處理,,公式為:
其中new為歸一化后的數(shù)據(jù),old為歸一化前數(shù)據(jù),,max為屬性的最大值,,min為屬性的最小值。
6.2 實(shí)驗(yàn)結(jié)果
網(wǎng)格搜索,、LWDPSO算法和并行PSO算法分別對(duì)LSSVM的參數(shù)尋優(yōu),,并建立各自的模型,對(duì)測(cè)試數(shù)據(jù)集進(jìn)行了檢測(cè),。實(shí)驗(yàn)結(jié)果如表2所示,。
從表2可以得出,,由于訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)采自不同的數(shù)據(jù)集,網(wǎng)格搜索和LWDPSO算法的檢測(cè)率較低,,誤報(bào)率和漏報(bào)率較高,;采用并行PSO算法對(duì)LSSVM進(jìn)行參數(shù)尋優(yōu)所建立的入侵檢測(cè)模型檢測(cè)率、誤報(bào)率和漏報(bào)率都優(yōu)于其他兩種算法參數(shù)尋優(yōu)后所建立的模型,。
本文給出并分析了基本PSO算法和LWDPSO算法的定義及特點(diǎn),。提出并行PSO算法,將粒子群分成兩組,分別設(shè)置不同的慣性權(quán)重,,慣性權(quán)重大的粒子組側(cè)重全局搜索,,慣性權(quán)重小的粒子組側(cè)重在慣性權(quán)重大的粒子組找到全局最優(yōu)位置的附近區(qū)域進(jìn)行精細(xì)搜索。根據(jù)進(jìn)化代數(shù)動(dòng)態(tài)調(diào)整兩組中進(jìn)化的粒子數(shù),,并給出了每組粒子的數(shù)量調(diào)整公式,。通過(guò)四個(gè)適應(yīng)度函數(shù)仿真實(shí)驗(yàn),證明了并行PSO算法的尋優(yōu)性能優(yōu)于基本PSO算法與LWDPSO算法,。通過(guò)入侵檢測(cè)實(shí)驗(yàn)測(cè)試,,并行PSO算法對(duì)LSSVM參數(shù)尋優(yōu)后建立的模型可以有效提高入侵檢測(cè)的性能指標(biāo)。
參考文獻(xiàn)
[1] ANDERSON J P. Computer sercurity threat monitoring and surveillance[R]. James PAnderson Co, Fort Washington, Pennsylvania, Aprial 1980.
[2] MUKKAMALA S, JANOSKIG I, SUNGA H. Intrusion detection using neural networks and support vector machines[C]. Proc of IEEE International Joint Conference on Neural Networks. Washington DC:IEEE Computer Society, 2002: 1702-1707.
[3] 陳光英,張千里,李星. 特征選擇和SVM訓(xùn)練模型的聯(lián)合優(yōu)化[J]. 清華大學(xué)學(xué)報(bào)(自然科學(xué)版),2004,44(1);9-12.
[4] SHI Y, EBERHART R. A modified particle swarm optimizer[C]. IEEE World Congress on Computational Intelligence. Piscataway:IEEE Press,1998:69-73.
[5] 龍文,,梁昔明,肖金紅,,等.一種動(dòng)態(tài)分級(jí)的混合粒子群優(yōu)化算法[J].控制與決策.2009,24(6):1406-1411.
[6] CLERC M, KENNEDY J. The particle swarm: explosion, stability, and convergence in multi-dimension complex space[J]. IEEE Transactions on Evolutionary Computation, 2002,16(1):58-73.