一种提高SVM分类速度的新方法

任逸卿，朱昌杰，吴 波

(淮北师范大学 计算机科学与技术学院，安徽 淮北 235000)

支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多优势，并能够推广应用到函数拟合等其他机器学习问题中[1].它的分类方法是建立在统计学习理论的VC维理论和结构风险最小化原理基础上的.

本文提出一种改进的SVM分类器.改进分类器的主要功能是通过引入分类圆心，分类半径，分类圆心距的概念，从而快速地对非支持向量点进行删除，提高分类速度.引入混消度的概念，保证在训练样本严重混淆时的算法泛化性[2].

1 现有的一些SVM改进算法

SVM具有很强的泛化能力.但是实际问题中，两类训练样本时常混淆严重.这种情况下，SVM分类面就非常复杂，分类效率低下.现有的解决这个问题的办法有使用NN-SVM-KNN[3]分类器以及使用SVMKNN[4]等.SVM对于数据量很大的样本的训练效率都很低，针对大规模样本的分类办法有Light-SVM，最远邻等.但是这些方法分类精度都有所下降，而且效率不高[5]，删减后依然有大量数据.

2 改进算法

解决样本混淆严重的分类问题时，算法需要既能快速地对样本中非支持向量的混淆点进行删减，又能保证训练的结果泛化能力.然而在支持向量机中，不会出现在两个样本集间隔以外的正确划分区.我们就引入下面几个概念:

一个类 S=｛t1，t2，t3，…，tn｝包含有 N个点，其中 t是 S中的一个样本，这里每个样本都是 m维向量.

分类圆心距:S=|C1-C2|，表示两个分类圆心之间的距离.

混淆度:计算每个样本 ti与它距离最近的 L个样本的几何距离.设这 L个样本 ti的距离分别为 D1，D2，…， DL.分下面几种情况:

这个概念表示了一样本点周围点的混淆程度.

分类方法:假设一个训练集为两类，一类为正，一类为负，分别用+和-表示，算法步骤如下:

(1)计算两类样本的分类圆心 C+，C-;分类半径 R+，R-;分类圆心距 L.

(2)分情况比较:

正类中，若 R+＞L，则删去对应分类圆心 C+大于 R+的+类样本.

若 R+＜L，则删去对应分类圆心 C+大于 L的+类样本.

负类中，若 R-＞L，则删去对应分类圆心 C-小于 R-的-类样本.

若 R-＜L，则删去对应分类圆心 C-小于 L的-类样本.

(3)经过上面修剪剩下的样本成为支持向量的概率就很高.对这些剩下的每个样本 ti计算混淆度 Ei，进行进一步的删减提高泛化性.这里我们给每个样本的混淆度设定一个因子 ε(ε＞0)

当 Ei＞ε，混淆程度在接受范围，保留样本点;

当 Ei＜ε，混淆严重，删除样本该样本点.

经过两次修剪以后，使用支持向量机对剩下的样本进行分类.

由此可见，前两步是进行选取出那些可能成为支持向量的样本，算法复杂度为 O(n)(n为样本数量)，最远邻算法的复杂度为 O(n2)，分类效率已经有很大提高.NN-SVM-KNN分类器和SVM-KNN分类器处理混淆样本问题的时，对周围样本进行数量上的考察，第三步在此基础上增加了对距离的考察，算法复杂度依然是 O(n2)，本步效率没有提高，但是三步综合来看分类速度明显提高，满足了设计之初的要求.

3 实验结果及分析

在PC机上(I7，Q720处理器，4G内存)上，利用已有的LIBSVM软件工具包(软件包是采用SMO快速算法实现SVM)以及http:∥ir.hitede.cn/上的两组数据进行删减实验.具体如下:

(1)鸢尾属植物样本实验.鸢尾属植物数据集的样本，共有150个样本分为3类，分别是:S类，Ve类，Vi类.每类有50个样本，每类都有4个属性是4维向量.这个样本各类别之间样本混淆不严重.

用修剪程序对数据集进行测试，实验结果如下(其中取 ε=0，L=5):

表1 对鸢尾属样本计算结果

表2 对鸢尾属样本修剪结果

由上面数据可以看出，步骤(1)(2)删除的样本占总数的42%，效果很好，而且算法复杂度由 O(n2)下降到O(n).

(2)鲍鱼样本实验.数据集也是包含3类，分别用M，F，I标示进行区分，每类都是8维的向量，共有M类样本1 530个，F样本1 310个，I样本1 340个，总数4 180个.取其中M，F类进行实验.鲍鱼样本的特点是各样本之间混淆严重.

对鲍鱼样本中的两类进行测试，结果如下:

表3 对鲍鱼样本计算结果

表4 对鲍鱼样本修剪结果

表5 算法步骤(3)固定 ε=3改变 L的值结果

表6 算法步骤(3)固定 L=5改变 ε的值结果

由上面数据看出，经过步骤(1)(2)删除的样本数占总样本数的近一半，效果很好，而且算法复杂度由最远邻法的 O(n2)下降到 O(n).

经过步骤(3)删除的样本占到(1)(2)之后剩余样本的40%左右，说明算法对于混淆严重的样本分类效果很明显.而 ε和 L两个参数的取值对于混淆度的影响如下:

1)随着 ε值的增大，可以删除的混淆点越来越少，ε是由我们人为设定的混淆因素，ε值取值越大说明我们对每个样本数据的重视程度越高，不会轻易地删除样本数据.

2)L值增大以后，刚开始时混淆点的删除率是增大的，L值达到5以后，混淆点的删除率开始基本维持不变.

4 结语

本文提出一种改进的新支持向量机分类方法，使得对于不同的数据集分类算法的效率有不同程度的提高，同时可以根据数据需要改变参数选择混淆点删除程度，有一定灵活性.进一步的工作是从SVM分类机理出发，在提高分类速度的同时提高分类正确率.

[1]VAPNIK V.An overview of statistical learning theory[J].Ieee Trans，1999，2(6):57-58.

[2]VAPNIK V，LEVIN E.Measuring the VC dimension of a learning machine[M].Neural Computation，1994:851-876.

[3]邓乃扬.数据挖掘中的新方法:支持向量机[M].北京:科学出版社，2004.

[4]郑春颖.一种改进SVM算法[J].航空计算技术，2005，35(2):6-8.

[5]李蓉，叶世伟，史忠植.SVM-KNN分类器——一种提高SVM精度的新方法[J].电子学报，2002(5):745-748.