基于伽馬內(nèi)核與加權(quán)K近鄰的流量分類算法

徐 魁，海 洋，許藝凡，段靖海，孫煒策，陶 軍

(1.寶雞市公安局通信處，陜西 寶雞 721014;2.東南大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，江蘇 南京 211189;3.計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室(東南大學(xué))，江蘇 南京 211189)

0 引 言

網(wǎng)絡(luò)安全逐漸成為當(dāng)今信息化社會(huì)的焦點(diǎn)問題，目前網(wǎng)絡(luò)上存在的攻擊種類相當(dāng)多，例如拒絕服務(wù)攻擊、端口掃描以及Web木馬等等。異常流量的分類成為防護(hù)環(huán)節(jié)中必不可少的一環(huán)。除了傳統(tǒng)基于端口和載荷的流量分類，將機(jī)器學(xué)習(xí)應(yīng)用至網(wǎng)絡(luò)流量的分類[1]也越來越多。相關(guān)的機(jī)器學(xué)習(xí)算法包括了聚類算法、KNN算法、決策樹、隨機(jī)森林和深度神經(jīng)網(wǎng)絡(luò)等[2]。其中，在分類問題中，KNN算法簡單而高效。

對于各種分類問題的改進(jìn)，主要體現(xiàn)在權(quán)重函數(shù)改良、距離函數(shù)的設(shè)計(jì)等方向；而數(shù)據(jù)集不均衡問題的處理方式最常見的是過采樣和降采樣，讓數(shù)據(jù)集分布變得均衡，但通過加權(quán)的方式也能夠抑制數(shù)據(jù)集不均衡帶來的問題。

在權(quán)重設(shè)計(jì)方面，H. Yigit等[3]提出用人工蜂群算法找到KNN的最佳權(quán)重，從而實(shí)現(xiàn)更好的分類效果；Su等人[4]提出使用遺傳算法來計(jì)算最佳權(quán)重，同時(shí)用聚類中心代替部分訓(xùn)練數(shù)據(jù)集，縮短執(zhí)行時(shí)間；畢等人[5]提出了一種基于高斯函數(shù)定權(quán)的KNN算法，應(yīng)用在室內(nèi)定位問題上，提高了定位準(zhǔn)確率和魯棒性。

而在距離函數(shù)的處理上，Juan Aguilera等人[6]提出了用基于牛頓引力公式進(jìn)行加權(quán)；Zhang等人[7]提出了基于隨機(jī)森林的加權(quán)特征，考慮了每個(gè)特征的差異性；但兩者都沒有考慮數(shù)據(jù)集不均衡問題。楊等人[8]提出了一種基于語義距離的KNN算法，分析屬性內(nèi)取值的語義差異，尤其在數(shù)據(jù)集不完整的情況下，分類準(zhǔn)確率優(yōu)于傳統(tǒng)方法。

在函數(shù)設(shè)計(jì)方面，Lin等人[9]提出了Focal Loss的概念，在原有的交叉熵?fù)p失函數(shù)上做了進(jìn)一步修改，使得模型更加關(guān)注于小樣本的部分，進(jìn)一步提高了網(wǎng)絡(luò)分類的準(zhǔn)確率，這一修改思路也可以在KNN分類中借鑒；周等人[10]提出了一種基于聚類改進(jìn)的KNN分類算法，先聚類再分類，提升了KNN算法的效率；韋等人[11]提出了一種基于改進(jìn)極端隨機(jī)樹的方法，通過對加權(quán)統(tǒng)計(jì)和修改投票規(guī)則，其模型在異常流量樣本較少的類別上分類效果較好。

對于數(shù)據(jù)集不均衡問題，Liu等人[12]提出了類置信權(quán)重，依據(jù)每類標(biāo)簽屬性值的概率對KNN進(jìn)行加權(quán)，對于不平衡的數(shù)據(jù)集，其分類效果有一定的改善；Cao等人[13]為每個(gè)樣本分配反比例權(quán)重然后與距離權(quán)重結(jié)合，這是一種簡單的距離加權(quán)；Ying等人[14]在異常日志分類中用到了大量數(shù)據(jù)挖掘和自然語言處理的方法，使數(shù)據(jù)集不平衡問題得到改善。

Zhao等人[15]提出了一種加權(quán)混合集成方法，在Boosting框架下，為每個(gè)基分類器分配權(quán)重，實(shí)現(xiàn)對不平衡數(shù)據(jù)集的有效分類；Li等人[16]提出了一種融合的等比例抽樣方法，對少數(shù)類進(jìn)行了更多的關(guān)注，提升了分類的準(zhǔn)確率；王等人[17]提出了一種SVM和KNN結(jié)合的算法，對于較遠(yuǎn)樣本使用SVM分類，對于距離近的樣本用支持向量進(jìn)行KNN分類，提高了少數(shù)類樣本的識(shí)別率。

1 KNN算法

在實(shí)際網(wǎng)絡(luò)環(huán)境中，流量往往呈現(xiàn)傾斜式分布，異常流量是少數(shù)，數(shù)據(jù)集一般不均衡，這對于分類結(jié)果產(chǎn)生了一定的影響。

原始的KNN根據(jù)預(yù)測樣本周圍距離最近的K個(gè)點(diǎn)，根據(jù)少數(shù)服從多數(shù)的原則，將這個(gè)數(shù)據(jù)劃分為K個(gè)數(shù)據(jù)中出現(xiàn)次數(shù)最多的那個(gè)類別。

若K的取值較小，分類器很容易受到局部噪聲數(shù)據(jù)的干擾，分類會(huì)出現(xiàn)較大偏差；如果K的取值過大，分類器忽略了訓(xùn)練數(shù)據(jù)中的有效信息，樣本更容易被分類到數(shù)目多的類別中。而數(shù)據(jù)集不均衡更容易導(dǎo)致分類準(zhǔn)確率下降。

傳統(tǒng)的KNN分類存在一定的缺陷，例如，沒有充分考慮距離遠(yuǎn)近對樣本權(quán)重的影響，距離待測樣本近的點(diǎn)，其對分類的結(jié)果影響應(yīng)該更大，應(yīng)當(dāng)有更大的權(quán)值；同時(shí)在數(shù)據(jù)集分布不均時(shí)，KNN總是傾向于將未知測試樣本分類為占比數(shù)量較多的類，導(dǎo)致占比數(shù)量較少的類的分類效果不佳。而在網(wǎng)絡(luò)流量中，異常流量本身屬于少數(shù)類別，少數(shù)類別的分類準(zhǔn)確率對于整個(gè)模型分類準(zhǔn)確率的貢獻(xiàn)也很重要，但傳統(tǒng)的KNN不能很好地區(qū)分出這些少數(shù)異常流量的樣本。

而簡單的WKNN，為每一個(gè)訓(xùn)練樣本點(diǎn)給予d的權(quán)重，其中d是待測樣本與訓(xùn)練樣本的距離。這樣的方法一定程度上給近距離的點(diǎn)更大的權(quán)重，但也使得計(jì)算量變大，同時(shí)當(dāng)d趨近于0時(shí)，即待測樣本和訓(xùn)練樣本非常接近時(shí)，其權(quán)重1/d會(huì)趨近于無窮，對應(yīng)權(quán)重值沒有上確界。事實(shí)上，在高維數(shù)據(jù)中，計(jì)算得到的距離通常都較小，樣本之間的差異性更難體現(xiàn)。若這一點(diǎn)為噪聲數(shù)據(jù)，反而會(huì)使得分類準(zhǔn)確率下降。同時(shí)，簡單的WKNN也不能緩解數(shù)據(jù)集分布不均帶來的問題。

對于上述提到的兩個(gè)問題，一個(gè)是分類樣本對距離的感知所有差別，不同距離的樣本，其權(quán)重應(yīng)該要有區(qū)分，這是區(qū)分樣本間的差異性；另一個(gè)是對于數(shù)據(jù)集不均衡的處理，由于KNN總是傾向于將預(yù)測樣本分類為數(shù)量較多的類別，因此需要?jiǎng)討B(tài)調(diào)整權(quán)重，這是類別間差異性的體現(xiàn)。

同時(shí)，KNN算法屬于計(jì)算密集型，記訓(xùn)練數(shù)據(jù)的數(shù)量為n，數(shù)據(jù)的維度為m，則預(yù)測一個(gè)樣本，其時(shí)間復(fù)雜度T=O(mn)。若在這一階段進(jìn)行加權(quán)，與一個(gè)訓(xùn)練樣本每計(jì)算一次距離，則至少需要多m次乘法運(yùn)算，預(yù)測一個(gè)樣本類別至少多出mn次乘法運(yùn)算。而KNN分類的實(shí)質(zhì)是考慮其周邊很少的點(diǎn)，這些點(diǎn)稱為關(guān)鍵決策點(diǎn)；對于那些距離很遠(yuǎn)的點(diǎn)，實(shí)則參考性并不大，因此在第二個(gè)“投票階段”進(jìn)行加權(quán)和處理。由于K?n，因此計(jì)算量也會(huì)隨之減少。

為了解決這些問題，該文提出了一種基于Gamma分布函數(shù)的自適應(yīng)加權(quán)KNN模型(G-WKNN)，對于數(shù)據(jù)集的分布具有一定的自適應(yīng)性，能夠根據(jù)樣本的差異和類別的差異綜合對分類模型進(jìn)行調(diào)整，在提高模型準(zhǔn)確率和穩(wěn)定性的同時(shí)，對數(shù)量少的類別的分類效果也有提升。在數(shù)據(jù)不均衡時(shí)，類別負(fù)載因子起主要調(diào)節(jié)作用；而在數(shù)據(jù)較為均衡時(shí)，距離感知因子起主要調(diào)節(jié)作用，從而動(dòng)態(tài)適應(yīng)數(shù)據(jù)的變化。

2 基于Gamma分布的自適應(yīng)WKNN

針對上述提到的問題，該文提出了基于Gamma內(nèi)核的自適應(yīng)加權(quán)KNN算法，即Gamma-WKNN(G-WKNN)。其中，綜合權(quán)重w由距離感知權(quán)重wd和類別負(fù)載權(quán)重wf構(gòu)成。距離感知權(quán)重wd反映了決策樣本的差異，能夠起到不同樣本間的調(diào)節(jié)作用；類別負(fù)載權(quán)重wf反映了各個(gè)類別之間的差異，對于類別不均衡問題，能夠起到調(diào)節(jié)作用。綜合權(quán)重w的計(jì)算方法如式(1)。

w=wdwf

(1)

2.1 距離感知權(quán)重wd

記數(shù)據(jù)集一共有C個(gè)類別，樣本具有M個(gè)屬性，在空間Rm中，測試樣本P=(x1,x2,…,xm)和訓(xùn)練樣本Q=(y1,y2,…,ym)間的閔可夫斯基距離dist可以表示為:

(2)

p取1或者2對應(yīng)的閔式距離最為常用，這里取p=2，此時(shí)的距離為歐幾里得距離，得式(3):

(3)

距離感知權(quán)重wd，指標(biāo)應(yīng)該呈現(xiàn)出隨著距離增大，權(quán)重降低。同時(shí)所選函數(shù)應(yīng)該有上確界，在d很小，甚至趨近于0時(shí)，不應(yīng)該出現(xiàn)無窮大的情況，需要避免1/d這樣的函數(shù)的缺陷，其衰減應(yīng)該控制在一個(gè)區(qū)間范圍內(nèi)；對于常見的高斯內(nèi)核而言，其可調(diào)參數(shù)有(μ,σ)，但由于高斯內(nèi)核的對稱性，只能夠使用內(nèi)核函數(shù)的一部分區(qū)間，同時(shí)高斯內(nèi)核的參數(shù)μ只影響曲線在x軸上的偏移，因此可調(diào)參數(shù)僅有σ。相比之下，Gamma內(nèi)核的變化較為豐富，更能夠適應(yīng)不同的情況。Gamma內(nèi)核定義如式(4)所示：

(4)

其中，參數(shù)α決定了曲線的形狀；而β決定了曲線的陡峭程度，β越大，曲線越陡峭。相比于反比例函數(shù)，Gamma分布函數(shù)隨距離衰減程度可控，可以自由調(diào)整；相比于高斯內(nèi)核，其分布不完全對稱，具有一定的擾動(dòng)，這樣的隨機(jī)性一定程度能夠避免受到噪聲數(shù)據(jù)的影響，減少過擬合。

對式(4)x求導(dǎo)，得式(5):

(5)

令Gamma(x|α,β)'=0，得到方程的根，這里考慮α≥1，β>0的情況，得式(6):

(6)

結(jié)合一階導(dǎo)數(shù)的在x0處的符號(hào)和函數(shù)圖像，可以判定x0為一個(gè)極大值點(diǎn)。將x0帶入式(4)，得到Gamma的極大值Gamma(α,β)*，如式(7)所示：

(7)

關(guān)于參數(shù)α,β對函數(shù)峰值的影響，Gamma(α,β)*函數(shù)是關(guān)于(α,β)的單調(diào)函數(shù)，關(guān)于β單調(diào)遞增，關(guān)于α單調(diào)遞減。即，若希望函數(shù)峰值較大，可以選擇較小的α和較大的β。

當(dāng)α>1，β>0時(shí)，可以得到Gamma分布函數(shù)導(dǎo)數(shù)的遞推公式，如式(8)所示：

(8)

根據(jù)遞推關(guān)系式(8)，可求得二階導(dǎo)數(shù)，如式(9)所示：

Gamma(x|α,β)''=

(9)

令Gamma(x|α,β)''=0，可以求出其變化率最快的點(diǎn)xm，如式(10):

(10)

在區(qū)間[x0,xm+]內(nèi)，既能夠保證Gamma分布函數(shù)值較大，同時(shí)也能夠保證距離衰減速率較快，從而讓距離衰減權(quán)重真正發(fā)揮作用。

綜上，距離感知權(quán)重wd的計(jì)算公式如式(11):

(11)

其中，dist≥0。

2.2 類別負(fù)載權(quán)重wf

記數(shù)據(jù)集一共有N個(gè)樣本，每個(gè)類別的樣本數(shù)為Ci(i=1:m)。假設(shè)抽樣是隨機(jī)的，則用于訓(xùn)練的樣本的分布和總體的分布是一致的，考慮不同類別數(shù)量的差異性，假設(shè)不同類別的數(shù)據(jù)之間相對獨(dú)立，其出現(xiàn)的概率分布P={p1,p2,…,pn}。其中pi的計(jì)算方式如式(12)所示:

(12)

則類別的自信息Ie=-log(pi)，即類別被選中的概率越小，其在實(shí)際決策的時(shí)候，所蘊(yùn)含的自信息越大，即事件發(fā)生時(shí)，其能夠減少不確定性的程度越大。在考慮類別負(fù)載權(quán)重時(shí)，對于自信息越大的類別應(yīng)該更加重視，其權(quán)值也更大。

令wfi=Ie，得式(13)：

(13)

對于這樣一個(gè)決策系統(tǒng)，系統(tǒng)自信息的期望值H如式(14)所示：

(14)

實(shí)際上，H是這個(gè)系統(tǒng)的熵值，熵值越大，其在決策前，不確定性越大。容易證明，當(dāng)pi=1/m時(shí)，即每種類別出現(xiàn)的概率一致時(shí)，H有最大值H0=log(m)。此時(shí)外部數(shù)據(jù)的噪聲對系統(tǒng)影響最小。即，在實(shí)際決策時(shí)，熵的減少最大限度依賴于KNN模型的有效計(jì)算，而不是初始的系統(tǒng)分布。特別地，如果數(shù)據(jù)集分布不均，類別預(yù)測時(shí)，會(huì)較大程度受到系統(tǒng)初始分布的影響，KNN決策時(shí)對熵減小的貢獻(xiàn)度有損失。

一般KNN的K的取值范圍為3～15，不會(huì)過大，過大容易傾向于分類為數(shù)量較多的類別；也不宜過小，否則容易受到噪聲數(shù)據(jù)干擾。

函數(shù)在前期變化劇烈，當(dāng)類別比例差距足夠大時(shí)，變化相對緩和。例如，兩個(gè)類別的數(shù)據(jù)量差距在100倍左右時(shí)，權(quán)值差距在4.5倍左右；而類別數(shù)據(jù)量差距在1 000倍左右時(shí)，權(quán)值差距在7倍左右。權(quán)值差距倍數(shù)與超參數(shù)K的取值相當(dāng)，能夠較好權(quán)衡類別數(shù)量差距帶來的影響，從而實(shí)現(xiàn)根據(jù)數(shù)據(jù)集的差異進(jìn)行動(dòng)態(tài)加權(quán)。

2.3 G-WKNN算法流程

記有n個(gè)訓(xùn)練樣本，樣本的維度數(shù)為m，一共有M個(gè)類別C1～CM，算法輸入包括了訓(xùn)練數(shù)據(jù)Xn,m，測試樣本P1,m。算法實(shí)現(xiàn)過程如算法1所示。

算法1：G-WKNN算法實(shí)現(xiàn)

輸入:訓(xùn)練樣本數(shù)據(jù)X，標(biāo)簽Y，以及待測樣本P

輸出:待測樣本的分類結(jié)果Ci

1. 初始化K、α和β

2. FORitondo

3. disti←0

4. FORjtomdo

5. dist←‖Xi-P‖ /*計(jì)算Xi與P之間的歐幾里得距離*/

6. END FOR

7. END FOR

8. dist←Sort(dist) /*對距離向量升序排序*/

9. 選擇dist的前K個(gè)元素

10. 初始化score，每個(gè)類別均為0

11. FORktoKdo

12. /*f(k)是第k個(gè)元素對應(yīng)的類別映射*/

13. scoref(k)←scoref(k)+wf(k)×Gamma(distk+x0|α,β)/Gamma(α,β)*

14. END FOR

15. score←ArgSort(score) /*對score降序排序，返回下標(biāo)*/

16. RETURNf(score[0])

3 實(shí)驗(yàn)與結(jié)果

為了驗(yàn)證G-WKNN模型，使用公開數(shù)據(jù)集對模型的準(zhǔn)確率、穩(wěn)定性以及參數(shù)靈敏度等指標(biāo)進(jìn)行了對比實(shí)驗(yàn)。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

CIC-IDS2017數(shù)據(jù)集從2017年7月3日(星期一)開始搜集，于2017年7月7日(星期五)結(jié)束。主要攻擊類型包括暴力破解FTP和SSH、DoS、Heartbleed、Web攻擊、滲透、僵尸網(wǎng)絡(luò)和DDoS。

數(shù)據(jù)集正常流量類數(shù)目相對較多，流量呈現(xiàn)高度分布不均，正常流量占到了80%，對于部分異常流量，其占比不超過1%。對數(shù)據(jù)集做了如下調(diào)整，剔除了部分?jǐn)?shù)據(jù)量極少的異常流量，如Sql Injection類型的異常流量，同時(shí)對正常流量抽取一部分作為實(shí)驗(yàn)數(shù)據(jù)。

3.2 評價(jià)指標(biāo)

實(shí)驗(yàn)中使用了混淆矩陣、準(zhǔn)確率、精確度、召回率和F1值對模型進(jìn)行評估。

其中準(zhǔn)確率的定義如式(15)：

(15)

精確度表示預(yù)測為正樣本中，被正確分類的比例，如式(16)所示:

(16)

召回率表示對于真實(shí)的樣本，預(yù)測為正樣例所占比例，如式(17)所示:

(17)

而F1分?jǐn)?shù)兼顧了模型的精確率和召回率，其表達(dá)式如式(18)所示:

(18)

其中，TP、FP、TN和FN的含義如下:

在二分類的情況下，TP表示正例被預(yù)測為正例；FP表示正樣例被錯(cuò)誤識(shí)別為負(fù)樣例；TN表示負(fù)樣例被正確識(shí)別為負(fù)樣例；而FN表示負(fù)樣例錯(cuò)誤地被預(yù)測為正樣例；多分類計(jì)算方式同理。

3.3 少數(shù)類分類性能測試

從實(shí)驗(yàn)數(shù)據(jù)集中按類別比例抽取10 000條數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)。其中數(shù)據(jù)集不均衡對分類準(zhǔn)確率的影響主要體現(xiàn)在訓(xùn)練數(shù)據(jù)上，即那些被標(biāo)記好用于未知樣本分類的數(shù)據(jù)，實(shí)驗(yàn)中隨機(jī)按類別比例抽取數(shù)據(jù)集的一部分作為訓(xùn)練數(shù)據(jù)，剩下的數(shù)據(jù)再按照分層抽樣，每個(gè)類別抽取固定數(shù)量的數(shù)據(jù)用于結(jié)果測試。

使用原始的KNN，在K取值為3、5和7的情況下，測試結(jié)果的混淆矩陣如圖1(a)、(b)、(c)所示。在數(shù)量較少的類別，如Bot、BruteForce和XSS三類攻擊的分類效果相對較差，分別對應(yīng)于混淆矩陣的第二行和最后兩行。尤其是XSS攻擊類別，對應(yīng)的混淆矩陣的值僅有0.04左右。

在固定參數(shù)α=4、β=5的情況下，G-WKNN的表現(xiàn)如圖2(a)、(b)、(c)所示。除了總體分類效果有提升外，對于數(shù)量較少的類別，其分類準(zhǔn)確率有比較明顯的提升。Bot、BruteForce和XSS三類攻擊對應(yīng)混淆矩陣的值達(dá)到了0.8、0.6和0.5左右?；煜仃嚨膶蔷€更加突出，模型對少數(shù)類別分類的準(zhǔn)確率有提升。

圖1 原始KNN分類混淆矩陣

圖2 G-WKNN分類混淆矩陣

3.4 參數(shù)α和β靈敏度分析

為了對比不同α和β參數(shù)對模型分類效果的影響，本節(jié)設(shè)計(jì)了參數(shù)α和β敏感性分析實(shí)驗(yàn)，以驗(yàn)證模型的穩(wěn)定性和解釋參數(shù)選擇的合理性。

選擇不同α和β，測試模型的分類準(zhǔn)確率，對比不同K值情況下模型的穩(wěn)定性，實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 α和β參數(shù)對模型準(zhǔn)確率影響

參數(shù)K在9至17時(shí)，參數(shù)α和β的選擇對模型準(zhǔn)確率影響不顯著，模型準(zhǔn)確率基本維持在0.89上下；但在K值較小或者較大時(shí)，α和β對模型分類準(zhǔn)確率影響變大。

同時(shí)，無論α和β的取值如何變化，模型準(zhǔn)確率較高的點(diǎn)首次出現(xiàn)于K=9前后，雖然一些模型隨著K增大，其準(zhǔn)確率還會(huì)略有增長，但不明顯。當(dāng)K值過大時(shí)，此時(shí)權(quán)值差距倍數(shù)與K值相差較大，模型的準(zhǔn)確率會(huì)受到一定程度影響；尤其對于衰減區(qū)間長度較長的模型，其準(zhǔn)確率下降較為顯著，此時(shí)模型動(dòng)態(tài)加權(quán)的能力減弱。

3.5 參數(shù)K靈敏度分析

K是KNN模型關(guān)鍵的超參數(shù)。為此，本節(jié)設(shè)計(jì)了不同模型對參數(shù)K靈敏度分析實(shí)驗(yàn)，以驗(yàn)證G-WKNN模型的有效性。

固定參數(shù)α和β,對比分析了幾種改良KNN模型的靈敏度，測試數(shù)據(jù)如表1所示?？傮w而言，加權(quán)KNN的表現(xiàn)比原始KNN更好；而G-WKNN的表現(xiàn)更佳，比1/d型的KNN準(zhǔn)確率高，并且受超參數(shù)K的影響更小，同時(shí)對于超參數(shù)α和β，模型表現(xiàn)不過于靈敏。

表1 實(shí)驗(yàn)結(jié)果

就模型分類準(zhǔn)確率而言，對K值從3到21逐一測試，原始KNN和三種WKNN的對比結(jié)果如圖4所示。

G-WKNN的準(zhǔn)確率基本維持在0.9，對K選擇敏感度低；其余兩種WKNN相對穩(wěn)定，但準(zhǔn)確率在0.85和0.8左右；而原始KNN對K的選擇較為敏感，模型預(yù)測準(zhǔn)確率容易隨著K的取值發(fā)生較大波動(dòng)；G-WKNN具備較好的調(diào)節(jié)能力，其準(zhǔn)確率波動(dòng)更小，模型更加健壯。

圖4 K取值對預(yù)測準(zhǔn)確率的影響

將1/d加權(quán)方式替換Gamma內(nèi)核，替換后的模型，其分類準(zhǔn)確率比原始的1/d-WKNN更好，更穩(wěn)定，證明了類別負(fù)載權(quán)重調(diào)節(jié)的有效性；但準(zhǔn)確率比G-WKNN低，說明了在合適的參數(shù)α和β下，Gamma分布函數(shù)對于樣本距離加權(quán)調(diào)節(jié)更加有效?？傮w而言，G-WKNN分類準(zhǔn)確率的波動(dòng)更小，其準(zhǔn)確率比另外兩種WKNN也更高。

3.6 數(shù)據(jù)集均衡分布對模型的影響

為了說明不均衡數(shù)據(jù)集對模型準(zhǔn)確率的影響，本節(jié)設(shè)計(jì)了分層抽樣實(shí)驗(yàn)，通過分層抽樣，能夠?qū)⒚總€(gè)類別的訓(xùn)練數(shù)據(jù)集控制在相當(dāng)?shù)姆秶瑴y試樣本不變。由于XSS類別數(shù)目最少，僅有600余條，選擇75%作為訓(xùn)練集，各個(gè)類別采樣均為450條。此時(shí)，不同KNN模型分類結(jié)果如圖5所示。

圖5 數(shù)據(jù)集分布均衡下各個(gè)模型分類準(zhǔn)確率

從圖5可以看出，在數(shù)據(jù)集分布均衡的情況下，三種模型的分類準(zhǔn)確率均有不少提升，但從穩(wěn)定性和分類結(jié)果看，原始KNN和1/d-WKNN對于超參數(shù)K較為敏感，模型分類準(zhǔn)確率不穩(wěn)定，而G-WKNN分類準(zhǔn)確率基本維持在0.91以上。

在類別均衡的情況下，類別負(fù)載權(quán)重wf作用被削減；特別地，若類別絕對均衡，則類別負(fù)載權(quán)重退化為1，此時(shí)距離感知權(quán)重發(fā)揮調(diào)節(jié)作用，從實(shí)驗(yàn)結(jié)果可以看到，Gamma內(nèi)核對分類器的調(diào)節(jié)是有效的，G-WKNN分類準(zhǔn)確率始終高于其他兩個(gè)模型。

3.7 模型運(yùn)行時(shí)間性能分析

為了說明模型運(yùn)行時(shí)間性能，本節(jié)設(shè)計(jì)了對比實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)集數(shù)量為10 000條，在測試數(shù)據(jù)集為每個(gè)類別50例的情況下，對比了原始KNN和G-WKNN的運(yùn)行時(shí)間，如表2所示。

表2 模型運(yùn)行時(shí)間實(shí)驗(yàn)結(jié)果

由表2可知，G-WKNN在運(yùn)行時(shí)間上盡管優(yōu)勢不顯著，與原始KNN運(yùn)行時(shí)間相當(dāng)，但模型在準(zhǔn)確率上的提升較為突出。

3.8 數(shù)據(jù)集數(shù)量對模型的影響

為了說明數(shù)據(jù)量大小對模型的影響，本節(jié)設(shè)計(jì)了對比實(shí)驗(yàn)，通過調(diào)節(jié)參與分類的數(shù)據(jù)集的數(shù)量，對比不同模型的分類準(zhǔn)確率。

實(shí)驗(yàn)結(jié)果表明，通過增加訓(xùn)練數(shù)據(jù)集，一定程度上緩解了數(shù)據(jù)集不均帶來的問題，如圖6(a)、(b)和(c)所示。增加訓(xùn)練數(shù)據(jù)集后，三種模型分類準(zhǔn)確率有一定的提升，原始的KNN通過增加數(shù)據(jù)集準(zhǔn)確率最高達(dá)到了0.85；而1/d-WKNN隨訓(xùn)練樣本數(shù)量的增加，分類效果也有一定的提升；G-WKNN模型的準(zhǔn)確率基本維持在0.88至0.90。這說明，通過增加數(shù)據(jù)集數(shù)量的方式，一定程度能夠緩解數(shù)據(jù)集不均帶來的分類準(zhǔn)確率下降的問題。

但在實(shí)際情況中，數(shù)據(jù)集往往分布不理想，同時(shí)數(shù)據(jù)集數(shù)量可能有限，G-WKNN算法能夠在數(shù)據(jù)集較少，并且分布不平衡的情況下，達(dá)到比較高的分類準(zhǔn)確率。數(shù)據(jù)集數(shù)量對模型準(zhǔn)確率影響較小，模型較為穩(wěn)定。

圖6 三種模型在不同數(shù)據(jù)量下的分類準(zhǔn)確率對比

4 結(jié)束語

G-WKNN算法緩解了數(shù)據(jù)集分布不均帶來的類別傾向問題。通過設(shè)計(jì)距離感知權(quán)重和類別負(fù)載權(quán)重，分別調(diào)節(jié)類別間的差異和樣本間的差異。對于類別分布不均的數(shù)據(jù)集能夠自動(dòng)適應(yīng)數(shù)據(jù)集的傾斜程度，其表現(xiàn)優(yōu)于傳統(tǒng)KNN和簡單的1/d-WKNN，并且結(jié)果更加穩(wěn)定；在分類結(jié)果中，針對數(shù)目較少的類別，其預(yù)測的準(zhǔn)確率有比較明顯的提升。這對于傾斜分布的數(shù)據(jù)集以及數(shù)據(jù)集較少的情況，分類效果有較為明顯的改善。同時(shí)，分類效果也不能僅僅依賴于權(quán)重函數(shù)的設(shè)計(jì)，實(shí)驗(yàn)結(jié)果也表明，在相同的情況下，分布均勻的數(shù)據(jù)集，分類器的表現(xiàn)會(huì)更加突出和穩(wěn)定。