机器学习之手把手实现第1部分:支持向量机的原理和实现
https://www.ibm.com/developerworks/cn/analytics/library/machine-learning-hands-on1-svn/index.html
本文將介紹機器學習領域經典的支持向量機 SVM 模型，它利用了軟間隔最大化、拉格朗日對偶、凸優化、核函數、序列最小優化等方法。支持向量機既可以解決線性可分的分類問題，也可完美解決線性不可分問題。您將看到 SVM 的原理介紹、SVM 實現步驟和詳解、SVM 實現代碼以及用 SVM 解決實際的分類問題。通過閱讀本文，您會對 SVM 的原理了如指掌，并可以自己開發出 SVM 的實現代碼。
關于機器學習的簡介
機器學習是從大量數據中學習出特定規律的算法。其中提到的規律有很多種，比如分類、聚類、回歸、關聯分析等。
分類就是給定大量帶標簽的數據，計算出未知標簽樣本的標簽取值。如年齡 40 歲以上、工科、研究生以上學歷，這類人薪資水平是高收入；年齡 20-30 歲、文科、大專學歷，這類人的薪資水平是低收入；現有一位 23 歲大專文科人士，求該人的薪資水平是哪類？根據分類建模，就可以知道這個人的薪資水平很可能是低收入。
聚類是將大量不帶標簽的數據根據距離聚集成不同的簇，每一簇數據有共同的特征。如電信行業可以根據用戶的月長途電話分鐘數、上網時長、短信使用數、地理位置、月消費數，將所有用戶聚集成有典型特征的簇，聚集出的某簇特征可能是月長途電話分鐘數長、上網時間長、地理位置變化不大、月消費數目低，分析可得這類人極有可能是在校大學生，那么電信公司就可以針對這類特定人群制定有針對性的營銷策略。
回歸是根據特征值、目標變量擬合出特征值與目標變量之間的函數關系，可用來估計特征值對應的目標變量的可能取值。舉個簡單的例子，某市今年某 100 平米的房子價格是 80 萬，某 150 平米房子價格是 120 萬，那么某 200 平米的房子價格的取值就可能是 200*0.8=160 萬左右。
關聯分析是計算出大量數據之間的頻繁項集合。如超市訂單中有大量訂單同時包含啤酒與尿布，這其中的頻繁項就是啤酒和尿布，那么超市就可以針對這個規律對啤酒和尿布進行組合促銷活動。
分類算法主要包括 K 近鄰、決策樹、樸素貝葉斯、邏輯回歸、支持向量機、AdaBoost 等；聚類主要包括線性回歸、嶺回歸、lasso、樹回歸等；聚類主要包括 K-Means 以及它的各種變形算法；關聯分析主要包括 Apriori、FP-growth 等算法。
支持向量機即 support vector machine(簡稱 SVM)，是機器學習領域經典的分類算法。
關于 SVM 的簡介
支持向量是距離分類超平面近的那些點，SVM 的思想就是使得支持向量到分類超平面的間隔最大化。出發點很容易理解，距離分類超平面近的那些點到該超平面的間隔最大化代表了該超平面對兩類數據的區分度強，不容易出現錯分的情況。如圖 1 所示，支持向量到超平面 1 的間隔大于支持向量到超平面 2 的間隔，因此超平面 1 優于超平面 2。
圖 1. 兩個超平面示例
SVM 可以很好得解決二分類問題，對于多分類情況，就需要對模型進行改動。如 one-versus-rest 法，這種方法每次選擇一個類別作為正樣本，剩下其他類別作為負樣本，假設一共有 3 個類別，這樣相當于訓練出了 3 個不同的 SVM。然后將測試數據分別帶入 3 個 SVM 模型中，得到的 3 個結果中的最大值則為最終的分類結果。
支持向量到分類超平面的間隔最大化的思路很完美，按這種思路得到的模型理論上是準確度最高的一種模型。但是使用過 SVM 的朋友都知道，調用 SVM 算法的測試準確度并不一定都很高。這其中有很多原因，比如數據預處理的效果、訓練集的大小、特征值的選擇、參數設置以及核函數的選擇等因素。
任何模型都是優點與缺點并存的。
SVM 的優點是：
SVM 的缺點是：
圖 2. 線性不可分問題
SVM 基本原理
SVM 原理分為軟間隔最大化、拉格朗日對偶、最優化問題求解、核函數、序列最小優化?SMO?等部分。雖然這些名詞看起來很晦澀，但是深入探索后就會發現其中的思想并沒有那么復雜。
軟間隔最大化
SVM 的核心思路是最大化支持向量到分隔超平面的間隔。后面所有的推導都是以最大化此間隔為核心思想展開。一般的機器學習問題都是先得到模型的目標函數和約束條件，然后在約束條件下對目標函數求得最優解。因此，我們下面首先需要推導出 SVM 模型的目標函數和約束條件。
既然要最大化間隔，那么回顧下點 x 到超平面(w,b)的距離公式：
其中超平面的公式為：
由此可推出點 x 到超平面(w,b)的幾何間隔為：
其中 xi 代表第 i 條數據，yi 代表第 i 條數據對應的目標變量的取值，取值有+1 和-1 兩種。所以當第 i 條數據被正確分類時，y 取值和 w*x+b 取值的正負一致，幾何間隔為正；當被錯誤分類時，y 取值和 w*x+b 取值的正負相反，幾何間隔為負。
圖 3. 樣本數據關于 w*x+b 的取值符號
定義幾何間隔中最小的為：
由此，可以得到間隔最大化問題的目標函數：
并遵循如下約束條件：
做如下變換：
則目標函數轉換為：
相應的約束條件變為：
做如下變換：
可得目標函數和約束條件變為：
由于 w, b 成倍數變化并不會影響超平面的公式，所以：
此時得到最終的間隔最大化的目標函數和約束條件如下：
但是，到這里并沒有真正得結束。考慮到現實生活中的真實數據，存在一些特異點即 outliers，這些數據點并不滿足上面推導出的約束條件，如圖 4 所示，圖中點 A 就是 outlier 特異點。
圖 4. Outlier 特異點
為了解決這種問題，對每個樣本點引進一個松弛變量，使得約束條件變為：
這樣給 outlier 的約束條件加上一個變量，使其可以滿足大于等于 1 的條件。則相應的目標變量變為：
其中 C 為懲罰參數，它的目的是使得目標變量最小即幾何間隔最大，且使得松弛變量最小化。加入松弛變量的目標函數就是軟間隔最大化。
拉格朗日對偶
對于凸二次優化問題，通過引入拉格朗日乘子，將目標函數和約束條件整合到拉格朗日函數中，這樣能方便求解最值問題。那么，對每個不等式約束引入拉格朗日乘子，得到拉格朗日函數如下：
分析可知：
則原最優化問題轉換成：
由于原最優化問題直接求解很困難，利用拉格朗日對偶性，可通過求解原最優化問題的對偶問題得到原問題的最優解。原最優化問題的對偶問題為：
最優化問題求解
到此為止，已經將目標函數和約束條件轉換成了極大極小化拉格朗日函數的問題了。首先求解關于拉格朗日函數的極小化問題。
對三個變量分別求偏導得：
將以上三式帶入拉格朗日函數中得：
那么極大極小化拉格朗日函數轉換成：
為求解方便，將極大轉換成極小得：
核函數
對于線性不可分問題，如圖 2 所示，這類問題是無法用超平面劃分正負樣本數據的。倘若能將超平面換成超曲面，則可以將正負樣本正確分類，如圖 5 所示。
圖 5. 超曲面分離正負樣本
我們知道曲面的公式是：
映射到新坐標如下：
可將超曲面在新坐標下表示成超平面：
也就是將在二維空間(x1,x2)下線性不可分的問題轉換成了在五維空間(z1,z2,z3,z4,z5)下線性可分的問題。
得映射后新坐標下的內積：
有一核函數如下：
可知
何為核函數？核函數在低維空間中完成了映射到高維空間后的內積運算。這點非常有用，利用核函數，無需先將變量一一映射到高維空間再計算內積，而是簡單得在低維空間中利用核函數完成這一操作。為什么說不用一一映射到高維空間很有用呢？原因就在于首先我們無法針對每種情況提供精確的映射函數，再者對于需要映射到無窮維的情況顯然無法一一映射完成。
那么為什么是映射到高維后的內積運算呢？這是因為在上節中我們得到了如下目標函數：
正是因為該目標函數中包含自變量的內積運算，而映射到高維空間后的內積運算又恰好可以通過核函數在低維空間中直接求得，故而有了核函數的由來。較常用的核函數是高斯核，高斯核可以將低維空間映射到無窮維。
運用核函數后，最優化問題的目標函數和約束條件變為：
序列最小優化 (Sequential minimal optimization)
到目前為止，優化問題已經轉化成了一個包含 N 個 alpha 自變量的目標變量和兩個約束條件。由于目標變量中自變量 alpha 有 N 個，為了便與求解，每次選出一對自變量 alpha，然后求目標函數關于其中一個 alpha 的偏導，這樣就可以得到這一對 alpha 的新值。給這一對 alpha 賦上新值，然后不斷重復選出下一對 alpha 并執行上述操作，直到達到最大迭代數或沒有任何自變量 alpha 再發生變化為止，這就是 SMO 的基本思想。說直白些，SMO 就是在約束條件下對目標函數的優化求解算法。
為何不能每次只選一個自變量進行優化？那是因為只選一個自變量 alpha 的話，會違反第一個約束條件，即所有 alpha 和 y 值乘積的和等于 0。
下面是詳細的 SMO 過程。假設選出了兩個自變量分別是 alpha1 和 alpha2，除了這兩個自變量之外的其他自變量保持固定，則目標變量和約束條件轉化為：
將約束條件中的 alpha1 用 alpha2 表示，并代入目標函數中，則將目標函數轉化成只包含 alpha2 的目標函數，讓該目標函數對 alpha2 的偏導等于 0：
可求得 alpha2 未經修剪的值：
之所以說 alpha2 是未經修剪的值是因為所有 alpha 都必須滿足大于等于 0 且小于等于 C 的約束條件，用此約束條件將 alpha2 進行修剪，修剪過程如下：
由此得：
分兩種情況討論：
情況 1.當 y1 等于 y2 時，有：
情況 2.當 y1 不等于 y2 時，有：
修剪后，可得 alpha2 的取值如下：
由 alpha2 和 alpha1 的關系，可得：
在完成 alpha1 和 alpha2 的一輪更新后，需要同時更新 b 的值，當 alpha1 更新后的值滿足 0<alpha1<C 時，由 KKT 條件得：
由于篇幅有限，在此就不把推導過程一一列舉，可得：
同樣的道理，當 alpha2 更新后的值滿足 0<alpha1<C 時可得：
若更新后的 alpha1 和 alpha2 同時滿足大于 0 且小于 C 的條件，那么 b 就等于 b1 等于 b2;否則，b 取 b1 和 b2 的中點。
那么問題來了，如何選擇 alpha1 和 alpha2 呢？
選擇違背下列 KKT 條件推導結果的 alpha 作為 alpha1：
為了讓每次變化盡可能大，alpha2 的選擇滿足如下式子最大，即步長最大化：
其中 E 是上面提到過的預測值和真實值差值的絕對值，也就是誤差值。
按上述方法不斷選擇一對 alpha 并更新，直到達到最大迭代次數或所有 alpha 都不再變化，則停止迭代。有朋友就會問，求出 alpha 之后呢？如何判斷新樣本數據屬于 1 還是-1 呢？
別忘了，在最優化求解一節，我們得到了如下：
若 f(x)大于 0，則新樣本數據屬于 1；否則，新樣本數據屬于-1。
可以見得，求出 alpha 后，所有問題都迎刃而解了。
實現步驟: 自己動手實現 SVM
以上都為推導部分，實現代碼主要圍繞對目標函數的優化求解上，即序列最小優化算法部分。
清單 1. alpha1 選擇
| 1 2 3 4 5 6 | yI = diyObj.yMat[alphaI] EI = calcE(alphaI, diyObj) diyObj.E[alphaI] = [1, EI] # if alpha1 violates KKT if((yI * EI > diyObj.toler and diyObj.alphas[alphaI] > 0) or (yI * EI < - diyObj.toler and diyObj.alphas[alphaI] < diyObj.C)): |
選擇違背 KKT 條件推導結果的 alpha 作為 alpha1，本代碼中 diyObj.toler 取值為 0.0001。
清單 2. alpha2 選擇
| 1 2 3 4 5 6 7 8 | for j in nonzeroEIndex: if alphaI == j: continue EJtemp = calcE(j, diyObj) deltaE = abs(EI - EJtemp) if(deltaE > maxDelta): maxDelta = deltaE alphaJ = j EJ = EJtemp |
alpha2 的選擇遵循步長最大化，即 E 值與 alpha1 的 E 值相差最大的 alpha 選為 alpha2。
清單 3. alpha1,alpha2,b 求解
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | alpha1old = diyObj.alphas[alphaI].copy() alpha2old = diyObj.alphas[alphaJ].copy() eta = diyObj.K[alphaI,alphaI] + diyObj.K[alphaJ, alphaJ] - 2 * diyObj.K[alphaI, alphaJ] if eta <= 0: return 0 alpha2newUnclip = alpha2old + yJ * (EI - EJ) / eta if(yI == yJ): L = max(0, alpha1old + alpha2old - diyObj.C) H = min(diyObj.C, alpha1old + alpha2old) else: L = max(0, alpha2old - alpha1old) H = min(diyObj.C, diyObj.C - alpha1old + alpha2old) if L == H: return 0 alpha2new = clipAlpha(alpha2newUnclip, L, H) if abs(alpha2new - alpha2old) < 0.00001: return 0 alpha1new = alpha1old + yI * yJ * (alpha2old - alpha2new) b1new = - EI - yI * diyObj.K[alphaI,alphaI] * (alpha1new - alpha1old) \ - yJ * diyObj.K[alphaJ, alphaI] * (alpha2new - alpha2old) + diyObj.b b2new = - EJ - yI * diyObj.K[alphaI,alphaJ] * (alpha1new - alpha1old) \ - yJ * diyObj.K[alphaJ, alphaJ] * (alpha2new - alpha2old) + diyObj.b b = calcb(b1new, b2new) |
先算出 alpha 取值的上下界，求出 alpha2 后用上下界進行裁剪。用裁剪后的 alpha2 新值計算 alpha1 新值。b 的取值由 b1 和 b2 綜合決定。
清單 4. 核函數
| 1 2 3 4 5 6 7 8 9 10 | def transfer2Kernel(X, Xi, kernelParam): m = shape(X)[0] Ktemp = mat(zeros((m, 1))) if kernelParam[0]=="rbf": for i in range(m): xdelta = X[i,:] - Xi Ktemp[i] = xdelta * xdelta.T Ktemp = exp(-Ktemp/kernelParam[1]**2) else: raise NameError("undefined kernel name!") return Ktemp |
本代碼中使用高斯核完成從低維到高維的映射。
代碼下載 (code downloads)
本文所有 SVM 實現代碼可在文末下載。
本文數據集簡介
圖 6. 數據集樣例
數據集是獻血中心關于某人是否在 2007 年三月獻血的數據。前四列分別代表距離上次獻血的月份數、總獻血次數、總獻血毫升數、距離第一次獻血的月份數。最后一列代表是否在 2007 年三月獻血，1 代表是，-1 代表否。本數據集共 748 條。
應用示例: 應用實現的 SVM 解決實際問題
清單 5. 用 SVM 解決實際問題
| 1 2 3 4 5 6 7 8 9 10 11 | dataMat,yMat = loadDataset("bloodTransfusion.txt") alphas,b = smo(dataMat, yMat, 200, 0.0001,100, ("rbf",20)) #yi of testData: 1,1,1,-1,-1,-1,-1,1,1,-1 testData = [[2,50,12500,98],[0,13,3250,28],[1,16,4000,35],[1,24,6000,77],[4,4,1000,4] ?,[1,12,3000,35],[4,23,5750,58],[2,7,1750,14],[2,10,2500,28],[1,13,3250,47]] m, n = shape(testData) testmat = mat(testData) for i in range(m): kernelEval = transfer2Kernel(mat(dataMat), testmat[i,:],("rbf",20)) predict = kernelEval.T * multiply(mat(yMat).transpose(), alphas) + b print(sign(predict)) |
用 bloodTransfusion 數據集訓練 SVM 模型，得到該模型的 alpha 矩陣和 b 值。然后將 10 條測試數據輸入模型中，輸出結果為 10 條測試數據對應的預測值。
表 1. 應用本文實現的 SVM 對 10 條數據進行預測的結果示例
| [2,50,12500,98] | 1 | 1 |
| [0,13,3250,28] | 1 | 1 |
| [1,16,4000,35] | -1 | 1 |
| [1,24,6000,77] | -1 | -1 |
| [4,4,1000,4] | -1 | -1 |
| [1,12,3000,35] | -1 | -1 |
| [4,23,5750,58] | -1 | -1 |
| [2,7,1750,14] | -1 | 1 |
| [2,10,2500,28] | 1 | 1 |
| [1,13,3250,47] | -1 | -1 |
從表中可以看出，8 條數據分類正確，2 條數據分類有誤。要想提高模型準確度，可以修改模型參數如最大迭代數、C 懲罰系數、高斯核參數等。
總結
本文首先介紹了機器學習的體系框架，接著詳細深入地講解了 SVM 的基本原理，分別為軟間隔最大化、拉格朗日對偶、最優化問題求解、核函數和序列最小優化等。通過代碼樣例，介紹了在自己動手實現 SVM 模型時的思路。最后，用獻血中心的數據展示了如何應用 SVM 解決實際問題。本文的內容不算高深，讀者如果能靜下心來細讀，將會有很大收獲。如若文中有紕漏的地方，歡迎廣大讀者留言指正，也很期待在接下來的機器學習系列文章中繼續和志同道合的讀者相遇。
參考資源
本文用到的參考文獻如下：
- 參考李航著《統計學習方法》，了解 SVM 基本原理。
- 參考 Peter Harrington 著《機器學習實戰》，了解 SVM 代碼框架。
- 參考周志華著《機器學習》，了解 SVM 基本思路。
- http://archive.ics.uci.edu/ml/datasets/Blood+Transfusion+Service+Center，本文所用數據集網址。
轉載于:https://www.cnblogs.com/davidwang456/articles/8926969.html
總結
以上是生活随笔為你收集整理的机器学习之手把手实现第1部分:支持向量机的原理和实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 利用反射给JAVABEAN实例赋值
- 下一篇： 机器学习之手把手实现，第 2 部分 频