大数据集的快速svm训练方法

《大数据集的快速svm训练方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、大数据集的快速SVM训练方法BoyangLI,QiangweiWANGandJingluHU摘要：训练标准支持向量机需要O(n2)的时间复杂度和O(n3)的空间复杂度，其中n表示数据集的大小。因此支持向量机不能应用到大规模数据集中，因此需要减少数据集的规模，来解决数据集规模过大的问题。对于支持向量机，只有分类边界上的支持向量影响分类器性能。因此那些可能成为支持向量的样本需要被保留。本文提出一种边界检测技术用于保留潜在的支持向量。并且利用k均值聚类的方法对样本集进行聚类，并保留聚类中心，用以反映样本的分布状况。在不影响分类精度的前提下，本文提出的方法可以有效的降

2、低训练集的规模，同时提高训练支持向量机的效率。引言支持向量机是运用核方法的成功范例。许多核方法的公式中需要用到多次求解二次规划的问题。如果训练集的样本数目为n,那么求解二次规划问题的时间复杂度为O(n3)，并且空间复杂度最少为O(n2)。因此对于训练支持向量机，最主要的问题就是如何减少计算的时间复杂度和空间复杂度。为了减少支持向量机的时间和空间复杂度，许多改进算法得到了成功的应用，其中一种方法是通过贪心算法获得核矩阵的低阶近似值[1]，或者样本[2],或者矩阵的分解。然而分解后的核矩阵的维数依然很高，导致支持向量机的训练效率依然非常低下。另外一种方法提高支持向

3、量机的效率是分块算法。然而分块需要优化整个非零拉格朗日乘法器，但其产生的核矩阵仍然可能太大了，导致内存出现溢出状况。第三种方法是避免二次规划问题，如中心支持向量机算法[5]，规模化的方法[6]，拉格朗日支持向量机算法（LSVM）[7]。这类算法对于线性具有非常好的性能，然而，对于非线性核，但它仍然需要大量的矩阵运算。另外一种算法是在训练支持向量机之前减少训练集规模。本文将深入讨论这种更加直观并且从根本上解决问题的方法。Pavlov[8]和Collobert[9]等人提出了利用那个改进的基于神经网络的阈值选择方法用以减少支持向量的规模。Lee和Mangasari

4、an[10]等人提出了RSVM算法，RSVM利用随机获取的一个训练集的子集，用以代替原训练集。这种方法的基本问题是如何检测训练集中不相关的样本。这一类算法都可以减少训练集的规模，但是仍然有许多与分类不相关的非支持向量被保留，这样严重的限制了训练SVM分类器的效率。因此需要提出一种更加行之有效的相关样本保留算法，用以检测潜在的支持向量。本文提出一种边界检测技术，用以减少原支持向量机的训练集规模。在数字图像处理，边缘检测是一种减少的数据量和过滤掉无用信息技术，同时保留了重要的结构特性。这种方法也可以应用于缩减数据的过程中。因此，边缘检测技术可以引入到快速发展的SV

5、M训练算法中用以保持分类边界附近的支持向量稳定。聚类精度并不重要，因此本文采用K-means聚类算法。重建后的训练集由边缘点和聚类中心组成。两个参数用来调整边缘检测的精度和聚类数据。由于该方法关注于聚类边缘的样本，支持向量被极大的减少了。本文的其余部分安排如下：下一节提供了一个介绍SVM分类器。然后，第3节边缘检测方法的基础上介绍了训练SVM过程中减少训练集。第4节提出了一个模拟实验，并给出实验结论。在最后一节给出总结。2SVMSVM在许多实际应用，特别是在分类问题在显示其突出的能力。SVM的基本设计理念是最大化分类边界。支持向量机的基本目的是最大化分类超平面

6、。由于现实应用中，许多问题都不是线性可分的，因此对于一个非线性可分问题，应该将其映射为线性可分问题。首先，将输入的向量映射到高维特征空间中，通过求解二次规划问题找到最优分类超平面，因此这个算法的空间复杂度最少是O(n2)二元分类是最简单的分类模型，任何复杂的分类模型都建立在二维空间分类的基础上，所以我们首先分析二分类问题。假定我们有一个分类训练集，用{Xi,Yi}表示。训练集被分类A.B两个分类类别，其对应的分类标签为+1，-1。两个边界类之间的距离被定义为分类边界。很显然，最大化分类边界可以优化分类器的分类能力。在训练数据是不可分的情况下，我们应该尽量减少分

7、离的错误，同时最大化分类边缘。只有在分类边界上的决定分类最有超平面的样本才被称作支持向量。支持向量的数目越小，训练分类器所需要的二次规划的运算次数也越小，因此训练分类器的计算时间消耗越小。3SVM的问题由于支持向量机需要求解多次二次规划问题，训练时间复杂度和空间复杂度分别为O(n3)和O(n2),其中n表示训练样本的数目。因此，减少整个训练集的大小可以有效的提高训练效率。由于支持向量机的训练集中，有效的样本只有支持向量，因此在训练分类器之前，提取支持向量可以有效的提高训练分类器的时间和空间效率。然而，抽样减少训练数据集会影响分类器的性能。在支持向量机中，分类边

8、界是由支持向量决定的。为了保证分类效率