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

大数据集的快速 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 SVMSVM 在许多实际应用，特别是在分类问题在显示其突出的能力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 均值聚类算法获得聚类中心这些聚类中心也将被包保留下来，用于重新构建一个小规模训练集在模拟实验阶段，我们将本文提出算法同。