0 引言

    网络流量分类是指将混合有各种应用的流量，按产生这些流量的应用协议进行分类。网络流量分类既是高性能网络协议设计的基础，又是网络运营管理、网络发展规划的依据，也是网络攻击与恶意代码检测的重要手段^[1]。

    自互联网诞生之日起，学术界和产业界就一直对网络流量分类进行研究。就目前的研究进展来说，网络流量分类主要可以归为四类方法：基于标准端口匹配、基于深度包检测(Deep Packet Inspection，DPI)、基于网络协议解析和基于统计学习算法。

    当今互联网的发展规模造成了端口与应用之间的映射不再固定，因此基于端口的流量分类方法一般用于粗粒度的流量筛选；基于DPI的分类方法的一个主要弱点是无法适用于加密流量，另外也会涉及到侵犯个人隐私等法律问题；基于网络协议解析的网络流量分类方法是指通过对协议流量或行为的分析，利用流量特征或行为特征实现流量分类；基于统计学习的网络流量分类方法先定义一组流（Flow，一般以源IP地址、目的IP地址、源端口号、目的端口号和协议五元组定义）统计特征，再利用机器学习算法训练出分类模型，然后利用该模型进行后续的网络流量分类。目前后两种分类方法在学术界得到广泛关注。文献[2]利用支持向量机（Support Vector Machine，SVM）决策树在多类分类方面的优势，提出一种用SVM决策树来对网络流量进行分类的方法，公开数据集上的实验结果显示该方法的分类准确率达到了98.8%。文献[3]将相关向量机(Relevance Vector Machine，RVM)分类模型应用于网络流量分类中，提出了一种混合流量分类方法，并在准确性等3方面性能指标上优于SVM。ERMAN J等人在文献[4]中介绍了一种利用基于K-means的半监督学习分类算法对数据流进行分类的方法，实验结果表明该方法能够达到70%~90%的总体识别准确率，但算法中初始聚类中心的选取仍然是随机选取的方式。文献[5]对K-means算法中初始聚类中心的选取进行了改进，通过基于密度因子的相似性函数来满足聚类数据的全局一致性要求以获取更合适的初始聚类中心，但仍然需要事先确定聚类个数k。

    在当前应用于网络流量分类的众多机器学习算法中，K-means算法是应用最为广泛的算法。但是K-means算法也存在两个主要的缺点：(1)需要事先确定聚类个数k的大小；(2)标准算法中初始聚类中心选择的随机性导致算法对异常数据敏感，对分类准确度有较大影响。本文结合之前学者的研究，针对K-means算法的两个主要缺点对算法进行全面优化，通过基于密度的思想对数据区域进行划分，从高密度区域产生初始聚类中心；引入聚类有效性判别准则函数，以确定最佳的聚类个数k。实验结果表明，优化后的算法提升了网络流量分类的准确率，提高了分类稳定性。

1 算法描述

1.1 相关定义

    传统的K-means算法需要事先确定聚类个数k，并随机选取k个初始聚类中心，但这种选择的随机性往往导致聚类结果有很大的波动性。根据网络流量的行为特征和统计特性可知，同一应用类型的流量数据往往分布在一个相对比较密集的区域，不同的密集区域会被一些稀疏区域隔离开来。所以在选择初始聚类中心时，考虑数据对象的密度，将高密度区域作为产生聚类中心的候选集合。同时为了确定最佳的聚类数目k，避免人为设定对分类准确率造成影响，定义聚类有效性判别准则函数，将准则函数取得最小值时的聚类数作为最佳聚类数。

    设数据集合S={x_i|x_i∈R^p，i=1，2，3,…,n}，其中n为集合中数据对象个数，p为数据空间维数。

    定义1 数据集合S中任意两个数据对象x_i、x_j间的距离为欧式距离，即：

其中，k为聚类个数且k>2，|C_i|为簇C_i中数据对象的个数，x_i、x_j分别为簇C_i、C_j的数据对象均值中心。di(k)、db(k)分别表示数据集合S的簇内距离和簇间距离，用于描述同一类型数据之间的相似性和不同类型数据之间的相异性。

    由式(6)～式(9)可知，簇内距离定义为簇中每个数据对象与同一个簇中所有其他对象之间平均距离的最小值，数据集合S的簇内距离为k个簇内距离中的最大值；数据集合S的簇间距离定义为k个簇的数据对象均值中心之间距离的最小值。由式(5)可知，di(k)越小，db(k)越大，判别准则函数J(k)的值越小，当J(k)取最小值时，表示数据集合S的簇内数据对象之间相似性最高，簇间数据对象之间相异性最高。所以选择使J(k)取值最小时的k作为最佳聚类个数。

1.2 基于改进K-means的网络流量分类方法

    令C={c₁，c₂，c₃，…，c_k}表示网络流量聚类后的类簇集合，k为簇数。M={m₁，m₂，m₃，…，m_r}为网络中流量的应用类型集合，r为应用种类个数，r≤k，则网络流量分类中存在映射f:C→M。

    本文采用最大似然估计实现映射f。基于最大似然估计，定义映射f的概率模型为：

    对于没有包含任何被标记网络流的类簇，其所对应的网络流量被认定为未知应用类型。

    网络流量分类方法详细描述如下：

    输入：网络流量(traffic)的流(flow)统计特征属性表征集合S={x₁，x₂，…，x_n}，x_i=(t₁，t₂，…，t_p)，x_i表示为一个包含p项网络流特征属性的特征向量。

    输出：网络流量应用类型集合M。

    分类过程可以抽象为构造分类模型g:S→C和映射模型f:C→M。

2 实验与结果分析

2.1 实验工具、数据集与特征选择

    本文使用的主要实验工具是MATLAB 8.1和Weka 3.8。Weka是新西兰怀卡托大学开发的一个基于JAVA环境的开源机器学习以及数据挖掘软件，软件包含多种机器学习算法，并提供JAVA接口，便于用户自己编写代码进行算法开发^[6]。

    实验利用MOORE A W等人在文献[7]中所使用的实验数据集Moore_set作为源数据集，这是目前网络流量分类研究中最为权威的测试数据集。Moore_set中包含378 101个网络流样本，共10种应用类型，统计信息如表1所示。

    由于Moore_set中网络流样本数量总量较大，但INT和GAMES两种类型应用的样本数量相对过少，不具有代表性，所以本文选取Moore_set的一个数据子集Moore_subset作为实验数据集，并删除INT和GAMES两种应用类型。实验数据集统计信息如表2所示。

    MOORE A W等人在文献[8]中提出了249个可用于流量分类的统计特征属性（最后一个特征属性是目标属性，即指出网络流所属的应用类型，所以真正的特征属性共248个），涵盖了当前流量分类研究中使用的绝大多数特征。这些特征大致可分为双向特征和单向特征，双向特征包括服务器和客户机所用端口号、包到达时间间隔统计量、以太帧字节长度统计量、包字节长度统计量等；单向特征包括传输的字节总数、发送的各类数据包计数(包括ACK包、纯ACK包、SACK包、PUSH包、SYN包等)、TCP数据载荷包计数、重传包计数、窗口参数相关统计、数据传输时间、空闲时间、吞吐量等。

    目前基于统计学习方法的流量分类研究中，一般只从上述248个特征中选择10~20个特征。这是因为上述248个特征中存在很多冗余特征和无关特征，如果全部采用不仅会大大增加流量分类系统的负载，甚至还会降低分类准确率。考虑到K-means算法固有的特点，本文选择了11项具有代表性的特征属性用于表征网络流，具体信息如表3所示，其中标识符参照文献[8]中的定义。

2.2 实验结果分析

    设定实验数据集Moore_subset中每种应用类型各自所包含网络流中被标记为该类型的流数量所占比例均为γ。在基于密度的聚类算法中，密度的定义因实验数据集的不同而有所不同，根据经验，实验令半径系数ρ=1。

    在γ=5%、ρ=1的情况下，运行K-means算法(k=8)和本文改进的K-means算法，分别得到每种应用的分类识别准确率，如图1所示。从图中可以看出，即使在提前给出最优的聚类个数的情况下，改进的K-means算法网络流量分类识别准确率仍然比标准K-means算法高，这是因为初始聚类中心的选取直接影响聚类结果，而改进算法对其进行了优化。

    令γ∈[5%，7%，9%，11%，13%，15%]，测试数据集中被标记网络流数量的大小对分类识别结果的影响。在γ不同取值情况下的网络流量分类识别总体准确率如图2所示。从图中可以看出，已标记网络流所占比例越大，即数量越多，分类识别的总体准确率越高。

    总体上，经过改进后的网络流量分类方法在准确率方面具有更好的稳定性，网络流量分类识别总体准确率可以达到90%以上，能够满足一定的网络应用分类识别需求。

3 结论

    首先针对标准K-means算法的两个主要缺陷，通过基于密度的思想改进初始聚类中心的选取以及引入聚类有效性判别准则函数确定最优的聚类个数对算法进行全面优化，然后据此提出一种基于改进K-means算法的网络流量分类方法。在权威数据集Moore_set上的实验表明，该分类方法可以取得较好的分类效果，能够满足一定的网络应用分类识别需求。但同时也应该看到，随着技术的发展，网络新应用层出不穷，网络架构设计不断优化演进，使得网络流量分类问题不断面临新的巨大挑战，诸如高带宽带来的数据实时无损采集的挑战，应用多样化和协议私有化给应用协议特征分析带来的挑战，分类器在线部署面临的挑战等。这些都是今后继续努力研究的方向。

参考文献

[1] 汪立东，钱丽萍，王大伟，等.网络流量分类方法与实践[M].北京：人民邮电出版社，2013.

[2] 邱婧，夏靖波，柏骏.基于SVM决策树的网络流量分类[J].电光与控制，2012，19(6)：13-16.

[3] 柏骏，夏靖波，鹿传国，等.基于RVM的网络流量分类研究[J].电子科技大学学报，2014，43(2)：241-246.

[4] ERMAN J，MAHATI A，ARLITT，M.Semi-supervised network traffic classification[C].Proceedings of the 2007 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems，New York，USA，2007：369-371.

[5] 周文刚，陈雷霆，董仕，等.基于半监督的网络流量分类识别算法[J].电子测量与仪器学报，2014，28(4)：381-386.

[6] 袁梅宇.数据挖掘与机器学习：WEKA应用技术与实践[M].北京：清华大学出版社，2014.

[7] MOORE A W，ZUEV D.Internet traffic classification using Bayesian analysis techniques[C].Proceedings of the 2005 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems，Banff，Canada，2005：50-60.

[8] MOORE A W，ZUEV D，CROGAN M.Discriminators for use in flow-based classification，RR-05-13[R].London：Queen Mary University of London，2005.