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

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

核方法［1］的基本思想是將輸入空間通過某種非線性映射變換到一個高維的特征空間，借助于“核技巧”［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ù)趨于無窮時，KMSE模型將以最小均方誤差逼近特征空間中的貝葉斯判別函數(shù).

根據(jù)再生核理論，KMSE模型在特征空間中的鑒別向量是此空間中樣本的線性組合.相應(yīng)地，KMSE模型對一個樣本的特征抽取結(jié)果為該樣本與所有(訓(xùn)練)樣本間核函數(shù)的線性組合.因此，KMSE特征抽取效率與訓(xùn)練集的大小成反比.為了提高學(xué)習(xí)效果，人們往往需要數(shù)百甚至成千上萬個樣本進(jìn)行學(xué)習(xí)(訓(xùn)練)，而這樣大規(guī)模的訓(xùn)練集無疑會大大降低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個訓(xùn)練樣本 x1，x2，…，xn中，前 n1個屬于第1類，類別標(biāo)識為1;其余的n2個屬于第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的個數(shù)為n1，-1的個數(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時，將x分到第1類，其類標(biāo)記為1;否則，它被分到第2類，其類標(biāo)記為-1.

2 KMSE的快速算法(FKMSE)

由式(2)知，如果要確定一個樣本的類別，需要把它與所有訓(xùn)練樣本的點(diǎn)積求出，才能判別其類別.當(dāng)訓(xùn)練樣本非常多時，若要給大容量的測試集分類，顯然，其效率是不高的.在輸入空間中，訓(xùn)練樣本的維數(shù)一般不是很高.由線性相關(guān)性理論，n+1個n維向量必線性相關(guān)，所以，當(dāng)訓(xùn)練樣本的個數(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ù)某個準(zhǔn)則選取該向量組的一個極大無關(guān)組，用這個無關(guān)組代替原向量組，從而可以減少鑒別方向W中涉及向量的個數(shù).這樣，式(6)中的n將減小，測試時所需的計算代價變小，因此，能夠提高分類效率.理論上，一個向量組與它的極大無關(guān)組等價，也就是能夠相互線性表示，而且，一個向量組往往不止一個極大無關(guān)組.在實(shí)際應(yīng)用中，極大無關(guān)組的形式越簡單往往被使用得越多，如單位向量組.在本文應(yīng)用中，主要考慮方程組的求解誤差，也就是訓(xùn)練模式向量對應(yīng)的準(zhǔn)則值.根據(jù)式(5)，本文選取的準(zhǔn)則為:J即給出快速算法過程:

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

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

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

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

取R中元素xi'，令

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

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

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

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

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

本文實(shí)驗(yàn)包括2個部分:實(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個基準(zhǔn)模式集上進(jìn)行.每個模式集被隨機(jī)分成了100個部分，每個部分又包括4個子部分:訓(xùn)練數(shù)據(jù)集、訓(xùn)練標(biāo)記集、測試數(shù)據(jù)集和測試標(biāo)記集.實(shí)驗(yàn)采用高斯型核函數(shù)為

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

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

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

表3 FKMSE和TKMSE分類時間

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

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

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

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

表4 KMSE和FKMSE的檢測效果和時間

4 結(jié)論

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

2)FKMSE適合實(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ò)入侵檢測中的自動決定聚類數(shù)算法［J］.軟件學(xué)報，2008，19(8): 2140-2148.

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