一种基于近邻区的支持向量机样本约减算法

【摘 要】支持向量机 （Support Vector Machine，SVM）以实现结构风险最小化为原则，成功避免了传统机器学习基于无穷样本数量的假设，以及推广能力差、“过学习”、局部最优值、“维数灾难”等问题。对分类起作用的支持向量只存在于样本分界处，其他对分类不起作用的样本会增加构造支持向量的时间，导致分类速度较慢。本文提出了一种基于近邻区的样本约减算法，将异类样本中离得最近（特征空间中离得近意为相似性高）的聚类区域内的样本集合作为SVM新的训练样本集合，从而有效减少训练样本数量和构造支持向量的时间，在保证分类准确度的前提下提高分类速率。

【关键词】SVM，分类，样本约减，近邻区

一、引言

SVM是在小样本情况下发展起来的统计机器学习理论，基于结构风险最小化原则[1]，可以解决分类、回归等问题。结构风险最小化就是指在保证分类精度的同时，降低学习机器的VC维，使学习机器在整个样本集上期望风险得到控制。

SVM最初以成功解决二分类问题著称，其分类准确性高、受“噪音”样本干扰小、稳定性好，通过在样本之间寻找一个最优分类面分隔异类样本。寻找最优分类面的问题最终转换成凸二次优化问题的求解过程，样本数量及样本的维数都将直接影响分类性能。因此，在数据分类中减少样本数量不仅可以减少SVM分类时间，而且可以实现结构风险最小化。

二、SVM[2]

三、SVM样本约减算法研究现状

为了提高分类性能，有效优化SVM的样本训练效率，目前已经提出了一些方法。文献[3]提出采用聚类方法寻找代表 k 个簇的聚类中心作为约简集，该方法只能表现为超球面的形状，以单一的点代替整个不规则的聚类簇很不合适。

也有的方法将主动学习策略用于 SVM 的样本选择[4]，以及在特征空间中将样本做分离，将高维二次凸优化问题分化成多个低维凸优化问题的组合[5]。

张金泽[6]等人提出模糊超球支持向量机，将样本空间划分成有限个超球子空间，超球球心作为新的训练集。

文献[7]提出的算法通过计算样本与类中心点的夹角进行样本约减，该方法有一定错选或多选，达不到最佳效果。

四、基于近邻区的SVM样本约减算法

对SVM分类起作用的只有位于样本集合交界处支持向量，而其它非支持向量对分类没有任何贡献。本文提出的基于“近邻区”的SVM样本约减算法将两类样本中离得最近（特征空间中离得近意为相似性高）聚类区域内的样本作为SVM新的训练样本集合，从而减少构造支持向量的时间，提高分类速率。

（一）相关定义

（二）基于近邻区的样本约减算法过程

在样本的特征空间中，每一个聚类都占据一定的区域，聚类区域内的样本可以用该聚类的聚类中心近似代表。本文基于近邻区的样本约减算法具体过程描述如下：

注意，采用样本约减算法后的样本数量与异类子近邻区中的值选取有关，值越大，约减算法处理后的样本所包含的支持向量可能更多、更全面，但样本训练时间随之增加。因此，在实际应用中应当从SVM训练样本时间、分类准确性等多方面进行考虑与权衡。

本文提出的基于“近邻区”的SVM样本约减算法将那些分布于样本分界处附近、处于自身所在类别边界处的带状区域内的样本作为新的样本集合，从而保证约减后得到的样本集合与支持向量出现的位置相同，大大降低了计算量，减少了构造支持向量的时间。因此，本文提出的样本约减算法在保证分类准确度的同时有效减少了分类时间。

参考文献：

[1]Hou Jinbiao.Design and implementation of a system of video image capture of camera based on JMF[C]. MultiMedia and Information Technology，International Conference，2008：201-204.

[2]G. Song， J. Guo， Y. Nie. An Intrusion Detection Method Based on Multiple Kernel Support Vector Machine [C]. International Conference on Network Computing and Information Security. 2011， 119C123.

[3]李晓黎， 刘继敏， 史忠植，基于支持向量机与无监督聚类相结合的中文网页分类器，

计算机学报，2001，24（1）： 62～68.

[4]Schohn G，Cohn D.Less is more：Active learning with support vector machines[C]. Proceedings of the 17th International Conference on Machine Learning. IEEE Press，2000：839-846.

[5]王勇. 基于特征空间中样本选取与分离的 SVM 简化方法 [J].长春工业大学学报（自然科学版）， 2008， 29（5）：486-491.

[6]张金泽，单甘霖，模糊支持向量机，军械工程学院学报，2005，17（3）：65～67.

[7]罗瑜，易文德.大规模数据集下支持向量机训练样本的缩减策略[J].计算机科学， 2007， 34（10）：211-213.