SMO算法內容提要線性可分支持向量機線性不可分支持向量機支持向量機回歸實現策略多分類報告內容SVM簡介求解算法-SMO優化算法多分類問題系統演示SeparatingSurface:A+A-SVM算法特點SVM有如下主要幾個特點：(1)非線性映射是SVM方法的理論基礎,SVM利用內積核函數代替向高維空間的非線性映射；(2)對特征空間劃分的最優超平面是SVM的目標,最大化分類邊際的思想是SVM方法的核心；(3)支持向量是SVM的訓練結果,在SVM分類決策中起決定作用的是支持向量。因此，模型需要存儲空間小，算法魯棒性強；(4)無序任何前提假設，不涉及概率測度；(1)SVM算法對大規模訓練樣本難以實施由于SVM是借助二次規劃來求解支持向量，而求解二次規劃將涉及m階矩陣的計算（m為樣本的個數），當m數目很大時該矩陣的存儲和計算將耗費大量的機器內存和運算時間。針對以上問題的主要改進有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、張學工的CSVM以及O.L.Mangasarian等的SOR算法(2)用SVM解決多分類問題存在困難經典的支持向量機算法只給出了二類分類的算法，而在數據挖掘的實際應用中，一般要解決多類的分類問題?？梢酝ㄟ^多個二類支持向量機的組合來解決。主要有一對多組合模式、一對一組合模式和SVM決策樹；再就是通過構造多個分類器的組合來解決。主要原理是克服SVM固有的缺點，結合其他算法的優勢，解決多類問題的分類精度。如：與粗集理論結合，形成一種優勢互補的多類問題的組合分類器。問題提出線性可分的分類問題：（令黑色的點=-1，白色的點=+1）所以當有一個新的點x需要預測屬于哪個分類的時候，我們用sgn(f(x))，就可以預測了，sgn表示符號函數，當f(x)>0的時候，sgn(f(x))=+1,當f(x)<0的時候sgn(f(x))=–1。+1-1我們怎樣才能取得一個最優的劃分直線f(x)呢？最大距離MaximumMarginal選擇使得間隙最大的函數作為分割平面是由很多道理的，比如說從概率的角度上來說，就是使得置信度最小的點置信度最大（聽起來很拗口），從實踐的角度來說，這樣的效果非常好，等等。最大距離f(x)=wx+b=0wx+b=1wx+b=-1(x,y)M目標函數：等價于：因為單調，并且為了計算方便：求解問題數據集合：優化目標：x，y為已知數求解建立拉格朗日公式：求偏導數：求解：對偶問題求解將兩式帶回L(w,b,a)得到對偶問題的表達式求解問題數據集合：優化目標：x，y為已知數核函數線性不可分的情況我們可以為分錯的點加上一點懲罰，對一個分錯的點的懲罰函數就是這個點到其正確位置的距離：軟間隔C-SVMC是一個由用戶去指定的系數，表示對分錯的點加入多少的懲罰，當C很大的時候，分錯的點就會更少，但是過擬合的情況可能會比較嚴重，當C很小的時候，分錯的點可能會很多，不過可能由此得到的模型也會不太正確軟支持向量機求解構造拉格朗日公式：求偏導數：求解問題數據集合：優化目標：其中C為人為設定，x，y為已知數問題？實際上在處理大型問題時，由于存儲和計算兩方面的要求，這些算法往往會失效。這些算法都要存儲與訓練集相應的核矩陣，然而存儲核矩陣所需要的內存是隨著訓練集中訓練點數L的平凡增長的。例如，當訓練點數目超過4000時，存儲核函數矩陣需要多達128兆。求解方法：坐標上升法固定除之外的所有參數，這時W可看作只是關于的函數，那么直接對求導優化即可?？梢酝ㄟ^更改優化順序來使W能夠更快地增加并收斂。如果W在內循環中能夠很快地達到最優，那么坐標上升法會是一個很高效的求極值方法。問題？固定以外的所有參數，那么將不再是變量（可以由其他值推出），因為問題中規定了因此，我們最少一次需要選取兩個參數做優化，比如

和，此時可以由和其他參數表示出來。=>SMO算法SMO算法由MicrosoftResearch的JohnC.Platt在1998年提出，并成為最快的二次規劃優化算法，特別針對線性SVM和數據稀疏時性能更優。第一步選取一對參數，選取方法使用啟發式方法（Maximalviolatingpair）。第二步，固定除被選取的參數之外的其他參數，確定W極值。SMO算法設我們選取了初始值滿足了問題中的約束條件。接下來，我們固定其余參數，這樣W就是和的函數。并且和滿足條件：由于其余參數都是已知固定，因此為了方便，可將等式右邊標記成實數值。SMO算法進而其中：目標函數：求偏導：帶入w,v：求得：參數的求解最終參數的解為：其中：和？a的取值范圍當a1和a2異號時，也就是一個為1，一個為-1時，他們可以表示成一條直線，斜率為1。如下圖：橫軸是

，縱軸是

，

和

既要在矩形方框內，也要在直線上，因此同理，當和同號時a2a1CCa1-a2=E(0,-E)(C,C-E){{參數求解參數計算：參數b計算：？b的求解設在界內，則有，帶入上式得：兩邊同乘以，得b的求解在界內，則在界內，則、都在界內，則情況1和情況2的B值相等，任取一個；都不在界內，則取值為情況1和情況2之間的任意值。問題？算法如何終止？對于SMO算法，其中的兩個參數如何選擇呢？隨機？啟發式規則一個自然的想法是那些違反KKT最嚴重的點，他們對間距貢獻最大，因此可以通過該啟發規則來完成調整參數的選取。（并且此種啟發規則