基于DT-KSVM的业务感知算法

 董  昊 ．曲  桦 ，赵季红 ，陈梁骏，戴慧珺 

(1．西安交通大学软件学院西安710049；2．西安交通大学电子与信息工程学院西安710049；3．西安邮电大学通信与信息工程学院西安710061)

摘  要：提出一种新的基于DT-KSVM (decision tree kemel support vector machine，决策树支持向量机)的业务感知算法，利用ReliefF特征选择算法提取特征，提出样本间类别可分度计算方法排序不同业务感知难度，优先感知易分业务。在实际网络业务数据集上与传统一对-( one-versus-one) SVM感知方法进行对比，结果表明该方法具有较高的业务识别准确率和更好的时间性能。

关键词：SVM;决策树；业务感知

doi: 10.11959/j.issn.1000-0801.2015227

 Service-Aware Algorithm Based on DT-KSVM

 Dong Hao , Qu Hua , Zhao Jihong , Chen Liangjun , Dai Huijun 

 (1. School of Software, Xi'an Jiaotong University* Xi'an 710049, China;2. School of Electronic&Information

 Engineering, Xi'an Jiaotong University, Xi'an 710049, China;3.School of Telecommunication＆Information

 Engineering, Xi'an University of Posts&Telecommunications, Xi'an 710061, China)

Abstract:  A  novel service-aware method based on decision tree kemel support vector machine (DT-KSVM)algorithm was proposed.A service-aware model was developed by using ReliefF algorithm to extract servicecharacteristics, and proposing the separable degree between samples to simply the service-aware process. Throughexperiment comparison between this proposed model and traditional one-versus-one SVM method, it is shown thatthe proposed method has a better service-aware accuracy and time performance.

Key words: support vector machine, decision tree, service-aware

1  引言

 日渐增长的网络规模和用户需求带给互联网越来越多的挑战，其中P2P等网络共享业务更给网络造成了巨大的压力，同时也降低了用户上网体验。为了保障高质量业务的QoS（quantity of service，服务质量），必须对业务加以区分，以此来对不同的网络业务进行差分服务。对网络中业务内容的区分可认为是对网络业务的感知过程，此过程对管理网络性能、QoS保障、准人控制等有很重要的意义。通过对业务的感知来对网络的各种资源进行合理的分配，实现异构网络的协同、网络负载的均衡，从而优化网络性能。这是当前研究的热点内容，也是运营商设计更好系统的依据和保障QoS的关键。

 本文针对网络业务感知，提出了融合决策树算法与核SVM (support vector machine，支持向量机)方法的DT-KSVM算法。结合决策树算法描述简单、分类速度快的特点以及KSVM算法基于结构风险最小原则，平面与核函数的优点，能有效地将难以解决的原始空间样本的非线性运算映射为线性空间的线性运算。通过对英国剑桥大学网络数据集的感知仿真，证实DT-KSVM算法具有感知速度快、识别率高、顽健性强的特点。

2相关工作

 目前，业务感知方法主要有：端口识别法、DPI(deeppacket identify，深度分组检测)法、基于流量统计的流量识别方法和基于机器学习的识别方法。端口识别法效率低下，对网络中的大多数业务都无法感知：DPI感知算法感知精度高，但对加密业务无法很好处理；基于流量统计的业务感知方法目前的感知精度不高；基于机器学习的方法利用业务流中存在的统计信息数据感知网络业务，但时间复杂度较高。

 将SVM用于业务感知中，主要优势在于：首先是SVM利用高维映射，将非线性问题向线性问题转化，且在分类过程中不需要知道具体的业务特征：其次．SVM的分类面个数取决于支持向量机数目，可以和其他算法进行结合来改变支持向量的数目，从而对分类面的数量进行调整，即它的时间复杂度可根据情况调整，泛化性好，顽健性高；最后，在求解过程中，SVM将问题转化为二次规划类型的问题，得到的最优解是全局的，较其他算法分类准确率高很多。

 现有的基于SVM的感知方法主要有一对一( one-versus-one)分类方法、一对多(one-versus-rest)分类方法以及有向无环图(directed acyclic graph)SVM分类方法等。其中一对一方法是最早出现也是应用较多的方法，在本文仿真部分中作为对比方法。其原理是在每两个类别之间都构造分类面，对样本进行分类判断时，需要将样本和每个分类平面进行判断，最后判为哪个类别的次数较多，该样本就属于哪类。对于有k个类别的样本，该方法需要构造的分类面数量为k(k-l)/2。

 由目前的研究现状可知，SVM具有较好的推广性能和较好的分类准确率，本文在前人研究的基础上，提出DT-KSVM方法，结合决策树思想，通过核化的SVM方法对网络业务进行感知。

3  基于DT-KSVM的业务感知算法

 DT-KSVM算法构造了一个决策树的结构，首先对样本进行特征提取，计算样本间类别可分度，再对其中较易区分的样本先进行分类，最后按照所构造的树型结构感知出各个样本类别。

3.1  特征提取

 在数据集中存在一些对感知没有影响甚至影响感知准确率的属性，不适合用来作为感知的特征依据，需要将这些属性剔除。具体方法是对样本中的各个属性按照计算出来的属性权重平均值，设置阈值，将权重小于阈值的属性去除，剩下对感知有重大贡献的属性特征。针对网络业务样本数据，本文采用ReliefF算法进行特征提取，该方法运行效率高，对数据类型没有限制，可处理多类别问题。

3.2定义样本间类别可分度

 特征提取完成后，为了缓解决策树结构中的误差累积问题，本文提出样本间类别可分度概念，通过对样本类别间的分类难易程度进行量化，衡量样本类别分类难易程度。下面介绍本文中定义的样本间类别可分度。

 在计算可分度之前，先计算样本的分离系数，本文中用样本的中心距离和样本的方差以及类别间的欧几里得距离( Eudidean  distance) -起，作为样本分离系数的计算指标。单用欧几里得距离计算得到类别中心间的距离，并不能完全体现样本的可分程度。因此，计算欧几里得距离的同时引入权重，权重是计算样本的类别中心和方差的比值，方差能很好地体现样本的分布情况。样本越紧凑，方差则相对较小，相反，方差越大，则样本越离散。通过将类间中心距离和类的分布综合考虑进行类间分离系数的计算，准确率会提高很多。分离系数Φij的计算如式(1)所示：

 其中，d。和dj分别是第i类和第j类样本的类别中心，计算式如式(2)所示，ωi为第i类样本的欧几里得权重，它的计算方法如式(3)所示：

其中，ni表示Xi的样本数量，Xi为样本所属种类，1表示样本的类别数。φi表示第i类样本的方差，体现样本分布。其计算方法如式(4)所示：

 其中，xi表示第i类样本的属性值。将式(2)～式(4)代入式(1)中，即可求得样本间类别分离系数φij。φij的值越大，说明样本间的分离度越高，样本越易被分开。计算出各个样本的类间分离系数φij后，统计各个样本类别的数量ni,最终定义类间的可分度表达式如下：

 其中，k为样本的类别数目，可以看出样本的可分度就是样本与和与它不同类的样本分离系数之和再和该类别样本的数量做乘积运算所得的结果。Di是第i类样本的可分度。

3.3 DT-KSVM算法

 DT-KSVM算法通过将决策树结构和KSVM算法结合，进行网络业务的感知，它是一种类似平衡二叉树的树型结构形态。其中，每个树节点上的样本类别和样本的可分度大小相关联。中间节点上至少有两个样本种类，叶子节点便是最终分出来的样本种类。DT-KSVM算法的流程如图1所示。

 经过自上而下的感知，到叶子节点时各个业务类别就能被很好地感知出来。本文通过对网络业务的特征提取、样本类别间可分度的计算，构建DT-KSVM算法训练模型对样本进行感知。

 算法的具体步骤如下。

 步骤1  通过ReliefF算法对样本的重要属性进行提取，去掉对样本区分度不大的属性。

 步骤2特征选取后，根据式(5)计算每个样本类别的可分度，计算出每类样本的可分度，按照可分度从大到小进行排序，若遇到可分度相同的情况，则统计样本的数量，数量多的类别排在前面。

 步骤3根据可分度排序结果，将排在前1/2的样本类别作为正类，排在后面的类别作为负类。

 步骤4使用DT-KSVM算法构造分类平面，优化参数，并训练。

 步骤5通过对DT-KSVM算法的训练，则样本的正类和负类作为决策树的两个子节点，由于样本类别较多，第一次分类决策后，每个子节点中可能含有两个以上的类别，若要将子类别分开，则转到步骤3，对各个子节点的样本类别同样一半取正类，一半取负类，进入步骤4训练，进行再次决策。

 步骤6不断执行上面的过程，直到节点中只含有一个样本类别时为止，即到达叶子节点，此时所有的样本类别将被分开。

4仿真与分析

4.1  数据处理

 本文数据是采用英国剑桥大学的网络数据集。该大学的Moore等人的数据集收集了该学校的双工网络流量。每个文件含半小时统计的流，每个流由一行记录组，该数据集特征全面完整，有一定代表性。Moore数据集中业务的属性是通过流的属性表现出来，其中统计了其249个属性值。对采集来的原始数据进行预处理，包括对数据集进行抽样、数据规整、数据归一化等过程。对归一化后的数据集采用SVM算法分类出样本集中的P2P业务，用于DT-KSVM算法的仿真。本文实验数据中的P2P业务主要有以下5个类别，分别为：Gnutella、eDonkey、Thunder、KaZaA和BitTorrent。

 通过特征提取及样本间可分度计算，表1中列出各P2P业务的可分度值。

 在构造各分类平面时需要对SVM核函数中的参数和惩罚因子进行优化调整。在选取参数时采用交叉验证来建模，网格搜索来寻优。本文采集的数据集中，P2P业务有5个类别，根据DT-KSVM算法可知，该样本集需要N-l即4个分类平面就可以将所有的类别分开。表2列出了各个分类平面所对应的数据集以及各个分类平面的参数选择结果。其中Originals.libsvm中为所有的数据集，OriginalOs.libsvm中在没分错的情况下应该包含Thunder和eDonkey的样本集，Originalls.libsvm中应为BitTorrent、KaZaA和Gnutella的样本集，Originallls.libsvm中为KaZaA和Gnutella的样本集。

4.2仿真结果

 本文通过DT-KSVM算法对提取出的P2P业务进行感知，感知结果见表3。

 表3的识别结果是对本次采集的数据进行感知的结果，从结果中可以看出，依然存在少量的错分误分的现象，但该算法基本能较准确地感知出样本中不同的P2P业务，另外，除Gnutella外各个类别的召回率基本可达到95 010以上，其中召回率指算法正确决策的样本数和该类样本总数之比。将DT-KSVM算法与传统的lvsl多分类感知算法相比较，其感知准确率见表4。

 从表4中可知，DT-KSVM算法比lvsl算法的准确率要高很多，其准确率是指算法正确决策的样本数和样本总数之比。这是因为DT-KSVM算法比lvsl算法多了特征提取和类间可分度计算，另外．DT-KSVM所构造的分类平面较lvsl算法少，因此，算法在时间性能方面也较lvsl算法要好。

 图2为在抽取不同的样本数量时,lvsl和DT-KSVM对样本训练所花费时间的对比。

 从图2中可看出，样本数量越多，lvsl算法与DT-KSVM算法的样本训练时间差距越大。这是由于lvsl算法需要构造更多的分类面，因此其花费的时间较长，DT-KSVM算法较lvsl算法构造的分类面要少一些，因此时间性能更好。

5结束语

 本文主要通过和传统的多分类算法相比较，提出DT-KSVM方法来感知网络业务。在感知过程中采用ReliefF算法对网络业务的主要特征进行提取，通过本文中的类别可分度来衡量样本的易分程度，并对样本进行排序。按照可分度从大到小排序结果，运行DT-KSVM算法对网络业务进行感知。最后，通过仿真，与lvsl算法进行对比，可知DT-KSVM算法的感知准确率和时间性能均较好，是有效的网络业务感知算法。这对网络性能的管理、服务质量的提升、网络资源的分配等都有重要意义。