一種基于特征集構建的Bagging集成方法及其在流量分類中的應用

錢亞冠，關曉惠，吳淑慧，云本勝，任東曉

（1.浙江科技學院大數據科學系，浙江 杭州310023；2.浙江水利水電學院，浙江 杭州310018）

1 引言

傳統的機器學習方法是在假設空間中尋找一個最能接近真實分類函數的假設。為此，機器學習研究者對各種分類模型進行了大量的研究，力圖提高單個分類器的泛化能力。人工神經網絡、支持向量機等分類模型在不同的應用領域取得了不錯的分類性能，但是也存在單個分類器性能提升越來越難、訓練時間越來越長的弊端，在大數據環境下尤其突出。集成方法的思路是把多個分類器集成起來，通過對多個分類器的結果進行某種方式的組合來決定最終的分類結果，以期取得比單個分類器更好的性能[1]。

目前集成分類器的方法有多種，Boosting 和Bagging是兩種典型集成方法[1]。Boosting采用序貫方式產生基分類器（base classifier），利用基分類器之間的相關性提升性能；而 Bagging是并行方式產生基分類器，利用基分類器之間的不相關性來提升性能。目前的集成框架有采用決策樹、神經網絡[2,3]，甚至深度神經網絡[4]作為基分類器，也有選擇支持向量機作為基本類器[5]。但集成學習理論的本意是利用弱分類器來構建強分類器，同時弱分類器往往訓練時間短，因此選擇用簡單的 Softmax回歸來構建強分類器。已有的研究表明[1]，基分類器之間差異度越大，Bagging集成方法的分類性能越好。前期研究表明，即使采用相同的特征選擇算法，在不同的訓練集上（例如不同時段獲得的流量數據）也可獲得較大差異的特征子集[6]。考慮到經典Bagging中的基分類器是在相同的特征集上構建分類模型，為進一步增大基分類器之間的差異度，提出每個基分類器采用獨立的特征子集。同時，經典 Bagging集成方法采用等權重投票表決的方式來給出最終的預測結果，而事實上每個基分類器的能力不同，為此采用帶權投票方式來進一步提高分類精度。

最后，把改進的Bagging集成分類方法應用到互聯網流量分類領域。流量分類是互聯網領域中的一個重要應用，如何準確識別出流量的應用類型對于網絡管理、流量控制及網絡安全等具有重要的意義[7]。由于互聯網的復雜性、動態性，在各種網絡應用層出不窮的情況下，如何準確識別出流量的應用類型目前仍然是個極具挑戰的課題，而利用分類器集成的方式可以克服上述動態性造成的分類誤差。通過實際的流量數據進行實驗，結果顯示改進方法比經典的Bagging方法有顯著的性能提升，與采用決策樹集成的隨機森林（random forest）方法相比也有提高，符合研究預期。

2 Bagging集成方法

簡單地說，集成學習就是利用多個分類器的能力來克服單個分類器的不足，圖1給出了集成方法的框架結構[1]。一般把參與集成的單個分類器稱為基分類器，基分類器由基學習算法（base learning algorithm）訓練獲得，決策樹、感知器等都可以作為基分類器。根據 Kearns和 Valiant[8,9]提出的強可學習與弱可學習理論，分類準確率只要略高于 50%的弱分類器（即比隨機猜測略好）是可以增強為強分類器的。集成方法正是基于此理論，集成多個弱分類器后獲得比單個強分類器更好的分類性能。

圖1 一個點位的交叉

目前集成分類器的方法有多種，Bagging和Boosting是兩種典型集成方法[1]。經典Bagging集成方法采用 bootstrap抽樣方法[10]獲得多個訓練集，在每個訓練集上獲得多個基分類器，最后通過投票的方式決定最終的分類預測標簽。bootstrap抽樣構建的Bagging算法如下。

算法1 Bagging算法

基學習器L；基學習器數量N

Bagging是通過并行方式產生基分類器，利用基分類器之間的差異性來提升性能。為方便分析，假設分類標簽集合為目標函數為f，每個基分類器具有獨立的泛化誤差ε，即對于每個基分類器hi，有把N個上述兩分類器用Bagging方式集成后的假設函數為：

由式（1）可知，當超過一半的基分類器犯錯時，集成分類器H才犯錯。根據 Hoeffding不等式，集成分類器H的泛化誤差為：

式（2）表明，不相關的基分類器越多，泛化誤差越小。因此，如何在有限的訓練集上得到盡可能多的、差異性顯著的基分類器是 Bagging集成方法成功的關鍵。本文正是通過進一步強化基分類器的差異性來提升 Bagging的分類能力。在大數據環境下，選擇 Bagging作為集成框架的另一個優點是可以充分利用目前多核處理器的并行能力來產生基分類器。

3 基于特征子集構建方法

經典Bagging方法采用bootstrap重抽樣來產生不同的訓練集，增加基分類器的個體差異度，從而提高泛化能力。但是bootstrap產生的訓練集與原始數據集仍有 63.2%的重合度，對于像 k-近鄰這樣的穩定分類器而言，并不能產生個體差異很大的基分類器。考慮到經典 Bagging集成方法是在相同的特征子集下構建基分類器，從特征子集入手來增大基分類器的差異度。同時，經典的Bagging方法假定每個基分類器的投票權重相等，不符合基分類器能力不同的實際情況。本文提出加權集成的思路，利用梯度下降的優化方法獲得權重系數。

3.1 基于遺傳進化的特征子集選擇

所謂特征選擇，就是從高維的特征空間中去除相關性強的冗余特征，獲得最優的特征子集。特征選擇算法一般包括子集產生過程、評價函數、停止準則和驗證過程這4個部分，其中子集產生過程是搜索特征子集空間的過程，是計算復雜度最高的部分。由于特征子集的搜索空間與特征數成指數關系，用蠻力法搜索整個特征子集空間將是一個 NP難問題。實際應用中通常采用啟發式搜索，本文采用隨機搜索的遺傳算法來獲得不同訓練集上的特征子集，以保證訓練的基分類器之間有最大的差異度。

特征選擇的子集產生過程采用遺傳算法進行搜索，首先需要對染色體進行編碼，一個染色體表示一個特征子集。采用 0/1方式編碼染色體，例如染色體編碼為00101000，表示特征子集{3，5}，即第3和第5個特征被選取，這里假設用整數索引特征。第2個步驟是初始化一個種群P，它表示一個隨機生成的染色體集合。第3個步驟是計算每個染色體的適應度，模擬生物對環境的適應能力。本文中的適應能力是指該特征子集是否有利于分類器的性能提高，因此定義適應度評價函數為：

其中，C表示染色體，Xc表示染色體C對應的特征子集。J（Xc,D）是對特征子集的評估，取分類準確率為評價指標；penalty(Xc)是特征數目的懲罰項，防止特征子集過大。第4個步驟是按照適應度對種群中的染色體排序，適應度高的染色體會被高概率選中用于繁殖下一代，本文采用基于排序輪盤賭的選取方法。第5個步驟是把選出的染色體進行交叉繁殖，圖1和圖2是常見的幾種交叉方式。第6個步驟是交叉繁殖后的后代染色體進行變異操作。最后用步驟3的適應度評價函數評估新繁殖的染色體，如果優于其雙親染色體，則從種群中替換雙親染色體。步驟3至步驟7反復迭代執行，直到滿足最優終止條件。由于上述進化過程中存在隨機選擇雙親染色體的行為，因此可以避免迭代過程陷入局部最優，最終有可能找到全局最優解。算法結束后，種群P中的染色體按適應度排序，據前列的染色體即是需要的特征子集。算法2描述了上述基于遺傳算法的特征子集選擇過程。

圖2 兩個點位的交叉過程

算法2 GAFeatureSelect //基于遺傳算法的特征子集選擇

for i=1,…,K //初始化 K 個染色體（特征子集）

3.2 基分類器的加權集成

經典的 Bagging方法假定每個基分類器在投票中的權重相等，而本文提出的方法是在不同的特征子集上訓練基分類器，這些分類器在分類能力上會存在一定的差異，因此本文進一步提出加權集成的思路，賦予每個基分類器不同的投票權重。圖3是改進后的Bagging集成框架，可以發現，每個基分類器是在單獨的特征子集上構建的。假設訓練集為是k個類標簽的索引值。本文采用Softmax回歸作為基分類器，它是Logistic回歸往多分類器上的推廣。Softmax回歸的假設函數為：

y 的后驗概率構成的。假設第i個 Softmax回歸基分類器的輸出是向量所有的輸出向量經加權求和集成后通常不滿足概率的規范性，采用 Softmax函數再次變換到[0,1]區間：

圖3 基于特征子集構建的加權Bagging集成框架

其中，I(x)是指示函數，即當x是true時，I(x)=1，否則I(x)=0。yj是第 j個類的輸出標簽，pj是第j個類的后驗概率。由式（5）可知，代價函數是權重向量的函數。可以通過迭代的方式更新權重向量：

其中，[?]j表示向量中的第j個分量。通過最速梯度下降法迭代收斂到最權重，代入式（6），即最終的集成分類器，見算法3。

算法3 WeighedBagging

Softmax回歸學習器L；基學習器數量N；步長λ=0.1

4 流量分類中的應用

流量分類是互聯網領域中的一個重要應用，如何準確識別出流量的應用類型對于網絡管理、流量控制及網絡安全等具有重要的意義。由于互聯網的復雜性、動態性，如何準確識別出流量的應用類型目前仍然是個極具挑戰的課題。由于數據分組加密技術的出現，深度分組檢測（DPI）技術顯得力不從心，而基于流量統計特征的機器學習方法不依賴于特征字串，因此成為流量分類領域的新興技術[11-13]。

所謂的基于機器學習的流量分類方法就是通過機器學習算法，從流量訓練數據中建立分類模型，從而實現對流量類型的預測。這種方法的優點是可以克服數據加密的限制，同時僅利用IP和TCP這兩層數據分組頭部的信息，不受隱私保護的制約。但是，互聯網流量行為的高度不確定性，導致不同地點、不同時間段獲取的數據集之間存在較大的差異性。因此，不同的數據集訓練獲得的模型對預測結果就會產生較大的波動，而Bagging集成機器學習方法則可以有效地克服這種波動性。進一步在經典的 Bagging集成方法基礎上，引入特征子集和加權集成基分類器的思想，提高互聯網高動態環境下的流量分類準確性。

4.1 流量數據集

本文實驗室數據的來源有兩個：一是英國劍橋大學 Moore等提供的公開流量數據集[14]，二是從校網中心的某臺交換機上獲得的流量數據，該交換機匯聚了某幢男生宿舍訪問外網的所有網絡流量。采用兩個不同的數據集合在一起產生集成分類器，目的是把不同地點和不同時間獲取的流量數據訓練集成分類器，以期獲得更好的泛化能力。Moore等提供的實驗數據是通過連續采集24 h的網絡流量，并按28 min為間隔隨機抽取10個數據塊，本文只選用其中的5個數據塊。

校網中心的數據選在周一晚上 21：30—22：30、周二下午 15：00—16：00、周三上午 10：30—11：30、周五晚上 19：30—20：30、周六下午 16：00—17：00 和周日上午8：30—10：30。其中，前5天的數據用于訓練基分類器，周日的數據用于測試。為保護隱私，只截取數據分組的分組頭部分，并通過Tcpdpriv工具對IP地址進行了匿名化處理。由于Moore流量數據集由248個特征構成，把校網中心獲取的數據預處理成與Moore數據集同樣的特征集。

紫薇是我國夏季重要的觀花樹種，因此在復色紫薇栽培過程中，花性狀的重要性明顯高于生長性狀，而生長性狀也是促進花性狀充分表現的基礎，在花性狀不受到顯著影響的情況下應該適當兼顧[11]。根據以上原則，我們應采用兩次葉面肥的追肥方法，基肥采用拌土方式施用均衡肥料，展葉期以高鉀肥料追肥，花期以高磷或均衡營養肥料追肥，適當提早花期追肥時間能夠獲得較好的效果。

考慮到Moore數據集中的某些流量類型的定義與本文的數據有差異，最后兩個數據集都統一選用 WWW、mail、FTP、P2P、database、multimedia等幾種類型的數據流。提出的集成方法在 Moore的5個數據集和本文采集的5個數據集上共訓練10個基分類器，每個基分類器采用Softmax回歸線性模型，并采用自己的特征子集和加權權重。

4.2 實驗分析

把改進方法命名為 Bagging+，與經典的Bagging方法、隨機森林進行性能比較。性能評估采用召回率（recall）、精度（precision）和 F-measure這3個指標：

其中，P為測試集中事先標識為正例的樣本數，TP為分類器正確預測為正例的樣本數，FP為被分類器錯誤地將正例預測為負例的樣本數。F-measure是召回率和精度的調和平均，是一個能比較好地反映分類性能的綜合指標。

表1給出了Bagging+與經典Bagging方法之間的性能比較。盡管這兩種集成方法均采用了Softmax回歸線性分類器作為基分類器，由于Bagging+采用了不同的特征子集訓練，且采用優化權重集成，可以發現，召回率、精度和F-measure這3個指標均比經典Bagging方法有提升。WWW、mail、FTP-control這 3種流量類型的識別率提高幅度不大，因為經典 Bagging方法已具有非常好的識別率。但是 FTP-PASV、P2P和 multimedia的識別率提高顯著。從 F-measure指標看，multimedia從39.7%提高到96.9%，幅度超過50%。而FTP-PASV和P2P盡管絕對指標只達到67%左右，但是比經典方法提高了 40%左右，提升效果也是顯著的。

表2給出了Bagging+方法與隨機森林的性能比較。隨機森林的集成框架為Bagging，基分類器為決策樹。由于決策樹是一種不穩定的分類器，不同數據集可以產生不同的決策樹，因此通過Bagging集成后能極大地提高分類性能。通過比較可以發現，隨機森林比經典的 Bagging方法的性能要提高不少，但改進的Bagging+方法則比隨機森林有較好的提升，特別是P2P的F-measure指標從52.1%提高到67.1%、FTP-data從83.0%提高到99.9%。FTP-PASV則有小幅下降，從70.8%降到67.5%，其他類別基本持平。因此，總體上看，Bagging+方法比隨機森林方法有提高，特別是占比少的流量類別改進比較明顯。

從實驗結果看，改進 Bagging集成方法通過遺傳算法搜索特征子集，再通過加權集成基分類器可以提高分類正確率。Bagging集成的性能主要取決于基分類器的差異度，遺傳算法是一種隨機搜索優化方法，在不同的數據集上這種隨機性會得到差異性較大特征子集，而不同的特征子集又進一步加大了基分類器之間的差異性。通過交叉熵代價函數最小的方式獲得的加權集成可以較好地確定不同分類器對最后判決的貢獻度，比同等權重的投票表決更加精確。

表1 Bagging+方法與Bagging方法比較

表2 Bagging+方法與隨機森林比較

5 結束語

本文提出基于特征集構建的 Bagging集成方法，利用遺傳算法在不同的數據集上獲取特征子集，不同的基分類器在獨立的特征子集上訓練獲得，這樣可以最大限度地挖掘基分類器之間的差異性。同時，還進一步采用加權集成的方法優化基分類器的投票組合，進一步提高分類器的預測性能。最后把這種改進的集成分類方法應用到互聯網流量的分類中，目的是克服網絡的動態性帶來的分類模型的不穩定性。通過實際的流量數據測試，這種新的集成分類器具有較好的泛化能力，適合應用于互聯網這種高度動態環境。

參考文獻：

[1] ZHOU Z H.Ensemble methods： foundations and algorithms[M].Boca Raton： CRC Press, 2012.

[2] LI H, WANG X, DING S.Research and development of neural network ensembles： a survey[J].Artificial Intelligence Review,2017： 1-25.

[3] AMOZEGAR M, KHORASANI K.An ensemble of dynamic neural network identifiers for fault detection and isolation of gas turbine engines[J].Neural Networks, 2016(76)： 106-121.

[4] INOUE H.Fast and accurate inference with adaptive ensemble prediction in image classification with deep neural networks[J].arXiv preprint arXiv：1702.08259, 2017.

[5] WANG Q, LUO Z H, HUANG J C, et al.A novel ensemble method for imbalanced data learning： bagging of extrapolation-SMOTE SVM[J].Computational Intelligence and Neuroscience, 2017(3)： 1827016.

[6] 高文, 錢亞冠, 吳春明, 等.網絡流量特征選擇方法中的分治投票策略研究[J].電子學報, 2015, 43(4)： 795-799.GAO W, QIAN Y G, WU C M, et al.The divide-conquer and voting strategy for traffic feature selection[J].Acta Electronica Sinica, 2015, 43(4)： 795-799.

[7] 錢亞冠, 張旻.基于過抽樣技術的 P2P 流量識別方法[J].電信科學, 2014, 30(4)： 109-113.QIAN Y G, ZHANG M.P2P traffic identification based over-sampling technique[J].Telecommunications Science, 2014,30(4)： 109-113.

[8] KEARNS M.Learning Boolean formulae or finite automata is as hard as factoring[R].Technical Report TR-14-88 Harvard University Aiken Computation Laboratory, 1988.

[9] KEARNS M, VALIANT L.Cryptographic limitations on learning Boolean formulae and finite automata[J].Journal of the ACM (JACM), 1994, 41(1)： 67-95.

[10] EFRON B, TIBSHIRANI R.An introduction to the bootstrap[M].New York： Chapman & Hall, 1993.

[11] TONGAONKAR A, TORRES R, ILIOFOTOU M, et al.Towards self-adaptive network traffic classification[J].Computer Communications, 2015(56)： 35-46.

[12] SOYSALA M, SCHMIDT E G. Machine learning algorithms for accurate flow-based network traffic classification： evaluation and comparison[J].Performance Evaluation, 2010, 67(6)： 451-467.

[13] SINGH H.Performance analysis of unsupervised machine learning techniques for network traffic classification[C]//2015 Fifth International Conference on Advanced Computing&Communication Technologies (ACCT), May 15-16, 2015,Haryana, India.Piscataway： IEEE Press, 2015： 401-404.

[14] MOORE A W.Dataset[EB].2017.