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

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

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

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

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

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

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

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

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

1. Pegasos算法

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

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

上述算法偽代碼如下：

將w初始化為0

對每次批處理

      隨機(jī)選擇k個樣本點(diǎn)（向量)

     對每個向量

            如果該向量被錯分：

                 更新權(quán)重向量w

      累加對w的更新

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

程序清單1 SVM的Pegasos算法

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