曾文璽, 董育寧

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

0 引言(Introduction)

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

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

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

1 相關工作(Related work)

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

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

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

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

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

2 本文方法(The proposed method)

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

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

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

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

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

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

(1)

(2)

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

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

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

2.2 去除異常流樣本

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

表1 去除異常流樣本算法

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

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

2.3 確定新類判別閾值

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

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

2.4 分類模型

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

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

(3)

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

同時,引入異常置信度閾值β用于判斷,對于異常置信度大于閾值β的樣本,判為異常點,從候選新類中刪除,反之則判為新類。本文方法完整的測試過程表3中的算法3所示。

表3 新類-異常樣本檢測算法

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

3 實驗(Experiment)

3.1 實驗環(huán)境

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

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

3.2 評估指標

3.2.1 新類分類指標

采用分類準確率Ao作為分類準確性指標,定義如下:

(4)

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

采用F1值作為評估指標,由精確率P和召回率R計算得出,計算公式如下:

(5)

需要注意,計算F1時未將新類作為一個額外的樣本類加入計算,因為在分類器中,沒有新類的訓練樣本,所以將新類作為一個真陽性分類沒有意義。但是,在計算已知類的P和R時,FP和FN中也會包含錯誤分類的新類樣本。

3.2.2 濾除異常樣本指標

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

(6)

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

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

3.2.3 時間性能指標

分別用Tt和Tc表示訓練時間和分類時間,單位為ms/樣本,分別表示逐樣本的平均訓練時間和分類時間。

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

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

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

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

3.4 不同置信度異常閾值對比

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

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

3.5 不同新類分類閾值對比

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

表7 不同θ的性能對比

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

3.6 不同方法的性能對比

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

表8 不同分類方法在NDset上的對比結果

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

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

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

表10 不同分類方法的時間性能對比結果

在訓練時間上,EntC-NCD需要多訓練一個去異常點分類器,V-EVT則是需要擬合每一個已知類的Weibull分布,訓練耗時相差不大。

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

4 結論(Conclusion)

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