论文部分内容阅读
摘 要：支持向量机算法是一种基于结构风险最小化原则上，尽量提高学习机的泛化能力，在处理小样本、非线性及高维模式识别问题有许多优势，但在解决大规模数据时，训练速度会变得缓慢，影响训练的效果。所以，本文在原有支持向量机实现方式上，利用类似级联方式，增加算法处理的数据规模，并且基于云计算平台，利用Map/Reduce机制实现算法过程，加快算法的训练速度。
关键词：支持向量机；并行实现；Hadoop；Map/Reduce
中图分类号：TP18
在统计学理论的基础上，发展出来的机器学习方法——支持向量机（Support Vector Machine，SVM）。支持向量机算法是基于结构风险最小化原则上，尽量提高学习机的泛化能力，具有良好的推广性能和较好的分类精确性。
近年来，人们越来越多的将目光集中在支持向量机的可扩展性上，也提出了很多关于支持向量机的并行算法，主要是通过将数据集分割为小的数据模块，对每个小的数据模块进行支持向量机训练，通过多次迭代形式，形成级联式SVM实现并行处理样本数据，或者是通过多线程处理，得到训练模型。这些方法充分利用现阶段硬件的一些新特性，在不同程度上提高了支持向量机的性能。但是，通过这种方式并行处理数据来提高训练速度，由于计算步骤地设计和在每个小的数据子集训练状态的不同，导致再想进一步提高算法效率明显是比较难的。解决这一问题，一种有效的方式，就是利用云计算平台集群的优势，提高算法运算效率，加快算法运算时间。
1 PSVM算法
1.1 SVM简介
支持向量机是一种二类分类模型。SVM学习的基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面，等价于构造并求解最优化问题求得最优解，由此得到分离超平面。在线性可分的情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量（support vector）。支持向量是约束条件式成立的点，即：对的正例点，支持向量在超平面上，对的负例点，支持向量机在超平面上。
1.2 SMO
快速学习算法-序列最小最优化算法（sequential minimal optimization， SMO），是一种启发式算法，其基本思想是，如果所有变量的解都满足此最优化问题的KKT条件，那么这个最优化问题的解就得到了。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划的问题。SMO算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的。
2 PSVM实现过程
2.1 PSVM方法
本文中并行支持向量机算法是基于云计算平台实现的。根据Hadoop平台Map/Reduce实现机制的特点，采用类似级联SVM的方法对训练数据进行处理。PSVM实现方式是：（1）首先将训练数据分割成子集（依照级联方式逐次减少），对每个子集分别进行独立训练，得到支持向量。（2）对运行过程进行判断，如果没有结束，则对得到的支持向量结合后，再进行分块处理，进行操作（1）；否则，训练结束，则进行操作（3）。（3）训练结束，将训练得到的训练模型输出。在训练过程中，尽可能早地消除非支持向量来加速支持向量机过程。
下图以三层级联支持向量机训练过程为例，说明算法的实现过程。
3 实验结果
3.1 实验环境
3.2 实验数据
3.3 实验结果
实验使用的数据是libsvm的自带数据集，heart_scale数据集。
4 结束语
针对SVM对大规模训练样本存在的训练速度缓慢的问题，提出了基于Hadoop的Map reduce机制进行SVM训练，通过Map将训练样本分块，再在Reduce中进行SVM训练，输出支持向量，通过迭代的过程完成SVM训练过程。并行支持向量机增加了训练样本的大小，以及加快了训练时间，对于大数据的处理有很好的效果。
参考文献：
[1]NelloCristianini，JohnShawe Taylor，著.李国正，王猛，曾华军，译.支持向量机导论[M].北京：电子上业出版社，2004.
[2]Tomwhite，著，曾大耽，周傲英，译.Hadoop权威指南[M].北京：清华大学出版社，2010.
[3]邓乃杨，田英杰，著.数据挖掘中的新方法——支持向量机[M].北京：科学出版社，2004.
[4]Hans Peter Graf，Eric Cosatto，Leon Bottou. Parallel Support Vector Machines：The Cascade SVM，2005.
作者单位：北京邮电大学计算机学院，北京 100876
关键词：支持向量机；并行实现；Hadoop；Map/Reduce
中图分类号：TP18
在统计学理论的基础上，发展出来的机器学习方法——支持向量机（Support Vector Machine，SVM）。支持向量机算法是基于结构风险最小化原则上，尽量提高学习机的泛化能力，具有良好的推广性能和较好的分类精确性。
近年来，人们越来越多的将目光集中在支持向量机的可扩展性上，也提出了很多关于支持向量机的并行算法，主要是通过将数据集分割为小的数据模块，对每个小的数据模块进行支持向量机训练，通过多次迭代形式，形成级联式SVM实现并行处理样本数据，或者是通过多线程处理，得到训练模型。这些方法充分利用现阶段硬件的一些新特性，在不同程度上提高了支持向量机的性能。但是，通过这种方式并行处理数据来提高训练速度，由于计算步骤地设计和在每个小的数据子集训练状态的不同，导致再想进一步提高算法效率明显是比较难的。解决这一问题，一种有效的方式，就是利用云计算平台集群的优势，提高算法运算效率，加快算法运算时间。
1 PSVM算法
1.1 SVM简介
支持向量机是一种二类分类模型。SVM学习的基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面，等价于构造并求解最优化问题求得最优解，由此得到分离超平面。在线性可分的情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量（support vector）。支持向量是约束条件式成立的点，即：对的正例点，支持向量在超平面上，对的负例点，支持向量机在超平面上。
1.2 SMO
快速学习算法-序列最小最优化算法（sequential minimal optimization， SMO），是一种启发式算法，其基本思想是，如果所有变量的解都满足此最优化问题的KKT条件，那么这个最优化问题的解就得到了。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划的问题。SMO算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的。
2 PSVM实现过程
2.1 PSVM方法
本文中并行支持向量机算法是基于云计算平台实现的。根据Hadoop平台Map/Reduce实现机制的特点，采用类似级联SVM的方法对训练数据进行处理。PSVM实现方式是：（1）首先将训练数据分割成子集（依照级联方式逐次减少），对每个子集分别进行独立训练，得到支持向量。（2）对运行过程进行判断，如果没有结束，则对得到的支持向量结合后，再进行分块处理，进行操作（1）；否则，训练结束，则进行操作（3）。（3）训练结束，将训练得到的训练模型输出。在训练过程中，尽可能早地消除非支持向量来加速支持向量机过程。
下图以三层级联支持向量机训练过程为例，说明算法的实现过程。
3 实验结果
3.1 实验环境
3.2 实验数据
3.3 实验结果
实验使用的数据是libsvm的自带数据集，heart_scale数据集。
4 结束语
针对SVM对大规模训练样本存在的训练速度缓慢的问题，提出了基于Hadoop的Map reduce机制进行SVM训练，通过Map将训练样本分块，再在Reduce中进行SVM训练，输出支持向量，通过迭代的过程完成SVM训练过程。并行支持向量机增加了训练样本的大小，以及加快了训练时间，对于大数据的处理有很好的效果。
参考文献：
[1]NelloCristianini，JohnShawe Taylor，著.李国正，王猛，曾华军，译.支持向量机导论[M].北京：电子上业出版社，2004.
[2]Tomwhite，著，曾大耽，周傲英，译.Hadoop权威指南[M].北京：清华大学出版社，2010.
[3]邓乃杨，田英杰，著.数据挖掘中的新方法——支持向量机[M].北京：科学出版社，2004.
[4]Hans Peter Graf，Eric Cosatto，Leon Bottou. Parallel Support Vector Machines：The Cascade SVM，2005.
作者单位：北京邮电大学计算机学院，北京 100876