基于概念飘移检测的自适应流量识别的研究

第3卷第6期2013年12月智 能 计 算 机 与 应 用INTELLIGENT COMPUTER AND APPLICATIONSVol.3 No.6Dec.2013

摘要：基于机器学习的网络流量识别技术作为一种典型的数据流分类的应用，对概念漂移检测方法的要求越来越高。针就这个问题，首先分析了概念漂移检测的两种典型方法，然后结合实际的网络环境中经常存在类别不平衡的特性提出了一种检测概念漂移的算法CF_CDD，并对该算法的原理和统计学理论基础进行了详细的论述。再根据提出的概念漂移检测算法构建基于权重的集成分类器算法TCEL_CF_CDD，以达到自适应流量识别的目的。最后进行实验，验证了文中提出的概念漂移检测算法的可行性。

关键词：流量识别； 概念漂移； 统计学检验； 集成学习

中图分类号：TP393 文献标识码：A文章编号：2095-2163（2013）06-0050-05

0引言

随着网络日新月异地迅猛发展，网络上的各种协议也相继出现，与此相对应，流量识别技术则日趋显示了其重要的作用和价值。传统的基于端口的流量识别方法和深层数据包检测（DPI）技术已经不能很好地完成识别的任务，当前基于机器学习的流量识别技术已经成为引领该领域研究的主流和方向[1]。网络流量识别本质上是根据网络数据包的特征将网络数据流分成已知的协议类别，而这正是一种典型的数据流分类的应用，那么必然地数据流分类面临的概念漂移检测问题在进行流量识别技术研究时也就需要慎重对待、深入考虑。近年来，关于数据流分类中概念漂移检测的研究已取得了不少的成果，但是各类方法在应对某种具体的数据流时却都具有一定的局限性[2]。本文结合实际网络环境中存在类别不平衡的情况，提出了更适用于网络流量识别的概念漂移检测方法。

1流量识别与概念漂移

概念漂移是数据流分类中的问题。作为一种具体的数据流，网络数据流当然也存在概念漂移的相关问题。

1.1流量识别中的概念漂移

以机器学习的角度来看，基于机器学习的网络流量识别技术实际上就是学习概念的过程[3]。识别的实现是通过在训练网络数据集内寻找其蕴含的协议分类规则（概念），由此得到网络流量识别器，进而识别测试网络数据包或者实际工作中到来的网络数据包的类别。

假定网络数据流D={…，di-1，di，di+1，…}，其网络数据流中的协议类别C={C1，C2，…，Cn}，t时刻，在训练网络数据集Dt上训练得到识别规则f：DtC，那么在t+1时刻就可以对dt+1网络数据包的协议类别预测为f（dt+1）。但是，如果网络数据流的隐藏背景在t时刻和t+1时刻发生了改变，引发了概念漂移，t+1时刻的实际识别规则已经是g：Dt+1C，且g≠f。也就是说，dt+1的真实协议类别是g（dt+1），因而利用原来的识别规则f预测的dt+1的协议类别即是不尽合理的。通过上面的论述可以看到，概念漂移对网络流量识别的影响，而正确的做法也就相应可得了。假定在t+t时刻发生了概念漂移，应该迅速检测出漂移的发生，然后重新训练识别器，得到正确的识别规则g，然后利用g来进行以后的网络数据包协议类别预测。

自适应的流量识别就是能够自主地检测到概念漂移的发生，而后再对分类器进行重新构建，以保证其对动态网络数据流的正确识别。

1.2检测方法分类

由于概念漂移的生成原因极其复杂，目前的检测方法都不是直接的，而只是间接的[4]。最为基础的有两个：

（1）可能导致概念漂移发生的原因；

（2）概念漂移发生后可能产生的结果。

前者称之为性质法，后者为性能法[5]。

性质法是指监测最新的网络数据集合的相关统计性质，如协议种类的分布、各数据包的特征分布等等。Alippi设计了不依赖先验信息而只需要数据分布模型的中心极限定理的概念漂移检测算法[6]；Peter等提出了基于熵的概念漂移检测方法[7]。

性能法是指检测识别器最新的性能指标，如分类精度、召回率等等，如果分类器的性能指标出现较大波动，即说明发生了概念漂移。Widmer的FLORA算法依赖分类器的样本覆盖量和准确率决定窗口大小[8]；Last等提出的OLIN算法[9]即根据误差率来判断概念漂移产生与否。

2概念漂移检测

上节阐述的两种概念漂移检测方法中，最经常使用的是基于性能监测的方法，但是却不适合类别不平衡的数据流环境。本节将会看到，网络流量环境中经常出现的类别不平衡现象对概念漂移检测的影响，同时结合这点，本文也提出了改进算法，以适应实际网络环境下的动态流量变化。

2.1检测算法原理

对于稳定的网络流量，其各个协议类别是大致服从同一概率函数分布的，但是，如果一个存在概念漂移的网络流量中，网络数据包协议类别的分布概率却会随着概念漂移的发生而相应改变。因此以观察协议类别的概率分布变化来检测网络流量是否发生概念漂移则不失为一个恰当稳妥的办法。根据贝叶斯理论知道，概率分布P（w/x） = P（x/w）P（w）/P（x）。当P（x）改变而P（x/w）不变时，也就是说之前不常出现的协议数据包开始大量出现了或者相反，此时发生的概念漂移就是渐变；当P（x）不变而P（x/w）发生改变时，这种概念漂移就是突变。通常，在一个网络数据流中多会同时存在这两种类型的概念漂移，且也很难进行有效区分，但是从检测概念漂移的目的来说，检测到概念漂移后即可对分类器进行重新构建，因此也就没有必要区分概念漂移的具体类型了。

网络数据流量是按照时间相依有序的离散的数据集合，流量识别实质上就是进行时间序列分析。粗略来看，如果只是简单的对网络流量进行时序分析，似乎忽略了数据流变量之间内存因果关系和结构关系的影响。但是实际上时序分析是从总体方面对网络流量进行考察，综合说明各种作用力的共同影响。当无法轻易获得所关心的各种纷繁因素时，就可以直接将时间t用作变量来代替各种因素。因此，概念漂移检测就可以将时间t引入到文中的检测模型内，从而完成整个算法。

综上，当将时间t作为变量引入检测模型后，再加上一定的协议类别变量，此时如果能够找到两个变量之间的关系问题，就能够得到概念漂移检测的解决方法。而统计学理论已有很多研究成果就是致力于探讨变量之间的关系，本文就从统计学理论中寻求概念漂移检测的方法。

2.1.1统计学理论——卡方检验

卡方检验是一种应用相当广泛的非参数统计理论，利用该理论，可以判定实际观察的概率分布是否发生了改变还是仅来自于理论误差。

网络数据包集合，函数ψ是数据包的某项特征变量Z的概率分布，而且满足条件（1）：

P（Z=ci）=pi，s.t. Pi>0， ∑ni=1 pi=1（1）

变量ni代表监测到的网络流量数据集合中数据包协议类别为ci的数量，所有ni的和满足条件（2）：

∑mi=1 ni=n（2）

已经知道，ni是监测值，再假定mi是理论值，则根据以上定义可得卡方值，如式（3）：

χ2=∑ni=1（ni-mi）2mi（3）

综上可得，如果卡方值小于其临界值，函数ψ就是变量Z的最优拟合函数；相反，如果卡方值大于临界值，函数ψ就不再是变量Z的最优拟合函数。卡方的临界值取决于已验证得到的χ2统计理论表。

本文中，利用卡方值来检验连续两个网络流量的数据集合Di和Di+1是否发生了概念漂移。为了进一步阐述检测方法，先做如下两个假设。

（1）假定函数ψ已经满足于一个数据包集合的分布，然后验证其连续的下一个集合是否满足该条件；

（2）假定这个网络流量中只存在两种协议的数据包，即Http和Non-http。

根据上述假设，探讨分析可得如表1所示的连续两个网络流量的数据包集合Di和Di+1的类别分布，表1中变量c1， c2， c3， c4分别代表Http和Non-http在不同数据集合中的观察个数。根据这四个变量，就可以得到期望的两个数据包集合中的协议类别数c1，c2 ，c3 ，c4 ，具体如公式（4）、（5）、（6）、（7）所示。

计算得到卡方值后，再和临界值比较就能够判定函数ψ是否满足于Di+1，以此就可以判定概念漂移是否发生。

2.1.2类别不平衡与Fisher检验

χ2检验对2维表的各个协议类别的数量是有一定要求的，要求20%的协议类别数量不小于某个特定值。但是在真实的网络环境下，经常存在类别不平衡的流量，因此就无法满足χ2检验的要求，此时就只能应用Fisher精确检验。

同样，使用上小节的2*2表进行说明，先设几个变量：C1= c1 + c2，C2= c3 +c4，C3= c1 + c3，C4= c2 + c4，C = C1 + C2或C3 + C4 ，就可以得到p值，如式（9）所示，根据P{cij}来确定是否发生了概念漂移。

2.1.3检验步骤

根据概念漂移的检测原理和统计学理论，就可以利用χ2检验和Fisher检验来共同确定连续的两个数据包集合是否发生了概念漂移。具体步骤如下：

（1）建立零假说，即认为没有发生概念漂移；

（2）确定数据包集合之间的实际差异，即根据类别是否平衡，进行χ2检验或者Fisher检验；

（3）根据χ2检验或者Fisher检验的结果，和理论值进行比较。如果大于理论值，则拒绝零假说，即认为发生了概念漂移。

2.2概念漂移检测算法

通过上述的分析，本文接下来将给出一个利用统计学理论来检测概念漂移发生的方法。和已经存在的大部分概念漂移算法相比，该方法有两个显著的特征：第一，该方法属于显示探测概念漂移，因此其中含有单独的检测概念漂移发生的模块；第二，该方法结合网络流量识别的实际环境——经常存在类别不平衡的特性，利用集成学习的方法来适应动态的网络数据变化。当一个网络数据包集合到达以后，概念漂移检测模块就对其进行检测，检测是否有概念漂移发生，如果概念漂移发生了，检测模块就会告知流量识别器更新或者重构识别器，以保证流量识别器能够继续对其后的网络数据流进行准确识别。

算法CF_CDD旨在检测出动态变化的网络数据流中发生的概念漂移，一旦网络数据包数量达到合适的窗口大小，概念漂移模块就检测连续的两个网络数据包集合之间是否有概念漂移发生。CF_CDD （Di，Di-1）算法如下。

在如上算法中，第1步、第2步是分类器对数据包Di，Di-1进行分类，并统计了相应的样本数量，第3步判断协议类别是否出现了不平衡。若平衡，就进行χ2检验；不平衡，就是Fisher检验。最后，根据检验结果P和CONST的比较，判定是否发生了概念漂移。其中，CONST是根据自由度和置信度查表得来的界限。

2.3自适应流量识别

若要完成自适应的网络流量识别，就要有效地检测出概念漂移，再对分类器进行调整。本文采用集成学习来构建分类器，因而构建集成分类器的子分类器的机器学习算法就需要进行重点研究和专门讨论了。

2.3.1类别不平衡下的机器学习算法

网络数据流量中经常存在协议类别不平衡的情况，协议类别的分布对基于机器学习的流量识别技术有着不小的影响。因此，选择合适的机器学习算法以适应网络协议流不平衡环境下的在线流量分类，即显得尤为重要[10]。

本文在实验与分析中，将几种典型的机器学习算法——决策树C4.5、NBK、SVM与提出的概念漂移检测算法结合后进行了对比，选取得到最能适应含有类别不平衡协议流的真实环境的算法，且算法性能良好。

2.3.2集成学习

算法TCEL_CF_CDD，利用权重集成分类器对到达的网络数据包进行分类，集成分类器的子分类器要根据概念漂移检测模块的结果进行调整、更新。

在上述算法的第4步中，基分类器的构建过程中采用的是一种常用的机器学习算法，本文将通过实验来选择出实验真实环境的算法；第4-6步是集成分类器的构建过程，当变量Num等于Max时，标志着集成分类器构造完成；而后在第8-11步中定义基分类器在相应的数据集上的准确性；第12步是对各子分类器权重进行规格化；第13步表明了在本课题中为了充分利用样本信息，对每组样本均采用了先测试、后训练的策略；第14步是调用CF_CDD算法来检测连续的两个样本网络数据包集合之间是否发生了概念漂移，如果发生了概念漂移就要在最新的样本数据集中构建最新的基分类器，并用构建出来的新分类器替换已经存在的基分类器中表现最差的那个；第19步是在调整子分类器后，对各分类器的权重进行调整。

3实验与分析

本文利用已经捕获的几个网络数据包集合来模拟网络流量，将数据包按捕获的时间进行顺序排列，并用实现的算法对其进行分类识别。本文的算法是在MOA平台上实现的，MOA是一个典型的利用WEKA实现的数据流分析软件。

3.1机器学习算法的比较

将三种典型的机器学习算法——决策树C4.5、NBK、SVM与本文提出的概念漂移检测算法CF_CDD结合，分别构造识别器，利用模拟的网络流量的第一个数据包集合作为训练集，并且对后续的五个数据包集合进行分类，以测试不同的机器学习算法对识别精确性的影响，其结果如表2所示。从表2中可以看到：NBK的精确度明显不高，而且也有随时间下降的趋势；决策树C4.5和SVM相比NBK则有不错且相对稳定的精确度，适合提出的概念漂移检测算法。

C4.5和SVM虽然都有不错的精确度，但是因为知道SVM的建模时间相对C4.5来说耗时更长，再结合处理概念漂移检测的实际特点——需要经常调整分类器，因而此处不难得出结论：决策树C4.5与本文提出的对概念漂移检测算法CF_CDD结合进行网络流量识别更能够自适应地处理实际网络环境中的概念漂移问题。

3.2漂移检测算法的比较

一般的数据流中，检测概念漂移的算法是基于误差率的，利用对分类器误差率的监测来判定是否发生了概念漂移。本实验就对基于误差率（Error_CDD）和本文提出的基于统计学检验（CF_CDD）的两种概念漂移的算法在模拟的网络流量识别的精度进行了对比，对比结果如图1所示。

从图1中可以看到，当有类别不平衡的协议类别时，Error_CDD的识别精度大幅度下降，验证了之前提到的性能法不适合于类别不平衡的网络数据流量识别，而本文提出的CF_CDD算法却有良好的稳定性，也说明本文提出的算法能够很好地适应类别不平衡现象。

4结束语

本文对流量识别中的概念漂移进行了深入研究，主要分析了漂移检测原理，并结合真实网络环境中存在的类别不平衡的特点，提出了基于统计学理论的概念漂移检测算法，在检测算法的基础上提出了利用集成学习来完成自适应的流量识别，最后的实验证明了本文提出的算法的可行性和可靠性。当然，数据流概念漂移的问题还有很多，建议其后的主要研究方向就是类似本文这样针对某种具体数据流的特点进行详细的分析。

参考文献：

[1]王耀南，张莹.基于可信多数投票的快速概念漂移检测[J].湖南大学学报（自然科学版）， 2010， 37（6）： 36-40.

[2]GUAN Jinghua， LIU Dayou. Selected ensemble of classifiers for handling concept-drifting data streams[J]. Computer Science， 2010，37（1）：204-207.

[3]王涛，李舟军，颜跃进，等.数据流挖掘分类技术综述[J].计算机研究与发展，2007，44（11）： 1809-1815.

[4]SUN Yue， MAO Guojun， LIU Xu. Mining concept drifts from data streams based on multi-classifiers[J]. Acta Automatica Sinica， 2008， 34（1）： 93-97.

[5]文益民.概念漂移数据流分类研究综述[J].智能系统学报， 2012，7（6）：1-10.

[6]ALIPPI C， BORACCHI G， ROVERI M. An effective just-in-time adaptive classifier for gradual concept drifts[C]//Proceedings of the 2011 International Joint Conference on Neural Networks. San Jose， USA， 2011： 1675-1681.

[7]PETER V， ABRANHAM B. Entropy-based concept drift detection[C]//Proceedings of the 6th International Conference on Data Mining. Hong Kong， China， 2006： 1113-1118.

[8]WIDMER G， KUBAT M. Effective learning in dynamic environments by explicit context tracking[C]//Proceedings of the Sixth European Conference on Machine Learning. Vienna， Austria， 2003： 69-101.

[9]LAST M. Online classification of non-stationary data streams [J]. Intelligent Data Analysis， 2005， 6 （2）： 1-16.

[10]鲁刚.分类不平衡协议流的机器学习算法评估与比较[J].软件学报.2012，23（6）：1500-1516.