一种基于动态二叉树的SVM多分类方法

摘要

本发明公开了一种基于动态二叉树的SVM多分类方法，属于数据挖掘技术领域。本发明基于动态二叉树的SVM多分类方法利用多个二分类SVM构成二叉树结构的SVM多分类器，并在分类过程中根据各二分类SVM的分类结果动态调整二叉树结构，将分类成功率较高的二分类SVM调整至二叉树结构的根部，从而提高早期分类成功的概率，并且减少单个样本所经过的二分类SVM的数量，在保证分类准确率的同时有效提高了分类速度。本发明还公开了一种采用本发明多分类方法的网络告警预测方法、P2P流量分类方法、图像语义分类方法、网络攻击检测方法及网页分类方法。

说明书

技术领域

本发明涉及一种SVM（Support Vector Machine，支持向量机）多分类方法，尤其涉及一种基于动态二叉树的SVM多分类方法，属于数据挖掘技术领域。

背景技术

支持向量机最初是为两类分类问题而设计的，而在实际应用中，多分类问题更为普遍。如何将支持向量机的优良性能推广到多类分类当中去，成为目前支持向量机研究的一个热点问题。

目前存在的支持向量机多分类方法可以分为两类：一类方法是在所有的训练样本上求解一个大的二次规划问题，同时将多个类分开。这类方法在思想上比较简单，但求解这样一个大的多类二次规划其计算复杂度大大增加，从而其训练时间较长。第二类方法是构造和结合多个两类分类问题进行多类分类。这类方法包括一类对余类法、一类对一类法、决策二叉树法和决策导向无环图法等。

一类对余类法(One Versus Rest，OVR)是目前应用最为广泛的方法之一，其步骤是：构造K个两类分类机(设共有K个类别)，其中第i个支持向量机以第i类样本为正类样本，其余样本为负类样本进行训练。

判别时，输入样本经过K个向量机共得到K个输出值，若有一个+1出现，则其对应类别为输入样本类别；若没有一个+1输出，则证明输入向量不属于这K种类型中的一种，而属于其他类型，本次分类失败。

OVR方法的优点是：只需要训练K个两类分类机，所得到的分类函数的个数(K个)较少，在样本数量不大的情况下训练速度较快。

OVR方法的缺点是：1、每个二分类向量机的训练都是将全部样本作为训练样本，这需要求解K个含全部变量的二次规划问题。因为支持向量机的训练速度随着训练样本数的增加而急剧减慢，因此，OVR方法训练时间较长；2.随着样本数量的增加分类速度也会急剧减慢，由判别方法可知，每一个样本必须经过每一个支持向量机，这样大大的降低了分类速度。

发明内容

本发明所要解决的技术问题在于克服传统基于支持向量机的分类技术所存在的随着样本数量的增多，分类速度急剧下降的不足，提供一种基于动态二叉树的SVM多分类方法，在不影响分类准确率的情况下有效提高多分类的速度，扩展了基于支持向量机的多分类方法的应用范围。

本发明具体采用以下技术方案解决上述技术问题。

一种基于动态二叉树的SVM多分类方法，首先利用训练好的多个二分类SVM构造二叉树结构的SVM多分类器，然后利用所构造的SVM多分类器对测试样本集进行分类；所述利用所构造的SVM多分类器对测试样本集进行分类，具体包括以下步骤：

步骤1、将测试样本集中的第一个测试样本输入所述SVM多分类器的根节点，并将SVM多分类器中各二分类SVM的调整因子初始化为0，所述调整因子的定义为该二分类SVM的分类成功次数与分类总次数的比值，分类成功次数为通过该二分类SVM并且输出结果为+1的测试样本的个数，分类总次数是指通过该二分类SVM的测试样本的总数；

步骤2、如当前节点为空节点，则分类过程结束，转到步骤4，否则，转至步骤3；

步骤3、用当前二分类SVM对待分类样本进行分类，如输出结果为-1，则根据输出结果动态调整当前二分类SVM的调整因子，并将该测试样本输入给当前二分类SVM的子节点所对应的二分类SVM，然后转步骤2；若为+1，则根据输出结果动态调整当前二分类SVM的调整因子，分类过程结束，转至步骤4；

步骤4、判断SVM多分类器中各二分类SVM的调整因子的最大值与最小值之间的比值是否大于一预设的调整阈值，如是，则按照以下方法重新调整所述SVM多分类器的二叉树结构：将调整因子值大的SVM向二叉树的根部位置调整，即调整因子最大的SVM作为根节点，次大的SVM作为根节点的子节点，以此类推，建立新的二叉树结构；如否，则保持二叉树的结构不变；

步骤5、将测试样本集中的下一个测试样本输入所述SVM多分类器的根节点，并重复执行步骤2—步骤4，直至测试样本集中所有测试样本均完成分类。

本发明的多分类方法可广泛用于各领域的数据挖掘，例如：

一种网络告警预测方法，对告警的时间序列进行分类，分类结果即为预测结果，所述对告警的时间序列进行分类，包括以下步骤：

步骤A、对一类网络告警历史数据进行向量提取并进行预处理，得到该类网络告警的训练样本；

步骤B、利用得到的训练样本对二分类SVM进行训练，得到该类网络告警的二分类SVM；

步骤C、选取多类网络告警历史数据分别重复步骤A—步骤B，得到多个训练好的二分类SVM；

步骤D、利用得到的多个训练好的二分类SVM，使用上述基于动态二叉树的SVM多分类方法对告警的时间序列进行分类，分类结果即为预测结果。

    一种P2P流量分类方法，用于对P2P流量所属类型进行识别，包括以下步骤：

步骤A、对一类P2P流量数据进行特征提取，得到该类P2P流量的训练样本；

步骤B、利用得到的训练样本对二分类SVM进行训练，得到该类P2P流量的二分类SVM；

步骤C、选取多类P2P流量数据分别重复步骤A—步骤B，得到多个训练好的二分类SVM；

步骤D、利用得到的多个训练好的二分类SVM，使用上述基于动态二叉树的SVM多分类方法对P2P流量数据进行分类。

    一种图像语义分类方法，包括以下步骤：

步骤A、对一类图像进行语义特征提取，得到该类图像的训练样本；

步骤B、利用得到的训练样本对二分类SVM进行训练，得到该类图像的二分类SVM；

步骤C、选取多类图像分别重复步骤A—步骤B，得到多个训练好的二分类SVM；

步骤D、利用得到的多个训练好的二分类SVM，使用上述基于动态二叉树的SVM多分类方法对图像进行语义分类。

    一种网络攻击检测方法，通过对网络数据包进行分类，判断是否发生网络攻击，所述对网络数据包进行分类，包括以下步骤：

步骤A、对一类网络攻击数据进行特征提取，得到该类网络攻击的训练样本；

步骤B、利用得到的训练样本对二分类SVM进行训练，得到该类网络攻击的二分类SVM；

步骤C、选取多类已知的网络攻击数据分别重复步骤A—步骤B，得到多个训练好的二分类SVM；

步骤D、利用得到的多个训练好的二分类SVM，使用上述基于动态二叉树的SVM多分类方法对网络数据包进行分类。

     一种网页分类方法，包括以下步骤：

步骤A、对一类网页数据进行特征提取，得到该类网页的训练样本；

步骤B、利用得到的训练样本对二分类SVM进行训练，得到该类网页的二分类SVM；

步骤C、选取多类网页数据分别重复步骤A—步骤B，得到多个训练好的二分类SVM；

步骤D、利用得到的多个训练好的二分类SVM，使用上述基于动态二叉树的SVM多分类方法对网页进行分类。

    本发明的多分类方法利用多个二分类SVM构成二叉树结构的SVM多分类器，并在分类过程中根据各二分类SVM的分类结果动态调整二叉树结构，将分类成功率较高的二分类SVM调整至二叉树结构的根部，从而提高早期分类成功的概率，并且减少单个样本所经过的二分类SVM的数量，在保证分类准确率的同时有效提高了分类速度。

附图说明

图1为二叉树结构的SVM多分类器的结构；

图2为本发明中定义的支持向量机的结构；

图3为本发明基于动态二叉树的SVM多分类方法的流程图。

具体实施方式

下面结合附图对本发明的技术方案进行详细说明：

本发明的目的在于解决现有基于支持向量机的多分类方法存在的分类速度低的问题。考虑到在具体的应用环境中每一个样本只能属于一个类别，所以在一个样本经过K个向量机形成的二叉树队列时，若输出结果为+1，则可以不经过剩下的向量机，这样会节约大量时间。基于这个思想可以将经常输出+1的支持向量机调到队列前半部，这样又会节省一部分时间，提高分类的速度。

基于以上思想，本发明在分类阶段，首先将多个训练好的二分类SVM组合成一棵二叉树，二叉树的结构如图1所示，同时在每一个支持向量机中增加一个调整因子属性，所述调整因子的定义为该二分类SVM的分类成功次数与分类总次数的比值，分类成功次数为通过该二分类SVM并且输出结果为+1的测试样本的个数，分类总次数是指通过该二分类SVM的测试样本的总数。在分类的过程中根据每个二分类SVM的分类结果不断调整其调整因子的大小，当各二分类SVM的调整因子的最大值与最小值之比大于预设的阈值时，对二叉树的结构重新进行调整，将调整因子最大的二分类SVM放到二叉树的根节点，第二大的作为其子节点，以此类推，形成一棵新的二叉树。调整后继续进行后续样本的分类过程。

本发明的基于动态二叉树的SVM多分类方法，首先利用训练好的多个二分类SVM构造二叉树结构的SVM多分类器，其中所述二分类SVM在传统支持向量机的结构基础上增加了三个属性，分别为分类成功次数、分类总次数和调整因子属性，分类成功次数为通过该SVM并且输出结果为+1的向量的个数，分类总次数是指通过该SVM的向量的总数。该二分类SVM的属性结构如图2所示。

然后利用所构造的SVM多分类器对测试样本集进行分类，具体包括以下步骤：

步骤1、将测试样本集中的第一个测试样本输入所述SVM多分类器的根节点，并将SVM多分类器中各二分类SVM的调整因子初始化为0；

步骤2、如当前节点为空节点，则分类过程结束，转到步骤4，否则，转至步骤3；

步骤3、用当前二分类SVM对待分类样本进行分类，如输出结果为-1，则根据输出结果动态调整当前二分类SVM的调整因子，并将该测试样本输入给当前二分类SVM的子节点所对应的二分类SVM，然后转步骤2；若为+1，则根据输出结果动态调整当前二分类SVM的调整因子，分类过程结束，转至步骤4；

步骤4、判断SVM多分类器中各二分类SVM的调整因子的最大值与最小值之间的比值是否大于一预设的调整阈值                                                ，如是，则按照以下方法重新调整所述SVM多分类器的二叉树结构：将调整因子值大的SVM向二叉树的根部位置调整，即调整因子最大的SVM作为根节点，次大的SVM作为根节点的子节点，以此类推，建立新的二叉树结构；如否，则保持二叉树的结构不变；

步骤5、将测试样本集中的下一个测试样本输入所述SVM多分类器的根节点，并重复步骤执行步骤2—步骤4，直至测试样本集中所有测试样本均完成分类。

本发明的基于动态二叉树的SVM多分类方法的流程如图3所示。

为了使公众更进一步了解本发明的技术方案，下面举几个不同领域的应用实例进行说明。

应用实例1、网络告警预测:

SVM的一个应用为网络告警的预测，利用SVM的分类功能，对告警的时间序列进行分类，分类结果即为预测结果，因为一个SVM只能分类预测一种类型的告警是否存在，而网络中需要对多种类型的告警进行预测，所以需要训练得到多个SVM，并将多个SVM组织成一个二叉树结构，解决多分类的问题。假设在一个双向有限电视网络中，主要管理HFC设备、光网络设备（Optical Network Unit, ONU）和MoCA（Multimedia over Coax Alliance）头端以及MoCA终端，其中可能出现五种类型的告警：光缆终端设备（Optical Line Terminal ，OLT）信号丢失、设备丢包率过高、链路故障、头端掉线和终端掉线。本实例对这五种类型的告警进行预测，则需要建立五个SVM。

网络告警预测的具体过程如下：

1、SVM的学习阶段：

1）对告警记录进行向量提取，得到目标告警为OLT信号丢失的向量，然后对其进行预处理，形成训练样本，对所得到的训练样本进行训练学习，生成可以分类出OLT信号丢失的SVM；

2）重复上述过程，分别得到四个是否为某种类型告警的SVM；

2、基于动态二叉树的SVM多分类阶段：

1）将五个SVM的调整因子都初始化为0；

2）按照训练得到SVM的顺序，构造初始二叉树，根节点为OLT信号丢失SVM，其孩子节点为设备丢包率过高SVM，以此类推分别为链路故障SVM、头端掉线SVM和终端掉线SVM；

3）将测试样本中的下一个样本通过该二叉树，向量首先通过根节点OLT信号丢失SVM；

4）判断当前节点是否为空节点，若为空节点，则当前向量分类结束，转步骤7），否则转步骤5）；

5）用当前节点对应的SVM对该向量进行二分类，并修改当前SVM的调整因子的值；

6）判断当前SVM的输出结果是否为+1，若为+1，表明当前样本已成功分类，转步骤7），若为-1，则该样本继续通过当前节点的孩子节点，转步骤4）； 

7）计算二叉树节点中最大调整因子与最小调整因子的比值，与阈值进行比较，若比值大于，则重新调整五个SVM在二叉树中的位置，将调整因子最大的作为根节点，次大的作为根节点的孩子节点，以此类推，形成新的二叉树，若比值小于，则保持二叉树的结构不变；

8）判断样本中的向量是否已全部分类结束，若未结束则转到步骤3），若样本分类结束，则整个分类过程结束。

 

应用实例2、P2P流量分类：

对等网络（Peer to Peer，P2P）通过对等节点之间直接连接而共享、传递资源，具有资源利用率高、服务器负载小、消除了服务器瓶颈等优势，因而在流媒体、即时通讯、文件共享、网络游戏、搜索引擎和协同工作等方面取得了广泛应用。但同时，P2P业务也过度消耗了网络资源，甚至引起网络拥塞。为了保证网络正常有序的运行，需要有效识别各种类型的P2P流量并采取相应的管理策略。本发明方法可部署在网络中的接入网关、核心路由器或其旁路上，通过多个SVM组织成动态二叉树对从接入网关或路由器上采集的网络流量进行分类。假设在局域网的核心路由器上采集了网络数据流的五元组(源、目的IP地址，源、目的端口号，协议)及其主要的流量统计特征，包括（数据包大小变化的均方差、主被动连接数比值、上下行流量的比值），形成数据流的样本数据，并应用本发明方法对从局域网的核心路由器上采集到的样本数据流进行分类，识别出非P2P流量和BitTorrent、PPLive、UUsee、Thunder、MSN以及Skype 六种常用的P2P流量，共需要建立七个SVM。

P2P流量分类的具体过程如下：

1、SVM的学习阶段：

1）对P2P数据流进行数据预处理，提取五元组及其主要属性特征，形成训练样本，用所得到的训练样本对一个SVM进行训练，生成一个可以分类出P2P流量的SVM。

2）重复上述过程，对BitTorrent流量、PPLive流量、UUsee流量、Thunder流量、MSN流量和Skype流量分别得到一个能判断数据流是否为该种类型流量的SVM。

2、基于动态二叉树的SVM多分类阶段：

1）将七个SVM的调整因子都初始化为0；

2）按照训练得到SVM的顺序，构造初始二叉树，根节点为P2P流量分类SVM，其孩子节点为BitTorrent流量分类SVM，以此类推分别为PPLive流量分类SVM、UUsee流量分类SVM、Thunder流量分类SVM、MSN流量分类SVM和Skype流量分类SVM；

3）将测试样本中的下一个样本通过该二叉树，向量首先通过P2P流量分类SVM；

4）判断当前节点是否为空节点，若为空节点，则当前样本分类结束，转步骤7），否则转步骤5）；

5）用当前节点对应的SVM对该样本进行二分类，并修改当前SVM的调整因子的值；

6）判断当前SVM的输出结果是否为+1，若为+1，表明当前样本已成功分类，转步骤7），若为-1，则当前样本继续通过当前节点的孩子节点，转步骤4）； 

7）计算二叉树节点中最大调整因子与最小调整因子的比值，与阈值进行比较，若比值大于，则重新调整七个SVM在二叉树中的位置，将调整因子最大的作为根节点，次大的作为根节点的孩子节点，以此类推，形成新的二叉树，若比值小于，则保持二叉树的结构不变；

8）判断样本是否已全部分类结束，若未结束则转到步骤3），若样本分类结束，则整个分类过程结束。

 

应用实例3、图像语义分类：

图像是多媒体的一种主要表现形式，将图像数据库划分为有意义的语义类别是基于内容的图像检索中的一个重要内容。SVM算法由于需要的训练样本少，分类效果好，被广泛应用在图像语义分类中。本应用实例对Corel image Datasets的图片（http：//corel.digitalriver.com/）进行语义分类，Corel 数据集包括土著居民、大海、建筑、大巴车、恐龙、大象、花、草原上的马、雪山、食物10 个类别。应用本发明方法先用每一类别中的已标注样本图片进行学习建立一个SVM，再将学习后的SVM建立动态二叉树对待分类的未标注样本图片进行快速分类。分类的图像特征（即分类器的输入特征）包括64 维颜色特征和18 维纹理特征。

图像语义分类的具体过程如下：

1、SVM的学习阶段：

1）对土著居民的样本图片集进行预处理，提取图片的82维图像特征形成训练样本，建立一个SVM并用所形成的训练样本进行学习，生成可以分类出土著居民的SVM；

2）重复上述过程，分别用每一种类别的样本图片集训练一个SVM，对大海、建筑、大巴车、恐龙、大象、花、草原上的马、雪山、食物九种类型分别得到一个能判断出图像是否为某种类型的SVM，共九个SVM。

2、基于动态二叉树的SVM多分类阶段：

1）将十个SVM的调整因子都初始化为0；

2）按照训练得到SVM的顺序，构造初始二叉树，根节点为土著居民的分类SVM，其孩子节点为大海的分类SVM，以此类推分别为建筑、大巴车、恐龙、大象、花、草原上的马、雪山、食物的分类SVM；

3）将由未标注图片的图像特征构成的测试样本集中的下一个样本通过该二叉树，向量首先通过土著居民的分类SVM；

4）判断当前节点是否为空节点，若为空节点，则当前样本分类结束，转步骤7），否则转步骤5）；

5）用当前节点对应的SVM对该样本进行二分类，并修改当前SVM的调整因子的值；

6）判断当前SVM的输出结果是否为+1，若为+1，表明当前样本已成功分类，转步骤7），若为-1，则当前样本继续通过当前节点的孩子节点，转步骤4）； 

7）计算二叉树节点中最大调整因子与最小调整因子的比值，与阈值进行比较，若比值大于，则重新调整七个SVM在二叉树中的位置，将调整因子最大的作为根节点，次大的作为根节点的孩子节点，以此类推，形成新的二叉树，若比值小于，则保持二叉树的结构不变；

8）判断样本是否已全部分类结束，若未结束则转到步骤3），若样本分类结束，则整个分类过程结束。

 

应用实例4 、网络攻击检测：

在一个网络的交换机、入口路由器或防火墙内部等数据流的关键入口，监听本网段内的所有数据包并使用本发明方法对捕获的网络数据包进行分类，判断是否发生异常入侵。设已采集到的网络数据集（如：MIT林肯实验室收集的网络入侵检测数据集KDDCUP99）包括涉及基本特征、内容特征、流量特征和主机流量特征四类特征的41维属性，其中有34个连续属性和7个分类属性，需从中检测出拒绝服务攻击(Denial of Service, DoS)、探测攻击(Probing)、用户获取超级权限攻击(User to Root, U2R)和远程网络用户攻击(Remote to Local, R2L)四种常见的网络攻击。则应用本发明方法先对每一种攻击数据进行学习建立一个SVM，再将学习后的SVM建立动态二叉树结构对样本数据包进行快速分类。

网络入侵检测的具体过程如下：

1、SVM的学习阶段：

1）对网络数据集进行数据预处理，提取DoS攻击数据集中的34个连续属性形成训练样本，建立一个SVM并用所形成的训练样本进行学习，生成可以分类出DoS攻击的SVM；

2）重复上述过程，分别用每一种攻击数据集训练一个SVM，对Probing、U2R和R2L型攻击分别得到一个能判断出是否为某种攻击的SVM。

2、基于动态二叉树的SVM多分类阶段：

1）将四个SVM的调整因子都初始化为0；

2）按照训练得到SVM的顺序，构造初始二叉树，根节点为DoS分类SVM，其孩子节点为Probing分类SVM，以此类推分别为U2R分类SVM和R2L分类SVM；

3）将测试样本中的下一个样本通过该二叉树，向量首先通过DoS分类SVM；

4）判断当前节点是否为空节点，若为空节点，则当前样本分类结束，转步骤7），否则转步骤5）；

5）用当前节点对应的SVM对该样本进行二分类，并修改当前SVM的调整因子的值；

6）判断当前SVM的输出结果是否为+1，若为+1，表明当前样本已成功分类，转步骤7），若为-1，则当前样本继续通过当前节点的孩子节点，转步骤4）； 

7）计算二叉树节点中最大调整因子与最小调整因子的比值，与阈值进行比较，若比值大于，则重新调整七个SVM在二叉树中的位置，将调整因子最大的作为根节点，次大的作为根节点的孩子节点，以此类推，形成新的二叉树，若比值小于，则保持二叉树的结构不变；

8）判断样本是否已全部分类结束，若未结束则转到步骤3），若样本分类结束，则整个分类过程结束。

 

应用实例5、网页分类：

Internet的迅速普及使网络成为人们信息获取的主要来源。而网页自动分类是一种有效处理海量Web信息的重要技术，可以帮助用户从海量的网页中迅速准确地获取所需信息。它是指对于待分类网页根据其内容，由计算机根据某种自动分类算法，把网页分为预先定义好的类别。本发明方法可以对网页实现快速自动分类。本应用实例从Internet下载一定数量的（如2000个）网页，手工分为财经、体育、军事、科技、文化共5个类别。其中，选取一部分网页（如1500个）作为训练集，其余网页（500个）作为样本集。在用本发明方法进行分类之前，需首先对网页进行特征提取，即：先对超文本进行网页过滤，获得网页正文、超文本标记和超链接信息。再对网页正文进行分词处理，并用TF-IDF（term frequency–inverse document frequency）特征表示法将正文文本表示成由词条组成的向量形式，设所有网页文本的全部特征总数是n，则构成一个n 维的向量空间，其中每一个网页文本被表示为一个n 维向量（w₁, w₂, … ,w_n），向量在每一维上的分量对应该特征在这个页面中的权值。然后，运用本发明方法对每一类别的网页训练集进行学习建立一个SVM，再将学习后的SVM建立动态二叉树结构对网页样本集进行快速分类。

网页分类的具体过程如下：

1、SVM的学习阶段：

1）对网页训练集进行数据预处理，提取财经类网页中每一个网页的n维特征向量形成训练样本，建立一个SVM并用所形成的训练样本进行学习，生成可以分类出财经类网页的SVM；

2）重复上述过程，分别用每一种类别的网页集训练一个SVM，对体育、军事、科技、文化这四个类别分别得到一个能判断出网页是否为某种类型的SVM。

2、基于动态二叉树的SVM多分类阶段：

1）将五个SVM的调整因子都初始化为0；

2）按照训练得到SVM的顺序，构造初始二叉树，根节点为财经分类SVM，其孩子节点为体育分类SVM，以此类推分别为军事、科技和文化分类SVM；

3）将测试样本中的下一个样本通过该二叉树，向量首先通过判断是否为财经类网页的SVM；

4）判断当前节点是否为空节点，若为空节点，则当前样本分类结束，转步骤7），否则转步骤5）；

5）用当前节点对应的SVM对该样本进行二分类，并修改当前SVM的调整因子的值；

6）判断当前SVM的输出结果是否为+1，若为+1，表明当前样本已成功分类，转步骤7），若为-1，则当前样本继续通过当前节点的孩子节点，转步骤4）； 

7）计算二叉树节点中最大调整因子与最小调整因子的比值，与阈值进行比较，若比值大于，则重新调整七个SVM在二叉树中的位置，将调整因子最大的作为根节点，次大的作为根节点的孩子节点，以此类推，形成新的二叉树，若比值小于，则保持二叉树的结构不变；

8）判断样本是否已全部分类结束，若未结束则转到步骤3），若样本分类结束，则整个分类过程结束。

以上应用实例仅为了便于公众理解本发明的技术方案，并非对本发明的限定，本领域技术人员应知，在不脱离本发明的精神和范围的情况下，还可以作出各种变化或应用于不同领域，因此所有等同的技术方案以及在不同领域的应用均属于本发明的保护范围。