杜紅樂， 張 燕

(商洛學(xué)院 數(shù)學(xué)與計算機(jī)應(yīng)用學(xué)院， 商洛 726000)

?

基于增量支持向量機(jī)的入侵檢測算法

杜紅樂， 張 燕

(商洛學(xué)院 數(shù)學(xué)與計算機(jī)應(yīng)用學(xué)院， 商洛 726000)

針對網(wǎng)絡(luò)入侵檢測無法識別新的入侵行為，利用增量學(xué)習(xí)不斷完善分類器，使得分類器可以識別新的入侵行為。提出一種基于相似度的增量支持向量機(jī)算法，該算法依據(jù)新增樣本與支持向量之間的相似度來選擇樣本(當(dāng)前分類器缺少該樣本的空間信息)，然后加入訓(xùn)練集中參加下一次迭代訓(xùn)練。實驗結(jié)果表明，該算法能夠提高最終分類器的分類精度和算法的訓(xùn)練速度。

支持向量機(jī)； 入侵檢測； 相似度

0 引言

支持向量機(jī)(support vector machine，簡稱SVM)[1]是在統(tǒng)計學(xué)習(xí)理論基礎(chǔ)上發(fā)展起來的一種新的機(jī)器學(xué)習(xí)方法，它基于結(jié)構(gòu)風(fēng)險最小化原則，在解決小樣本、非線性及高維模式識別問題中表現(xiàn)出許多特有的優(yōu)勢，近年來，SVM在許多領(lǐng)域都取得廣泛的應(yīng)用。

在實際的應(yīng)用中往往無法一次性收集到完備的數(shù)據(jù)集，數(shù)據(jù)集是在使用的過程中逐漸收集的，例如入侵檢測中，入侵行為不斷更新，永遠(yuǎn)無法收集完備的數(shù)據(jù)集，需要分類器在使用的過程中不斷學(xué)習(xí)新的數(shù)據(jù)，逐漸完善分類器，增量學(xué)習(xí)算法應(yīng)運而生。支持向量機(jī)增量學(xué)習(xí)算法主要算法層面[1-5]和數(shù)據(jù)層面[6-15]兩種，算法層面主要是利用當(dāng)前分類器的計算信息和新增樣本信息獲得新的分類器，無需迭代訓(xùn)練;數(shù)據(jù)層面方法多是針每次迭代中原有樣本的篩選及對新增樣本的篩選，目的在于保證算法的速度，同時保證分類器的分類精度。對新增樣本通過一定方法，選擇樣本包含的空間信息是分類器缺少的樣本加入下一次訓(xùn)練，從而把新增樣本中的空間信息逐漸納入到分類器中。文獻(xiàn)[6]充分利用KKT條件，利用最大似然確定邊界向量，然后把確定的邊界向量加入到訓(xùn)練集中，進(jìn)行下一次迭代；文獻(xiàn)[7]利用KKT條件及時淘汰對后續(xù)訓(xùn)練影響不大的樣本，同時保留包含重要信息的樣本，可以有效提高算法的訓(xùn)練速度；文獻(xiàn)[8]依據(jù)相似度選擇樣本，保證所選樣本的質(zhì)量，同時利用誤差驅(qū)動的原則對原有樣本進(jìn)行刪減，可以刪除包含空間信息少的以及噪聲樣本，可以提高算法速度；文獻(xiàn)[9]根據(jù)加入新增樣本后支持向量集的變化，淘汰那些對最終分類無用的樣本，提出基于密度法的支持向量機(jī)增量學(xué)習(xí)淘汰算法；文獻(xiàn)[10]提出球結(jié)構(gòu)多類SVM 增量學(xué)習(xí)算法，該算法將新增樣本集中根據(jù)KKT條件選取部分樣本和原始訓(xùn)練集中的支持向量以及分布在球體一定范圍內(nèi)的樣本合并作為新的訓(xùn)練集，完成分類器的重構(gòu)；文獻(xiàn)[11]利用新增樣本到類中心的距離計算概率密度，依據(jù)概率密度選擇樣本加入下一次迭代，但是該方法每次需要計算到所有樣本的距離，會影響算法的速度?；谝陨戏治?，通過計算每個新增樣本與正類支持向量及負(fù)類支持向量的相似度，然后利用相似度選擇加入下次迭代的樣本，把該算法叫作基于相似度的增量支持向量機(jī)算法，并把該算法應(yīng)用到入侵檢測中，仿真實驗結(jié)果表明算法的有效性。

1 相似度

SVM為解決線性不可分問題，使用核函數(shù)將樣本從輸入空間映射到某一特征空間中，使得樣本在該特征空間中線性可分，設(shè)映射函數(shù)為：φ:Rk|→F，核函數(shù)為K(x,y)=<φ(x),φ(y)>，常采用的核函數(shù)有高斯核、多項式核、RBF核等等，SVM的計算過程是在核空間下進(jìn)行的，因此為了更準(zhǔn)確的描述樣本與支持向量之間的關(guān)系，在核空間下計算樣本與支持向量之間的距離，設(shè)樣本x、y，則兩樣本之間的距離d(x,y)在核空間下表示,為式(1)。

(1)

若采用RBF核函數(shù)，即K(x,y)=exp(-g||x-y||2)，則兩樣本之間的距離為式(2)。

(2)

對于增量樣本的xi，對正支持向量和負(fù)支持向量的相似度用到達(dá)正負(fù)支持向量的平均距離的倒數(shù)表示，計算方法如式(3)。

其中l(wèi)+、l-分別表示正負(fù)支持向量數(shù)量，d(x,y)在核空間下計算，本文實驗中計算相似度的核函數(shù)與支持向量機(jī)采用相同的核函數(shù)，都采用的RBF核函數(shù)。

2 增量支持向量機(jī)算法

2.1 算法原理

增量學(xué)習(xí)為了減少每次迭代的訓(xùn)練時間，需要選擇對分類器有改變的樣本進(jìn)入訓(xùn)練集，即選擇選擇的樣本所包含空間信息是當(dāng)前分類器缺少的，例如依據(jù)KKT條件[9]、依據(jù)概率密度[10]等選擇樣本進(jìn)行迭代。

對增量樣本集中的每個樣本，計算對正負(fù)支持向量的相似度，分別依據(jù)正負(fù)相似度進(jìn)行排序，選擇K個相似度大的樣本，對于正相似度，若樣本的實際類別為正，則樣本不做處理，否則就把該樣本放入T中；對于負(fù)相似度，若樣本實際類別為正，則把該樣本放入T中，重新訓(xùn)練得到新的分類器和支持向量。K值是為了控制算法速度，K值越大，每次迭代中的訓(xùn)練集規(guī)模就越大，但迭代次數(shù)會減少；K值小，則迭代次數(shù)增加，迭代中訓(xùn)練集規(guī)模減小。

2.2 算法步驟

算法：增量支持向量機(jī)算法SISVM

輸入：初始訓(xùn)練集集T，增量樣本集U，選擇樣本數(shù)K

輸出：最終分類器

step1.用SVM對初始訓(xùn)練集T進(jìn)行訓(xùn)練，得到分類器f和支持向量SV+和SV-；

step2.增量樣本選擇：

step2.1 判斷增量樣本集T是否為空，若為空則算法終止；否則，對T中的每個樣本，利用計算與正負(fù)支持向量的相似度；

step2.2 對正負(fù)支持向量相似度進(jìn)行排序，選擇其中K個相似度值大的樣本，若S+(xi)≥S-(xi)，且樣本的實際類別為負(fù)，則把該樣本放入Temp中；若S+(xi)≤S-(xi)，且樣本實際類別為正，則把樣本放入Temp中，同時從U中刪除該樣本；

step2.3 判斷Temp是否為空，若不為空，則合并Temp和T，重新訓(xùn)練得到新的分類器和支持向量集，返回step2；若為空，則直接返回step2；

step3. 得到最終分類器。

該方法與PISVM相比，PISVM需要計算每個增量樣本與當(dāng)前訓(xùn)練集中每個樣本的距離，而本文算法只需計算與支持向量之間的距離，而支持向量數(shù)量要小于訓(xùn)練集，因此可以提高算法速度；PISVM算法每次迭代選擇1～2個樣本，而本文算法通過調(diào)控參數(shù)K控制每次選擇樣本的數(shù)量，引入S+(xi)≥S-(xi)和S+(xi)≤S-(xi)的判斷，確保被選擇樣本包含有分類器缺少的空間信息，提高準(zhǔn)確度。

3 實驗及數(shù)據(jù)分析

本文中所做實驗是在Matlab 7.11.0環(huán)境下，結(jié)合臺灣林智仁老師的LIBSVM[16]，主機(jī)為Intel Core i7 2.3GHz，4G內(nèi)存，操作系統(tǒng)為Win7的PC機(jī)上完成。

3.1 數(shù)據(jù)集

KDDCUP1999[17]數(shù)據(jù)集是關(guān)于入侵檢測的標(biāo)準(zhǔn)數(shù)據(jù)集，包括訓(xùn)練集和測試集，其中訓(xùn)練集有494022條記錄，測試集有311030條記錄，訓(xùn)練集中包含24種攻擊，而測試集有38種攻擊。本文算法是針對二類分類問題，把數(shù)據(jù)集也看作是兩類分類數(shù)據(jù)，把所有攻擊數(shù)據(jù)看作一類。KDDCUP99數(shù)據(jù)集的41個數(shù)據(jù)屬性中，有數(shù)值型，也有字符型，因此首先對數(shù)據(jù)集進(jìn)行數(shù)值化和歸一化，數(shù)值化是對字符類型數(shù)據(jù)用數(shù)字進(jìn)行簡單的替代，歸一化采用LIBSVM中的歸一化工具進(jìn)行處理。為了驗證算法的有效性，從數(shù)據(jù)集中取了2組數(shù)據(jù)集data1和data2，每組實驗數(shù)據(jù)從訓(xùn)練數(shù)據(jù)中去300條記錄作為初始訓(xùn)練集(Train set)，從測試數(shù)據(jù)集中取出1000條記錄作為增量樣本集，數(shù)據(jù)集1中的測試集是數(shù)據(jù)集2的增量樣本集，數(shù)據(jù)集2中的測試集用的是數(shù)據(jù)集1中的增量樣本集，詳細(xì)的數(shù)據(jù)集分布情況如表1所示。

3.2 實驗結(jié)果及分析

對于入侵檢測來說，為了更準(zhǔn)確的描述算法的有效性，不僅要對比算法的整體準(zhǔn)確率，還要綜合考慮對樣本的查準(zhǔn)率和查全率，因此本文主要從準(zhǔn)確率、查準(zhǔn)率、查全率以及算法時間方面進(jìn)行對比，驗證本文算法的有效性，其中算法PISVM來自于文獻(xiàn)[10] 。

表1 實驗數(shù)據(jù)集

從整體、正常行為、攻擊行為、已有攻擊、未知攻擊幾方面的分類準(zhǔn)確率進(jìn)行對比，如表2所示。

表2 準(zhǔn)確率對比

查準(zhǔn)率進(jìn)行對比的結(jié)果，如表3所示。

表3 查準(zhǔn)率對比

表3中，SVM算法結(jié)果是直接對300個樣本進(jìn)行訓(xùn)練，得到分類器對1000個測試樣本進(jìn)行測試的結(jié)果，由于未能學(xué)到新攻擊類型數(shù)據(jù)的空間信息，導(dǎo)致對未知攻擊的分類準(zhǔn)確率較低；PISVM算法是根據(jù)新增樣本到各類中心距離計算概率密度，然后依據(jù)概率密度選擇加入訓(xùn)練集的樣本，用成對標(biāo)注的直推式支持向量機(jī)算法，該算法的前提是兩類樣本數(shù)量相當(dāng)，而實際的測試集中兩類樣本不均衡，因此，分類準(zhǔn)確率仍不理想，但學(xué)習(xí)了測試樣本及未知攻擊類型的空間分布信息，因此分類準(zhǔn)確率有了明顯的提升；TISVM是本文算法的分類結(jié)果，該算法可以盡快獲得無標(biāo)簽樣本中的空間信息，減少錯誤的傳遞和累積，因此對分類準(zhǔn)確率及未知攻擊的分類準(zhǔn)確率都有了明顯的提高，實驗結(jié)果是K=2時候的結(jié)果，如表2、表3所示。

從實驗結(jié)果中可以看到，data1的實驗結(jié)果要比data2的結(jié)果好，無論是準(zhǔn)確率海是查準(zhǔn)率，分析數(shù)據(jù)可以看到，data1中的攻擊數(shù)據(jù)數(shù)量多于data2中，data1和data2都屬于不均衡數(shù)據(jù)，并且data1中未知攻擊數(shù)據(jù)也多于data2中，因此data1所得的實驗結(jié)果優(yōu)于data2的實驗結(jié)果。

4 總結(jié)

入侵檢測要不斷適應(yīng)新的攻擊行為，需要不斷完善分類器，增量學(xué)習(xí)可以很好解決這樣的問題，本文利用新增樣本與支持向量的相似度對新增樣本進(jìn)行刪除，保留包含豐富空間信息的樣本，從而提高算法的速度和精度。然而不均衡數(shù)據(jù)下同樣會導(dǎo)致分類超平面的偏移，會使錯誤累積和傳遞，不均衡數(shù)據(jù)集下的增量學(xué)習(xí)將是下階段的主要工作。

[1] 權(quán)鑫,顧韻華,鄭關(guān)勝，等.一種增量式的代價敏感支持向量機(jī)[J].中國科學(xué)技術(shù)大學(xué)學(xué)報,2016,46(9):727-735.

[2] 王洪波,趙光宙,齊冬蓮,等.一類支持向量機(jī)的快速增量學(xué)習(xí)方法[J].浙江大學(xué)學(xué)報(工學(xué)版),2012,46(7):1327-1332.

[3] 郝運河,張浩峰.基于雙支持向量回歸機(jī)的增量學(xué)習(xí)算法[J].計算機(jī)科學(xué),2016,43(2):230-234.

[4] 徐久成,劉洋洋,杜麗娜,等.基于三支決策的支持向量機(jī)增量學(xué)習(xí)方法[J].計算機(jī)科學(xué),2016,42(6):82-87.

[5] 劉偉,謝興生,肖超峰.一種基于支持向量閾值控制的優(yōu)化增量SVM算法[J].計算機(jī)工程與應(yīng)用,2015,51(3):124-128.

[6] 曹健,孫世宇,段修生,等.基于KKT條件的SVM增量學(xué)習(xí)算法[J].火力與指揮控制,2014,39(7):139-143.

[7] 馬占飛,樊捷杰,張文興.廣義KKT約束的增量支持向量機(jī)建模研究[J].機(jī)械設(shè)計與建造,2015,(11):167-170.

[8] 豐文安,王建東,陳海燕.一種快速SVR增量學(xué)習(xí)算法[J].小型微型計算機(jī)系統(tǒng),2015,36(1):162-166.

[9] 李娟,王宇平.基于樣本密度和分類錯誤率的增量學(xué)習(xí)矢量量化算法研究[J].自動化學(xué)報,2015,41(6):1187-1200.

[10] 潘世超,王文劍,郭虎升.基于概率密度分布的增量支持向量機(jī)算法[J].南京大學(xué)學(xué)報(自然科學(xué)版),2013,49(5):603-610.

[11] 王立梅,李金鳳,岳琪.基于k均值聚類的直推式支持向量機(jī)學(xué)習(xí)算法[J].計算機(jī)工程與應(yīng)用,2013,49(14):144-146.

[12] 楊海濤,肖軍,王佩瑤,等.基于參數(shù)間隔孿生支持向量機(jī)的增量學(xué)習(xí)算法[J].信息與控制,2016,45(4):432-436.

[13] 郭虎升,王文劍, 潘世超.基于組合半監(jiān)督的增量支持向量機(jī)學(xué)習(xí)算法[J].模式識別與人工智能,2016,29(6):504-510.

[14] 杜紅樂,滕少華,張燕.協(xié)同標(biāo)注的直推式支持向量機(jī)算法[J].小型微型計算機(jī)系統(tǒng).2016,37(11):2443-2447.

[15] Xie Zhiqiang, Gao Li, Yang Jing. Improved multi-class classification incremental learning algorithm based on sphere structured SVM [J]. Journal of Harbin Engineering University. 2009, 30(9):1041-1046.

[16] Chang C C, Lin C J. LIBSVM: A library for support vector machines. (2014-07-10). [EB/OL]. http://www.csie.ntu.tw/～cjlin/libsvm.

[17] http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html. 1999.

Intrusion Detection Based on Incremental Support Vector Machine

Du Hongle, Zhang Yan

(School of mathematics and computer application, Shangluo University, Shangluo 726000, China)

Because network intrusion detection system cannot identify new intrusion behavior, incremental learning can improve classifier, and classifier can identify the new intrusion behavior. This paper presents an incremental support vector machine algorithm based on similarity. The algorithm selects the sample according to the similarity between the new samples and support vectors. These samples contain the spatial information that the current classifier lacks. Then these samples are added to the training center for the next iteration. This algorithm can improve the training speed and classification accuracy. Finally, the experimental results show that the proposed algorithm can improve the classification accuracy and the training speed.

Support vector machine; Intrusion detection; Similarity

陜西省自然科學(xué)基礎(chǔ)研究計劃資助(2015JM6347)、陜西省教育廳科技計劃項目(15JK1218)、商洛學(xué)院科學(xué)與技術(shù)研究項目(15sky010)

杜紅樂(1979-)，男，碩士，講師，研究方向：機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘。 張燕(1977-)，女，碩士，講師，研究方向：模式識別、機(jī)器學(xué)習(xí)。

1007-757X(2017)07-0015-03

TP301.6

A

2016.10.30)