一種基于信息熵的級(jí)聯(lián)式新類識(shí)別方法

曾文璽, 董育寧

(南京郵電大學(xué)通信與信息工程學(xué)院, 江蘇 南京 210003)

0 引言(Introduction)

在常見的閉集假設(shè)中,傳統(tǒng)機(jī)器學(xué)習(xí)(Machine Learning,ML)已取得顯著的成效[1]。但是,現(xiàn)實(shí)場(chǎng)景已不再是簡(jiǎn)單的靜態(tài)環(huán)境,這大大削弱了現(xiàn)有方法的魯棒性,因此新類檢測(cè)(Novel Class Detection,NCD)問(wèn)題成為網(wǎng)絡(luò)流分類的重要挑戰(zhàn)之一。

針對(duì)開放環(huán)境的問(wèn)題,目前ML中有一種解決方案是基于極值理論(Extreme Value Theory,EVT)[2]的方法。BALASUB-RAMANIAN等[3]將EVT與ML中的隨機(jī)森林(Random Forest,RF)相結(jié)合,基于每個(gè)已知類Weibull分布的累積概率識(shí)別新類。本文在南郵數(shù)據(jù)集和ISCX數(shù)據(jù)集兩個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)驗(yàn)證,分類精度只有85%左右,并且由于需要對(duì)不同的已知類類別分別進(jìn)行擬合,并判斷是否拒絕擬合,導(dǎo)致預(yù)測(cè)時(shí)間較長(zhǎng)。

上述方法未能很好地解決ML中的NCD問(wèn)題,其分類準(zhǔn)確率有待提高且不滿足在線分類的速度要求。因此,本文提出一種基于信息熵的級(jí)聯(lián)式新類識(shí)別(Entropy based Cascade NCD,EntC-NCD)方法用于改善以上問(wèn)題,并將其與現(xiàn)有代表方法進(jìn)行了對(duì)比。

1 相關(guān)工作(Related work)

目前,針對(duì)NCD問(wèn)題,研究人員從生成模型(Generative Model,GM)和判別模型(Discriminative Model,DM)兩個(gè)不同的角度進(jìn)行探索,并取得一定成果?，F(xiàn)有的方法主要有基于距離、基于支持向量機(jī)(Support Vector Machine,SVM)和基于EVT的方法。

在基于距離的方法研究中,MU等[4]基于孤立樹異常檢測(cè)算法[5]的思想提出了基于完全隨機(jī)樹的無(wú)監(jiān)督學(xué)習(xí)算法(SENCForest);武煒杰等[6]則是在SENCForest基礎(chǔ)上融入了k近鄰,不僅提高了在異常區(qū)域內(nèi)搜索新類的準(zhǔn)確率,也降低了系統(tǒng)開銷。

基于SVM的方法是由SCHEIRER等[7-8]首次應(yīng)用到NCD中,首先提出1-vs-Set模型,再進(jìn)一步使用非線性內(nèi)核融入EVT,提出了基于Weibull校正的SVM(W-SVM)模型;針對(duì)W-SVM中所有的已知類具有相同閾值的問(wèn)題,JAIN等[9]又引入了概率開放集SVM(Probabilistic Open Set SVM,POS-SVM),該分類器可以對(duì)每個(gè)已知類采用不同的拒絕閾值,從而達(dá)到提高分類準(zhǔn)確率的效果。

基于EVT擬合分布的方法如今被廣泛使用,除了前文提到的W-SVM;BALASUBRAMANIAN等[3]則是提出了基于投票的極值理論模型(Vote-Based EVT,V-EVT),通過(guò)結(jié)合RF擬合已知類別樣本的投票分布,得到逐類的Weibull分布。通過(guò)對(duì)應(yīng)的Weibull分布計(jì)算其累積概率,根據(jù)閾值判斷是否為已知類。

受V-EVT思路的啟發(fā),本文選擇傳統(tǒng)ML中分類效果較好的RF模型,與評(píng)估不確定性的信息熵相結(jié)合,提出基于信息熵的新類檢測(cè)方法,想要達(dá)成的目標(biāo)是在保證較高分類準(zhǔn)確率的同時(shí),克服需要多次計(jì)算Weibull累積概率導(dǎo)致分類耗時(shí)較長(zhǎng)的問(wèn)題。

2 本文方法(The proposed method)

基于信息熵和RF的NCD方法的模型框架如圖1所示,主要分為訓(xùn)練、校準(zhǔn)和測(cè)試三大模塊。其中:訓(xùn)練集只包含已知類樣本,校準(zhǔn)集包含已知類和少量偽新類樣本,測(cè)試集包含全部已知類和新類樣本;訓(xùn)練集按照3∶7的比例隨機(jī)分為D1和D2兩個(gè)部分,D1訓(xùn)練多分類器RF1;θ為新類判別閾值;β為異常流樣本置信度閾值。

圖1 基于信息熵和RF的NCD方法的模型框架Fig.1 Model framework of NCD method based on information entropy and RF

2.1 基于信息熵的新類發(fā)現(xiàn)方法

RF投票的分布中含有較多信息,投票的分散程度反映出分類器對(duì)樣本的不確定性。當(dāng)訓(xùn)練樣本的類別ci∈Ck={c1,c2,…,cn}時(shí),若測(cè)試樣本的類別ci?Ck,分類器對(duì)其判決的不確定性會(huì)遠(yuǎn)高于類別ci∈Ck的測(cè)試樣本。據(jù)此引入信息熵作為評(píng)估不確定性的標(biāo)準(zhǔn),并作為已知類和新類的分類依據(jù)。

為了驗(yàn)證這一想法,以ISCX數(shù)據(jù)集為例,隨機(jī)抽取7個(gè)類作為已知類訓(xùn)練集和測(cè)試集,另外3個(gè)類作為新類測(cè)試集,分別測(cè)試并統(tǒng)計(jì)已知類和新類的信息熵分布[10]。

根據(jù)RF的投票結(jié)果計(jì)算樣本信息熵的方法如下:首先將樣本d判為已知類ci的樹的數(shù)目占樹總數(shù)的比例作為樣本d屬于已知類ci的概率,其次計(jì)算樣本d被判為每個(gè)已知類的概率,并由此計(jì)算樣本d的信息熵,計(jì)算已知類概率和信息熵的方法分別如公式(1)和公式(2)所示:

(1)

(2)

其中:Ib(ci|d)∈{0,1}是第b棵樹判斷樣本d是否為類ci的結(jié)果,若判為ci,則設(shè)為1,否則為0;B為RF中樹的總數(shù)目,n為已知類的類別數(shù)。

ISCX數(shù)據(jù)集的信息熵分布統(tǒng)計(jì)結(jié)果如圖2所示。已知類的信息熵值明顯聚集于小于1的區(qū)域內(nèi),而新類的信息熵則普遍較大,這為基于信息熵的新類檢測(cè)提供了可行性。

圖2 已知類和新類信息熵分布統(tǒng)計(jì)Fig.2 Information entropy distribution statistics for known and novel classes

2.2 去除異常流樣本

在實(shí)際網(wǎng)絡(luò)的流傳輸過(guò)程中會(huì)產(chǎn)生異常流樣本,從而降低分類器學(xué)習(xí)的準(zhǔn)確性。因此,訓(xùn)練前需篩選出訓(xùn)練集中的異常樣本,具體步驟如表1中的算法1所示;得到干凈的已知類樣本訓(xùn)練集Dt和異常樣本數(shù)據(jù)集Do,并用Dt訓(xùn)練新類分類器RFn。

表1 去除異常流樣本算法

測(cè)試集中同樣會(huì)存在異常已知類樣本,因此分類器對(duì)其判定的不確定性會(huì)增大,使該樣本的信息熵增大,容易被誤判為新類。

為此,從Dt中抽取與Do數(shù)量相等的樣本集Dp,Do和Dp分別作為正、負(fù)樣本訓(xùn)練去異常點(diǎn)二分類器RFo。測(cè)試階段通過(guò)級(jí)聯(lián)RFo,對(duì)RFn認(rèn)定的新類樣本進(jìn)行再分類,刪除其中的異常已知類樣本。

2.3 確定新類判別閾值

依據(jù)校準(zhǔn)集選取新類的判別閾值,校準(zhǔn)數(shù)據(jù)集Dv中包括全部已知類和少量偽新類的樣本;用RFn進(jìn)行預(yù)測(cè),計(jì)算各個(gè)樣本的信息熵,并以0.1為區(qū)間分別統(tǒng)計(jì)已知類和新類的信息熵分布,取兩個(gè)分布的交點(diǎn)作為新類判別閾值θ,具體過(guò)程表2中的算法2所示。

其中:hi表示[i-0.05,i+0.05);Khi、Uhi分別表示已知類和新類樣本的信息熵在hi區(qū)間內(nèi)的樣本數(shù)量;Ck、Cu分別表示已知類、新類;I(hi,Ck|d)∈{0,1}表示若d∈Ck且Hd∈hi,則I(hi,Ck|d)等于1,否則為0。

2.4 分類模型

如上文所述,測(cè)試集中異常樣本的信息熵比正常樣本高,導(dǎo)致誤判為新類。因此,采用級(jí)聯(lián)模式進(jìn)行二次篩選。經(jīng)過(guò)RFn分類后,信息熵小于等于θ的樣本被認(rèn)定為已知類,并直接輸出RFn的分類結(jié)果;而信息熵大于θ的樣本,稱其為候選新類(包含新類和已知類中的異常樣本)。

對(duì)于候選新類樣本通過(guò)級(jí)聯(lián)的去異常點(diǎn)二分類器RFo進(jìn)一步判斷,并引入異常置信度ACon,計(jì)算公式如下:

(3)

其中:Co表示異常類;Ib(Co|d)∈{0,1}表示若第b棵樹判斷樣本d∈Co,則Ib(Co|d)等于1,否則為0。

同時(shí),引入異常置信度閾值β用于判斷,對(duì)于異常置信度大于閾值β的樣本,判為異常點(diǎn),從候選新類中刪除,反之則判為新類。本文方法完整的測(cè)試過(guò)程表3中的算法3所示。

表3 新類-異常樣本檢測(cè)算法

其中:θ為算法2中獲取的新類判別閾值,β為異常置信度閾值,可以靈活調(diào)節(jié)以平衡分類的準(zhǔn)確率和覆蓋率;Hd為根據(jù)多分類器分類結(jié)果計(jì)算的信息熵;ACon(Co|d)為根據(jù)RFo得到的異常置信度;yu和yo分別表示預(yù)測(cè)標(biāo)簽為新類和異常點(diǎn)。

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

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)使用惠普筆記本電腦,硬件和軟件的配置如下:CPU為AMD R5-4600H@3.00 GHz,GPU為NVIDIA GTX 1650 Ti-4G,16 GB運(yùn)存,操作系統(tǒng)為64位Windows 10;在Python編程語(yǔ)言環(huán)境下運(yùn)行。

分類器均采用RF,樹的數(shù)目設(shè)置為100棵,葉節(jié)點(diǎn)最小樣本數(shù)設(shè)置為1個(gè),所有實(shí)驗(yàn)采用五折交叉驗(yàn)證。

3.2 評(píng)估指標(biāo)

3.2.1 新類分類指標(biāo)

采用分類準(zhǔn)確率Ao作為分類準(zhǔn)確性指標(biāo),定義如下:

(4)

其中:TPi、TNi、FPi、FNi分別代表已知類的真陽(yáng)性、真陰性、假陽(yáng)性、假陰性,TU、FU分別代表新類的正確判斷和錯(cuò)誤判斷,n為已知類類別數(shù)目。

采用F1值作為評(píng)估指標(biāo),由精確率P和召回率R計(jì)算得出,計(jì)算公式如下:

(5)

需要注意,計(jì)算F1時(shí)未將新類作為一個(gè)額外的樣本類加入計(jì)算,因?yàn)樵诜诸惼髦?沒(méi)有新類的訓(xùn)練樣本,所以將新類作為一個(gè)真陽(yáng)性分類沒(méi)有意義。但是,在計(jì)算已知類的P和R時(shí),FP和FN中也會(huì)包含錯(cuò)誤分類的新類樣本。

3.2.2 濾除異常樣本指標(biāo)

本文方法包含從候選新類樣本中過(guò)濾異常樣本的模塊,準(zhǔn)確率仍然使用Ao,但是樣本總數(shù)減少。因此,定義覆蓋率指標(biāo)Coverage如下所示:

(6)

其中:N表示預(yù)測(cè)樣本總數(shù),Nn表示判為異常樣本的數(shù)目。

定義ORR(Outlier Removal Rate)表示已知類異常樣本的濾除率、FDR(False Deletion Rate)表示新類樣本被判為異常點(diǎn)的比例。

3.2.3 時(shí)間性能指標(biāo)

分別用Tt和Tc表示訓(xùn)練時(shí)間和分類時(shí)間,單位為ms/樣本,分別表示逐樣本的平均訓(xùn)練時(shí)間和分類時(shí)間。

3.3 數(shù)據(jù)集

使用南郵數(shù)據(jù)集(NJUPT Dataset,NDset)、ISCX數(shù)據(jù)集進(jìn)行方法驗(yàn)證。NDset是通過(guò)WireShark于2020年在南京郵電大學(xué)校園網(wǎng)環(huán)境下采集的[11]。NDset和ISCX數(shù)據(jù)集的具體類別和樣本數(shù)如表4和表5所示。

表4 南郵數(shù)據(jù)集

表5 ISCX數(shù)據(jù)集

3.4 不同置信度異常閾值對(duì)比

為了驗(yàn)證級(jí)聯(lián)式去除異常樣本模塊的有效性,以NDset為例,新類類別選取為[1080P_douyu,1080P_huya,720P_tencent,QQ_music]共4類,校準(zhǔn)數(shù)據(jù)集Dv選取的偽新類為1080P_huya。通過(guò)修改閾值β對(duì)比去除異常點(diǎn)前后的各項(xiàng)評(píng)估指標(biāo)的變化,結(jié)果如表6所示,β=1表示未做去除異常點(diǎn)處理。

在未進(jìn)行去除異常點(diǎn)的情況下,6 330個(gè)已知類測(cè)試樣本中有1 133個(gè)被新類識(shí)別模塊判為候選新類,約占所有已知類測(cè)試樣本的17.9%,而4 910個(gè)新類測(cè)試樣本被判斷為候選新類的個(gè)數(shù)為4 856個(gè),約占比98.9%。級(jí)聯(lián)去異常點(diǎn)模塊后,β使用0.5時(shí),會(huì)有66.3%的已知類異常樣本被刪除,而新類中有18.5%的樣本被當(dāng)作異常樣本被誤刪。表6中的數(shù)據(jù)表明,去異常點(diǎn)模塊能從候選新類樣本中刪除大部分的已知類異常樣本,并且保留大多數(shù)新類樣本,進(jìn)一步提高新類樣本的純度,并且可以根據(jù)需要自行調(diào)節(jié)閾值。需要注意,F1沒(méi)有跟隨閾值變化是因?yàn)镽和P的計(jì)算中未包含判為候選新類的樣本。

3.5 不同新類分類閾值對(duì)比

根據(jù)本文提出的算法2,計(jì)算得到一個(gè)新類分類的閾值,會(huì)對(duì)于分類的最終性能有著較強(qiáng)的影響,因此設(shè)置實(shí)驗(yàn)通過(guò)修改θ值進(jìn)行對(duì)比,驗(yàn)證其有效性。新類和校準(zhǔn)集選取同本文“3.4”小節(jié),根據(jù)算法2得到閾值θ為0.9,閾值β統(tǒng)一設(shè)置為0.5,不同θ的性能對(duì)比結(jié)果如表7所示。

表7 不同θ的性能對(duì)比

當(dāng)θ取0.9時(shí),覆蓋率比θ取1.1時(shí)小1.3%,但準(zhǔn)確率高1%,F1值也高2.4%;而相比于θ取0.7時(shí),準(zhǔn)確率幾乎一樣,但覆蓋率高2.3%,只有F1值低0.6%且θ取0.9時(shí),對(duì)新類樣本的誤刪率最低。因此,由算法2計(jì)算的閾值θ的分類性能較好。

3.6 不同方法的性能對(duì)比

將本文方法EntC-NCD與文獻(xiàn)方法V-EVT分別在NDset和ISCX兩個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)對(duì)比,采用本文所提方法進(jìn)行去異常點(diǎn)處理時(shí),閾值β分別設(shè)置為0.5、0.8,結(jié)果如表8和表9所示,EntC-NCD-1表示未做去異常點(diǎn)處理。

表8 不同分類方法在NDset上的對(duì)比結(jié)果

表9 不同分類方法在ISCX數(shù)據(jù)集上的對(duì)比結(jié)果

在兩個(gè)數(shù)據(jù)集上,EntC-NCD-1比V-EVT的Ao高1.5%～2.6%;F1則是在ISCX數(shù)據(jù)集上兩者相似,在NDset上是本文所提方法較優(yōu);EntC-NCD通過(guò)去除異常點(diǎn)處理,進(jìn)一步提高了分類準(zhǔn)確率,其Ao高于V-EVT方法4.7%～7.4%。V-EVT是通過(guò)RF投票數(shù)分布擬合每個(gè)已知類的Weibull分布,再通過(guò)計(jì)算測(cè)試樣本的累積概率判斷是否屬于該類;若不屬于所有已知類,則判為新類。但是,實(shí)際的擬合結(jié)果并不完全貼合實(shí)際投票的分布,導(dǎo)致V-EVT的分類性能不如本文所提方法。

在不同數(shù)據(jù)集上的時(shí)間性能對(duì)比結(jié)果如表10所示。EntC-NCD只需要進(jìn)行一次多分類并計(jì)算一次信息熵,預(yù)測(cè)時(shí)間較短,在NDset上,即使加上去異常點(diǎn)處理,平均一個(gè)樣本也僅需0.079 ms;V-EVT雖然只需要進(jìn)行一次分類器分類,但是需要分別計(jì)算每一個(gè)已知類的Weibull分布值進(jìn)行判斷,所以需要0.592 ms,分類時(shí)間仍較本文所提方法高一個(gè)數(shù)量級(jí)。

表10 不同分類方法的時(shí)間性能對(duì)比結(jié)果

在訓(xùn)練時(shí)間上,EntC-NCD需要多訓(xùn)練一個(gè)去異常點(diǎn)分類器,V-EVT則是需要擬合每一個(gè)已知類的Weibull分布,訓(xùn)練耗時(shí)相差不大。

綜上所述,相比于V-EVT,本文方法在不同的數(shù)據(jù)集上均有更好的表現(xiàn),同時(shí)具有一定的普適性。

4 結(jié)論(Conclusion)

本文提出了一種基于信息熵的級(jí)聯(lián)式新類識(shí)別和去異常點(diǎn)模型,并針對(duì)新類分類閾值的選取給出了優(yōu)選方法。此外,本文還討論了不同新類判別閾值、異常置信度閾值對(duì)分類性能的影響,在兩個(gè)真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)集上對(duì)本文所提方法進(jìn)行驗(yàn)證,并與文獻(xiàn)方法進(jìn)行對(duì)比。實(shí)驗(yàn)數(shù)據(jù)表明,本文所提方法的識(shí)別準(zhǔn)確率均可達(dá)到約95%,單個(gè)樣本的識(shí)別時(shí)間僅需0.079 ms,在分類精度和時(shí)間性能上均優(yōu)于對(duì)比方法且有一定的普適性,更加適用于不同需求的新類分類場(chǎng)景。