一种改进的局部支持向量机算法＊

朱莹莹，尹传环，牟少敏

（1.北京交通大学计算机与信息技术学院，北京 100044；2.山东农业大学信息科学与工程学院，山东 泰安 271018）

1 引言

20世纪90年代中期，由Vapnik教授根据统计学习理论提出的支持向量机SVM（Support Vector Machine）思想，可用于模式分类和回归估计[1～4]。由于支持向量机与传统的模式分类、机器学习的方法如人工神经网络等相比有其显著优越性，如泛化能力强、全局优化等，因此获得了越来越广泛的应用。

从本质上来说，支持向量机是一种二类分类器，能够求解各种二类分类问题。假设给定一个独立同分布的样本集X：

根据结构化风险最小化原则，在训练集中构造目标函数[5]：

其中，w 是垂直于超平面的向量，φ（xi）相当于把xi映射到特征空间中的向量，ξi 是松弛变量（松弛因子），用来惩罚那些不能被正确分开的样本点；C 是惩罚项常数，用来权衡惩罚力度，C 越大，错误分类的惩罚越重；b是常数项。最后，利用决策函数：

由于二类分类的一致性问题[6]，基于减少参与分类的样本数目，以提高分类速度为目的的局部支持向量机一经提出就倍受关注。除了理论研究之外，局部支持向量机在实际应用方面也得到了广泛研究，如遥感图像分类[7]、网络流量预测[8]、脑电图信号处理[9]等领域。

2 局部支持向量机及加权支持向量机

2.1 局部支持向量机的思想

局部支持向量机的思路最早是由Brailovsky等人[10]提出的，他们将两个乘子添加在核函数中，使之具有局部性。定义如下：

重新定义一个新的核函数：

且令：

并且可通过设定θr的取值定义一个局部核函数：

2.2 Falk-SVM 算法

传统的一些局部支持向量机，例如SVMKNN、KNNSVM 和LSVM 等，都需要为每一个样本构造模型，虽然局部支持向量机减少了参与建模的样本数量，但在测试样本数量比较多的情况下，局部支持向量机的时间复杂度还是相当高的，因为需要构造的模型个数增长更多。因此，如何提高测试效率是近年来局部支持向量机研究的一个主要内容。

在局部支持向量机中，最直观的改进思路就是减少需要训练的支持向量机模型的个数，具体的改进方法如算法1所示。

算法1 局部支持向量机改进算法

步骤1 将训练集中的样本依据某种原则划分为k类，并找到k个中心；

步骤2 为每个中心构造一个支持向量机；

但是，Segata和Blanzieri认识到这种改进仍存在一些问题[11，12]，于是他们在kNNSVM 的基础上提出了Falk-SVM （FAst Local Kernel Support Vector Machine）算法，该算法的基本思路与算法1相似，区别在于选取中心点的过程。

Falk-SVM 在训练集上采用类似于求最小覆盖集[13]的方法来获得覆盖所有训练集的中心。定义一个集合A 的最小距离d（A）和最大距离D（A）：

因此，对于训练集X 来说，最小距离和最大距离分别为d（Χ）和D（Χ）。

首先构造一系列X 的子集Si，使得Si⊆Χ，并且满足：

在构造Si时可以更具体地引入一个大于1的数值b，使得d（Si）＞bi。称Si中的最小索引i为bot，最大的索引i为top。通过递归得到：

其中，choose（A）表示从非空集合A 中选择一个元素的函数。这个函数可以根据情况有不同定义，即选择元素的方法不同，例如，可以简单地将choose（A）定义为取得A 中下标最小的元素等，在这里就是这么定义的。该递归的真正含义可表示为：Si不仅需要包含Si＋1中所有的元素，还应该尽可能多地包含那些不在Si＋1中并且距离Si＋1足够远的样本，这样通过式（8）构造出来的一系列Si就可以满足式（7）的要求。

接着从一系列Si中选取中心，使得这些中心的k′-近邻能够覆盖所有的训练样本。选取中心也是通过一个递归公式实现的：

值得注意的是：选取中心时，是所有中心的k′-近邻能够覆盖所有训练样本，而不是它们的k-近邻覆盖所有样本，而基于某中心构造支持向量机时，是将该中心的k-近邻选做训练集，k′≤k，因此有一部分训练样本将被重复使用。实际上Segata和Blanzieri在他们的工作中设置k′＝k／2，这是在实验中通过参数调优得到的一个经验值。

2.3 加权支持向量机

范昕炜等[14]首先提出了对每一类样本赋予不同权值的加权支持向量机 WSVM（Weighted SVM）模型，对类别差异造成的影响进行了相应的补偿，从而提高了小类别样本的分类精度。其优化问题描述为：

其中，υ是v-SVM 中的系数，用于对每一类的支持向量数界限分别进行调整；ρ是常数设置。

采用拉格朗日乘子法求解式（9）优化问题，即：

其中αi、βi 和δ 都是拉格朗日乘子，并且αi≥0，βi≥0和δ≥0。通过微分计算得到对偶表达式为：

其中，si是为每一个样本增加的一个系数作为权值，它可以是0和1之间的常数，也可以是函数，例如，随样本到达时间变化的函数。

如果某一种样本是非常重要的或者某些被噪声污染的样本点要舍去，都可通过对每个样本赋予不同的权值来解决这些问题。例如，对于要舍去的样本点，可将其权值赋值为近似零的数，而将重要的样本点的权值赋值为1或者近似为1的数，这样就可以克服广义SVM 算法在权重方面的缺陷。

3 Weighted Falk-SVM 算法

尽管上述提到的Falk-SVM 取得了比较好的分类精度，但依然存在几个问题：

（1）在构造的每个支持向量机模型中，存在正负样本不均衡的情况，此时，单个模型的分类精度并不理想，尽管在总的分类精度上影响不大。因此，通过某种技术提高单个支持向量机的分类精度以进一步提高总的分类精度是十分必要的。

（2）对于大规模数据集而言，这样的k-近邻数据量依然比较庞大，将会导致单个支持向量机模型的训练速度较低，从而大大增加训练多个支持向量机的时间复杂度。因此，大量减少需要构造的支持向量机的数量来降低整个局部支持向量机的时间复杂度是非常必要的。

针对Falk-SVM 中存在的问题，在加权支持向量机的启发下，本文提出将加权思想应用在Falk-SVM 之上的加权局部支持向量机算法WFalk-SVM（Weighted Falk-SVM）。这样，就可以克服局部支持向量机中单个模型正负样本不均衡的问题，提高单个支持向量机模型的分类精度。

WFalk-SVM 的算法步骤和Falk-SVM 相似，区别在于对每个样本都添加了一个权重值。具体的WFalk-SVM 算法步骤可描述为：

（1）通过Falk-SVM 中选取中心点的方法选取k个中心点；

（2）按照加权支持向量机的思想为每一个中心点进行加权；

（3）按照Falk-SVM 中建模的方法为每一个中心点建模；

（4）采用Falk-SVM 中的方法为每一个测试样本选取模型进行测试。

考虑到加权思想的目的和数据集中正负样本的数目，上述算法采用的权重值以正负样本数目的比例为基础，通过其各种变形寻找最佳权值。当然，对于不同的数据集获得的最佳权值是不同的，如两者比例的幂次方、多项式形式等。

4 实验

实验将算法WFalk-SVM与Falk-SVM 应用于同样的数据集，观察分析结果。此次实验的数据集ijcnn1、splice、a9a、svmguide3、cov-type都来自LibSVM 数据库，如表1描述。

Table 1 Data sets used in experiment表1 实验中用到的数据集

表2中描述的是五个数据集的实验结果，其中，Falk-SVM 和WFalk-SVM 分别表示各自算法的分类精度。通过表2可以看出，对于不同的数据集，加权方式对其产生的影响是不同的，对于一些数据集有很大提高。例如，对于splice 提高了17%，对于svmguide3，加权方法甚至使分类精度提高了将近25%，而对于另外一些数据集则没有显著效果，例如，ijcnn1和cov-type准确度分别只提高了2.6%和5.2%。

Table 2 Experiment results of Falk-SVM and WFalk-SVM表2 将数据集分别应用于Falk-SVM 和WFalk-SVM 的实验结果

表3是以svmguide3为例，针对每个模型进行的使用加权和不使用加权的对比实验。通过表3可知，在每个模型中正负样本比例较大的时候，正如我们预期的那样，WFalk-SVM 的分类精度要比Falk-SVM 的高很多。通过分析数据集合的不同，我们发现svmguide3中测试样本中全为同一类样本（正类样本），训练集中负类样本远远多于正类样本，此时正类样本比较重要，权值应当大一些，对于这样的数据集采用加权的方法可以使准确度提高。例如，在svmguide3和cov-type中，当样本比例为1∶3或者1∶4左右时，模型分类精度都有显著提高，coy-type结果如表4 所示。对于ijcnn1而言，正负样本比例相差非常大（近似10∶1），而每个模型中正负样本比例很多没有达到这么高的比例差，因此分类效果并没有显著的改变，这也正是使用加权思想的目的所在。

Table 3 Different classification models of Falk-SVM and WFalk-SVM in svmguide3表3 svmguide3中Falk-SVM 和WFalk-SVM分类效果不同的模型

Table 4 Different classification models of Falk-SVM and WFalk-SVM in cov-type表4 cov-type中Falk-SVM 和WFalk-SVM分类效果不同的模型

但是，在splice中，当模型中样本比例接近于1的时候，WFalk-SVM 的分类效果同样比Falk-SVM 的好。并且尽管a9a与svmguide3这两个数据集总体上的正负样本比例相同，单个模型中样本比例也相似，但是a9a 的实验结果并不如svmguide3的结果那样令人满意。这也是需要我们进一步研究的内容。实验进一步说明了加权思想在处理数据类型不均衡或者某一类样本比较重要时的作用，也证实了我们提出将加权思想应用于局部支持向量机，即WFalk-SVM 对改善模型中样本不均衡的数据集分类效果的可行性和有效性，但对于不适合于所有数据集的问题有待我们进一步讨论研究。

5 结束语

在众多局部支持向量机中存在诸如时间复杂度过高、分类精度不够满意等缺点，基于局部支持向量机算法kNNBSVM 提出的Falk-SVM 从理论和实验中都验证了Falk-SVM 的快速性和准确性。实际上，该算法是目前为止见诸报端的各种局部支持向量机中，训练和测试速度以及分类精度最好的一种局部支持向量机。

即便这样，对于类别数目比例差异较大或者样本集中存在重要性差异较大的样本类别的数据集，仅仅使用Falk-SVM 的分类精度并不理想，在加权支持向量机的启发下提出的将加权思想应用于Falk-SVM 的思路可以对类别差异造成的影响进行相应的补偿，从而可以提高小类别样本的分类精度。今后的工作主要集中在对加权权值的判断和选取上，以及其适用的数据集的研究上，以期对分类精度做进一步的改进。

[1]Burges C J C.A tutorial on support vector machines for pattern recognition[J].Data Mining and Knowledge Discovery，1998，2.2）：121-167.

[2]Scholkopf B，Smola A.Learning with kernels[M].Cambridge，MA：MIT Press，2001.

[3]Smola A，Schölkopf B.A tutorial on support vector regression[J].Statistics and Computing，2004，14（3）：199-222.

[4]Vapnik V.The nature of statistical learning theory[M].Berlin：Springer Verlag，2000.

[5]Vapnik V N.Statistical learning theory[M].New York：John Wiley and Sons，1998.

[6]Zakai A，Ritov Y.Consistency and localizability[J].Journal of Machine Learning Research，2009（10）：827-856.

[7]Blanzieri E，Melgani F.Nearest neighbor classification of remote sensing images with the maximal margin principle[J].IEEE Transactions on Geoscience and Remote Sensing，2008，46（6）：1804-1811.

[8]Meng Qing-fang，Chen Yue-hui，Peng Yu-hua.Small-time scale network traffic prediction based on a local support vector machine regression model[J].Chinese Physics B，2009，18（6）：2194-2199.

[9]Shen Min-fen，Chen Jia-liang，Lin Chun-hao.Modeling of nonlinear medical signal based on local support vector machine[C]∥Proc of International Instrumentation and Measurement Technology Conference，2009：675-679.

[10]Brailovsky V L，Barzilay O，Shahave R.On global，local，mixed and neighborhood kernels for support vector machines[J].Pattern Recognition Letters，1999，2.（11-13）：1183-1190.

[11]Segata N，Blanzieri E.Fast and scalable local kernel machines[J].Journal of Machine Learning Research，2010（11）：1883-1926.

[12]Segata N.Local approaches for fast，scalable and accurate learning with kernels[D].Trento：University of Trento，2009.

[13]Chen L.New analysis of the sphere covering problems and optimal polytope approximation of convex bodies[J].Journal of Approximation Theory，2005，133（1）：134-145.

[14]Fan Xin-wei，Du Shu-xin，Wu Tie-jun.Reimbursable class differences weighted support vector machine algorithm[J].Chinese Journal of Graphics，2008，8A（9）：1037-1042.（in Chinese）

附中文参考文献：

[14]范晰炜，杜树新，吴铁军.可补偿类别差异的加权支持向量机算法[J].中国图像图形学报，2008，8A（9）：1037-104.