江澤濤，錢 藝，張少欽

(1. 桂林電子科技大學廣西圖像圖形與智能處理重點實驗室，廣西 桂林 541004；2. 南昌航空大學，江西 南昌 330063)

1 引言

隨著網(wǎng)絡的不斷發(fā)展，網(wǎng)絡安全的重要性日益突出。用于識別網(wǎng)絡中異常數(shù)據(jù)的入侵檢測系統(tǒng)扮演著越來越重要的角色。傳統(tǒng)分類算法更傾向于相對平衡的數(shù)據(jù)集，而實際入侵檢測系統(tǒng)數(shù)據(jù)集存在著數(shù)據(jù)類型不平衡，因此在處理不平衡數(shù)據(jù)類型時傳統(tǒng)分類算法往往注重整體準確率，從而導致少數(shù)類樣本的識別正確率偏低。

目前針對不平衡數(shù)據(jù)類型的研究主要包括數(shù)據(jù)預處理層面、特征層面和分類算法層面。在特征層面，通過特征選擇刪除不平衡數(shù)據(jù)中不具區(qū)分性的特征，增加數(shù)據(jù)間的區(qū)分度，提高分類的準確率。在分類算法層面，通過改進分類算法在處理不平衡數(shù)據(jù)的缺陷，結合不平衡數(shù)據(jù)的特點，對分類算法進行改進以提升分類的準確率。由于數(shù)據(jù)預處理層面的方法不依賴于分類器，具有通用性，因此本文將通過數(shù)據(jù)預處理層面方法，采用一定的策略來改變樣本的分布，以達到降低或解決數(shù)據(jù)類型不平衡性的問題。該方法包括過采樣和欠采樣兩種技術，其中欠采樣技術在數(shù)據(jù)集較小時可能會丟失數(shù)據(jù)集中的重要信息，因此過采樣技術是數(shù)據(jù)不平衡問題研究的重點。隨機過采樣是最簡單的過采樣方法，通過隨機復制少數(shù)類樣本達到少數(shù)類與多數(shù)類數(shù)量平衡的目的，該方法雖然簡單，但不能生成新樣本，容易造成過擬合。Chawla等提出的SMOTE(Synthetic Minority Over-sampling Technique)方法是過采樣中的經(jīng)典方法，該方法通過尋找少數(shù)類樣本的K個近鄰節(jié)點，然后從中隨機選擇一個近鄰節(jié)點，在少數(shù)類樣本點與選中的近鄰節(jié)點之間合成新樣本，但增加了類之間重疊的可能性。Han等提出了Borderline-SMOTE方法，該方法將少數(shù)類樣本點分為安全樣本，危險樣本和噪聲樣本三類，僅對危險樣本合成新樣本，該方法考慮到了少數(shù)類數(shù)據(jù)分布不均勻的情況，卻未邊界樣本的差異作出考慮。Douzas等提出了K-means SMOTE方法，將K-means聚類算法與SMOTE方法結合在一起，在聚類中過采樣能有效避免噪聲，該方法考慮到了少數(shù)類樣本的密度，但沒有考慮到少數(shù)類樣本的密度分布問題。

針對入侵檢測系統(tǒng)數(shù)據(jù)集數(shù)據(jù)不平衡的情況，本文從數(shù)據(jù)采樣層面出發(fā)，在K-means SMOTE方法的基礎上做進一步改進，提出了一種基于最高密度點過采樣方法(Highest Density Point SMOTE，HDP-SMOTE)方法。該方法根據(jù)少數(shù)類的最高密度點對聚類劃分出密集區(qū)域和非密集區(qū)域，并對不同區(qū)域采取不同的方法進行過采樣，可以有效地增強決策邊界，改善樣本點的分布，達到提升分類器性能的目的。本文使用隨機森林(Random Forest)算法作為基準分類器，選用precision(查準率)、recall(召回率)、F1-score和G-mean作為評價指標，在入侵檢測系統(tǒng)常用的NSL-KDD和UNSW-NB15數(shù)據(jù)集上進行測試。實驗結果表明，使用本文提出的方法進行數(shù)據(jù)過采樣后，分類方法能對入侵檢測數(shù)據(jù)進行有效的分類，方法的整體性能較好。

2 基于最高密度點的入侵檢測數(shù)據(jù)過采樣方法

2.1 相關理論介紹

2.1.1 SMOTE方法

SMOTE(Synthetic Minority Oversampling Technique)是最經(jīng)典的過采樣方法，現(xiàn)在許多過采樣方法都是以它為原型提出的。該方法的主要步驟如下：

1)對于每一個少數(shù)類樣本

x

，計算它到其它所有少數(shù)類樣本的歐氏距離，如式(1)所示，并使用KNN算法尋找與該樣本點的K近鄰。

(1)

(2)

3)將新合成的樣本與原樣本合并，構成新的數(shù)據(jù)集。

2.1.2 K-means SMOTE方法

K-means SMOTE方法將K-means和SMOTE相結合，來解決數(shù)據(jù)不平衡問題。該方法僅在安全區(qū)域進行過采樣避免了噪聲的產(chǎn)生。由于K-means以及SMOTE的被廣泛使用的特性，該方法易于實現(xiàn)。該方法的主要步驟如下：

首先，使用K-means方法將數(shù)據(jù)集分為k個聚類。

然后，根據(jù)每個聚類在少數(shù)類和多數(shù)類中所占個數(shù)計算聚類的不平衡率，如式(3)所示。當該聚類的不平衡率達到閾值時對此進行過采樣，否則放棄過采樣。默認閾值為1，即少數(shù)類樣本數(shù)至少達到50

%

。其中

maj

＿

count

表示多數(shù)類個數(shù)，min＿

count

表示少數(shù)類個數(shù)。

(3)

最后，使用SMOTE對每個過濾后的聚類進行過采樣。

2.2 HDP-SMOTE的計算結構設計

為了避免潛在生成樣本丟失，增強決策邊界，提升分類器性能，更好地解決不同類型數(shù)據(jù)的不平衡問題，在K-means SMOTE方法中，若其聚類未達到閾值

t

(默認情況下閾值

t

為1，即少數(shù)類樣本至少占50

%

)將不會生成樣本，但其中可能含有新的樣本，則會導致潛在樣本的丟失。則本文在K-means SMOTE的結構基礎上改進，提出了HDP-SMOTE方法，增加聚類細分步驟，如圖1所示。

圖1 HDP-SMOTE方法的計算結構圖

圖1的創(chuàng)新思想是對未達到閾值t的聚類進行再次篩選，從而避免潛在生成樣本丟失。HDP-SMOTE方法前期與K-means Smote方法一樣，需要進行聚類步驟和過濾步驟；其創(chuàng)新點在于當聚類中少數(shù)類樣本不平衡率低于閾值

t

時，計算聚類的最高密度點和類內(nèi)平均距離；當樣本點與最高密度點的距離大于類內(nèi)平均距離則劃為非密集區(qū)點，反之劃為密集區(qū)點；在劃分密集區(qū)與非密集區(qū)之后，再計算該密集區(qū)的不平衡率；當不平衡率大于閾值

t

，進入過采樣操作；當不平衡率小于閾值

t

說明密集區(qū)中的少數(shù)類樣本點占比很少則會放棄過采樣。HDP-SMOTE方法針對密集區(qū)中的少數(shù)類樣本點較為稀疏和較為密集兩種情況分別進行處理，3.2節(jié)與3.3節(jié)對這兩種情況進行分別闡述。

2.3 針對密集區(qū)內(nèi)的少數(shù)類樣本點較為稀疏的方案

為了解決密集區(qū)內(nèi)少數(shù)類樣本較為稀疏情況的生成樣本丟失問題，本文通過計算聚類中的最高密度點和類內(nèi)平均距離將區(qū)域劃分為密集區(qū)和非密集區(qū)，提出了針對密集區(qū)內(nèi)的少數(shù)類樣本點較為稀疏的方案。

在K-means SMOTE方法中，如果聚類中少數(shù)類個數(shù)未達到閾值t比例會放棄在該聚類中進行過采樣，造成潛在新樣本的丟失。本節(jié)在K-means SMOTE方法基礎上增加了聚類細分步驟，針對少數(shù)類無法達到閾值t比例的情況，基于最高密度點和類內(nèi)平均距離將原本少數(shù)類較為稀疏的聚類范圍縮小到少數(shù)類較為密集的區(qū)域，增加了少數(shù)類樣本被過采樣的可能性。

1)計算聚類中少數(shù)類的最高密度點

首先使用式(4)計算兩樣本點之間的歐氏距離

D

(

x

，

x

)，其中

x

，

x

是少數(shù)類樣本集合

D

中任意兩個樣本點，

d

表示特征維數(shù)，

k

表示當前特征維數(shù)。

(4)

其次使用式(5)計算

x

的密度

Density

(

x

)，其中

p

表示當前區(qū)域中總的少數(shù)類樣本個數(shù)，

Density

(

x

)越大時表示樣本周圍的樣本越多。

?

x

∈

D

(

i

∈{1，2，…，

p

})

(5)

繼而尋找少數(shù)類樣本點中最高密度點，如式(6)所示

(6)

2)計算類內(nèi)平均距離，根據(jù)最高密度點劃分密集區(qū)

接著計算類內(nèi)平均距離

dist

＿

aver

，類內(nèi)平均距離實際是指每兩點之間歐幾里得距離的平均距離，如式(7)所示

(7)

隨后根據(jù)最高密度點與類內(nèi)平均距離將樣本劃分為密集區(qū)和非密集區(qū)，如式(8)所示。若樣本點與最高密度點的距離大于類內(nèi)平均距離，該樣本點屬于非密集區(qū)，記為

Spar

＿

area

；否則屬于密集區(qū)，記為

Den

＿

area

，如式(5)所示。最后將少數(shù)類樣本未達閾值

t

的聚類用此聚類中的密集區(qū)替代計算，使之擁有更高的少數(shù)類占比。在劃分密集區(qū)和非密集區(qū)后，可以增大密集區(qū)內(nèi)合成少數(shù)類樣本的密度，在一定程度上達到增強決策邊界的目的。

(8)

圖2中描述了HDP-SMOTE方法的五個步驟。步驟1)輸入數(shù)據(jù)，將輸入數(shù)據(jù)讀入。步驟2)聚類步驟，將輸入數(shù)據(jù)聚為四個區(qū)域并使用式(3)計算這四個區(qū)域的不平衡率

IR

(其中

i

代表不平衡率的計算范圍)，得到

IR

()=3

/

8，

IR

()=8

/

7，

IR

()=8

/

9，

IR

()=7

/

9(

IR

()，

IR

()，

IR

()，

IR

()分別表示區(qū)域(

a

)，(

b

)，(

c

)，(

d

)的不平衡率)。其中min＿

count

代表少數(shù)類樣本個數(shù)，

maj

＿

count

代表多數(shù)類樣本個數(shù)。步驟3)聚類細分步驟，計算(

c

)和(

d

)區(qū)域中少數(shù)類樣本最高密度點和類內(nèi)平均距離劃分密集區(qū)，分別得到區(qū)域(

c

)的密集區(qū)(

c

)和非密集區(qū)(

c

)，區(qū)域(

d

)的密集區(qū)(

d

)和非密集區(qū)(

d

)，兩個密集區(qū)的不平衡率為

IR

()=6

/

4和

IR

()=5

/

4(

IR

()，

IR

()分別表示區(qū)域(

c

)，(

d

)的不平衡率)。

圖2 HDP-SMOTE方法圖

步驟4)過濾步驟和步驟5)過采樣步驟，篩選符合條件的聚類進行過采樣。

IR

()<閾值

t

，放棄采樣；

IR

()>閾值

t

，直接進行Kmeans-SMOTE采樣；

IR

()和

IR

()小于閾值

t

，在原K-means SMOTE中不能進行采樣，當

IR

()，

IR

()不小于閾值

t

時可以通過本文提出的方法進行采樣。根據(jù)密集區(qū)中少數(shù)類樣本點的占比分別采用少數(shù)類樣本點較為稀疏和較為密集的方案進行過采樣操作。如圖2中2)的(

d

)區(qū)域圖所示，根據(jù)式(6)計算得知

IR

()=7

/

9，該聚類中雖有大量少數(shù)類樣本具有生成樣本的條件，但由于少數(shù)類樣本所占比例沒有達到閾值

t

，在經(jīng)過K-means SMOTE的過濾步驟時該聚類會被過濾掉，造成潛在新樣本的丟失。對于這類情況，HDP-SMOTE方法會通過最高密度點和類內(nèi)平均距離劃出該聚類的少數(shù)類密集區(qū)來代替原聚類范圍，如圖2中3)的(

d

)區(qū)域所示。對密集區(qū)進行過濾和過采樣步驟，通過計算找到聚類中的最高密度點(被標注下劃線的×)，分別以最高密度點和類內(nèi)平均距離為中心和距離繪制密集區(qū)，密集區(qū)的

IR

()=5

/

4達到閾值

t

條件，可以通過過濾步驟進行過采樣，以達到避免潛在新樣本的丟失的目的。

2.4 針對密集區(qū)內(nèi)的少數(shù)類樣本點較為密集的方案

針對密集區(qū)內(nèi)的少數(shù)類樣本點較為密集的情況使用3

.

2節(jié)中的方法來解決，可能會引起的樣本重疊問題，本節(jié)針對密集區(qū)內(nèi)的少數(shù)類樣本點較為密集的情況提出解決方案。該方案的生成區(qū)域不再局限于密集區(qū)，也包括非密集區(qū)。該方案通過將該聚類的生成數(shù)分散到密集區(qū)和非密集區(qū)中，來避免樣本重疊問題。該方案與其它方法不同的是在密集區(qū)采用傳統(tǒng)的SMOTE方法進行過采樣，在非密集區(qū)拋棄了傳統(tǒng)的將目標樣本分組的思想，采用放射型SMOTE方法，使得在非密集區(qū)域只關注該聚類中目標類樣本的最高密度點和非密集區(qū)的樣本點。

該方案如圖2所示，其中(3)-(4)圖的(c)區(qū)域使用了該方案。該方案在前一個方案的過濾步驟和過采樣步驟提出的。具體如下：

首先使用式(9)計算生成樣本的距離比值，其中x表示非密集區(qū)少數(shù)類樣本點，rand(0，1)表示(0，1)之間的隨機數(shù)。

(9)

其次在非密集區(qū)少數(shù)類樣本點

x

與最高密度點

x

max＿之間的非密集區(qū)內(nèi)做線性插值得到新生成的少數(shù)類樣本

x

，如式(10)所示。最后將新生成的少數(shù)類樣本與原始訓練樣本合并，構成新的訓練樣本集。

x

=

x

+(

x

max＿-

x

)×

δ

(10)

兩個方案是根據(jù)密集區(qū)內(nèi)少數(shù)類樣本的密集程度提出的，它們的思想是一致的，都是從少數(shù)類占比較低的聚類中生成樣本，圍繞最高密度點生成，能更好的改善樣本點的分布，提升分類器的性能。

3 實驗

實驗環(huán)境為Windows Server 2016 操作系統(tǒng)、Intel Xeon E5-2620 V3 2.4GHZ、64GB內(nèi)存，編譯環(huán)境為Python 3.6.5。

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

實驗數(shù)據(jù)集選用當今入侵檢測系統(tǒng)領域普遍認可的NSL-KDD和UNSW-NB15數(shù)據(jù)集進行實驗。

3.1.1 NSL-KDD數(shù)據(jù)集

NSL-KDD數(shù)據(jù)集是在KDD CUP 99數(shù)據(jù)集基礎上改進后的數(shù)據(jù)集。NSL-KDD數(shù)據(jù)集解決了KDD CUP99數(shù)據(jù)集存在的數(shù)據(jù)冗余問題，使得分類器在對訓練集的學習過程中不再偏向頻繁出現(xiàn)的記錄。NSL-KDD數(shù)據(jù)集是KDD數(shù)據(jù)集系列中最優(yōu)秀的代表。

表1 NSL-KDD數(shù)據(jù)集

NSL-KDD共包括五種攻擊類型：Normal、Probe、DOS、U2R和R2L。U2R和R2L攻擊數(shù)據(jù)不同于DOS和probe攻擊，它們在短時間內(nèi)向同一個目的主機發(fā)起大量連接，而U2R和R2L攻擊在連接記錄中沒有明顯的頻繁連續(xù)攻擊模式，這兩種攻擊行為嵌入在報文的數(shù)據(jù)部分，通常只涉及單個連接，因此所占比例較少。

由表1可知，訓練集的各類攻擊數(shù)據(jù)中，DOS類型數(shù)量為45927，R2L和U2R類型數(shù)量為995和52，相差46和883倍。NSL-KDD訓練集數(shù)據(jù)分布存在極度不均衡，分類算法會偏向于高頻數(shù)據(jù)，但占比較少的攻擊類型如U2R攻擊往往對網(wǎng)絡的危害更大。

3.1.2 UNSW-NB15數(shù)據(jù)集

NSL-KDD雖然是被目前所普遍使用的數(shù)據(jù)集，但它的基準數(shù)據(jù)集產(chǎn)生于二十年前，根據(jù)大量的研究表明，NSL-KDD數(shù)據(jù)集不能很好的反映現(xiàn)代網(wǎng)絡的特點。本文引用了新一代UNSW-NB15數(shù)據(jù)集，它是于2015年由澳大利亞網(wǎng)絡安全中心Cyber Range實驗室推出的用于評估網(wǎng)絡入侵檢測的綜合數(shù)據(jù)集。在UNSW-NB15數(shù)據(jù)集中存在38.55%的重復數(shù)據(jù)，為了避免生成重復數(shù)據(jù)，影響評判指標的準確性，在本次實驗中對UNSW-NB15數(shù)據(jù)集進行了去重處理。

由表2可知，訓練集的各類攻擊數(shù)據(jù)中，DOS類型數(shù)量為19844，Worms和Shellcode類型數(shù)量為127和1091，相差156和18倍。雖然UNSW-NB15數(shù)據(jù)集的分布也存在不平衡，但優(yōu)于NSL-KDD數(shù)據(jù)集。

表2 UNSW-NB15數(shù)據(jù)集

3.2 實驗結果與分析

一般分類方法是以accuracy(準確率)作為評價指標。當樣本的分布不平衡時，由于少數(shù)類樣本對整體準確率的影響較小，即使分類算法將全部樣本都被視為多數(shù)類，仍然可以獲得較高的準確率，因此僅使用準確率作為評價指標，很難準確地反映出不平衡數(shù)據(jù)集的分類性能。

本文使用評估不平衡數(shù)據(jù)的分類性能時常用的precision(查準率)、recall(召回率)、F1-score和G-mean作為評價指標。

precision是指正確預測的正樣本數(shù)占所有預測為正樣本的數(shù)量的比值。它只關注預測為正樣本的部分，所有預測為正樣本的樣本中有多少是真正的正樣本。定義如下

(11)

recall是指正確預測的正樣本數(shù)占真實正樣本總數(shù)的比值，定義如下

(12)

F1-score綜合考慮了precision(查全率)和recall(召回率)，是兩者的一種調(diào)和平均，對不平衡類別非常有用的一種評價指標，定義如下

(13)

G-means也綜合了查全率(precision)和查全率(recall)，是兩者的幾何平均數(shù)，定義為

(14)

其中：TP(true positive)為正確識別的正樣本數(shù)，TN(true negative)為正確識別的負樣本數(shù)，F(xiàn)P(false positive)為錯誤識別的正樣本數(shù)，F(xiàn)N(false negative)為錯誤識別的負樣本數(shù)。

為使模型能達到最佳效果，需要針對不同數(shù)據(jù)集確定K-means算法用到的k1值和Smote方法中KNN算法用到的k2值。

對于K-means聚類中的k1值，本文使用手肘法(Elbow Method)和輪廓系數(shù)法(silhouette coefficient)來相結合的方式縮小k1值的取值范圍。k2值一般取一個比較小的值，這里將(2，3，4，5，6，7)作為候選值。最終采用交叉驗證法來選取最優(yōu)的k1和k2值。

根據(jù)手肘法可確定KDD和UNSW數(shù)據(jù)集的k1值取值范圍分別為(2～12)和(2～9)，結合輪廓系數(shù)法可將取值范圍縮小至(2～9)和(2，4，5)。兩個數(shù)據(jù)集的k2值取值范圍設定在(2～7)。采用交叉驗證法，最終確定兩個數(shù)據(jù)集k1，k2的取值范圍為(6，4)和(4，5)。

本文實驗將SMOTE、K-means Smote(表3中簡稱為KMS)和HDP-SMOTE三種采樣方法分別與經(jīng)典的隨機森林分類算法相結合進行實驗對比。為了驗證過采樣的有效性，加入隨機森林算法未結合任何采樣方法的分類結果作為對比。實驗首先對數(shù)據(jù)集進行數(shù)值化處理，然后采用十折交叉驗證作為評估方法，分別運行50次取平均值。兩組數(shù)據(jù)集的實驗結果如表3和表4所示，分別列出不同算法在各類攻擊數(shù)據(jù)的precision、recall、F1-score和G-mean的值。表中加粗項代表性能最佳的方法。

表3 不同方法在NSL-KDD數(shù)據(jù)集的評估結果

表4 不同方法在UNSW-NB15數(shù)據(jù)集的評估結果

如3.1節(jié)中提到的HDP＿SMOTE方法包括針對密集區(qū)內(nèi)的少數(shù)類樣本點較為稀疏和較為密集兩種情況的實現(xiàn)。若密集區(qū)少數(shù)類個數(shù)與多數(shù)類個數(shù)的不平衡率達到閾值t，并且使用式(13)計算密集區(qū)中少數(shù)類個數(shù)占聚類中少數(shù)類總數(shù)之比MCP是否超過閾值t2(默認情況下閾值t2為70%，即密集區(qū)中的少數(shù)類個數(shù)至少占聚類中少數(shù)類總數(shù)的70%)，若MCP超過閾值t2說明密集區(qū)內(nèi)的少數(shù)類樣本點過于密集，可能會引起樣本重疊的問題，選用第二種方案。該方法可以將生成數(shù)量分散到密集區(qū)和非密集區(qū)中來避免這個問題。若密集區(qū)中少數(shù)類個數(shù)沒有超過閾值t2，則選用第一種方案。

(15)

從表3和表4可以看出，K-means SMOTE方法用于入侵檢測系統(tǒng)數(shù)據(jù)集的過采樣效果雖然優(yōu)于原始數(shù)據(jù)集，但效果不如SMOTE方法。本文提出的兩個方法，均是基于K-means SMOTE方法提出，而效果明顯優(yōu)于其它方法。SMOTE方法對少數(shù)類樣本不加區(qū)分地進行過采樣，雖然能提升少數(shù)類樣本的評價指標，但整體表現(xiàn)一般，這是因為SMOTE方法進行插值運算時沒有考慮到樣本的分布問題。K-means SMOTE方法雖然通過對整個數(shù)據(jù)集劃分子類的方式考慮到了子類分布的問題，只有當聚類中少數(shù)類個數(shù)達到閾值t時，對該聚類中的少數(shù)類使用SMOTE方法進行過采樣；若少數(shù)類的數(shù)量未達到閾值t時會忽略該聚類，造成潛在新樣本的丟失。

4 結束語

本文提出的HDP-SMOTE方法是在K-means SMOTE方法基礎上改進得到的。該方法在一定程度上彌補了潛在新樣本的丟失問題。針對不同情況該方法提供了密集和稀疏兩種數(shù)據(jù)過采樣方案，能夠有針對性的進行新樣本的生成，更好的改善樣本點的分布。在入侵檢測系統(tǒng)的主流數(shù)據(jù)集上與其它采樣方法相比，該方法有著較為明顯的優(yōu)勢。本文方法比其它采樣方法能有效地解決數(shù)據(jù)不平衡問題，但該方法依然存在噪聲樣本。

如何將欠采樣方法和過采樣方法有效地結合起來，剔除破壞樣本分布的噪聲樣本和異常點是今后研究的方向。