论文部分内容阅读
支持向量机(Support Vector Machine,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-II-SVM)算法。此外,对MapReduce进行了支持迭代的扩展及针对MR-C-SVM算法的改进。最后,在理论上证明了MR-C-SVM算法收敛于全局最优解。对MR-II-SVM算法的各项流水线性能指标进行了计算分析。基于SpamBase数据集及MINIST数据集的实验表明,MR-C-SVM算法在保持标准SVM算法精度的同时提高了数据处理能力及运行效率,并超过了其它基于MapReduce的并行SVM算法的精度;MR-II-SVM算法在加速比和运行效率方面比同类高精度算法具有明显优势。