论文部分内容阅读
分类问题是机器学习的主要研究内容,支持向量机(Support Vector Machine,SVM)作为主流的分类方法之一,在软件模块缺陷检测、图像识别等领域取得了广泛的应用,倍受研究者的关注。然而,经典的串行SVM主要针对小规模数据,面对大规模数据存在效率低的不足。为此,设计适用于大规模海量数据的并行SVM算法成了关键任务。目前,经典的并行SVM的研究主要集中在数据层面,即在原始数据集的多个子数据集上并行训练支持向量机,进而通过合并得到最终分类结果。相对于面向数据层面的并行SVM而言,在求解算法上进行并行化的SVM还不多见,且在SVM模型中考虑类分布信息的研究工作也比较少。为此,本文在MapReduce模型框架下,对支持向量机的次梯度投影算法(Pegasos)的并行化进行了深入的研究,并在软件模块缺陷数据集上进行有效地实验验证。论文的主要工作如下：1.提出了并行SVM的随机次梯度投影算法(PPegasos)。PPegasos算法将SVM随机次梯度投影算法中的求次梯度和投影的步骤进行并行,并运用基于MapReduce并行框架的云计算平台Hadoop进行了算法的实现。在软件模块缺陷数据集CM1和PC1上对PPegasos算法进行了实验验证。实验表明,PPegasos算法是有效可行的,适用于面向大规模数据的分类。2.提出了并行结构化SVM的随机次梯度投影算法(PSPegasos)。PSPegasos算法将样本的结构信息融入到SVM随机次梯度投影算法中,在MapReduce框架下进行了并行化实现。该算法中分别考虑了整体、类和聚类三种不同粒度下的样本的结构信息。在软件模块缺陷数据集CM1和PC1上对PSPegasos算法进行了实验验证。实验表明,结构化信息的嵌入使寻找到的最终分类超平面会更加符合数据的分布方向,有效提高分类器的预测精度。3.提出了一种基于聚类的欠抽样的并行结构化SVM随机次梯度投影集成算法(EPSPegasos)。EPSPegasos算法主要针对软件模块缺陷检测这一类不平衡问题而设计的。基于聚类的欠抽样,一定程度上保留了样本的分布信息,克服欠采样所造成的信息的丢失,可防止过抽样带来的样本规模过大问题。借助MapReduce并行框架,训练多个基分类器,集成得到最终的分类结果。在软件模块缺陷数据集CM1和PC1上对EPSPegasos算法进行了实验验证。实验表明,EPSPegasos算法能够获得比单个分类器更好的分类效果。