一種基于聚類分析的增量支持向量機入侵監(jiān)測方法

摘要：提出了一種聚類學(xué)習(xí)與增量SVM訓(xùn)練相結(jié)合的的入侵檢測方法，采用聚類分析、樣本修剪與增量學(xué)習(xí)相結(jié)合的方式，通過聚合相似的訓(xùn)練樣本以支持多類別分類，通過去除相似的樣本而只取其代表點，從而減少參加訓(xùn)練的樣本數(shù)量，提高學(xué)習(xí)效率，同時采用基于廣義KKT判決的增量學(xué)習(xí)方法，有效改善了多類別入侵檢測場合下樣本數(shù)據(jù)集過于龐大，學(xué)習(xí)速度過慢且難以保障SVM入侵檢測能力持續(xù)優(yōu)化的問題。

關(guān)鍵詞：支持向量機；入侵檢測；聚類；非線性分類

中圖分類號：TP393 文獻標(biāo)識碼：A 文章編號：1009-3044（2014）19-4417-04

An Novel Proposal For Intrusion Detections Based on Clustering Analysis and Increamental Support Vector Machine

WANG Ya-bin

（Jiangsu Tcnet Technology Co.， LTD.， Suzhou 215000，China）

Abstract： An novel incremental SVM intrusion detection algorithm based on Clustering Learning is proposed in this paper. By using the clustring analysis and data pruning， the purpose of efficient simplification and multi-classification for trainning samples is achieved. An improved algorithm of incremental SVM trainning based on generalized KKT condition is also presented. Our simulation result shows that this method could effectively improve the trainning and classification speed caused by datasets updating， while at the same time the classification precision is guaranteed.

Key words： SVM； Intrusion Detection； Clustering； non-Linear Classification

隨著計算機軟硬件的迅猛發(fā)展，計算機網(wǎng)絡(luò)之上的應(yīng)用日益廣泛，在享受互聯(lián)網(wǎng)帶來的各種便利的同時，人們面臨著更嚴重的網(wǎng)絡(luò)入侵的威脅。網(wǎng)絡(luò)上隨處可見的黑客軟件使得入侵行為與日俱增，統(tǒng)計數(shù)據(jù)表明，每年網(wǎng)絡(luò)入侵事件的數(shù)量呈指數(shù)形式增長。與此同時，網(wǎng)絡(luò)入侵更顯示出多樣性，智能性，隱蔽性等特點，這使得僅靠傳統(tǒng)的殺毒軟件、防火墻等靜態(tài)防御技術(shù)無法保證網(wǎng)絡(luò)的安全。

入侵檢測系統(tǒng)（Intrusin Detection System，IDS）與傳統(tǒng)的防火墻相比，是一種積極主動的安全防護技術(shù)，提供了對內(nèi)部攻擊、外部攻擊和誤操作的實時保護。它能很好的彌補防火墻的不足，可以對系統(tǒng)中未授權(quán)訪問或異常現(xiàn)象、活動與時間進行審計、追蹤、識別和檢驗的安全過程。它可以識別出系統(tǒng)是否被入侵，從而做出及時的反應(yīng)，切斷網(wǎng)絡(luò)連接、記錄時間和報警，提醒系統(tǒng)管理員采取相應(yīng)的措施，避免系統(tǒng)受到進一步的侵害。

入侵檢測問題實質(zhì)上可被視為一個區(qū)分入侵行為與正常行為的分類問題。這一問題在機器學(xué)習(xí)、最優(yōu)化等領(lǐng)域獲得了深入研究。其中，基于VC維理論和風(fēng)險最小化原理的支持向量機（Support Vector Machine）技術(shù)日益受到了人們的關(guān)注，SVM在解決小樣本、非線性及高維模式識別問題中具有的特有優(yōu)勢，使得其非常適合用以解決入侵檢測分類問題。然而在實際應(yīng)用中，面對層出不窮的海量入侵行為，如何在有效保障SVM訓(xùn)練效率、以便及時響應(yīng)入侵事件的同時，實現(xiàn)其學(xué)習(xí)、推廣能力的持續(xù)強化與提升，以滿足快速應(yīng)對新興威脅的需要，其目前已成為SVM應(yīng)用于入侵檢測實用場合所必須解決的兩個關(guān)鍵問題。

針對上述問題，目前學(xué)術(shù)界已進行了大量研究，Mukkamala等人[1]利用SVM技術(shù)實現(xiàn)了入侵檢測，并與神經(jīng)網(wǎng)絡(luò)方法進行了比較，獲得了良好結(jié)果；Syed等[2]對樣本支持向量集進行了分析，首次提出一種SVM增量學(xué)習(xí)算法；段丹青等[3]提出了一種基于粗糙集與SVM的入侵檢測算法，有效地解決了訓(xùn)練樣本降維問題；于靜等[4]將PCA主成分分析應(yīng)用于特征樣本處理中，以提升SVM訓(xùn)練效率；張永俊等[5]則采用了一種簡化二進制差別矩陣與云模型的方式，來對SVM訓(xùn)練樣本進行增量式屬性約簡。這些工作均在不同程度上改善了SVM應(yīng)用于入侵檢測場合中的學(xué)習(xí)、分類效率。

本文提出了一種聚類學(xué)習(xí)與增量SVM訓(xùn)練相結(jié)合的的入侵檢測方法，采用聚類分析、樣本修剪與增量學(xué)習(xí)相結(jié)合的方式，通過聚合相似的訓(xùn)練樣本以支持多類別分類，通過去除相似的樣本而只取其代表點，從而減少參加訓(xùn)練的樣本數(shù)量，提高學(xué)習(xí)效率，同時采用基于廣義KKT判決的增量學(xué)習(xí)方法，從而有效改善了多類別入侵檢測場合下樣本數(shù)據(jù)集過于龐大，學(xué)習(xí)速度過慢且難以保障SVM入侵檢測能力持續(xù)優(yōu)化的問題。

1 支持向量機與聚類分析簡介

1.1 支持向量機模型

假設(shè)已知訓(xùn)練樣本[{xi，yi}，yi=±1，i=1，2，...n]，其中xi為樣本的特征向量輸入，yi為分類結(jié)果，n為樣本數(shù)。當(dāng)[yi=1]時為正類，即正常；[yi=-1]時為負類，即異常。SVM方法就是通過尋求一個最優(yōu)分類超平面[ω，x+b=0]，使得其對于所有訓(xùn)練樣本滿足：endprint

[yi[ω，x+b]-1]

其中，[ω]為輸入數(shù)據(jù)的權(quán)重矢量，b為分類超平面的偏置。上式可轉(zhuǎn)化為一個二次凸優(yōu)化問題，該問題表述如下：

其中，C為懲罰因子，[ξi]為松弛因子，利用拉格朗日乘數(shù)法對上述問題進行最優(yōu)化求解，可將上式轉(zhuǎn)換為對偶問題：

式中[αi]為拉格朗日算子。在針對上式優(yōu)化問題的解中，存在部分[αi]不為0，其所對應(yīng)的訓(xùn)練樣本即為“支持向量”。同時，上式將[ω]的最優(yōu)化求取問題，轉(zhuǎn)換為了[α]的參數(shù)優(yōu)化問題，并可通過[α]解得[ω]為：

在式對偶問題求解的基礎(chǔ)上，可得到SVM線性判別函數(shù)為：

對于線性不可分的數(shù)據(jù)，可以使用非線性映射函數(shù)[?]將輸入數(shù)據(jù)從原低維空間變換到高維特征空間，使得原空間中線性不可分的樣本數(shù)據(jù)變得高維線性可分，然后再求其最優(yōu)決策平面。故有擴展后的廣義SVM判決函數(shù)為：

式中的K被稱之為與[?]所對應(yīng)的核函數(shù)。

1.2 廣義KKT條件

針對式（）對偶問題的最優(yōu)化問題求解需要用到最優(yōu)性KKT條件（Karush-Kuhn-Tucker），該條件是SVM凸二次規(guī)劃獲得全局最優(yōu)解的充分必要條件，其表述如下：

對于所有i，以下條件成立：

[yif（xi）1， ai=0yif（xi）=1， 0

由上述條件可看出，[ai=0]對應(yīng)的樣本點（xi，yi）是被正確分開的點，當(dāng)[0

針對一個已有的SVM分類器，可證明[6]，如果新增樣本不違背KKT條件，則加入這個樣本將不會對當(dāng)前分類器產(chǎn)生影響，而違背KTT條件的樣本參與訓(xùn)練的話將有可能改變原問題的解。同時還可證明[7]，當(dāng)新增樣本中存在違背KKT條件的樣本時，原有的非支持向量有可能轉(zhuǎn)化成新的支持向量。上述結(jié)論為基于新增樣本的增量SVM訓(xùn)練提供了基礎(chǔ)依據(jù)。

1.3 聚類分析方法

聚類分析（Clustering）是一種將樣本集合粗分組成為由類似的對象組成的多個類的分析過程。目前已經(jīng)存在著大量的聚類算法[8]，算法的選擇多取決于數(shù)據(jù)類型、聚類目的和應(yīng)用范圍，其典型聚類算法一般可分為基于劃分的方法、基于層次的方法、基于網(wǎng)格的方法、基于密度的方法及基于模型的方法等。

K-Means算法是其中應(yīng)用得最為廣泛的一種劃分方法。其核心思想在于：首先從樣本數(shù)據(jù)集中隨機選取k個樣本作為k個類的初始中心，剩余樣本點根據(jù)最小距離原則，分配給與之距離最近的那個中心點，然后計算每個類的平均值作為新的聚類中心點，反復(fù)迭代以上過程，直至平方誤差準(zhǔn)則函數(shù)收斂為止。平方誤差準(zhǔn)則函數(shù)被定義為：

其中，E為樣本空間中所有樣本的平方誤差之和，x為所有屬于類Ci的樣本，mi是類Ci中所有樣本的平均值。

值得指出的是，K-Means算法較大依賴于對初始聚類中心點的選取，不同中心點的初始選取有可能會導(dǎo)致不同的聚類結(jié)果及聚類效率，同時有可能使得算法終止于局部最優(yōu)解。

2 基于聚類的多分類SVM入侵檢測方法

2.1 整體模型框架

考慮到在實際應(yīng)用中，入侵檢測系統(tǒng)不僅需要判斷異常行為是否存在，同時還需要判斷具體異常行為的類屬與所屬類別異常行為的普遍性，該文提出了一種基于聚類分析的多分類SVM入侵檢測方法，其所采用的處理步驟如下：

1） 首先針對訓(xùn)練樣本集中的樣本進行異構(gòu)數(shù)據(jù)處理，將其屬性特征進行數(shù)據(jù)值化與歸一化

2） 采用改進型的密度聚類及K-Means聚類方法，消除樣本中的噪聲點和干擾點，同時劃分為m個聚類，每一聚類代表著一類具有相似特征的網(wǎng)絡(luò)行為；

3） 針對每個聚類樣本集合，計算其正負類別的最相鄰樣本集合，并進行相應(yīng)的樣本裁剪，以在保障學(xué)習(xí)所得分類器精度的同時，減少樣本冗余，提高分類器學(xué)習(xí)效率；

4） 針對每一聚類，將其最相鄰樣本集合作為訓(xùn)練樣本進行學(xué)習(xí)，為每一聚類均生成一個SVM分類器，用以判別本聚類中的異常行為；

5） 針對后繼新增的已標(biāo)記樣本數(shù)據(jù)，首先根據(jù)密度與特征距離判斷其所屬聚類，選擇相應(yīng)的SVM分類器，然后以廣義KKT條件為增量學(xué)習(xí)依據(jù)，分析新增樣本對當(dāng)前聚類分類器的影響，并實現(xiàn)對已有分類器的更新修正；

6） 對于持續(xù)輸入的測試樣本數(shù)據(jù)，將首先判斷其屬于哪個聚類，然后再選用相應(yīng)的SVM分類器進行分類，最終得出多類別的入侵檢測結(jié)果判定。

2.2 改進型K-Means樣本聚類

本文采用了一種基于節(jié)點分布的判斷方式進行聚類初始中心點的選取，繼而在選取中心點基礎(chǔ)上進行相應(yīng)的K-Means聚類。

設(shè)當(dāng)前樣本集合M中有N個樣本點，其中每一樣本點x可用n維向量表示為（x1，x2，….xn），其中n為特征屬性的維度；則可定義樣本點[xi]與[xj]之間的歐式空間距離為：

定義樣本點[xi]的分布密度為DS（[xi]），則有：

其中[num[D（xi）

基于上述定義，則有改進型K-Means聚類算法步驟如下：

1） 選取樣本的密度半徑r=mean（x）/N0.18，其中mean（x）為樣本集合中所有樣本距離的平均值；N0.18為一可調(diào)經(jīng)驗閾值；

2） 針對全體樣本計算其分布密度，然后計算所有樣本密度平均，并將每一個大于平均值的樣本點放在備選集合S中；

3） 挑揀S中密度最大的樣本作為初始聚類中心點c1，將其從S中取出，并放入初始聚類中心點集合T中；

4） 從S中尋找下一個初始聚類中心點c2，且其需滿足如下條件：[D（c2，c1）>τ]，且其密度盡可能的大；其中[τ]取整個樣本空間最大樣本距離的1/m，m為聚類個數(shù)；將c2從S中移出，并放入初始聚類中心點集合T；

5） 重復(fù)4），直至找到m個初始聚類中心點為止。

6） 設(shè)初始聚類中心點為{c1，c2，…cm}，t為當(dāng)前的聚類迭代步驟；

7） 將所有待分類的樣本逐個按“離中心點距離最近”的原則劃分至m個類中；

8） 重新計算m個聚類的中心點；以當(dāng)前聚類中所有樣本的幾何平均值作為新的聚類中心；

9） 如對于m個聚類中心點在重新計算前后均未發(fā)生變化，則算法終止；否則轉(zhuǎn)至7）進一步迭代，直至所有聚類中心點收斂為止；

10） 輸出m個聚類節(jié)點集合作為聚類處理的結(jié)果。

與通常K-Means算法不同，以上算法采用了一種基于樣本節(jié)點分布的確定性初始中心點選取方法，通過根據(jù)樣本密度和間距來擇優(yōu)選取初始中心點，從而以啟發(fā)式方式避免了傳統(tǒng)K-Means算法選取初始中心點的過度隨機性，進而有效保障了后繼聚類分析結(jié)果的質(zhì)量。

2.3 最相鄰樣本集合裁剪

本文采用一種基于最相鄰樣本集合的裁剪方式，以減少樣本集合冗余，提升學(xué)習(xí)效率。

考慮兩類別分類場合，設(shè)x+為正類樣本，而x-則為樣本集中的負類樣本，不妨設(shè)，，則兩者之間的歐式空間距離為：

我們可針對正類中每一個樣本x'+，計算出其與所有負類樣本x'-之間的距離，然后標(biāo)記出其中距離最小的那一個。由這些距離最小的負類樣本所構(gòu)成的集合被稱之為正類的最相鄰樣本集合M+。反過來，我們也可針對負類所屬樣本，求取出其所對應(yīng)的最相鄰樣本集合M-，且其集合中的每一個樣本均屬于正類。

根據(jù)SVM最優(yōu)分隔界面的性質(zhì)可知，在兩類別分類場合下，其SVM所對應(yīng)的支撐向量必包含在M+ ∪ M-中。即，在進行SVM訓(xùn)練時，我們可排除那些未被包含在最相鄰樣本集合中的節(jié)點，而不會對所得的SVM分類器產(chǎn)生任何影響，這是因為這些節(jié)點不可能位于SVM最優(yōu)分隔界面之上，所以它們不可能成為支撐向量。通過上述裁剪方式，可以極大地壓縮參與后繼SVM訓(xùn)練的樣本數(shù)據(jù)，從而顯著提高訓(xùn)練性能。

值得指出的是，在增量學(xué)習(xí)場合下，非最相鄰樣本數(shù)據(jù)并沒有被完全刪除，而僅只是將其從當(dāng)前訓(xùn)練集合中排除。這主要是因為，盡管這些樣本在當(dāng)前學(xué)習(xí)階段中不可能成為支撐向量，但這卻并不意味著在后繼增量學(xué)習(xí)階段中，其也不可能成為支撐向量。因此，為使得上述裁剪方法能適用于增量SVM學(xué)習(xí)場合，我們采取了一種以空間換時間的策略，即保存下聚類中所有樣本與樣本之間的距離，以便在每個增量學(xué)習(xí)階段中快速引用并排序，進而快速地裁剪出當(dāng)前學(xué)習(xí)階段所需的實際訓(xùn)練樣本集合。實際應(yīng)用中，盡管上述策略將不可避免地導(dǎo)致內(nèi)存等資源占用的增長，然而在已事先劃分聚類的場合下，這一影響被限制在單個聚類范圍之內(nèi)，因而可以極大地減輕。綜合而言，我們認為這種存儲空間與訓(xùn)練性能的折衷是值得的。

2.4 增量SVM訓(xùn)練更新

本文采取了一種基于最相鄰樣本集合的增量學(xué)習(xí)方式，來更新聚類對應(yīng)的SVM分類器。

設(shè)聚類A初始訓(xùn)練樣本集E及其訓(xùn)練所得的分類器為V；屬于聚類A的新增樣本集E及其訓(xùn)練所得的分類器為V。令，其中為違背V的廣義KKT條件的樣本集，為滿足V的廣義KKT條件的樣本集；與之類似的，令，其中為違背V的廣義KKT條件的樣本集，為滿足V的廣義KKT條件的樣本集。其算法步驟如下：

1） 檢查E中是否存在違背V的廣義KKT條件的樣本，如無，則算法終止，輸出V為增量訓(xùn)練結(jié)果；如有，則將E劃分為與；

2） 計算E中正負類的最相鄰集合，并基于此計算其分類器V；

3） 檢測E中是否存在違背V的廣義KKT條件樣本，如無，算法停止，輸出V為增量訓(xùn)練結(jié)果；如有，則將E劃分為與；

4） 合并、以及E、E的支撐向量集，針對其合集進行正負類最相鄰集合裁剪，繼而對該合并集合進行訓(xùn)練，并輸出其分類器為增量學(xué)習(xí)結(jié)果。

3 實驗與分析

本文采用了KDDCup99測試數(shù)據(jù)集[9]對上述方法進行了驗證，其樣本共計41個特征屬性，共計DOS（拒絕服務(wù)攻擊）、R2L（遠程權(quán)限獲?。2R（用戶權(quán)限提升攻擊）、Probing（端口及漏洞掃描）等4大類攻擊行為。

仿真實驗采用Libsvm[10]與C++實現(xiàn)，其采用了RBF核函數(shù)，其中取0.98。整個實現(xiàn)采用了交叉對比的方式，其比較對象為一般的全樣本SVM學(xué)習(xí)器。其實現(xiàn)結(jié)果如下表所示。

表1 一般SVM算法仿真實驗結(jié)果

[訓(xùn)練樣本數(shù)＼&訓(xùn)練時間（s）＼&測試時間（ms）＼&分類準(zhǔn)確度（%）＼&50＼&0.094＼&0.994＼&99.21＼&1000＼&0.297＼&0.1219＼&99.75＼&20000＼&8.437＼&0.3047＼&99.95＼&100000＼&232.141＼&0.5766＼&99.98＼&]

表2 基于聚類分析的增量支撐向量機仿真實驗結(jié)果

[訓(xùn)練樣本數(shù)＼&聚類數(shù)量＼&訓(xùn)練時間（s）＼&測試時間（ms）＼&分類準(zhǔn)確度（%）＼&100000＼&10＼&29.763＼&0.1206＼&99.946＼&100000＼&50＼&44.721＼&0.0832＼&99.958＼&100000＼&100＼&126.813＼&0.0921＼&99.971＼&]

由表可見，在訓(xùn)練樣本數(shù)為100000的場合下，該文算法的訓(xùn)練時間與測試時間均大大低于一般SVM全量學(xué)習(xí)算法，與此同時，其分類準(zhǔn)確率在聚類數(shù)量足夠的情況下，也基本達到了標(biāo)準(zhǔn)SVM算法同等的水平。同時還值得指出的是，隨著聚類數(shù)量的增多，該文算法所得分類檢測率是遞增的，這與我們的直覺是相符的。上述實驗充分說明了本文方法在大訓(xùn)練樣本量場景下的有效性與適用性。

4 結(jié)論與下一步工作

本文提出了一種基于聚類分析的增量SVM相結(jié)合的的多類型入侵檢測學(xué)習(xí)方法，該方法通過采用了一種基于樣本分布的改

（下轉(zhuǎn)第4432頁）

（上接第4420頁）

進K-Means聚類方式來針對訓(xùn)練樣本進行歸類，同時提出了一種基于最相鄰樣本集合的訓(xùn)練樣本裁剪方法，并將上述裁剪方式與廣義KKT條件判定相結(jié)合，提出了一個多類別增量SVM學(xué)習(xí)方法。分析與實驗表明，上述方法可顯著改善大訓(xùn)練樣本量下SVM分類器訓(xùn)練時間長、學(xué)習(xí)速度慢的問題，同時有效保障了系統(tǒng)檢測能力的持續(xù)優(yōu)化與更新。

下一步工作包括：進一步評估新增樣本對聚類分析結(jié)果的影響，以進一步提升多類別SVM訓(xùn)練、檢測性能；嘗試結(jié)合采用超球、軟邊界等其他裁剪算法，優(yōu)化最相鄰樣本集合的樣本揀選與數(shù)據(jù)存儲，在降低內(nèi)存消耗的同時保持其較高的學(xué)習(xí)檢測效率。

參考文獻：

[1] Mukkamala S，Janowski G.Identifying important features for intrusion detection using support vector machines and neural networks[J].Proceedings of Applications and the Internet， 2003， 14（4）.

[2] Syed N， Liu H. Sung K Incremental Learning with Support Vector Machines[J].Proceedings of IJCAI Conference， Sweden， 2000.

[3] 段丹青.入侵檢測算法及關(guān)鍵技術(shù)[D].長沙：中南大學(xué)學(xué)位論文， 2007.

[4] 于靜，王輝.改進支持向量機在網(wǎng)絡(luò)入侵中的應(yīng)用[J].微電子學(xué)與計算機， 2012， 29（3）.

[5] 張永俊，牟琦，畢孝儒.基于云模型的增量SVM入侵檢測方法[J].計算機應(yīng)用與軟件， 2013， 30（3）.

[6] 周偉達，張莉，焦李成.支撐矢量機推廣能力分析[J].電子學(xué)報， 200l：590-594.

[7] 王曉丹，鄭春穎，吳崇明. 一種新的SVM對等增量學(xué)習(xí)算法[J].計算機應(yīng)用， 2006， 26 （10）.

[8] 范明，孟小峰.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機械工業(yè)出版社， 2008.

[9] KDD99 cupdataset. http：//kdd.ics.uci.edu /databases /kddcup99/kddcup99.html， 2014.

[10] LibSVM. www.csie.ntu.edu.tw/～cjlin/libsvm， 2014.

1） 檢查E中是否存在違背V的廣義KKT條件的樣本，如無，則算法終止，輸出V為增量訓(xùn)練結(jié)果；如有，則將E劃分為與；

2） 計算E中正負類的最相鄰集合，并基于此計算其分類器V；

3） 檢測E中是否存在違背V的廣義KKT條件樣本，如無，算法停止，輸出V為增量訓(xùn)練結(jié)果；如有，則將E劃分為與；

4） 合并、以及E、E的支撐向量集，針對其合集進行正負類最相鄰集合裁剪，繼而對該合并集合進行訓(xùn)練，并輸出其分類器為增量學(xué)習(xí)結(jié)果。

3 實驗與分析

本文采用了KDDCup99測試數(shù)據(jù)集[9]對上述方法進行了驗證，其樣本共計41個特征屬性，共計DOS（拒絕服務(wù)攻擊）、R2L（遠程權(quán)限獲?。?、U2R（用戶權(quán)限提升攻擊）、Probing（端口及漏洞掃描）等4大類攻擊行為。

仿真實驗采用Libsvm[10]與C++實現(xiàn)，其采用了RBF核函數(shù)，其中取0.98。整個實現(xiàn)采用了交叉對比的方式，其比較對象為一般的全樣本SVM學(xué)習(xí)器。其實現(xiàn)結(jié)果如下表所示。

表1 一般SVM算法仿真實驗結(jié)果

[訓(xùn)練樣本數(shù)＼&訓(xùn)練時間（s）＼&測試時間（ms）＼&分類準(zhǔn)確度（%）＼&50＼&0.094＼&0.994＼&99.21＼&1000＼&0.297＼&0.1219＼&99.75＼&20000＼&8.437＼&0.3047＼&99.95＼&100000＼&232.141＼&0.5766＼&99.98＼&]

表2 基于聚類分析的增量支撐向量機仿真實驗結(jié)果

[訓(xùn)練樣本數(shù)＼&聚類數(shù)量＼&訓(xùn)練時間（s）＼&測試時間（ms）＼&分類準(zhǔn)確度（%）＼&100000＼&10＼&29.763＼&0.1206＼&99.946＼&100000＼&50＼&44.721＼&0.0832＼&99.958＼&100000＼&100＼&126.813＼&0.0921＼&99.971＼&]

由表可見，在訓(xùn)練樣本數(shù)為100000的場合下，該文算法的訓(xùn)練時間與測試時間均大大低于一般SVM全量學(xué)習(xí)算法，與此同時，其分類準(zhǔn)確率在聚類數(shù)量足夠的情況下，也基本達到了標(biāo)準(zhǔn)SVM算法同等的水平。同時還值得指出的是，隨著聚類數(shù)量的增多，該文算法所得分類檢測率是遞增的，這與我們的直覺是相符的。上述實驗充分說明了本文方法在大訓(xùn)練樣本量場景下的有效性與適用性。

4 結(jié)論與下一步工作

本文提出了一種基于聚類分析的增量SVM相結(jié)合的的多類型入侵檢測學(xué)習(xí)方法，該方法通過采用了一種基于樣本分布的改

（下轉(zhuǎn)第4432頁）

（上接第4420頁）

進K-Means聚類方式來針對訓(xùn)練樣本進行歸類，同時提出了一種基于最相鄰樣本集合的訓(xùn)練樣本裁剪方法，并將上述裁剪方式與廣義KKT條件判定相結(jié)合，提出了一個多類別增量SVM學(xué)習(xí)方法。分析與實驗表明，上述方法可顯著改善大訓(xùn)練樣本量下SVM分類器訓(xùn)練時間長、學(xué)習(xí)速度慢的問題，同時有效保障了系統(tǒng)檢測能力的持續(xù)優(yōu)化與更新。

下一步工作包括：進一步評估新增樣本對聚類分析結(jié)果的影響，以進一步提升多類別SVM訓(xùn)練、檢測性能；嘗試結(jié)合采用超球、軟邊界等其他裁剪算法，優(yōu)化最相鄰樣本集合的樣本揀選與數(shù)據(jù)存儲，在降低內(nèi)存消耗的同時保持其較高的學(xué)習(xí)檢測效率。

參考文獻：

[1] Mukkamala S，Janowski G.Identifying important features for intrusion detection using support vector machines and neural networks[J].Proceedings of Applications and the Internet， 2003， 14（4）.

[2] Syed N， Liu H. Sung K Incremental Learning with Support Vector Machines[J].Proceedings of IJCAI Conference， Sweden， 2000.

[3] 段丹青.入侵檢測算法及關(guān)鍵技術(shù)[D].長沙：中南大學(xué)學(xué)位論文， 2007.

[4] 于靜，王輝.改進支持向量機在網(wǎng)絡(luò)入侵中的應(yīng)用[J].微電子學(xué)與計算機， 2012， 29（3）.

[5] 張永俊，牟琦，畢孝儒.基于云模型的增量SVM入侵檢測方法[J].計算機應(yīng)用與軟件， 2013， 30（3）.

[6] 周偉達，張莉，焦李成.支撐矢量機推廣能力分析[J].電子學(xué)報， 200l：590-594.

[7] 王曉丹，鄭春穎，吳崇明. 一種新的SVM對等增量學(xué)習(xí)算法[J].計算機應(yīng)用， 2006， 26 （10）.

[8] 范明，孟小峰.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機械工業(yè)出版社， 2008.

[9] KDD99 cupdataset. http：//kdd.ics.uci.edu /databases /kddcup99/kddcup99.html， 2014.

[10] LibSVM. www.csie.ntu.edu.tw/～cjlin/libsvm， 2014.

1） 檢查E中是否存在違背V的廣義KKT條件的樣本，如無，則算法終止，輸出V為增量訓(xùn)練結(jié)果；如有，則將E劃分為與；

2） 計算E中正負類的最相鄰集合，并基于此計算其分類器V；

3） 檢測E中是否存在違背V的廣義KKT條件樣本，如無，算法停止，輸出V為增量訓(xùn)練結(jié)果；如有，則將E劃分為與；

4） 合并、以及E、E的支撐向量集，針對其合集進行正負類最相鄰集合裁剪，繼而對該合并集合進行訓(xùn)練，并輸出其分類器為增量學(xué)習(xí)結(jié)果。

3 實驗與分析

本文采用了KDDCup99測試數(shù)據(jù)集[9]對上述方法進行了驗證，其樣本共計41個特征屬性，共計DOS（拒絕服務(wù)攻擊）、R2L（遠程權(quán)限獲?。?、U2R（用戶權(quán)限提升攻擊）、Probing（端口及漏洞掃描）等4大類攻擊行為。

仿真實驗采用Libsvm[10]與C++實現(xiàn)，其采用了RBF核函數(shù)，其中取0.98。整個實現(xiàn)采用了交叉對比的方式，其比較對象為一般的全樣本SVM學(xué)習(xí)器。其實現(xiàn)結(jié)果如下表所示。

表1 一般SVM算法仿真實驗結(jié)果

[訓(xùn)練樣本數(shù)＼&訓(xùn)練時間（s）＼&測試時間（ms）＼&分類準(zhǔn)確度（%）＼&50＼&0.094＼&0.994＼&99.21＼&1000＼&0.297＼&0.1219＼&99.75＼&20000＼&8.437＼&0.3047＼&99.95＼&100000＼&232.141＼&0.5766＼&99.98＼&]

表2 基于聚類分析的增量支撐向量機仿真實驗結(jié)果

[訓(xùn)練樣本數(shù)＼&聚類數(shù)量＼&訓(xùn)練時間（s）＼&測試時間（ms）＼&分類準(zhǔn)確度（%）＼&100000＼&10＼&29.763＼&0.1206＼&99.946＼&100000＼&50＼&44.721＼&0.0832＼&99.958＼&100000＼&100＼&126.813＼&0.0921＼&99.971＼&]

由表可見，在訓(xùn)練樣本數(shù)為100000的場合下，該文算法的訓(xùn)練時間與測試時間均大大低于一般SVM全量學(xué)習(xí)算法，與此同時，其分類準(zhǔn)確率在聚類數(shù)量足夠的情況下，也基本達到了標(biāo)準(zhǔn)SVM算法同等的水平。同時還值得指出的是，隨著聚類數(shù)量的增多，該文算法所得分類檢測率是遞增的，這與我們的直覺是相符的。上述實驗充分說明了本文方法在大訓(xùn)練樣本量場景下的有效性與適用性。

4 結(jié)論與下一步工作

本文提出了一種基于聚類分析的增量SVM相結(jié)合的的多類型入侵檢測學(xué)習(xí)方法，該方法通過采用了一種基于樣本分布的改

（下轉(zhuǎn)第4432頁）

（上接第4420頁）

進K-Means聚類方式來針對訓(xùn)練樣本進行歸類，同時提出了一種基于最相鄰樣本集合的訓(xùn)練樣本裁剪方法，并將上述裁剪方式與廣義KKT條件判定相結(jié)合，提出了一個多類別增量SVM學(xué)習(xí)方法。分析與實驗表明，上述方法可顯著改善大訓(xùn)練樣本量下SVM分類器訓(xùn)練時間長、學(xué)習(xí)速度慢的問題，同時有效保障了系統(tǒng)檢測能力的持續(xù)優(yōu)化與更新。

下一步工作包括：進一步評估新增樣本對聚類分析結(jié)果的影響，以進一步提升多類別SVM訓(xùn)練、檢測性能；嘗試結(jié)合采用超球、軟邊界等其他裁剪算法，優(yōu)化最相鄰樣本集合的樣本揀選與數(shù)據(jù)存儲，在降低內(nèi)存消耗的同時保持其較高的學(xué)習(xí)檢測效率。

參考文獻：

[1] Mukkamala S，Janowski G.Identifying important features for intrusion detection using support vector machines and neural networks[J].Proceedings of Applications and the Internet， 2003， 14（4）.

[2] Syed N， Liu H. Sung K Incremental Learning with Support Vector Machines[J].Proceedings of IJCAI Conference， Sweden， 2000.

[3] 段丹青.入侵檢測算法及關(guān)鍵技術(shù)[D].長沙：中南大學(xué)學(xué)位論文， 2007.

[4] 于靜，王輝.改進支持向量機在網(wǎng)絡(luò)入侵中的應(yīng)用[J].微電子學(xué)與計算機， 2012， 29（3）.

[5] 張永俊，牟琦，畢孝儒.基于云模型的增量SVM入侵檢測方法[J].計算機應(yīng)用與軟件， 2013， 30（3）.

[6] 周偉達，張莉，焦李成.支撐矢量機推廣能力分析[J].電子學(xué)報， 200l：590-594.

[7] 王曉丹，鄭春穎，吳崇明. 一種新的SVM對等增量學(xué)習(xí)算法[J].計算機應(yīng)用， 2006， 26 （10）.

[8] 范明，孟小峰.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機械工業(yè)出版社， 2008.

[9] KDD99 cupdataset. http：//kdd.ics.uci.edu /databases /kddcup99/kddcup99.html， 2014.

[10] LibSVM. www.csie.ntu.edu.tw/～cjlin/libsvm， 2014.