基于多層MapReduce的混合網絡流量分類特征選擇方法

王　勇，龍　也，陶曉玲，韋　毅

(1.桂林電子科技大學 計算機科學與工程學院，廣西 桂林　541004；2.桂林電子科技大學 信息與通信學院，廣西 桂林　541004；3.桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林　541004)

基于多層MapReduce的混合網絡流量分類特征選擇方法

王勇1,3，龍也1，陶曉玲2,3，韋毅2

(1.桂林電子科技大學 計算機科學與工程學院，廣西 桂林541004；2.桂林電子科技大學 信息與通信學院，廣西 桂林541004；3.桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林541004)

摘要：針對傳統的特征選擇方法只適用于小規模數據集、運行效率低的缺陷，結合Filter方法和Wrapper方法的特點，提出一種基于多層MapReduce的混合網絡流量分類特征選擇方法。該方法通過Fisher score對數據進行預處理，剔除部分無關特征，實現高維數據的降維。采用序列前向搜索的搜索策略，通過多層MapReduce實現不斷選取分類能力最好的特征。實驗結果表明，該方法既保持較高的分類精度，又減少特征選擇時間，實現較好的加速比，提高了網絡流量分類的執行效率。

關鍵詞：特征選擇；Fisher score；SFS；MapReduce

特征選擇[1]是網絡流量分類的重要預處理步驟，它在損失較少信息的前提下，從原始特征集中選取，有助于分類決策的特征子集以使特定的評價標準最優。特征選擇因其對大規模數據性能的顯著影響，已成為機器學習、數據挖掘、模式識別等領域的研究熱點。根據選擇過程是否依賴于后續的分類算法，可將特征選擇方法分為過濾型(Filter)、包裝型(Wrapper)。Filter方法運算速度快，但準確率低，Wrapper方法準確率高，但訓練時間長，兩者均不能很好地平衡執行效率和準確率。因此，如何結合這兩種類型的特征選擇，實現去除高維特征中的冗余性和相關性特征，達到選取最優特征子集的目的，是目前特征選擇方面的一個研究熱點。

伴隨著高速、大規模復雜網絡的出現，網絡流量數據集規模日益增大，對網絡流量分類方法的時間、性能要求也隨之提高。對此，許多研究將特征選擇方法進行并行化設計，但當數據量超過數十GB時，其可行性仍顯著下降。云計算作為以數據為中心的密集型超級計算技術，其并行處理技術MapReduce[2]能為可劃分的大規模數據并行處理問題提供充分的計算語義，實現快速、高效、實時的執行并發任務。Hadoop作為MapReduce的一個典型開源實現，已被廣泛用于解決TB級以上數據集的存儲、分析和學習問題。

通過研究Filter和Wrapper兩種方法的思想，提出一種基于多層MapReduce的網絡流量特征選擇方法(hybrid network traffic classification feature selection method based on multilayer MapReduce，簡稱HTCFMM)。該方法先通過Filter方法的Fisher score剔除區分度小及鑒別性能較差的特征，以減小后續搜索過程的規模；采用Wrapper方法的思想，使用序列前向搜索(sequential forward search，簡稱SFS)作為搜索策略，分類器準確率作為評價準則，通過多層MapReduce實現不斷選取分類能力強的特征，最終得到最優特征子集。

1特征選擇算法研究現狀

目前，關于特征選擇方面的研究較多。Filter方法通過分析特征子集內部的特點來衡量其好壞。較為常用的方法有信息增益[3]、費舍爾得分(Fisher score)[4]、Relief-F[5]等。Wrapper方法采用不同的搜索策略搜索特征子集，一種評價準則評估候選子集。Rodrigues等[6]以蝙蝠算法BA作為指導，最優路徑森林分類器OPF作為評價函數來選擇最優特征子集。Chuang等[7]結合二進制粒子群優化算法BPSO與遺傳算法GA，并采用KNN作為分類器來選擇特征，獲得了較好的分類效果。Filter方法和Wrapper方法各有其優缺點，是2種互補的模式。Peng等[8]將2種方法整合成一個序列搜索方法以提高分類性能。這種混合型特征選擇方法一般先通過Filter方法過濾一部分無關或噪聲特征，然后使用Wrapper方法進一步優化選擇最優特征子集。此外，亓慧等[9]采用并行化的思想，集成多種特征選擇算法解決了高維數據問題，并提高了學習模型的泛化性。

近年來，云計算的研究為特征選擇提供新的方向，為大規模的數據集的特征選擇提供了新的研究方法。而利用云計算技術實現特征選擇的研究尚且較少。Zhou等[10]提出一種基于云模型的特征選擇方法，將其應用于入侵檢測，該方法評估每個屬性特征的權值，得到最優特征子集，解決了特征冗余問題，并提高了效率。Zhao等[11]引入云模型處理文本聚類高維特征選擇問題，將特征詞分塊處理，提高了聚類準確率。Sun等[12]基于Hadoop引入聯合互信息方法進行特征選擇，通過實驗驗證了該方法的高效性及可擴展性。Li等[13]基于云模型提出一種改進的SVM-BPSO特征選擇方法，采用Wrapper評估策略，以較快的收斂速度實現局部最優解，得到了較好的實驗結果。然而，關于云計算技術在網絡流量特征選擇方面的應用研究不多，通過多層MapReduce實現的相關研究更少，為此，將研究基于多層MapReduce的混合網絡流量特征選擇方法。

2HTCFMM方法

2.1基于Fisher score的Filter特征選擇方法

Fisher score是一種較為常用的Filter方法，是基于類內距離最小、類間距離最大的有監督特征選擇方法，它依據特征的內在屬性對單個特征進行打分并排序。相關定義為

(1)

通過Fisher score，可剔除區分度較小和鑒別性較差的特征，從而達到降維的目的。由于其計算簡單快捷，適合用于處理高維數據，但存在與后續學習算法不相關的缺陷，忽視了特征之間的相互作用，致使分類性能偏差較大。針對這一問題，通過Filter方法進行特征預處理后，采用Wrapper方法作進一步的特征選擇。

2.2基于SFS策略的Wrapper特征選擇方法

Wrapper方法中，獲得好的特征子集基于2個條件：1)一種評價準則來評估子集，2)根據一種搜索策略產生候選特征子集。本研究采用分類精度的評價準則和SFS的搜索策略。

SFS一般初始化最優特征子集V為空，每次選擇一個特征f加入到V，使得評估函數值最優。具體描述如下：

初始特征子集F={f1,f2,…,fm}，最優特征子集V為空集，類標簽向量C={c1,c2,…,cm}，分類模型M。

步驟：

1)將C與F的每個特征分別組成數據集，通過M得到分類準確率；

2)選出F中使數據集準確率最高的特征加入V，并從F中刪除該特征；

3)從F挑選任意一個特征與V的所有特征、C組成數據集，同樣通過M得到分類準確率；

4)選出F中使數據集準確率最高的特征加入V，并從F刪除該特征；

5)重復步驟3)～4)，直至達到停止準則給定的條件。

在此，所選取的停止準則是設定一個閾值γ，當前最大分類準確率與前一輪最大分類準確率差值大于γ時，停止運算。

2.3方法實現

MapReduce是用于大規模數據集并行運算的編程模型，將大規模數據集的操作分發給一個主節點管理下的多個分節點共同完成。MapReduce將數據集的分析操作抽象為Map(映射)和Reduce(規約)2種集合的操作，基于函數式編程語言的思想，屏蔽底層實現細節，降低了程序員并行編程的難度?；贛apReduce并行編程模型實現網絡流量特征選擇方法，其方法流程如圖1所示。

圖1　方法流程圖Fig.1　Flow chart of the method

該方法首先通過Fisher score對樣本數據集進行預處理，降低特征維數；然后采用序列前向搜索策略，不斷選出分類能力強的特征。

給定原始樣本數據集T=(F,X,C)。其中，數據樣本集X={x1,x2,…,xn}，共有n個樣本；F={f1,f2,…，fm}和C={c1,c2,…,cn}分別表示樣本集的特征集和類標簽集。樣本xi可形式化表示為特征值所對應的笛卡爾積：xi=〈a1,a2,…,am〉，ai為xi在特征fi上的具體取值，ci為xi的類標簽。設V、W為中間特征集合，S為最優特征子集，初始時均為空；R為最高分類準確率，初始化時為零。

整個過程通過多層MapReduce實現。具體描述如下：

1) 數據預處理。

a) 通過式(1)計算樣本集X中每個特征的區分度Fi，并將其值從大到小排序；

b) 選出前l個特征，從樣本集中刪除除l特征外的剩余特征，得到樣本集Y，Y={y1,y2,…,yn}；

c) 將樣本集按單個特征分割得到特征子集V，V={v1,v2,…,vl},l

2) 通過MapReduce過程挑選出準確率最高的樣本子集所對應的特征加入S。

a) Map過程。

輸入：key為R，value為S；

輸出：〈key1,value1〉對，key1為分類準確率Ri，value1為Ri所對應的特征。

對每個樣本子集通過重復采樣方式，抽取訓練子集Li；用Li訓練基分類器Ci，計算分類準確率Ri，輸出Ri及該基分類器相對應的特征。

b) Reduce過程。

輸入：key1為分類準確率Ri，value1為Ri所對應的特征；

輸出：〈key2，value2〉對，key2為R，value2為S。

對所有的Ri進行排序，選出分類準確率最大的基分類器；當Ri>R或R-Ri≤γ時，選出該基分類器，將R重設為最大準確率值，并將S重置為該基分類器所對應的全部特征；否則，R與S不變。

3) 當R與S不變時，過程結束，S即為被選的最優特征子集；否則，執行步驟4)～5)。

4) 將V中選出S中所有特征所對應的樣本子集合并，然后將V中剩余的樣本子集分別與該合并樣本子集合并得到集合W，W={w1,w2,…,wj},j

5) 執行步驟2)～3)。

3實驗結果與分析

3.1實驗環境與數據集設置

本實驗采用4個計算節點搭建Hadoop平臺，所有節點均參與計算和存儲，其中2個節點同時負責MapReduce任務調度。

實驗數據采用文獻[14]所使用的數據集[15]Moore-set，該數據集共包含2 265 156個網絡流量樣本，分為10大類，其中8類的統計信息如表1所示。由于Interactive 和Games的數量較少，不具代表性，因此，在實驗中不采用這2種數據。

表1　Moore-set流量數據統計

3.2結果分析

在實驗部分，測試算法2個方面的性能。1)比較本研究的特征選擇方法HTCFMM與NMIFS[16]、Fisher score在選擇不同特征維度下的分類精度，另外，還比較了與未經Filter方法預處理時方法的分類精度和執行效率；2)比較HTCFMM分別在Hadoop集群和單機環境下的執行效率。

實驗整合所有的Moore-set數據集，通過分層抽樣選取數據集中各應用類型的10%作為測試數據。實驗參數γ取0.000 1，采用4折交叉驗證方式，通過J48算法測試分類性能，重復10次，對所有結果取平均值。

3.2.1分類準確率

不同維度下的分類精度如圖2所示。從圖2可見，在不同的特征維度下，HTCFMM的分類準確率優于NMIFS和Fisher score，在特征維數為16時，HTCFMM基本達到最優，得到的特征序列有效性最佳。因為NMIFS和Fisher score方法在選取特征時，只通過分析特征集合內部的特點來衡量特征的好壞，與后續的學習算法相互獨立，HTCFMM方法既考慮了特征之間的相互作用，又將特征選擇過程與分類準確率相結合，分類效果明顯要好。

圖2　不同維度下的分類精度Fig.2　Classification accuracy under different dimensions

表2為通過HTCFMM方法與SFS搜索策略進行特征選擇的測試結果。

表2　HTCFMM與SFS特征選擇的測試結果

從表2可看出，在選擇不同的特征個數時，兩者的分類準確率相近；從時間比來看，HTCFMM的時間性能相比SFS改善了很多。由此可見，通過Filter預處理的方法對分類準確率影響較小，而在時間效率上差距明顯，這說明了HTCFMM方法結合了Filter方法與Wrapper方法。

3.2.2單機/并行執行效率

不同環境下的運行時間如圖3所示。從圖3可看出，當特征個數較少時，集群環境下的特征選擇時間與單機的特征選擇時間差距較小；隨著特征個數的增多，差距越來越大，而單機的特征選擇時間消耗顯著增加。因為當數據量較少時，MapReduce本身Job調用及數據的Split和重組等需要耗費一定的時間，但隨著數據量的不斷增加，MapReduce運行機制逐步穩定，并行算法的優越性也逐漸顯現，在很大程度上提高了算法效率，體現了并行模型的高效性。

圖3　不同環境下的運行時間Fig.3　Running time under different environments

為了精確地衡量HTCFMM在時間性能上的提升，采用了加速比S=Ts/Tp。其中：Ts為單個計算節點的特征選擇時間；Tp為計算節點p的特征選擇時間。實驗分別計算了節點數為2、3、4時的加速比，如圖4所示。

圖4　加速比Fig.4　Speedup ratio

從圖4可看出，當特征數一定時，隨著計算節點的增加，其加速比相差越來越小；隨著特征維數的增加，加速比在增大到一個最大值時減小，之后呈線性。由此可知，并行的特征選擇方法比單機的特征選擇方法可實現近似線性加速比，且隨著計算量的增大，并行的效果越來越好，計算節點個數的增加提高了算法執行效率。因此，MapReduce并行環境可解決高維數據特征選擇的問題。

4結束語

探討了基于多層MapReduce并行框架下的網絡流量特征選擇方法。該方法結合Filter方法與Wrapper方法，采用Fisher score去除不相關特征，以降低候選特征維數，通過后續學習算法進一步優化得到最優特征子集，提高了特征選擇方法的分類性能。另外，相關實驗表明，在Hadoop平臺上進行海量數據特征選擇時，算法的執行效率與集群的規模有著直接的關系，節點越多，加速比越明顯，效率越高。在高速網絡環境中，下一步的研究基于Hadoop平臺，實現一種并行網絡流量分類算法，與本研究的特征選擇方法相結合,實現網絡流量高效快速的分類。

參考文獻:

[1]姚旭，王曉丹，張玉璽，等．特征選擇方法綜述[J].控制與決策，2012,27(2):161-166．

[2]DEAN J,GHEMAWAT S.Mapreduce:simplified data processing on large clusters[J].Communications of the ACM，2008，51(1)：107-113．

[3]張振海，李士寧，李志剛，等.一類基于信息熵的多標簽特征選擇算法[J].計算機研究與發展，2013,50(6):1177-1184．

[4]BISHOP C M.Neural networks for pattern recognition [M].Oxford University Press,1995.

[5]黃莉莉，湯進，孫登第，等．基于多標簽ReliefF的特征選擇算法[J].計算機應用，2012,30(10):2888-2890.

[6]RODRIGUES D,PEREIRA L A M,NAKAMURA R Y M,et al.A wrapper approach for feature selection based on bat algorithm and optimum-path forest[J].Expert Systems with Applications,2014,41(5):2250-2258.

[7]CHUANG L Y,YANG C H,LI J C,et al.A hybrid BPSO-CGA approach for gene selection and classification of microarray data[J].Journal of Computational Biology,2012,19(1):68-82.

[8]PENG Yonghong,WU Zhiqing,JIANG Jianmin.A novel feature selection approach for biomedical data classification [J].Journal of Biomedical Informatics,2010,43:15-23.

[9]亓慧，王文劍，郭虎升．一種基于特征選擇的SVM Bagging集成方法[J]．小型微型計算機系統，2014，35(11): 2533-2537.

[10]ZHOU Liuhong,LIU Yanhua,CHEN Guolong.A feature selection algorithm to intrusion detection based on cloud model and multi-objective particle swarm optimization [C]//2011 Fourth International Symposium on Computational Intelligence and Design.New Jersey:IEEE Press,2011:182-185.

[11]ZHAO Junmin,ZHANG Kai,WAN Jian.Research of feature selection for text clustering based on cloud model [J].Journal of Software,2013,8(12):3246-3252.

[12]SUN Zhanquan,ZHAO Li.Data intensive parallel feature selection method study[C]//2014 International Joint Conference on Neural Networks.New Jersey:IEEE Press,2014:2256-2262.

[13]LI Jizhen,MENG Xiangru,WEN Jing.An improved method of SVM-BPSO feature selection based on cloud model[J].IAES TELKOMNIKA Indonesian Journal of Electrical Engineering,2014,12(5):3979-3986.

[14]ZUEV D,MOORE A W.Traffic classification using a statistical approach[C]//6th International Workshop on Passive and Active Network Measurement,Boston.Berlin Heidelberg:Springer Verlag Press,2005:321-324．

[15]MOORE A W,ZUEV D.Internet traffic classification using bayesian analysis techniques[EB/OL].[2011-08-10].http://www.cl.cam.ac.uk/research/srg/netos/nprobe/data/papers/ sigmetrics/index.html.

[16]ESTéVEZ P A,TESMER M,PEREZ C A,et al.Normalized mutual information feature selection[J].IEEE Transactions on Neural Networks,2009,20(2):189-201.

編輯：梁王歡

Hybrid network traffic classification feature selection method based on multilayer MapReduce

WANG Yong1,3, LONG Ye1, TAO Xiaoling2,3, WEI Yi2

(1.School of Computer Science and Engineering, Guilin University of Electronic Technology, Guilin 541004, China;2.School of Information and Communication Engineering, Guilin University of Electronic Technology, Guilin 541004, China;3.Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004, China)

Abstract：The traditional feature selection method is only suitable for small-scale datasets and the operating efficiency is low, combining the feature of Filter and Wrapper, a hybrid network traffic classification feature selection method based on multilayer MapReduce is proposed. In this method, Fisher score is used to preprocess the data, the part of unrelated feature is removed and the dimensionality is reduced. Then sequential forward search strategy is adopted, and the best feature for classification is selected constantly by multilayer MapReduce. The experimental results show that this method can not only keep the high classification accuracy, but also reduce the feature selection time. Meanwhile, it can get a nice speedup ratio and increase the efficiency of network traffic classification.

Key words：feature selection; Fisher score; SFS; MapReduce

收稿日期：2015-04-30

基金項目：國家自然科學基金(61163058,61363006)；廣西可信軟件重點實驗室開放基金(KX201306)

通信作者：王勇(1964-)，男，四川閬中人，教授，博士，研究方向為計算機網絡技術與應用、信息安全。E-mail:ywang@guet.edu.cn

中圖分類號：TP301.1

文獻標志碼：A

文章編號：1673-808X(2016)02-0123-06

引文格式： 王勇，龍也，陶曉玲，等.基于多層MapReduce的混合網絡流量分類特征選擇方法[J].桂林電子科技大學學報，2016,36(2)：123-128.