支持向量机采样简化的一种新方法

摘要：作为机器学习中一个强大的工具，由于需要巨量的原始训练样本，支持向量机在训练阶段同样深受算力耗费昂贵的困扰。为了解决这个问题，本文基于两步样本简化提出了一种新方法来简化训练样本。这个算法包含了通过模糊C均值聚类的聚类检测和通过多元高斯分布来进行样本简化。在实现过程中，模糊C均值聚类算法用来对原始训练样本进行聚类，而多元高斯分布算法通过仅选择边界样本作为下一次的训练样本来简化训练样本。实验发现，本算法可以在不降低分类精度的情况下，提高训练的速度。

关键词：样本简化；概率分布；FCM；SVM

1. 简介

基于统计学习理论[1]的支持向量机（SVM）是一种新的机器学习方法。由于其良好的性能，在模式识别[2]中得到了广泛的应用，在高维特征空间中采用了边缘最大化和核技术。此外，支持向量机具有很高的拟合精度和少量的可调参数，可以找到全局解。在利用支持向量机进行分类的同时，尝试寻找一个具有最大边缘和几个参数的最优分离超平面。在支持向量机算法中，首先解决了线性约束凸二次规划的优化问题。然后通过位于两类训练样本边界上的支持向量（SVS）得出系数。在此过程中，我们解决了优化问题，并用支持向量机得到了两类的边界。但在整个优化过程中，我们通常同时处理SVS和非SVS，这会带来一些不必要的计算成本。

为了在不降低分类性能的前提下，加快训练过程，降低计算成本，需要去除一些不相关的样本。因此，近年来研究者提出了许多样品还原的方法。最常用的方法之一是李东辉[3]提出的中心距比法，SVDD[4]算法通常用于提取边界目标[5]，另一种方法是KNN[6]。大家知道，这些方法可能不太好。它们都会迭代计算样本距离，通常会随着训练样本数的增加而增加计算成本，或者通常假定原始训练数据集是凸集。所以它只需要删除分布中心的数据部分。也就是说，它只需要从SVS中预先提取边界向量（BVS）来代替原始的训练样本进行训练。

为了节省计算成本，提高分类效率，本文提出了一种新的样本约简方法。该方法的关键问题是识别出了两步样本约简，即聚类检测和样本约简。它直接利用训练数据的概率分布作为阈值提取边界数据，不需要复杂的距离计算，也不需要知道训练样本的原始分布。该策略的性能表明，它不仅适用于各种原始训练样本，而且适用于非凸壳集和凸壳集。

1. 方法
2. SVM

SVM是一种有效的机器学习方法，主要用于分类和回归问题。在分类中，SVM的目标是寻找两类之间的最优分离超平面。

然后将边界最大化，解决QP难题。

此处 是松弛变量，且Wolfe对偶形式涉及拉格朗日乘子，这可以用标准二次优化包解决。决定函数是

如果拉格朗日乘子，那么相对应于训练数据，称它们为支持向量。超平面f(x)取决于这些点。

在非线性问题中，支持向量机利用满足梅瑟条件的核函数，利用非线性映射将输入空间的数据映射到高维特征空间。决定函数由下式给出：

B．模糊C均值聚类算法

传统的聚类方法很难在含有大量噪声或不同类型数据的数据集中检测聚类。因此，直接对原始分类数据进行模糊聚类，不仅包括凸集，也包括非凸集，这一点已经得到了广泛的认识。模糊聚类根据给定聚类中每个模式的隶属度表示的部分隶属度的概念生成一个模糊分区。模糊C均值（FCM）是一种聚类方法，它允许一条数据属于两个或多个聚类。该算法由Dunn开发，Bezdek[7，8]改进，旨在找到聚类数据的最佳聚类数。

它基于以下目标函数的最小化：

其中m是模糊参数，是j簇中的隶属度，是实测数据的第i个，是簇的d维中心，是点到簇中心的距离，通过迭代优化上面给出的目标函数进行模糊划分。如上图所示，随之隶属度和簇中心通过下式更新：

当满足 时，迭代停止。是介于0与1之间的终止条件，而k是迭代步数。

该算法由以下步骤组成：

1. 初始化矩阵U=[ ]和U(0)

1. 对于第k次迭代：使用U(k)计算中心向量C(k)=[ ]

1. 更新U(k)，U(k 1)
2. 如果停止算法，否则返回第2步。

C 多元高斯分布模型

在统计学理论中，对于输入向量，

其中是高斯模型G的平均值，是dxd的对角协方差矩阵，且在它的对角线上。关于概率分布函数，输入训练向量的值可通过以下公式计算：

这是多元高斯分布（MGD）模型[9]。文献[10]通过这个模型将向量转换成概率分布函数的值，本文中，我们也使用这个模型来根据它们的函数值选择数据。有趣的是，对这些概率值的观察发现，靠近高斯分布中心的向量具有较大的概率分布函数值，而靠近边界的向量具有较小的概率值。

1. 用于分类的一种样本简化方法
2. 新方法的框架

针对分类问题训练支持向量机在许多研究领域得到了广泛的应用。对于许多分类问题，支持向量机的数目远小于训练样本的数目。如果事先知道哪一个训练样本结果为SVS，那么只对这些样本进行训练就足够了，并且仍然得到相同的结果。这将使qp问题更小、更快地得到解决，因为我们不需要与svs不对应的训练样本部分，从而节省了时间和空间。提出了一种两步的样本约简方法，包括用FCM聚类检测聚类和用MGD进行样本约简。其框架如图2所示。

该方法的具体步骤如下：在第一步，分别在训练样本和训练样本中使用FCM检测聚类，然后在第一步检测到的每个聚类中使用MGD选择具有最小概率值的边界样本。最后，将第二步中获得的简化训练样本用于下一次训练。计算时间和空间的节省是显而易见的。

1. 分析

众所周知，如果原始训练样本是凸包集，则MGD模型可以很好地用于减少训练样本。换句话说，我们可以考虑一个简单的二维例子。给定一个特定的原始训练样本，假设将其表示为分布在一个区域上。下图显示了这一点：

在图3中，我们可以确定减少的训练样本（如图3（b）所示）可以通过原始训练样本（如图3（a）所示）完全获得。但对于非凸集，该方法可能涉及局部最优，如图4（b）通常直接从图4（a）中减少。为了解决这一问题，我们在样本约简之前使用FCM算法检测聚类，其中我们将一个非凸集划分为若干凸集，因此从图4（a）所示的原始训练数据中可以得到如图4（c）所示的约简样本。

1. 实验

实验是在一台个人电脑上进行的，该电脑有2.1 GHz的英特尔酷睿2双核CPU和2G字节的内存。我们实验的数据集来自UCI数据库[11]。我们的实验中使用了名为libsvm[12]的SVM实现。

在我们的实现中，首先执行了两步样本约简策略，然后将约简后的训练样本应用到一个分类问题中。在培训过程中，使用了9个来自UCI数据库[11]的123维“成人”数据集进行SVM分类，这些参数分别通过十倍交叉验证生成，因为不可能在每个类中选择这些参数，采用不同的参数值将导致不同的结果。为了评估我们的系统，除了经典的精度测量，还测试了训练样本的数量和支持向量的数量。表1显示了这些结果。

由表1可知，减少训练样本的训练样本数明显少于原始训练样本（尤其是A1A数据集，减少了32%的原始训练样本），减少训练样本的支持向量数也少于原始训练样本的支持向量数。虽然该算法只保持了分类的准确性，但对样本进行了训练。此外，还明显节省了培训时间（尤其对于A9A问题，减少了原始样本培训时间的65.8秒）。表1显然表明，训练样本的数量越多，节省的训练时间就越多。当训练集“a1a”中约有1000个数据时，只减少了0.13秒，当训练数据达到10000个以上时，节省的训练时间大于8秒。结果同时给出了基于大样本集的减少训练样本和训练时间的理想性能。

1. 结论

为了去除不相关的样本，降低支持向量机的计算成本，加快训练速度，本文提出了一种样本约简算法，去除分类样本中心附近的样本，保留边界样本。这两个步骤的样本减少，不同于传统的样本减少，是我们的一个突出表现。值得一提的是，该方法可以广泛应用于各种训练样本中，包括凸包集和非凸包集。实验结果表明，该算法在保证测试样本精度的前提下，大大减少了训练样本和支持向量的数目。

文献引用：

[1] V. N. Vapnik㧘Statistical Learning Theory, John Wiley amp; Sons, 1998.

[2] C. M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006.

[3] D. Li, Pre-extracting Support Vectors for Support Vector Machine, In Proceedings of the 5th International Conference on Signal Processing Proceedings, August 21- 25, pp.1432 - 1435, 2000.

[4] D.M.J. Tax, R.P.W. Duin, Support Vector Domain Description,Pattern Recognition, pp.1191-1199, 1999.R. Nicole, “Title of paper with only first word capitalized,” J. Name Stand. Abbrev., in press.

[5] J. Liang, S. Liu, D. Wu, Fast Training of SVDD by Extracting Boundary Targets, Iranian Journal of Electrical and Computer Engineering, 8(2):133-137, 2009.

[6] B. Li, Q. Wang, J. Hu, A Fast SVM Training Method for Very Large Datasets, Proceedings of International Joint Conference on Neural Networks, June 14-19, 2009.

[7] J. C. Dunn, A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters, Journal of Cybernetics, 3(3): 32-57, 1973.

[8] J. C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algoritms, Plenum Press, New York, 1981.

[9] T. W. Anderson, An Introduction to Multivariate Statistical Analysis, John Wiley amp; Sons, New York, 1984.

[10] Z. Yu, H.Wong, G.Wen, A Modified Support Vector Machine and its Application to Image Segmentation, Image and Vision Computing, 29:29-40, 2011.

[11] http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/.

[12] C. Chang, C.Lin, LIBSVM-A Library for Support Vector Machines, Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.

[13] X.Liu, Z. Chen, Fast Classification Alorithm of Support Vector Machines, Journal of Computer Research and Development, 41(8):1327–1332, 2004.

[14] H.W. Wang, B. Kong, An Improved Reduced Support Vector Machine, In Proceedings of 2010 IEEE Youth Conference on Information Computing and Telecommunications Conference on Neural Networks, Nov 28-30, 2010.

[15] L. Zhang, N. Ye, Support Vectors Pre-extracti

资料编号：[4600]