基于MapReduce的非线性支持向量机分类算法研究

摘要

支持向量机（SupportVectorMachine，SVM）算法是数据挖掘及机器学习领域中健壮性和稳定性较好的高精度算法，能够非常成功地处理分类和回归问题。然而，非线性SVM分类算法是一个计算密集型算法，仅适用于小样本统计学习问题。面对当今实际问题中的大数据集，本文旨在保持非线性SVM算法分类精度的基础上提高其处理能力及运行效率。
　　在对标准SVM算法及MapReduce编程模型进行深入分析的基础上，本文进行了如下研究工作并取得了一定的成果。
　　首先，为了提高串行非线性SVM算法的数据处理能力及运行效率，提出了基于MapReduce的并行SVM(MR-SVM)算法。通过均匀划分数据集，在各数据分片上利用map任务并行求解支持向量集SVs，而后联合各分布式训练结果利用一个reduce任务执行SVM重训练得出SVM分类器。其中联合重训练使得算法能自动收敛。
　　其次，为了弥补MR-SVM算法中分布式训练带来的精度损失，提出了基于MapReduce的并行迭代SVM(MR-C-SVM)算法。引入了迭代计算机制，通过反馈循环训练直至算法收敛于全局最优解。迭代过程中利用KKT条件筛选数据集的操作减少了重复计算。
　　再次，为了满足在线学习的需求及克服集群存储容量无法满足需求的难题，在MR-SVM算法和MR-C-SVM算法的基础上，提出了基于MapReduce的并行增量迭代SVM(MR-Ⅱ-SVM)算法。
　　此外，对MapReduce进行了支持迭代的扩展及针对MR-C-SVM算法的改进。
　　最后，在理论上证明了MR-C-SVM算法收敛于全局最优解。对MR-(Ⅱ)-SVM算法的各项流水线性能指标进行了计算分析。基于SpamBase数据集及MINIST数据集的实验表明，MR-C-SVM算法在保持标准SVM算法精度的同时提高了数据处理能力及运行效率，并超过了其它基于MapReduce的并行SVM算法的精度;MR-(Ⅱ)-SVM算法在加速比和运行效率方面比同类高精度算法具有明显优势。

目录

声明

摘要

1 绪论

1．1 研究背景和意义

1．2 研究现状

1．3 主要工作

1．4 论文的组织结构

2 背景知识

2．1 支持向量机

2．1．1 最大边缘超平面

2．1．2 线性支持向量机算法

2．1．3 非线性支持向量机分类算法

2．2 MapReduce编程模式

2．3 Hadoop平台

3 基于MapReduce的非线性支持向量机分类算法

3．1 MR-SVM算法分析与设计

3．1．1 并行策略

3．1．2 分布式训练与联合重训练

3．2 MR-C-SVM算法分析与设计

3．2．1 非线性SVM分类算法迭代执行的原理

3．2．2 迭代循环机制

3．2．3 MR-C-SVM算法数据处理模型

3．2．4 MR-C-SVM算法描述

3．3 MR-Ⅱ-SVM算法分析与设计

3．3．1 MR-Ⅱ-SVM的增量学习方法

3．3．2 MR-Ⅱ-SVM算法数据处理模型

3．4 MapReduce编程模式的扩展

3．4．1 支持迭代的扩展

3．4．2 针对MR-C-SVM的扩展

3．5 本章小结

4 收敛性证明与性能分析

4．1 MR-C-SVM算法的收敛性证明

4．2 MR-Ⅱ-SVM算法性能分析

4．3 本章小结

5 实验与结果分析

5．1 实验环境配置

5．2 数据集描述

5．3 MR-C-SVM算法实验与分析

5．3．1 MR-C-SVM算法的运行效率实验分析

5．3．2 MR-C-SVM算法的精度实验分析

5．4 MR-Ⅱ-SVM算法实验与分析

5．4．1 MR-Ⅱ-SVM算法的精度实验分析

5．4．2 MR-Ⅱ-SVM算法的加速比及运行效率实验分析

5．5 本章小结

6 总结与展望

6．1 论文工作总结

6．2 未来工作展望

参考文献

致谢

攻读硕士学位期间发表的学术论文与研究成果