一種快速KMSE算法及其在異常入侵檢測中的應(yīng)用

范自柱，徐 勇，徐保根，朱 旗

(1.哈爾濱工業(yè)大學(xué)深圳研究生院，518055廣州深圳，zzfan3@yahoo.com.cn; 2.華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院，330013江西南昌)

核方法［1］的基本思想是將輸入空間通過某種非線性映射變換到一個(gè)高維的特征空間，借助于“核技巧”［2］在新的空間中應(yīng)用線性分析方法.“核技巧”最早應(yīng)用于支持向量機(jī)(Support Vector Machines，SVM)中.隨后，基于核的主分量分析(Kernel Principal Component Analysis，KPCA)［3］、基于核的Fisher鑒別分析(Kernel Fisher Discriminant Analysis，KFDA)［4］和基于核的最小均方誤差(KMSE)［5］等核學(xué)習(xí)方法被提出.實(shí)際上，KMSE模型可以看作是在核主分量分析基礎(chǔ)上實(shí)施特征提取的過程，而且在形式上它等效于最小平方支持向量機(jī)(Least Squares Support Vector Machines，LS-SVM)［6］與核鑒別分析.當(dāng)樣本數(shù)趨于無窮時(shí)，KMSE模型將以最小均方誤差逼近特征空間中的貝葉斯判別函數(shù).

根據(jù)再生核理論，KMSE模型在特征空間中的鑒別向量是此空間中樣本的線性組合.相應(yīng)地，KMSE模型對一個(gè)樣本的特征抽取結(jié)果為該樣本與所有(訓(xùn)練)樣本間核函數(shù)的線性組合.因此，KMSE特征抽取效率與訓(xùn)練集的大小成反比.為了提高學(xué)習(xí)效果，人們往往需要數(shù)百甚至成千上萬個(gè)樣本進(jìn)行學(xué)習(xí)(訓(xùn)練)，而這樣大規(guī)模的訓(xùn)練集無疑會(huì)大大降低KMSE的特征抽取效率.針對這一問題，一些關(guān)于核的優(yōu)化算法［7-10］被相繼提出.本文首次將KMSE和其快速算法應(yīng)用于異常入侵檢測［11］這一信息安全領(lǐng)域，在經(jīng)典的入侵檢測實(shí)驗(yàn)數(shù)據(jù)集KDDCUP1999上的實(shí)驗(yàn)結(jié)果表明，KMSE是一種有效的異常入侵檢測方法，經(jīng)改進(jìn)后得到的快速KMSE方法檢測效率非常高，檢測結(jié)果十分理想.

1 KMSE模型

KMSE是對傳統(tǒng)的最小均方誤差(MSE)應(yīng)用核方法而得到的.本文主要考慮2類問題:假設(shè)在n個(gè)訓(xùn)練樣本 x1，x2，…，xn中，前 n1個(gè)屬于第1類，類別標(biāo)識為1;其余的n2個(gè)屬于第2類，類別標(biāo)識為-1，且n1+n2=n.這些樣本經(jīng)過一非線性映射φ(·)得到特征空間中的2組樣本: φ(x1)，φ(x2)，…，φ(xn1)對應(yīng)第1類;φ(xn+1)，…，φ(xn)對應(yīng)第2類.則KMSE模型為

其中:

式中:W為特征空間中的鑒別方向;w為鑒別矢量;w0為閾值權(quán);B中1的個(gè)數(shù)為n1，-1的個(gè)數(shù)為n2.根據(jù)再生核理論，W可以看作為閾值權(quán)w0與特征樣本的線性組合［13］，式(1)中的W變?yōu)?/p>

因此，借助核函數(shù)k(x，xi)=(φ(x)· φ(xi))，式(1)可以改寫為

其中:

式(3)的最小二乘解的一般形式為

由于KTK是病態(tài)矩陣，所以需要引入一正則項(xiàng)μ，則式(4)變?yōu)?/p>

式中:I為單位矩陣;A即為將min(μATA+(BKA)T(B-KA))作為目標(biāo)函數(shù)得出的解.根據(jù)式(5)求出A后，便可實(shí)現(xiàn)分類.設(shè)有一待測模式x，它在鑒別方向上的投影為

當(dāng)lp(x)＞0時(shí)，將x分到第1類，其類標(biāo)記為1;否則，它被分到第2類，其類標(biāo)記為-1.

2 KMSE的快速算法(FKMSE)

由式(2)知，如果要確定一個(gè)樣本的類別，需要把它與所有訓(xùn)練樣本的點(diǎn)積求出，才能判別其類別.當(dāng)訓(xùn)練樣本非常多時(shí)，若要給大容量的測試集分類，顯然，其效率是不高的.在輸入空間中，訓(xùn)練樣本的維數(shù)一般不是很高.由線性相關(guān)性理論，n+1個(gè)n維向量必線性相關(guān)，所以，當(dāng)訓(xùn)練樣本的個(gè)數(shù)大于其維數(shù)時(shí)，訓(xùn)練樣本間必然存在線性相關(guān)性.根據(jù)線性相關(guān)理論，得出下面的結(jié)論:

定理1 對于特征空間F中的一組向量: φ(x1)，φ(x2)，…，φ(xr)∈F，如果它們線性相關(guān)，即存在一組不全為0的數(shù):l1，l2，…，lr∈R，使得:

則有

證明 依次用φ(x1)，φ(x2)，…，φ(xr)乘式(7)左右兩邊，得:

定義核函數(shù)k(x，xi)=(φ(x)·φ(xi))，得出齊次線性方程組為

其中，L=(l1，l2，…，lr)T，顯然，A是方陣，根據(jù)求解線性方程組的Crame法則，齊次線性方程組若有非零解，則det(A)=0，即D=0.由題設(shè)，l1，l2，…，lr不全為零，也即是式(9)有非零解，所以有D=0.得證.

定理1的逆否命題也很有用，即:若D≠0，則φ(x1)，φ(x2)，…，φ(xr)線性無關(guān).

利用定理1，可以判斷特征空間中的一組向量是否線性相關(guān)，如果相關(guān)，則根據(jù)某個(gè)準(zhǔn)則選取該向量組的一個(gè)極大無關(guān)組，用這個(gè)無關(guān)組代替原向量組，從而可以減少鑒別方向W中涉及向量的個(gè)數(shù).這樣，式(6)中的n將減小，測試時(shí)所需的計(jì)算代價(jià)變小，因此，能夠提高分類效率.理論上，一個(gè)向量組與它的極大無關(guān)組等價(jià)，也就是能夠相互線性表示，而且，一個(gè)向量組往往不止一個(gè)極大無關(guān)組.在實(shí)際應(yīng)用中，極大無關(guān)組的形式越簡單往往被使用得越多，如單位向量組.在本文應(yīng)用中，主要考慮方程組的求解誤差，也就是訓(xùn)練模式向量對應(yīng)的準(zhǔn)則值.根據(jù)式(5)，本文選取的準(zhǔn)則為:J即給出快速算法過程:

1)計(jì)算每個(gè)訓(xùn)練模式x1，x2，…，xn對應(yīng)的準(zhǔn)則值J.為了計(jì)算J，必須先計(jì)算每個(gè)xi(i=1，2，…，n)對應(yīng)的矩陣K'為

計(jì)算出K'后，把K'代入式(5)中求出A，最后把每個(gè)J計(jì)算出來，并且依J值的大小用快速排序法將xi(i=1，2，…，n)按升序排成一序列，記為R;令極大無關(guān)組B={}.

2)從R中選出第1個(gè)元素x1'，計(jì)算它對應(yīng)的D=|k(x1'，x1')|，把x1'加入B，使其成為B的第1個(gè)元素:B={x1'}，R=R-{x1'}.

3)B中其他元素的確定.correlate(B)表示與B中所有元素線性相關(guān)的樣本.設(shè)經(jīng)過第i-1步選擇，B中有i-1個(gè)元素，B={x1'，x2'，…，xi'-1}，與其對應(yīng)的行列式為

取R中元素xi'，令

若Di=0，xi'∈correlate(B).則確定B中其他元素的過程的偽語言描述為:

最后獲得基樣本集B={x1'，x2'，…，xs'}.

4)用基樣本集B代替整個(gè)訓(xùn)練樣本集，修改式(6)，得:

利用式(10)，可以對一待測模式x進(jìn)行分類.一般地，s?n，所以對待測樣本的分類速度將會(huì)大大提高.

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

本文實(shí)驗(yàn)包括2個(gè)部分:實(shí)驗(yàn)1和實(shí)驗(yàn)2.它們都是在2.4 GHz CPU，256 M內(nèi)存環(huán)境中使用Matlab7.0實(shí)現(xiàn).

3.1 實(shí)驗(yàn)1

在實(shí)驗(yàn)1中，使用文獻(xiàn)［5，9］中提到的基準(zhǔn)數(shù)據(jù)庫，在7個(gè)基準(zhǔn)模式集上進(jìn)行.每個(gè)模式集被隨機(jī)分成了100個(gè)部分，每個(gè)部分又包括4個(gè)子部分:訓(xùn)練數(shù)據(jù)集、訓(xùn)練標(biāo)記集、測試數(shù)據(jù)集和測試標(biāo)記集.實(shí)驗(yàn)采用高斯型核函數(shù)為

實(shí)驗(yàn)時(shí)，先對每個(gè)數(shù)據(jù)集的第1個(gè)子集進(jìn)行訓(xùn)練，然后對100個(gè)測試集測試.按照這種方式，先在基準(zhǔn)數(shù)據(jù)集上，根據(jù)式(5)實(shí)現(xiàn)了傳統(tǒng)的KMSE方法(TKMSE).一方面是為了與新提出的方法FKMSE在算法效果方面進(jìn)行對比;另一方面，是為了確定核函數(shù)中的參數(shù)，實(shí)驗(yàn)結(jié)果如表1所示.表1最后1列括號中的值為最優(yōu)的核函數(shù)參數(shù)，式(5)中的正則項(xiàng)μ取1.0E-3.

表1給出了TKMSE、NKNM、FKNM、AB、SVM和FKMSE等6種方法的平均分類錯(cuò)誤率及其標(biāo)準(zhǔn)差.其中:AB和SVM這2種方法的結(jié)果引自文獻(xiàn)［5］;NKNM和FKNM這2種方法的結(jié)果引自文獻(xiàn)［9］.表1中的分類效果由2項(xiàng)構(gòu)成:第1項(xiàng)是100次測試所得的平均分類錯(cuò)誤率;第2項(xiàng)是其標(biāo)準(zhǔn)差.對于每一數(shù)據(jù)集，表1中的括號項(xiàng)標(biāo)出了使用5種方法NKNM、FKNM、AB、SVM和本文提出的FKMSE得到的最好分類效果.由表1看出，F(xiàn)KMSE與除TKMSE外的其他4種方法分類效果相當(dāng);對于數(shù)據(jù)集f.solar，F(xiàn)KMSE是5種非TKMSE方法中分類最好的.

表2給出了FKMSE和FKNM方法中的基樣本數(shù)及其與總訓(xùn)練樣本數(shù)的比例，基樣本數(shù)后面的百分比是指一次訓(xùn)練得到的基樣本個(gè)數(shù)與訓(xùn)練樣本數(shù)之比.此比例普遍較低，7個(gè)數(shù)據(jù)集中最高的是15%，有的甚至低至約1%.這就是本文方法實(shí)現(xiàn)速度快的根本原因.同時(shí)，從分類效果來看，F(xiàn)KMSE與原方法TKMSE相差無幾，基本可以取代原訓(xùn)練樣本進(jìn)行分類.從表1和表2中可以看出，雖然FKMSE的分類效果比TKMSE稍微下降一點(diǎn)，總體分類正確率下降大約2%.但是，它的效率大大提高了.表3給出了FKMSE和TKMSE這2種方法的分類時(shí)間.這里的分類時(shí)間是指測試100次所需要的時(shí)間，表中括號中的數(shù)值是FKMSE與TKMSE分類時(shí)間的比例.從表3可以看出，文中提出的快速算法比傳統(tǒng)的方法測試速度要快一個(gè)數(shù)量級以上，極大地提高了分類效率.而且，根據(jù)表2和3，數(shù)據(jù)集的訓(xùn)練樣本越多，本文方法的分類效率就越高.

表1 分類錯(cuò)誤率和標(biāo)準(zhǔn)差

表2 FKMSE和FKNM方法中的基樣本數(shù)及其與總訓(xùn)練樣本數(shù)的比例

表3 FKMSE和TKMSE分類時(shí)間

3.2 實(shí)驗(yàn)2

本文選用在入侵檢測領(lǐng)域中的經(jīng)典測試數(shù)據(jù)集KDDCUP1999［12］.該數(shù)據(jù)集主要由6個(gè)部分組成，實(shí)驗(yàn)在其中的一個(gè)子集kddcup.data-10-percent.gz上進(jìn)行.這個(gè)子集包含約49萬個(gè)樣本，每個(gè)樣本有41個(gè)特征.本文把數(shù)據(jù)集中的數(shù)據(jù)分成2類:1)正常數(shù)據(jù)，即類別表示為“normal”的數(shù)據(jù); 2)異常數(shù)據(jù)，包含4類攻擊:DOS、PROBE、R21和U2R.本文實(shí)驗(yàn)的訓(xùn)練集選取2 000個(gè)樣本，由2類組成:1)“normal”;2)DOS攻擊類型之一的“smurf”類，每類1 000個(gè)樣本，都是隨機(jī)抽取.測試集在kddcup.data-10-percent.gz中按先后順序選取10 000個(gè)樣本，分為10個(gè)測試子集，每個(gè)1 000個(gè)樣本，樣本的類別與訓(xùn)練集一致.

實(shí)驗(yàn)中，通過預(yù)處理，去除了12個(gè)特征，采用29個(gè)特征進(jìn)行計(jì)算.實(shí)驗(yàn)也選用形如式(11)的高斯核函數(shù)，其參數(shù)選為訓(xùn)練樣本方差的均值.其他參數(shù)同實(shí)驗(yàn)1.

表4給出了2種方法KMSE和FKMSE的入侵檢測效果和時(shí)間.實(shí)驗(yàn)中的檢測效果用平均檢測率表示，一次檢測率是指在一次測試中正確檢測出的攻擊次數(shù)與總的攻擊次數(shù)之比.平均檢測率則是對10個(gè)測試子集進(jìn)行檢測所得到的檢測率均值.表中檢測時(shí)間是指對10個(gè)測試子集進(jìn)行檢測所需的時(shí)間.從表4中可以看出，2種方法的檢測效果皆很理想，所以它們都是異常入侵檢測的有效方法.值得注意的是，本文提出的FKMSE方法在實(shí)驗(yàn)中，不僅檢測效果很好，而且非常高效，其檢測時(shí)間只有KMSE方法的0.2%.因此，比KMSE方法更適合實(shí)時(shí)大規(guī)模異常入侵檢測.根據(jù)表4，在硬件條件不高的情況下，用FKMSE方法對10 000個(gè)樣本檢測，只需要2.9 s，就可以完全達(dá)到實(shí)時(shí)入侵檢測的要求.

表4 KMSE和FKMSE的檢測效果和時(shí)間

4 結(jié)論

1)原始輸入空間的樣本經(jīng)非線性映射后變成特征空間的樣本，它們之間往往存在線性相關(guān)性.因此，如果通過訓(xùn)練學(xué)習(xí)，剔除線性相關(guān)性，減少參與計(jì)算的樣本的個(gè)數(shù)，將會(huì)提高分類效率.

2)FKMSE適合實(shí)時(shí)大規(guī)模異常入侵檢測.

［1］TAYLOR S，CRISTIANINI N.Kernel methods for pattern analysis［M］.London:Cambridge University Press，2004.

［2］ZHANG D，SONG F X，XU Y，et al.Advanced pattern recognition technologies with applications to biometrics［M］.New York:IGI Global，2009.

［3］XU Y，LIN C，ZHAO W.Producing computationally efficient KPCA-based feature extraction for classification problems［J］.Electronics Letters，2010，46(6):452-453.

［4］MIKA S，RATSCH G，WESTON J，et al.Fisher discriminant analysis with kernels［C］//Neural Networks for Signal Processing IX，1999.Proceedings of the 1999 IEEE Signal Proceesing Society Workshop.Madison，WI:IEEE Press，1999:41-48.

［5］LIU W F，PUSKAL P，JOSE P.The kernel least-meansquare algorithm［J］.IEEE Transactions on Signal Processing，2008，56(2):543-554.

［6］XU Y.A new kernel MSE algorithm for constructing efficient classification procedure［J］.International Journal of Innovative Computing，Information and Control，2009，5(8):2439-2447.

［7］CAWLEY G C，TALBOT C.Efficient leave-one-out cross-validation of kernel fisher discriminant classifiers［J］.Pattern Recognition，2003，36(11):2585-2592.

［8］ZHENG W M，ZOU C R，ZHAO L.An improved algorithm for kernel principal component analysis［J］.Neural Processing Letters，2005，22(1):49-56.

［9］XU Y，ZHANG D，JIN Z，et al.A fast kernel-based nonlinear discriminant analysis for multi-class problems［J］.Pattern Recognition，2006，39(6):1026-1033.

［10］LEE D，JUNG K H，LEE J.Constructing sparse kernel machines using attractors［J］.IEEE Trans on Neural Networks，2009，20(4):721-729.

［11］肖立中，邵志清，馬漢華，等.網(wǎng)絡(luò)入侵檢測中的自動(dòng)決定聚類數(shù)算法［J］.軟件學(xué)報(bào)，2008，19(8): 2140-2148.

［12］KDDCUP1999.http://archive.ics.uci.edu/ml/databases/kddcup99/kddcup99.html.