基于RIPPER的網絡流量分類方法

曹彥珍++何云斌++朱素霞++孫廣路

摘要：利用一種規則學習方法中的重復增量式降低錯誤剪枝方法解決網絡流量分類問題。利用該方法能夠挖掘出網絡流屬性特征和類別之間的相關關系，并將挖掘出的關系構成分類器用于網絡流量分類。該方法能夠解決傳統機器學習方法在網絡流量中有大量的不平衡數據集時，分類錯誤率高等問題。實驗證明，該方法在網絡流量分類標準數據集上具有很高的分類準確率、查全率和查準率。

關鍵詞：網絡流量分類；規則學習；重復增量式降低錯誤剪枝；不平衡數據

DOI：1015938/jjhust201705016

中圖分類號： TP393

文獻標志碼： A

文章編號： 1007-2683（2017）05-0085-06

Network Flow Classification MethodruleBased

CAO Yanzhen，HE Yunbin，ZHU Suxia，SUN Guanglu

（School of Computer Science and Technology， Harbin University of Science and Technology， Harbin， 150080， China）

Abstract：In this paper， repeated incremental pruning to produce error reduction which is a rule learning method is used to solve network traffic classification The method can be used to dig out the correlations between attributes and classes， which are utilized to build a classifier for traffic classification The proposed method can decrease the classification error rate when the traditional machine learning method has a large number of imbalanced data sets in the network traffic Experiments show that the method has a very high classification of accuracy， recall and precision in network traffic classification standard data sets

Keywords：traffic classification； rulebased learning； repeated incremental pruning to produce error reduction； unbalanced data

收稿日期： 2016-01-28

基金項目： 國家自然科學基金（60903083， 61502123）；黑龍江省新世紀人才項目（1155ncet008）；黑龍江省博士后科研啟動基金

作者簡介：

曹彥珍（1991—），女，碩士研究生；

朱素霞（1978—），女，博士，副教授

通信作者：

何云斌（1972—），男，博士，教授，Email：hybha@ 163com

0引言

隨著網絡中各種應用的逐漸增加，網絡越來越難以管理，網絡安全問題也越來越嚴重，在這種情況下網絡流量分類技術應運而生。網絡流量分類技術是針對網絡中的每一條流量進行分類，識別出其所屬的應用層協議類型，為流量控制提供依據，是網絡安全技術的基礎研究之一。同時，網絡流分類技術能夠增強網絡的可控性， 幫助相關的研究人員掌握網絡上的流量分布情況， 幫助網絡運營商優化服務質量，預防并阻止各種網絡犯罪行為[1][2]。

已有的網絡流量分類技術有基于端口、基于載荷、基于行為以及基于機器學習等方法。隨著越來越多的應用采用動態端口傳輸，導致基于端口的方法失效；基于載荷的方法有很高的識別精度，但侵犯用戶隱私，并且不能識別加密流量；基于行為的方法不能實現實時分類等[3-5]。近幾年，機器學習得到了迅猛發展，很多研究者將機器學習方法應用到了網絡流分類中，包括樸素貝葉斯（naive bayesian，NB）[6]、支持向量機（support vector machine，SVM）[7]、C45決策樹[8]等，并取得了不錯的效果。

面對網絡應用的快速發展，網絡中流量會出現應用協議類別不平衡的情況，而傳統的網絡流量分類方法的分類性能往往偏向大類，而忽略小類。在面對大量不平衡數據，傳統的機器學習方法不能取得很好的效果。因此，本文提出一種基于重復增量式降低錯誤剪枝（repeated incremental pruning to produce error reduction，Ripper）的網絡流量分類方法，由于Ripper方法是按照出現最不頻繁的類別到出現最頻繁的類別的順序產生規則的，使得它對于大量的不平衡數據集有很好的分類性能。

本文在第1部分簡要介紹了相關工作，包括應用于網絡流量分類的機器學習方法以及Ripper方法的應用等。第2部分首先介紹了特征選擇方法，然后詳細介紹了基于Ripper的網絡流量分類方法。第四部分介紹了實驗環境和實驗數據集，最后一部分得出實驗結果并對其進行分析，及得出結論。

1相關工作

隨著機器學習在各個領域的廣泛應用，基于機器學習[9]的網絡流量分類成為近年來的研究熱點。2004年，基于機器學習的網絡流量分類方法被一些學者提出，這種方法是根據網絡流量具有的統計特性來對網絡流量進行分類[10]。到現在已經有很多種機器學習方法被引入到網絡流量分類的研究中，其中具有代表性的有： Moore等在2005年利用有監督的樸素貝葉斯方法對網絡流量進行分類，取得了90%以上平均識別準確率[4]。Erman等在2007年融合了有監督和無監督的機器學習方法，提出了半監督的機器學習方法解決網絡流量分類問題，取得了很好的效果[11]。徐鵬等在2008年提出一種基于C45決策樹的網絡流量分類方法，利用訓練數據集中的信息熵來構建模型，這種方法也被證明在分類穩定性上有很好的效果[8]。之后他又提出一種基于支持向量機的網絡流量分類方法，該方法能夠解決以往方法中條件獨立假設的問題，在先驗知識相對不足的情況下，具有較高的分類準確率和分類穩定性[7]。Yu Jin等在2012年提出一種模塊化的機器學習方法，應用于大型網絡的流量分類中并取得了較好的效果[12]。endprint

不同的學習模型有不同的知識表示形式，其中，規則是一種非常直觀和自然的知識表示形式，由于其形式簡單、無結構而被廣泛研究，并得到快速發展。Ripper方法由Cohen提出[13]，是基于規則學習的方法中較為經典的一種。Nilgün等在2010年將Ripper方法用于對肝炎引起的死亡風險問題進行預測，實驗結果顯示Ripper方法有不錯的預測準確率，并且能夠產生非常簡單的規則[14]。2011年，Anil Rajput等利用Ripper方法處理電子政務數據，實驗結果表明通過Ripper方法產生的規則簡單易懂，利于相關人員對電子政務數據的研究和使用[15]。電子科技大學的鐘星將Ripper方法用于研究軟件缺陷預測，并取得了不錯的實驗效果[16]。M Tarun等將Ripper方法應用在教育研究中，通過對應試者的相關特征進行分析，并預測該應試者能否通過執照考試，實驗結果顯示該方法在預測方面有很高的準確率[17]。中國科學技術大學的張小康將Ripper方法應用于惡意代碼的檢測技術，取得了不錯的效果[18]。GMeeraGandhi等在對網絡入侵檢測的研究中，通過多種評估項對基于規則的幾種歸納學習方法進行對比，結果顯示Ripper方法在基于規則學習的方法中能表現出很好的性能[19]。

2基于Ripper的流量分類方法

本文首先對網絡流分類問題進行形式化定義。給定網絡流樣本集S={s1，s2，…，sn}，其特征集為F={f1，f2，…，fm}，其中n是樣本個數，m是特征維數，則對于某一條樣本可以表示為si={si1，si2，…，sim}，1≤i≤n。si的類別 ci∈C，C={c1，c2，…，cq}為類別集合，q為類別數量。

利用基于規則學習的方法處理分類問題通常分為兩步：第一步是通過對訓練樣本歸納學習總結出特征與類別之間的關聯關系，形成if-then形式的規則；第二步是利用形成的規則對未知的樣本進行匹配檢測，以達到分類的目的。本文首先采用ReliefF算法對數據進行降維，然后將降維后的數據利用Ripper方法進行規則提取，得到最簡的規則對測試數據進行測試。

21特征選擇算法

由于網絡流量的特征中存在與類別無關特征和冗余特征，因此需要對數據進行特征選擇。本文應用ReliefF算法進行特征選擇，該算法通用性較強，復雜性較低。

ReliefF算法是從訓練集中每一類的樣本中各選擇d個距離si最近的樣本，其中與si同類的d個樣本定義為集合H，與si不同類的樣本根據所屬類別c的不同分別定義為集合M（c），然后計算不同類別的樣本在某一特征t上的相關性，并給予不同的權重，W={wi，w2，…，wp}為最終所求的特征權重向量，并根據權重大小將特征按降序排序，從而得到特征對類別的從強到弱的區分能力順序。

ReliefF具體算法如下：

算法1 ReliefF

輸入：樣本集S，特征集F，類別集C，近鄰數d，取樣次數r

輸出：權值向量W

1初始化W=0

2for i←1 to r do

3從S中隨機選擇一個樣本si；

4從與si同類的樣本中選擇最近的d個近鄰，記為H；

5for each c∈C

6從與si不同類的樣本中選擇最近的d個近鄰，記為M（c）；

7wt=wt-∑x∈Hdiff（t，si，x）/（r*d）+

∑c≠class（si）[p（c）1-p（class（si））∑x∈M（c）diff（t，si，x）]/（r*d）

diff（t，si，x）=|sit-xtmaxt-mint|

8endfor

22基于Ripper的流量分類方法

規則學習是通過對訓練集的學習，總結歸納出特征值與類別之間的某種關系，形成if-then形式的規則，再利用這些形成的規則對數據集進行匹配檢測。規則的一般形式是：

ΛNi=1（ai=vi）→ci（1）

式中：箭頭左邊項稱為規則前件；ai表示特征；vi表示特征值；箭頭右邊項稱為規則后件；ci表示結論，即樣本所屬的類別。

Ripper方法是一種用于快速分類的規則學習方法，該方法是對增量式降低錯誤剪枝方法（Incremental Reduced Error Pruning，IREP）的一種改進。對于網絡流量中多種應用類別的分類問題，首先按照應用類別出現的頻繁程度進行排序，假設{c1，c2，…，cq}是排序后的類別順序，其中c1是最不頻繁的類別， cq是最頻繁的類別。然后將類別按照排列好的順序依次產生規則：首先將c1的樣本作為正例，其余類別樣本全部作為反例，并產生區別正例和反例的規則，依次執行，直到剩下cq類，并將其作為默認類。這樣Ripper方法能夠最先處理最不頻繁出現的類別，最后處理最頻繁出現的類別，使用從一般到特殊的策略進行規則的生成。正是由于Ripper產生規則的特殊性，使它對于處理不平衡數據有很好的性能。

Ripper方法的流程圖如圖1所示。

Ripper方法主要分兩部分，一部分為擴展，另一部分為收縮，在擴展的過程中，首先將規則集置空，再向規則集中添加條件，直到該規則集能夠擴展到涵蓋整個數據集為止；而在收縮的過程中，卻是不斷地刪除規則和收縮條件。最后利用式（2）來確定是否達到最精簡的規則：

C=xk-xpxk+xp（2）

其中：xk是規則所覆蓋的數據個數，xp是沒有被覆蓋的數據個數，當函數值C不能再變大時方法停止收縮。Ripper方法的具體算法如下：

算法2 Ripper

輸入：訓練集S

輸出：規則集Rendprint

1初始化R={}

2for{c1，c2，…，cq}中的每一類

3將所選中的類別的樣本作為正例Pos，其余類別的樣本作為反例Neg

4While Pos≠null do

//生長階段

5把Pos分為生長正例PosGrow （2/3）和剪枝正例PosPrune （1/3）

6把Neg分為生長反例NegGrow （2/3）和剪枝反例NegPrune （1/3）

7通過貪婪算法，在PosGrow集上利用信息增益條件P（log（pt）-log（PT））為特征值生成規則r

//修剪階段

8根據公式（2）的度量條件在PosPrune和NegPrune上對r進行剪枝，得到規則r′

9把r′加入到規則集R中，并刪除r′覆蓋的Pos和Neg中的樣本

10endWhile

11return R

本文將Ripper方法應用到網絡流量分類中，對于某一條樣本si， Ripper方法可以提取出以下格式的規則，從而形成規則庫：

class1：si1 =a，si2 =b。如果si1為a，si2為b，那么這條樣本屬于class1；

class2：si3=c，si5=d。如果si3為c，si5為d，那么這條樣本屬于class2；

class3：true。如果不滿足以上任何一個規則，則這條樣本屬于class3。

3實驗

31實驗環境

本文在實驗中使用了新西蘭懷卡托大學Witten教授等人開發的開源工作平臺Weka3713[20]。該工具利用Java語言實現了基于樸素貝葉斯、支持向量機、C45決策樹、規則等多種分類方法。本文的實驗平臺為PC機，其CPU為Intel（R）Core（TM）i3340GHz，內存為4G，運行Windows7操作系統。

32實驗數據

為了驗證方法的有效性，本文采用的數據集是劍橋大學Moore教授等人在網絡流量分類上使用的標準數據集[4]。該數據集是從2003年8月20日0時到24時流經3個生物學研究所中共享的網絡出口，這些網絡樣本被分為10個子集，形成實驗數據集。

數據集一共包含12類應用，但是某些應用的樣本在數據子集中的數量過少，不足以用來訓練分類器，因此，這里我們選擇其中的六類進行研究，分別是：WWW、MAIL、FTPDATA、DATABASE、P2P、SERVICES。在這六類中，WWW的數量占總數量的一半，其余五類的數量一共占總數量的一半，是一種典型的不平衡數據集。并且，每兩個數據子集作為一個實驗數據集，即entry01和entry02作為t1，entry03和entry04作為t2，entry05和entry06作為t3，entry07和entry08作為t4，entry09和entry10作為t5。另外，為了得到大量的不平衡數據，我們按照上述的比例將多個數據子集進行合并，形成足夠數量的數據樣本。表1為通過ReliefF算法選擇出的特征子集，表2為實驗數據集中各個類別的樣本數量。

33實驗結果與分析

實驗利用t1、t2、t3、t4、t5數據集分別在樸素貝葉斯、支持向量機、C45決策樹、Ripper這四個分類器上做的對比實驗，表3是將t1作為訓練集，將t2、t3、t4、t5分別作為測試集的實驗結果。圖2、圖3和圖4是將t1作為訓練集，將t2、t3、t4、t5分別作為測試集時，樸素貝葉斯、支持向量機、C45決策樹分別與Ripper方法的準確率對比情況。另外，實驗也采用各類別的查準率（Precision）、查全率（Recall）和它們的調和平均值FMeasure來評價結果。表4給出在不同方法準確率對比實驗中，以t1作為訓練集，t4作為測試集時的評價指標。

另外進行了一組分別采用不同樣本數的數據集在Ripper方法上進行的對比實驗，并對該方法進行評估。在Moore數據集上分別選取了50000個樣本、100000個樣本、150000個樣本以及200000個樣本進行實驗，在該實驗中所采取的實驗方法是十折交叉。圖5是不同數量的樣本的數據集在Ripper方法上的分類準確率。

通過以上實驗結果可以看出，在相同的數據集下，相比于傳統的樸素貝葉斯、支持向量機、C45決策樹等方法，Ripper方法有更高的準確率、查準率和查全率。在使用同一種方法時，在不同的樣本數進行實驗的結果中，增大樣本規模會對分類建模效果有一定提升作用。

4結論

本文重點介紹了一種規則學習算法Ripper，并將其應用于網絡流量分類的研究中，重點解決傳統網絡流量分類方法中分類模型偏向大類、忽略小類的問題。在訓練過程中，應用ReliefF特征選擇算法對數據進行降維，對降維后的數據用Ripper方法進行分類。在Moore數據集上與樸素貝葉斯、支持向量機、C45決策樹等方法進行實驗對比，結果表明在網絡流量數據出現大量的類別不平衡問題時，Ripper方法能夠實現很好的分類性能。

參 考 文 獻：

[1]MOORE A W，PAPAGIANNAKI K Toward the Accurate Identification of Network Applications[C]//International Workshop on Passive and Active Network Measurement Springer Berlin Heidelberg， 2005： 41-54

[2]孫廣路， 郎非， 楊明明 基于混合方法的流量測量系統[J]. 電機與控制學報， 2011， 15（6）： 91-96endprint

[3]FINSTERBUSCH M， RICHTERr C， ROCHA E， et al A Survey of Payloadbased Traffic Classification Approaches[J]. IEEE Communications Surveys & Tutorials， 2014， 16（2）： 1135-1156

[4]CHENG G， WANG S Traffic Classification Based on Port Connection Pattern[C]//Computer Science and Service System （CSSS）， 2011 International Conference on IEEE， 2011： 914-917

[5]董輝， 孫廣路， 李丹丹， 等 基于鏈路同質性的應用層流量分類方法[J]. 哈爾濱理工大學學報， 2013， 18（4）： 84-88

[6]MOORE A W，ZUEV D Internet Traffic Classification Using Bayesian Analysis Techniques[C]//ACM SIGMETRICS Performance Evaluation Review ACM， 2005， 33（1）： 50-60

[7]林森， 徐鵬， 劉瓊 基于支持向量機的流量分類方法[J]. 計算機應用研究， 2008， 25（8）： 2488-2490

[8]ZHANG Y， WANG H， CHENG S A Method for Realtime Peertopeer Traffic Classification Based on C4 5[C]//Communication Technology （ICCT）， 2010 12th IEEE International Conference on IEEE， 2010： 1192-1195

[9]王濤，余順爭 基于機器學習的網絡流量分類研究進展[J]. Journal of Chinese Computer Systems： Vol33 No5 2012

[10]ROUGHAN M， SEN S， SPATSCHECK O， et al Classofservice Mapping for QoS： a Statistical Signaturebased Approach to IP Traffic Classification[C]//Proceedings of the 4th ACM SIGCOMM conference on Internet measurement ACM， 2004： 135-148

[11]ERMAN J， MAHANTI A， ARLITT M， et al Offline/Realtime Traffic Classification Using Semisupervised Learning[J]. Performance Evaluation， 2007， 64（9）： 1194-1213

[12]JIN Y， DUFFIELD N， ERMAN J， et al A Modular Machine Learning System for Flowlevel Traffic Classification in Large Networks[J]. ACM Transactions on Knowledge Discovery from Data （TKDD）， 2012， 6（1）： 4

[13]COHEN WW Fast Effective Rule Induction[C]//Proceedings of the twelfth international conference on machine learning 1995： 115-123

[14]ULUTA

瘙 塁 DEMIR N， Dal Evaluation of Risk of Death in Hepatitis by Rule Induction Algorithms[J]. Scientific Research and Essays， 2010， 5（20）： 3059-3062

[15]RAJPUT A， AHARWAL R P， DUBEY M， et al J48 and JRIP Rules for EGovernance Data[J]. International Journal of Computer Science and Security （IJCSS）， 2011， 5（2）： 201

[16]鐘星 基于數據挖掘和多目標決策的軟件缺陷預測方法研究[D]. 電子科技大學， 2011

[17]IVY M T， BOBBY D G Generating Licensure Examinatio Performance Models Using PART and JRip Classifiers： A Data Mining Application in Education[J] International Journal of Computer and Communication Engineering， 2014，3（3）：

[18]張小康 基于數據挖掘和機器學習的惡意代碼檢測技術研究[D]. 合肥： 中國科學技術大學， 2009

[19]MEERA G G， KUMARAVEL Appavoo Effective Network Intrusion Detection using Classifiers Decision Trees and Decision rules[J] Int J Advanced Networking and Applications， 2010，2（3）：686-692

[20]WITTEN I H， FRANK EData Mining Practical Machine Learning Tools and Technique[M].2nd ed北京：機械工業出版社，2005

（編輯：溫澤宇）endprint