我們知道，簡單貝葉斯是可以應用于文本分類的算法，該算法將文本文檔看做是詞匯空間里的向量。而SVM分類算法是將每個文檔看做是成千上萬個特征組成的向量。在機器學習領域，海量文檔上做文本分類面臨很大的挑戰(zhàn)。怎樣在如此大的數(shù)據(jù)上訓練分類器呢？如果能將算法分成并行的子任務，那么MapReduce框架有望幫我們實現(xiàn)這一點。SMO算法一次優(yōu)化兩個支持向量，并在整個數(shù)據(jù)集上迭代，在需要注意的值上停止。該算法看上去并不容易并行化。

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

(1)收集數(shù)據(jù)：數(shù)據(jù)按文本格式存放。

(2)準備數(shù)據(jù)：輸入數(shù)據(jù)已經(jīng)是可用的格式，所以不需任何準備工作。如果你需要解析一個大規(guī)模的數(shù)據(jù)集，建議使用map作業(yè)來完成，從而達到并行處理的目的。

(3)分析數(shù)據(jù)：無。

(4)訓練算法：與普通的SVM一樣，在分類器訓練上仍需花費大量的時間。

(5)測試算法：在二維空間上可視化之后，觀察超平面，判斷算法是否有效。

(6)使用算法：本例不會展示一個完整的應用，但會展示如何在大數(shù)據(jù)集上訓練SVM。該算法其中一個應用場景就是文本分類，通常在文本分類里可能有大量的文檔和成千上萬的特征。

SMO算法的一個替代品是Pegasos算法，后者可以很容易地寫成MapReduce的形式。此文將分析Pegasos算法，介紹如何寫出分布式版本的Pegasos算法，最后在mrjob中運行該算法。

1. Pegasos算法

Pegasos是指原始估計梯度求解器（Primal Estimated sub-GrAdient Solver)。該算法使用某種形式的隨機梯度下降方法來解決SVM所定義的優(yōu)化問題，研究表明該算法所需的迭代次數(shù)取決于用戶所期望的精確度而不是數(shù)據(jù)集的大小，有關細節(jié)可以參考原文。原文有長文和短文兩個版本，推薦閱讀長文。

SVM算法的目的是找到一個分類超平面。在二維情況下也就是要找到一條直線，將兩類數(shù)據(jù)分隔開來。Pegasos算法工作流程是：從訓練集中隨機挑選一些樣本點添加到待處理列表中，之后按序判斷每個樣本點是否被正確分類；如果是則忽略，如果不是則將其加入到待更新集合。批處理完畢后，權重向量按照這些錯分的樣本進行更新。整個算法循環(huán)執(zhí)行。

上述算法偽代碼如下：

將w初始化為0

對每次批處理

      隨機選擇k個樣本點（向量)

     對每個向量

            如果該向量被錯分：

                 更新權重向量w

      累加對w的更新

為了解實際效果，Pythong版本的實現(xiàn)見程序清單1。

程序清單1 SVM的Pegasos算法

程序清單1 的代碼是Pegasos算法的串行版本。輸入值T和k分別設定了迭代次數(shù)和待處理列表的大小。在T次迭代過程中，每次需要重新計算eta。它是學習率，代表了權重調(diào)整幅度的大小。在外循環(huán)中，需要選擇另一批樣本進行下一次批處理；在內(nèi)循環(huán)中執(zhí)行批處理，將分類錯誤的值全部累加之后更新權重向量。