機器學習經典算法詳解及Python實現--基于SMO的SVM分類器

jopen 10年前發布 | 116K 次閱讀 Python 算法

支持向量機基本上是最好的有監督學習算法，因其英文名為support vector machine，簡稱SVM。通俗來講，它是一種二類分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，其學習策略便是間隔最大化，最終可轉化為一個凸二次規劃問題的求解。

（一）理解SVM基本原理

1，SVM的本質--分類

給定一些數據點，它們分別屬于兩個不同的類，現在要找到一個線性分類器把這些數據分成兩類--這就是最基本的線性可分。如果用x表示數據點、用y表示類別（y可以取1或者-1，分別代表兩個不同的類），線性分類器的學習目標便是要在n維的數據空間中找到一個分界使得數據可以分成兩類，分界方程可以表示為（此處w^T中的T代表轉置，x是一個數據點（有m個屬性的行向量），w也是一個大小為m的行向量，b是一個常數）：

在二維平面上，上述分界就是一條直線，如下圖將黑點和白點分開的線。三維平面上分界就會是一個平面，而更高維平面上就會是其他的分界表現形式，因此將這個分界稱為超平面（hyper plane）。

圖1

再次重申，我們假設統計樣本的分布式是均勻分布的，如此在兩分類分類中（類別-1或者1）可以將閾值設為0。實際訓練數據中，樣本往往是不均衡的，需要算法來選擇最優閾值（如ROC曲線）。

因此SVM分類器就是學習出一個分類函數，當f(x) 等于0的時候，x便是位于超平面上的點，而f(x)大于0的點對應 y=1 的數據點，f(x)小于0的點對應y=-1的點。換言之，在進行分類的時候，將新的數據點x代入f(x) 中，如果f(x)小于0則將x的類別賦為-1，如果f(x)大于0則將x的類別賦為1，f(x)=0就沒法分了。

下面以二維平面為例闡明SVM的原理。不難發現能夠實現分類的超平面（二維平面上就是一條直線）會有很多條，如下圖2所示，如何確定哪個是最優超平面呢？直觀而言，最優超平面應該是最適合分開兩類數據的直線。而判定“最適合”的標準就是這條直線距直線兩邊最近數據的間隔最大，也就是“使樣本中離超平面最近的點到超平面的距離最遠”--最大間隔。所以，得尋找有著“最大間隔”的超平面。下面的問題是--如何求“最大間隔”？

圖2

2，根據幾何間隔計算“最大間隔”

2.1 函數間隔

對任何一個數據點(x,y)，|w^T*x+b|能夠表示點x到距離超平面w^T*x+b=0的遠近，而w^T*x+b的符號與類標記y的符號是否一致可判斷是否分類正確。所以，可用y(w^T*x+b)的正負性判定或表示分類的正確性（為正才正確），引出了函數間隔（functional margin）的概念。定義函數間隔為：

而超平面所有樣本點(xi，yi)的函數間隔最小值便為超平面關于訓練數據集的函數間隔： mini (i=1，...n)

實際上，函數間隔就是幾何上點到面的距離公式。

2.2 幾何間隔

假定對于一個點 x ，令其垂直投影到超平面上的對應點為 x0 ，w 是垂直于超平面的一個向量，為樣本x到分類間隔的距離，如下圖所示：

有，||w||=w^T*w，是w的二階泛數。

又由于 x₀是超平面上的點，滿足 f(x₀)=0 ，代入超平面的方程即可算出：

數據點到超平面的幾何間隔定義為：

而超平面所有樣本點(xi，yi)的幾何間隔最小值便為超平面關于訓練數據集的函數間隔： min (i=1，...n)

幾何間隔就是函數間隔除以||w||，可以理解成函數間隔的歸一化。

2.3 定義最大間隔分類器Maximum Margin Classifier

前面已經提到，超平面離數據點的“間隔”越大，分類的確信度（confidence）也越大，為使分類的確信度盡量高，需要選擇能最大化這個“間隔”值的超平面，而這個間隔就是最大間隔。

函數間隔不適合用來衡量最大化間隔值，因為超平面固定后通過等比例縮放w的長度和b的值可使任意大。但幾何間隔除了，縮放w和b的時其值是不會改變的。所以幾何間隔只隨著超平面的變動而變動，最大間隔分類超平面中的“間隔”用幾何間隔來衡量。于是最大間隔分類器（maximum margin classifier）的目標函數可以定義為：

（i=1,2,...,n）,

根據前面分析過的，“使樣本中離超平面最近的點到超平面的距離最遠”，轉化成數學表達式就變為條件：

根據前面的討論：即使在超平面固定的情況下，的值也可以隨著 ∥w∥的變化而變化。為了簡化計算，不妨將固定為1（實質上就相當于式子兩邊同除以，則有w^T=w^T‘=w^T/,b=b'=b/），于是最大間隔分類器目標函數演化為為：

式中，s.t.是subject to的意思，它導出的是約束條件。

由于求的最大值相當于求（之所以這么轉化是為了求解方便，系數1/2和平方都是后面為了利用導數求最值方便，并無實質上的含義）的最小值，所以上述目標函數等價于（w由分母變成分子，從而也有原來的max問題變為min問題，很明顯，兩者問題等價）：

3，支持向量(Support Vector)的定義

SVM叫做支持向量機,討論了這么久,何謂'支持向量'尚未明了.從下圖3可以看到兩個支撐著中間的間隙的超平面，它們到中間分離超平面的距離(即我們所能得到的最大幾何間隔max()相等)，而“支撐”這兩個超平面的必定會有一些點，而這些“支撐”的點便叫做支持向量。

很顯然，由于這些支持向量(x,y)剛好在邊界上，所以它們滿足（前面，函數間隔固定為1）；而對于所有不是支持向量的點，也就是在“陣地后方”的點，則顯然有y(w^Tx + b) > 1。事實上，當最優的超平面確定下來之后，這些后方的點就不會對超平面產生任何影響。SVM這樣的特性一個最直接的好處就在于存儲和計算上的優越性-只需要存儲和計算少量的支持向量點即可完成對新數據的分類判斷。例如，如果使用 100 萬個點求出一個最優的超平面，其中是 supporting vector 的有 100 個，那么我只需要記住這 100 個點的信息即可，對于后續分類也只需要利用這 100 個點而不是全部 100 萬個點來做計算。當然，通常除了k 近鄰之類的“Memory-based Learning”算法，通常算法也都不會直接把所有的點用來做后續推斷中的計算。

4，容錯松弛因子Outlier

上述SVM超平面的構造過程中并未考慮數據有噪音（即偏離正常位置很遠的數據點）的情況，這些點稱之為 outlier。在原來的SVM 模型里，超平面本身就是只有少數幾個 support vector 組成的，outlier 的存在有可能造成很大的影響，如果這些 support vector 里又存在outlier的話，其影響就很大了。

上圖中用黑圈圈起來的那個藍點是一個 outlier ，它偏離了自己原本所應該在的那個半空間，如果直接忽略掉它的話，原來的分隔超平面還是挺好的，但是由于這個 outlier 的出現，導致分隔超平面不得不被擠歪了，變成途中黑色虛線所示（這只是一個示意圖，并沒有嚴格計算精確坐標），同時 margin 也相應變小了。當然，更嚴重的情況是，如果這個 outlier 再往右上移動一些距離的話，我們將無法構造出能將數據分開的超平面來。

為了處理這種情況，SVM 允許數據點在一定程度上偏離一下超平面。例如上圖中，黑色實線所對應的距離，就是該 outlier 偏離的距離，如果把它移動回來，就剛好落在原來的超平面上，而不會使得超平面發生變形了。加入松弛因子后，目標函數變為：

其中稱為松弛變量 (slack variable) ，對應數據點xi允許偏離的 functional margin 的量。當然，如果我們允許任意大的話，那任意的超平面都是符合條件的了。所以，我們在原來的目標函數后面加上一項，使得這些的總和也要最小：

其中是一個參數，用于控制目標函數中兩項（“尋找 margin 最大的超平面”和“保證數據點偏差量最小”）之間的權重。是需要優化的變量（之一），而是一個事先確定好的常量。

（二）SVM的求解

1，求解過程概述

經過第一節的討論，我們已經明確SVM的目的就是找到一組向量w和常量b，構成一個超平面，學習出一個分類函數，在進行分類的時候，將新的數據點x代入f(x) 中，如果f(x)小于0則將x的類別賦為-1，如果f(x)大于0則將x的類別賦為1，f(x)=0就沒法分了。SVM的求解就是要求出向量w和常量b，而求解過程通過轉換成拉格朗日函數，最終可以轉化成下述目標函數，可以利用求解對偶問題的序列最小最優化 SMO算法計算出拉格朗日因子，再計算出w和b。詳細的數學推導過程這里就不再累述了，這里只在前人的基礎上給出更為直觀的求解表達式。

目標函數中取值為：

，u_i=f(x_i)即為根據當前的w,b組合計算得出的第i個統計樣本的估計值

從中也可以看出支持向量之外的數據點其=0，即在最終分類函數中沒有意義。

= T(alpha*T(Y)) * X

b在SMO求解迭代過程中逐步更新得出。

因此分類函數為：

采取矩陣表示即為f(x)= T(X*T(x)) * (alpha(叉乘)T(Y) ) +b，其中參與運算的alpha（m，1）、Y（m，1）、X(m,n)均為矩陣,X表示m個統計樣本，每個統計樣本有n個屬性，x(1,n)表示待估計分類的新數據項。*為矩陣乘法，T()表示矩陣轉置，<x_i,x>表示內積。

2，SMO算法

SMO算法的具體推導過程請參考材料’SMO算法推導一節‘。

經過一系列的推導，目標函數的問題最終變為：在上求下述目標函數的最小值。

為了求解這些乘子，每次從中任意抽取兩個乘子a1和a2，然后固定其它乘子，使得目標函數只是關于a1和a2的函數。這樣，不斷的從一堆乘子中任意抽取兩個求解，不斷的迭代求解子問題，最終達到求解原問題的目的。迭代的停止條件是a2基本沒有改變或者總的迭代次數達到了迭代次數上限。

為了解決這個子問題，首要問題便是每次如何選取a1和a2。實際上，其中一個乘子是選取違法KKT條件最嚴重的，另外一個乘子則由另一個約束條件選取。的初始值均為0，因此迭代開始時的第一對乘子是隨機選擇的。所以，選擇乘子a1和a2就是采取啟發式搜索方法結合下述約束條件進行。

對于a1

，即第一個乘子，可以通過剛剛說的那3種不滿足KKT的條件來找；

（i）<=1但是<C則是不滿足的，而原本=C

(ii)>=1但是>0則是不滿足的，而原本=0

(iii)=1但是=0或者=C則表明不滿足的，而原本應該是0<<C

</li>

而對于第二個乘子

a2可以尋找滿足條件：

的乘子。（E_k=u_k-y_k，是根據當前

組合估算的第k個樣本的u_k與實際的分類y_k間的差值。

啟發式選擇方法主要思想是每次選擇拉格朗日乘子的時候，優先選擇樣本前面系數的 ai作優化（論文中稱為無界樣例），因為在界上（ai為0或C）的樣例對應的系數ai一般不會更改。啟發式搜索方法是選擇第一個拉格朗日乘子用的，比如前面的a2。那么這樣選擇的話，是否最后會收斂。可幸的是Osuna定理告訴我們只要選擇出來的兩個ai中有一個違背了KKT條件，那么目標函數在一步迭代后值會減小。違背KKT條件不代表，在界上也有可能會違背。是的，因此循環的算法是：

（i）在給定初始值ai=0后，先對所有樣例進行循環，循環中碰到違背KKT條件的（不管界上還是界內）都進行迭代更新。

（ii）第二輪開始就優先針對的樣例進行迭代更新，直至此類樣例沒有ai更新則進入（iii）。

（iii）再次對所有樣例進行循環一次后再次進入（ii）

（v）循環（ii）（iii）直至迭代終止（達到最大迭代次數或沒有ai得到更新）

最后的收斂條件是在界內（）的樣例都能夠遵循KKT條件，且其對應的ai只在極小的范圍內變動。

此外，更新的同時還要受到第二個約束條件的限制，即sum(ai*yi) = 0。

因此，如果假設選擇的兩個乘子a1和a2，它們在更新之前分別是、，更新之后分別是、，那么更新前后的值需要滿足以下等式才能保證和為0的約束：

其中，是常數。

兩個因子不好同時求解，所以可先求第二個乘子a2的解（），再用其表示a1的解（）。

第一步，求解的取值范圍

為了求解，得先確定的取值范圍，因為乘子都需要滿足的條件。因此需要根據乘子a1和a2來計算的上下界。假設它的上下邊界分別為H和L，那么有：

接下來，綜合和這兩個約束條件，求取的取值范圍。

根據y1和y2同號或異號，可得出的上下界分別為：

第二步，求解

利用y_ia_i+y_ja_j=常數，消去a_i，可得到一個關于單變量a_j的一個凸二次規劃問題，可得關于單變量的解析解（尚未考慮邊界條件）：

（表示預測值與真實值之差），（若為0則中止此次循環）

然后考慮約束可得到的最終解為：

第三步，求解

根據，便可以求出，得（此處不需要再根據邊界條件修剪）

第四步，更新b

b在滿足下述條件下更新：（Note：這里有一個疑問，經過裁剪后的必然是在邊界內的，所以：（a）第三種情況根本不會發生；（b）第一種和第二種的順序是否故意這么安排以確定b1優先級較高？）

且每次更新完兩個乘子a1\a2的優化后，都需要再重新計算b，及對應的Ei值。

另外，、還可以這么獲得：

然后考慮約束0<=a_j<=C可得到：

對于

這里、與前面的不同之處在于是沒有裁剪，是裁剪了，b的更新也要又有變化。這與前述方法本質上是一致的。

最后一步，獲得分類函數

最后迭代完成后，更新所有ai、y和b，就可以得到分類函數：

（三）核函數Kernel Function

前面討論的都是線性可分的情況，對于線性不可分的情況就必須采取某種手段使得數據點在另外一個維度（這個維度不一定都能夠直觀的視覺展示）變為可線性分類的。這種手段就是核函數。

用’機器學習中的算法(2)-支持向量機(SVM)基礎‘提到的來說：世界上本來沒有兩個完全一樣的物體，對于所有的兩個物體，我們可以通過增加維度來讓他們最終有所區別，當維度增加到無限維的時候，一定可以讓任意的兩個物體可分了。比如說兩本書，從(顏色，內容)兩個維度來說，可能是一樣的，我們可以加上作者這個維度，還不行就加入類型、成書年代、擁有者、購買地點等等，最終必然可以將兩本書區分開來。

在線性不可分的情況下，支持向量機首先在低維空間中完成計算，然后通過核函數將輸入空間映射到高維特征空間，最終在高維特征空間中構造出最優分離超平面，從而把平面上本身不好分的非線性數據分開。如下圖，左邊的一堆數據在二維空間無法劃分，右邊映射到三維空間里則可以劃分：

核函數能簡化映射空間中的內積運算—— SVM 里需要計算的地方數據向量總是以內積的形式出現的。對比剛才我們寫出來的式子，現在我們的分類函數為：

=T(k(X, x))*(alpha(叉乘)T(Y) ) +b

其中 a 由如下目標函數計算而得：

這樣一來計算的問題就算解決了，避開了直接在高維空間中進行計算，而結果卻是等價的。

實際應用中，根據問題和數據的不同，選擇不同的參數核函數中選擇。核的選擇對于支持向量機至關重要，這是一個不斷嘗試、優化選擇的過程。常用到的核函數有：

1，多項式核，該空間的維度是，其中 m是原始空間的維度。

2，高斯核，將原始空間映射為無窮維空間，是使用最廣泛的核函數之一。由于這個函數類似于高斯分布，因此稱為高斯核函數，也叫做徑向基函數(Radial Basis Function 簡稱RBF)。通過調控參數，高斯核實際上具有相當高的靈活性，下圖所示的例子便是把低維線性不可分的數據通過高斯核函數映射到了高維空間：

3，線性核=x₁*T(x₂)，實際上就是原始空間中的內積。這可以理解為是為了內積計算的統一而“占位”用的。代碼實現時不用再區分線性、非線性，對于線性的分類代入該核函數即可。

（四）SMO算法SVM分類器的python實現

SVM分類器Python學習包包括三個.py文件，svm/object_json /testsvm.py。其中svm.py實現SVM分類器，testsvm.py包含兩個測試用例。因為訓練過程耗時較長，object_json.py中則是通過自定義的json編碼函數將分類器對象永久保存，以后使用時只需要load分類器文件即可，除非需要更新分類器。

包中SVM分類器定義了兩個對象svmTrain和svmClassifer，前者根據訓練數據，通過SMO算法產生一個SVM分類器；后者則僅是一個SVM分類器，包括由svmTrain產生的支持向量、支持向量set和get函數，分類器永久保存支持函數等。

SVM分類器軟件包全部源文件和測試文件的下載地址是：

TBD

（五）SVM分類的應用

1，手寫識別

svm分類器包中的digits.rar是一個手寫識別測試用例，感興趣的話可以自己訓練svm分類器測試識別效果。

2，文本分類

文本分類與SVM

3，多分類簡介

基本的SVM分類器解決的2分類的問題，N分類的情況下有多種方式，這里介紹1vs(N–1)和1v1。更多的SVM多分類應用介紹，參考’SVM多類分類方法‘

前一種方法我們需要訓練N個分類器，第i個分類器是判斷新的數據屬于分類i還是屬于其補集（除去i的N-1個分類）。后一種方式我們需要訓練N * (N – 1) / 2個分類器，分類器(i,j)能夠判斷某個點是屬于i還是屬于j，當對一個未知樣本進行分類時，每個分類器都對其類別進行判斷．并為相應的類別“投上一票”，最后得票最多的類別即作為該未知樣本的類別。這種處理方式不僅在SVM中會用到，在很多其他的分類中也是被廣泛用到，從林教授（libsvm的作者）的結論來看，1vs1的方式要優于1vs(N–1)。