我们知道，简单贝叶斯是可以应用于文本分类的算法，该算法将文本文档看做是词汇空间里的向量。而SVM分类算法是将每个文档看做是成千上万个特征组成的向量。在机器学习领域，海量文档上做文本分类面临很大的挑战。怎样在如此大的数据上训练分类器呢？如果能将算法分成并行的子任务，那么MapReduce框架有望帮我们实现这一点。SMO算法一次优化两个支持向量，并在整个数据集上迭代，在需要注意的值上停止。该算法看上去并不容易并行化。

在MapReduce框架上使用SVM的一般方法

(1)收集数据：数据按文本格式存放。

(2)准备数据：输入数据已经是可用的格式，所以不需任何准备工作。如果你需要解析一个大规模的数据集，建议使用map作业来完成，从而达到并行处理的目的。

(3)分析数据：无。

(4)训练算法：与普通的SVM一样，在分类器训练上仍需花费大量的时间。

(5)测试算法：在二维空间上可视化之后，观察超平面，判断算法是否有效。

(6)使用算法：本例不会展示一个完整的应用，但会展示如何在大数据集上训练SVM。该算法其中一个应用场景就是文本分类，通常在文本分类里可能有大量的文档和成千上万的特征。

SMO算法的一个替代品是Pegasos算法，后者可以很容易地写成MapReduce的形式。此文将分析Pegasos算法，介绍如何写出分布式版本的Pegasos算法，最后在mrjob中运行该算法。

1. Pegasos算法

Pegasos是指原始估计梯度求解器（Primal Estimated sub-GrAdient Solver)。该算法使用某种形式的随机梯度下降方法来解决SVM所定义的优化问题，研究表明该算法所需的迭代次数取决于用户所期望的精确度而不是数据集的大小，有关细节可以参考原文。原文有长文和短文两个版本，推荐阅读长文。

SVM算法的目的是找到一个分类超平面。在二维情况下也就是要找到一条直线，将两类数据分隔开来。Pegasos算法工作流程是：从训练集中随机挑选一些样本点添加到待处理列表中，之后按序判断每个样本点是否被正确分类；如果是则忽略，如果不是则将其加入到待更新集合。批处理完毕后，权重向量按照这些错分的样本进行更新。整个算法循环执行。

上述算法伪代码如下：

将w初始化为0

对每次批处理

      随机选择k个样本点（向量)

     对每个向量

            如果该向量被错分：

                 更新权重向量w

      累加对w的更新

为了解实际效果，Pythong版本的实现见程序清单1。

程序清单1 SVM的Pegasos算法

程序清单1 的代码是Pegasos算法的串行版本。输入值T和k分别设定了迭代次数和待处理列表的大小。在T次迭代过程中，每次需要重新计算eta。它是学习率，代表了权重调整幅度的大小。在外循环中，需要选择另一批样本进行下一次批处理；在内循环中执行批处理，将分类错误的值全部累加之后更新权重向量。