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

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

Boyang LI, Qiangwei WANG and Jinglu HU

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

引言

支持向量机是运用核方法的成功范例。许多核方法的公式中需要用到多次求解二次规划的问题。如果训练集的样本数目为n,那么求解二次规划问题的时间复杂度为O(n3)，并且空间复杂度最少为O(n2)。因此对于训练支持向量机，最主要的问题就是如何减少计算的时间复杂度和空间复杂度。

为了减少支持向量机的时间和空间复杂度，许多改进算法得到了成功的应用，其中一种方法是通过贪心算法获得核矩阵的低阶近似值[1]，或者样本[2],或者矩阵的分解。然而分解后的核矩阵的维数依然很高，导致支持向量机的训练效率依然非常低下。

另外一种方法提高支持向量机的效率是分块算法。然而分块需要优化整个非零拉格朗日乘法器，但其产生的核矩阵仍然可能太大了，导致内存出现溢出状况。

第三种方法是避免二次规划问题，如中心支持向量机算法[5]，规模化的方法[6]，拉格朗日支持向量机算法（LSVM）[7]。这类算法对于线性具有非常好的性能，然而，对于非线性核，但它仍然需要大量的矩阵运算。

另外一种算法是在训练支持向量机之前减少训练集规模。本文将深入讨论这种更加直观并且从根本上解决问题的方法。Pavlov[8]和Collobert[9] 等人提出了利用那个改进的基于神经网络的阈值选择方法用以减少支持向量的规模。Lee和Mangasarian[10]等人提出了RSVM算法，RSVM利用随机获取的一个训练集的子集，用以代替原训练集。

这种方法的基本问题是如何检测训练集中不相关的样本。这一类算法都可以减少训练集的规模，但是仍然有许多与分类不相关的非支持向量被保留，这样严重的限制了训练SVM分类器的效率。

因此需要提出一种更加行之有效的相关样本保留算法，用以检测潜在的支持向量。本文提出一种边界检测技术，用以减少原支持向量机的训练集规模。在数字图像处理，边缘检测是一种减少的数据量和过滤掉无用信息技术，同时保留了重要的结构特性。这种方法也可以应用于缩减数据的过程中。因此，边缘检测技术可以引入到快速发展的SVM训练算法中用以保持分类边界附近的支持向量稳定。聚类精度并不重要，因此本文采用K-means聚类算法。重建后的训练集由边缘点和聚类中心组成。两个参数用来调整边缘检测的精度和聚类数据。由于该方法关注于聚类边缘的样本，支持向量被极大的减少了。

本文的其余部分安排如下：下一节提供了一个介绍SVM分类器。然后，第3节边缘检测方法的基础上 介绍了训练SVM过程中减少训练集。第4节提出了一个模拟实验，并给出实验结论。在最后一节给出总结。

2 SVM

SVM在许多实际应用，特别是在分类问题在显示其突出的能力。SVM的基本设计理念是最大化分类边界。支持向量机的基本目的是最大化分类超平面。由于现实应用中，许多问题都不是线性可分的，因此对于一个非线性可分问题，应该将其映射为线性可分问题。首先，将输入的向量映射到高维特征空间中，通过求解二次规划问题找到最优分类超平面，因此这个算法的空间复杂度最少是O(n2)

二元分类是最简单的分类模型，任何复杂的分类模型都建立在二维空间分类的基础上，所以我们首先

分析二分类问题。假定我们有一个分类训练集，用{Xi, Yi}表示。 训练集被分类A.B两个分类类别，其对应的分类标签为+1，-1。两个边界类之间的距离被定义为分类边界。很显然，最大化分类边界可以优化分类器的分类能力。在训练数据是不可分的情况下，我们应该尽量减少分离的错误，同时最大化分类边缘。只有在分类边界上的决定分类最有超平面的样本才被称作支持向量。支持向量的数目越小，训练分类器所需要的二次规划的运算次数也越小，因此训练分类器的计算时间消耗越小。 3 SVM

的问题

由于支持向量机需要求解多次二次规划问题，训练时间复杂度和空间复杂度分别为O(n3)和O(n2),其中n表示训练样本的数目。因此，减少整个训练集的大小可以有效的提高训练效率。由于支持向量机的训练集中，有效的样本只有支持向量，因此在训练分类器之前，提取支持向量可以有效的提高训练分类器的时间和空间效率。

然而，抽样减少训练数据集会影响分类器的性能。在支持向量机中，分类边界是由支持向量决定的。为了保证分类效率，应该有效的保存那些最有可能成为支持向量的样本。

假设，整个数据集可以作为一个图像表示，每个类都有一个特定的颜色，然后分类决策面可以被认为在图像边缘。根据SVM理论，在分类边界附近的样本，成为支持向量的可能性更高。因此，接近决策边界的样本更有可能在检测点附近的边缘。

4 通过边界检测技术减小分类边界规模

边界检测技术是在模式识别和图像处理领域中广泛应用的一种技术。边界点监测在图像处理中是一种最根本的问题。同样，查找决策边界的样本在文本分类领域中同样非常重要。这些在边界的样本更有可能是支持向量，因此在压缩支持向量机的训练集的过程中，应该要保留这些样本。

在图像处理过程中，图像处理的目标在于在到图像中亮度变化非常大的点。在图像处理中，边缘检测技术的目的是确定在数字图像，图像亮度的急剧变化或更正式有间断点。边缘强度强对比（在强度跳转到下一个像素）[18]等领域。边缘检测大大减少了数据量，并保留重要的属性。

在分类问题，我们的目的是检测不同类别之间的急剧变化，捕捉周围边界的重要样本。边缘检测中的分类问题比在图像处理中简单。在图像亮度不连续的边缘检测可能面对如下问题：深入的连续性，在表面方向的连续性，在材料的正确关系的变化，并在场景照明的变化。然而，在分类问题，我们只需要考虑类标号的变化。

一个典型的边缘可能是例如块的红色和黄色块之间的边界。在图像处理中，我们需要扫描一个像素的相邻像素的亮度和色彩检测的急剧变化。在我们的边界点监测模型中，这个规则被简化成找到m个最近邻点。如图1所示，假设存在5个最近邻点，对于某个给定点p，如果它的一个边界点与其标号不同，那么这个点将被认为潜在的支持向量，将被保留。

在这种情况下，我们采用边界点监测技术去查找边界点，得到的缩小的数据集，将由最优分类超平面附近的样本组成。而远离分类边界的样本点将被删除。因此训练集的样本数目将大大减少，那些被过滤掉的样本点是那些基本不含有分类信息的，而那别被保留的样本点反映了这个数据的分布结构，尤其是反映了分类超平面信息。由于支持向量分布在分类超平面附近，通过边界检测技术而保留的样本点基本包含了支持向量，进而不至于影响分类效果。

有时候，仅仅用分类超平面附近的样本训练支持向量机将导致过学习现象。也就是说，仅仅采用边界检测得到的样本不能有效的反映原训练集的分布状况，严重影响分类器的分类精度。因此，我们需要利用聚类技术，对原训练集进行聚类，并保留聚类中心，加入压缩的训练集。K均值算法是一种将一个训练集聚类成k组数据的聚类算法。这种聚类算法通过计算样本点到聚类中心的距离来进行聚类.

本文算法通过边界检测技术和K均值聚类算法重新构建训练集，通过压缩原训练集的大小，达到减少训练时间的目的。算法主要包括下面4个步骤：

步骤1：确定最近邻数目m

步骤2：通过边界检测技术，查找训练集的边界点

（1） 查找某个样本点的m个最近邻居。

（2） 检查最近邻居的样本类别，如果和该样本点属于同一个类别，那么这个样本点将被删

除，如果不是属于同一个类别，这个样本点将被保存

步骤3：确定K均值聚类的K值，并且对整个训练集进行K均值聚类。

步骤4：重建训练集。利用K均值聚类得到的聚类中心和通过边界检测得到的样本重建训练集。 从图2中可以看出，本文提出方法减小了数据集规模，让提高了支持向量机效率。

5 模拟实验

首先，我们的实验是在4X4的方格数据，这种数据经常用于衡量大规模训练集的支持向量机。原始的训练集和测试集都是随机产生的。我们分别采用1000个训练集进行训练和1000测试集对支持向量机进行测试。支持向量机所用的参数都是缺省的数据。因为我们需要用到非线性核函数，因此我们采用RBF作为核函数。在本文中，我们采用SVM-KM的工具箱（Matlab自带的工具箱）。

在实验中，传统的支持向量机方法也将被采用，用以比较本文提出的新的方法。训练数据集和训练结果在图3中将被展示出来。图3（a）是原始数据，图3（b）是采用本文给出方法重构的数据集，图3（c）是测试数据和分类边界。图3（d）重构数据的分类边界。从图3（c）和图3（d）我们可以看出，本文所给出的方法基本上维持了相同的分类边界。

不同大小规模的原始训练数据在图4中可以看到。从图中可以看出，本文提出的支持向量机的训练集的重构方法在分类精度和传统支持向量机的分类精度基本一致。另外，本文给出的方法的支持向量的数据和传统支持向量机产生的支持向量的数据基本差不多。但是由于去除了冗余的远离分类超平面的样本，本文给出的算法具有更少的训练样本数据，更快的训练时间。特别应该指出的是，如果最近邻样本的的数目选得太少，支持向量机的分类精度会降低。因此，在这个训练集之中，最近邻样本数据是8. 实际数据集

我们同样从UCI数据集中提取显示生活中的数据进行模拟实验。Iris数据集和forest数据集用于测试我们提出的方法。

Irish数据集手机了3种150个irish花朵，这个数据集有3个参数。75个样本被用于训练支持向量机分类器，而剩余的75个训练集用于测试。在比较实验中，我们用RTS的快速支持向量机和本文提出的支持向量方法进行对比。表1是一个实验IRIS的实验结构。表格的第一行显示本文的提出方法在精度方面和传统支持向量机差不多。剩下的几行比较了RTS支持向量机和本文提出支持向量机算法的各项性能指标。第一列显示了分类的成功率，第二列显示了保留支持向量的数目。换而言之，就是训练集的大小规模。最后一列显示了整个训练支持向量机的训练时间消耗。在本文提出的方法中，训练消耗时间包括压缩训练集的时间和训练支持向量机的时间。从表1可以看出，本文提出算法在各项指标上均优于传统的支持向量机和IRIS方法。同时，本文提出算法在分类器的分类精度方面优于其他两种算法。

另外，我们在一个非常大的训练数据集forest上测试了我们的分类器，这个训练集包含100000个训练样本，这些样本被分为两组，一组是训练集，而另外一组是测试集。1.2.5类被用于分类。分类结果可以在表3中看到。对于大数据集，本文提出的快速SVM训练，用本文提出的边界检测方法依旧取得了最好的效果，不管是在分类精度还是在分类时间方面。另外，用于构建压缩数据集的时间比训练支持向量机的时间消耗要大许多。然而，对于真个训练时间，本文提出的方法，比经典SVM和RTS 快速支持向量机要好。

5结论

本文提出了一种改进的SVM算法，用于克服支持向量机难以有效训练大规模训练集的问题。在支持向量机理论中，支持向量是接近分类超平面的样本。因此，本文提出了一种边界检测技术，用于检测分类超平面的边界，用于进一步压缩数据集，保留那些最有可能是支持向量的样本。为了更好的描述原样

本集的分布状况，本文提出了利用K均值聚类算法获得聚类中心。这些聚类中心也将被包保留下来，用于重新构建一个小规模训练集。在模拟实验阶段，我们将本文提出算法同传统的支持向量机，RTS快速支持向量机进行比较。从结论图表中，在分类成功率，训练集规模和计算时间消耗方面，本文提出算法均有更为优越的表现。

本文来源：https://www.bwwdw.com/article/2xd6.html