改進的二叉決策樹多分類算法在入侵檢測中的應用

劉銘 南西

摘要：網絡安全問題日益嚴峻，入侵檢測作為主要的網絡防范手段之一，但多分類的檢測普遍存在檢測率低漏報誤報率高的問題，本文結合入侵檢測數據中正常數據的數據量遠大于異常數據的特點，并根據類間分離性算法確定不同攻擊類型的分離順序，構造性能優良的二叉樹結構，有效提高入侵檢測的性能。

關鍵詞：入侵檢測;支持向量機;多分類;分離性測度;二叉樹

中圖分類號：TP393? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）24-0033-02

開放科學（資源服務）標識碼（OSID）：

隨著互聯網技術的日益發展和普及，人們在享受網絡帶來極大便利的同時，網絡安全問題也日益突出。為了更好地利用網絡，迫切需要提高網絡安全相關防范技術。

入侵檢測系統（Intrusion Detection System ，IDS）作為防火墻之后的第二道防線，具有主動性和實時性的特點，在網絡關鍵節點上收集信息并進行分析，從而對異常行為做出判別[1]。支持向量機（Support Vector Machine， SVM）作為一種在小樣本機器學習基礎上發展起來的方法，應用于網絡入侵檢測系統有較好的檢測性能。二叉樹法為常用的SVM多分類方法有結構靈活，所需構造的分類器數少，從根節點往下，訓練樣本數和支持向量數都逐級減少，檢測速度較快[2]。

本文在分析二叉樹多分類的基礎上，提出基于分離性測度的SVM多分類方法，根據類間分離性算法確定不同攻擊類型的分離順序，構造性能優良的二叉樹。

1 改進的決策樹多分類方法

目前，如何根據相關應用構造合理性能優良的二叉樹結構并沒有具體的定義。分類器的分類性與二叉樹的構建過程密切相關，上層節點的分類性能對整個分類模型的影響最大，在分類過程中，盡量減少在上層節點出現分類錯誤。在二叉樹的構造過程中，容易區分，不易產生分類錯誤的類在上層分類器中優先分離，逐層進行分析，使可能產生的分類錯誤盡量遠離上層節點，使其對整體產生的影響降至最小。

類間分離性算法定義

如何確定各類的分離順序，各類的易分性，目前通常將類中心間的歐氏距離或馬氏距離作為不同類間的測度。但該方法在很多情況下并不能正確反映類間的分離度，類的分布對類間的分離性也有著重要影響?；陬惖姆植碱愰g分離性測度[3]定義如下。

假設要進行M類分類，則樣本類別數為M，訓練樣本集由類[Xi，i=1，???，M]組成。通過訓練樣本計算得出類中心[ci]，

[ci=1nix∈Xix，i=1，???，M];? （[ni]為類[Xi]中樣本的個數）? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1）

[dij]表示類[i]與類[j]中心間的距離：

[dij=ci-cj，i，j=1，???，M];? ? ? ? ? ? ? ? ? （2）

[σi]表示類分布的類方差：

[σi=1ni-1x∈Xix-ci，i=1，???，M];? ? ? ? ? ? ? ? ?（3）

定義1：（類間分離度）類i和類j間的分離性測度[sepij]：

[sepij=dij（σi+σj）]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （4）

若[sepij≥1]，說明兩類之間無交疊;如果[sepij<1]，則兩類之間有一定交疊。類i與類j之間的分離性越好則[sepij]的值越大。

定義2：（類分離度）類i的分離性測度[sepi]：

[sepi=minsepijj=1，???，kj≠i]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （5）

[sepi]表明了該類與其他類間的分離性。

定義3：（類易分性）最易分的類s：

[s=argmaxsepii=1，???，k]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （6）

最容易分的類即為計算得到的分離性測度值最大的類。

改進的決策樹多分類SVM算法

改進的決策樹多分類SVM算法具體流程如下：

步驟1：根據上述公式（1）（2）（3）計算各類的相關參數，并根據公式（4）（5）得出各類樣本數據的類間分離度[sepij]和類的分離性測度[sepi]。

步驟2：比較得到的各類分離度，由大到小進行排列， [n1，n2，???，nM]，其中[ni∈1，2，???，M，i=1，2，???，M]為類的標號，分離性測度最大的類即最容易分的類。

步驟3：在二叉樹各節點利用SVM二分類算法構造最優超平面，利用改進的人工蜂群優化支持向量機算法[4]對SVM的相關參數進行優化。

步驟4：構造第一個分類器，在根節點選擇最容易分的類即分離性測度值最大的n1類作為正樣本集，其余各類數據為負樣本集，然后從總樣本集中將分離的正樣本集刪除，以此類推，按照此方法構造其余的分類器。如果有兩個類得出的分離性測度值相同，則兩類的分離順序不會對整體的分類效果產生實質的影響，算法選擇優先分離類標號較小的類，最終構造出改進后的二叉樹多分類SVM模型。

2 基于改進二叉決策樹多分類入侵檢測實驗

本文選用NSL-KDD數據集作為實驗數據集，該數據集將數據分為正常的數據NORMAL類和DOS、PROBE、U2R、R2L四類異常的攻擊數據[5]。數據集包含訓練集和測試集，分為正常數據和入侵異常數據。根據各類型數據的比例選取部分數據并進行標準化預處理進行實驗，實驗數據類型分布如表1所示。

在實際的網絡環境中，正常數據在總數據中所占的比例遠遠大于異常數據（1%-2%）。整個二叉樹每個節點分類器的不同會影響到分類器的分類性能，結合網絡環境中入侵檢測數據的實際特點，檢測數據輸入后，首先判斷是否為入侵數據，若為正常數據，則直接分離;如果判斷為入侵數據，則通過下層分類器繼續進行分離。

在二叉樹的構建過程中應充分考慮四種攻擊類型之間的關聯性，通過上述定義的類間分離性算法計算得到每個攻擊類別的易分性，并根據結果構造二叉樹。根據定義，本實驗通過java編程，使用eclipse平臺，最終得到DOS、PROBE、U2R和R2L四類的最小分離性測度值如表2所示：

考慮各類的易分性，根據類間分離性算法定義，結合表中數據可知，DOS類最易分離，不容易出現分類錯誤，將其在最上層節點進行分離。將U2R和R2L兩種類別這兩類放到最后分離。由此構造的二叉樹分離順序可以使分類過程中產生的錯誤遠離根節點，使其對整體性能產生的影響降至最小。根據類分離算法構建的入侵檢測的二叉樹結構圖如圖1所示。

3 結束語

針對目前各種攻擊類型不易區分導致入侵檢測系統檢測正確率較低，誤報率較高的問題，本文提出一種基于分離性測度的二叉決策樹多類入侵檢測方法，首先分離數據量最多的正常數據，對異常數據分類時，二叉決策樹構建的過程根據類的分離性測度，逐層選擇當前最易分的類進行分離，通過這種方法對二叉樹多分類算法進行改進，提出合理有效的二叉樹結構，有效地提高入侵檢測的性能。

參考文獻：

[1] 王貴珍，曲天光.入侵檢測系統研究與發展概述[J]. 保密科學技術， 2019（2）.

[2] 劉銘. 基于CMABC參數優化的SVM多分類入侵檢測方法研究[D]. 廣西大學， 2015.

[3] Wang X D， Wu C M. Using improved SVM decision tree to classify HRRP[C]//2005 International Conference on Machine Learning and Cybernetics. IEEE， 2005（7）： 4432-4436.

[4] 劉銘， 黃凡玲， 傅彥銘，等. 改進的人工蜂群優化支持向量機算法在入侵檢測中的應用[J]. 計算機應用與軟件， 2017（1）.

[5] 劉金平，何捷舟，馬天雨，等.基于KELM選擇性集成的復雜網絡環境入侵檢測[J].電子學報，2019，47（5）.

【通聯編輯：光文玲】