基于多层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种集合的操作，基于函数式编程语言的思想，屏蔽底层实现细节，降低了程序员并行编程的难度。基于MapReduce并行编程模型实现网络流量特征选择方法，其方法流程如图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.