支持向量機的演算法及應用

Ⅰ 支持向量機（SVM）

        支持向量機（support vector machine），故一般簡稱SVM，通俗來講，它是一種二分類模型，其基本模型定義為特徵空間上的間隔最大的線性分類器，這族分類器的特點是他們能夠同時最小化經驗誤差與最大化幾何邊緣區，因此支持向量機也被稱為最大邊緣區分類器。其學習策略便是間隔最大化，最終可轉化為一個凸二次規劃問題的求解。SVM在很多諸如文本分類，圖像分類，生物序列分析和生物數據挖掘，手寫字元識別等領域有很多的應用。

        支持向量機將向量映射到一個更高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數據的超平面的兩邊建有兩個互相平行的超平面，分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。

        假設給定一些分屬於兩類的2維點，這些點可以通過直線分割， 我們要找到一條最優的分割線，如何來界定一個超平面是不是最優的呢?

        如圖：

        在上面的圖中，a和b都可以作為分類超平面，但最優超平面只有一個，最優分類平面使間隔最大化。 那是不是某條直線比其他的更加合適呢? 我們可以憑直覺來定義一條評價直線好壞的標准:

        距離樣本太近的直線不是最優的，因為這樣的直線對雜訊敏感度高，泛化性較差。 因此我們的目標是找到一條直線（圖中的最優超平面），離所有點的距離最遠。 由此， SVM演算法的實質是找出一個能夠將某個值最大化的超平面，這個值就是超平面離所有訓練樣本的最小距離。這個最小距離用SVM術語來說叫做間隔(margin) 。

        描述：給定一些數據點，它們分別屬於兩個不同的類，現在要找到一個線性分類器把這些數據分成兩類。如果用x表示數據點，用y表示類別（y可以取1或者-1，分別代表兩個不同的類），一個線性分類器的學習目標便是要在n維的數據空間中找到一個超平面（hyper plane），這個超平面的方程可以表示為（ wT中的T代表轉置）：

        例如：現在有一個二維平面，平面上有兩種不同的數據，分別用圈和叉表示。由於這些數據是線性可分的，所以可以用一條直線將這兩類數據分開，這條直線就相當於一個超平面，超平面一邊的數據點所對應的y全是-1 ，另一邊所對應的y全是1。

        我們令分類函數為：

        當f(x) 等於0的時候，x便是位於超平面上的點，而f(x)大於0的點對應 y=1 的數據點，f(x)小於0的點對應y=-1的點，如下圖所示：

        一個點距離超平面的遠近可以表示分類預測的確信或准確程度，如何確定這個超平面呢？從直觀上而言，這個超平面應該是最適合分開兩類數據的直線。而判定「最適合」的標准就是這條直線離直線兩邊的數據的間隔最大。所以，得尋找有著最大間隔的超平面。

補充知識點： 點到平面的距離

        支持向量機學習的基本想法是求解能夠正確劃分訓練數據集並且幾何間隔最大的分離超平面.。對線性可分的訓練數據集而言，線性可分分離超平面有無窮多個(等價於感知機)，但是幾何間隔最大的分離超平面是唯一的。這里的間隔最大化又稱為硬間隔最大化。

        間隔最大化的直觀解釋是:對訓練數據集找到幾何間隔最大的超平面意味著以充分大的確信度對訓練數據進行分類。也就是說，不僅將正負實例點分開，而且對最難分的實例點(離超平面最近的點)也有足夠大的確信度將它們分開。這樣的超平面應該對未知的新實例有很好的分類預測能力。

      按照我們前面的分析，對一個數據點進行分類， 當它的margin越大的時候，分類的confidence越大。 對於一個包含n個點的數據集，我們可以很自然地定義它的margin為所有這n個點的margin值中最小的那個。於是，為了使得分類的confidence高，我們希望所選擇的超平面hyper plane能夠最大化這個margin值。讓所選擇的超平面能夠最大化這個「間隔」值，這個間隔就是下圖中的Gap的一半：

為什麼用幾何間隔求最大的分離超平面而不用函數間隔？

例題：

我們構造了約束最優化問題，就是下面這個：

        此外，由於這個問題的特殊結構，還可以通過拉格朗日對偶性（Lagrange Duality）變換到對偶變數 (al variable) 的優化問題，即通過求解與原問題等價的對偶問題（al problem）得到原始問題的最優解，這就是線性可分條件下支持向量機的對偶演算法，這樣做的優點在於：一者對偶問題往往更容易求解；二者可以自然的引入核函數，進而推廣到非線性分類問題。

補充知識點： 拉格朗日乘子法學習

                     拉格朗日KKT條件

                     KKT條件介紹

                     拉格朗日對偶

         通過給每一個約束條件加上一個拉格朗日乘子（Lagrange multiplier）α，定義拉格朗日函數（通過拉格朗日函數將約束條件融合到目標函數里去，從而只用一個函數表達式便能清楚的表達出我們的問題）：

 求解這個式子的過程需要拉格朗日對偶性的相關知識。

例題：

         接下來談談線性不可分的情況，因為 線性可分這種假設實在是太有局限性 了。下圖就是一個典型的線性不可分的分類圖，我們沒有辦法用一條直線去將其分成兩個區域，每個區域只包含一種顏色的點。

         要想在這種情況下的分類器，有兩種方式， 一種是用曲線 去將其完全分開，曲線就是一種 非線性 的情況，跟之後將談到的 核函數 有一定的關系：

         另外一種還是用直線，不過不用去保證可分性 ，就是包容那些分錯的情況，不過我們得加入懲罰函數，使得點分錯的情況越合理越好。其實在很多時候，不是在訓練的時候分類函數越完美越好，因為訓練函數中有些數據本來就是雜訊，可能就是在人工加上分類標簽的時候加錯了，如果我們在訓練（學習）的時候把這些錯誤的點學習到了，那麼模型在下次碰到這些錯誤情況的時候就難免出錯了。這種學習的時候學到了「雜訊」的過程就是一個過擬合（over-fitting），這在機器學習中是一個大忌。

我們可以為分錯的點加上一點懲罰，對一個分錯的點的 懲罰函數 就是 這個點到其正確位置的距離：

        對於線性不可分的情況，我們可以用核函數讓空間從原本的線性空間變成一個更高維的空間 ， 在這個高維的線性空間下，再用一個超平面進行劃分 。 這兒舉個例子，來理解一下如何利用空間的維度變得更高來幫助我們分類的：

        上圖是一個線性不可分的圖，當我們把這兩個類似於橢圓形的點映射到一個高維空間後，映射函數為：

        用這個函數可以將上圖的平面中的點映射到一個三維空間（z1,z2,z3)，並且對映射後的坐標加以旋轉之後就可以得到一個線性可分的點集了。

        形象說明：例如世界上本來沒有兩個完全一樣的物體，對於所有的兩個物體，我們可以通過增加維度來讓他們最終有所區別，比如說兩本書，從(顏色，內容)兩個維度來說，可能是一樣的，我們可以加上作者這個維度，是在不行我們還可以加入頁碼，可以加入擁有者，可以加入購買地點，可以加入筆記內容等等。當維度增加到無限維的時候，一定可以讓任意的兩個物體可分了。

核函數定義：

核技巧在支持向量機中的應用：

常用核函數：

非線性支持向量機學習演算法：

        支持向量機的學習問題可以形式化為求解凸二次規劃問題。這樣的凸二次規劃問題具有全局最優解，並且有許多最優化演算法可以用於這一一問題的求解。但是當訓練樣本容量很大時，這些演算法往往變得非常低效，以致無法使用。所以，如何高效地實現支持向量機學習就成為一一個重要的問題。目前人們已提出許多快速實現演算法.本節講述其中的序列最小最優化(sequential minimal optimization, SMO)演算法。

        上述問題是要求解N個參數(α1,α2,α3,...,αN)，其他參數均為已知，序列最小最優化演算法(SMO)可以高效的求解上述SVM問題，它把原始求解N個參數二次規劃問題分解成很多個子二次規劃問題分別求解，每個子問題只需要求解2個參數，方法類似於坐標上升，節省時間成本和降低了內存需求。每次啟發式選擇兩個變數進行優化，不斷循環，直到達到函數最優值。

        整個SMO演算法包括兩部分，求解兩個變數的 二次規劃 問題和選擇這兩個變數的 啟發式 方法。

 上面求得的(α1)new和(α2)new是在η>0的情況下求得的：

        當時為了推導公式我們直接默認它是大於0了，現在我們需要重新審視這一項（η）。這一項是原來關於的二次項的系數。我們可以分下面三種情況討論：

（1）當η>0時 ：這個二次函數開口向上，所以要求這個二次函數的最小值，如果說極值點不在計算出的可行域的范圍內，就要根據這個極值點和可行域邊界值的關系來得到取最小值的地方：

①如果這個極值點在可行域左邊，那麼我們可以得到這個可行域內二次函數一定在單增，所以此時L應該是那個取最小值的地方。就如大括弧的第三種情況。

②如果這個極值點在可行域右邊，那麼此時可行域內一定單減，所以此時H就是那個取最小值的地方，就是大括弧里的第一種情況。

（2）當η=0時： 這個二次函數就變成了一個一次函數，那麼不管這個一次函數的單調性怎樣，最小值一定是在邊界處取到。所以到時候計算可行域的兩個邊界的值，看哪個小就用哪個。

（3）當η<0時: 這個二次函數開口向下，那麼此時怎麼得到取最小值的點呢？很容易就能想到：最小值也是在可行域的邊界處取到。很容易理解，此時開口向下，當極值點在區間內時，最小值只能在端點處取，因為極值點處是最大的。而當極值點在區間外時，區間內一定是單調的，此時最小值也只能在端點處取。通過計算比較邊界處的目標函數值，哪個小取哪個。

通過以上判斷求出(α2)new以後，再根據公式求出(α1)new，然後帶入目標函數（1）中。即如下過程：

        上述分析是在從N個變數中已經選出兩個變數進行優化的方法，下面分析如何高效地選擇兩個變數進行優化，使得目標函數下降的最快。

Ⅱ 支持向量機的基本原理

支持向量機的主要思想是：建立一個最優決策超平面，使得該平面兩側距離該平面最近的兩類樣本之間的距離最大化，從而對分類問題提供良好的泛化能力。

對於一個多維的樣本集，系統隨機產生一個超平面並不斷移動，對樣本進行分類，直到訓練樣本中屬於不同類別的樣本點正好位於該超平面的兩側，滿足該條件的超平面可能有很多個，SVM正式在保證分類精度的同時，尋找到這樣一個超平面，使得超平面兩側的空白區域最大化。

支持向量機中的支持向量是指訓練樣本集中的某些訓練點，這些點最靠近分類決策面，是最難分類的數據點。SVM中最優分類標准就是這些點距離分類超平面的距離達到最大值；「機」是機器學習領域對一些演算法的統稱，常把演算法看做一個機器，或者學習函數。

SVM是一種有監督的學習方法，主要針對小樣本數據進行學習、分類和預測，類似的根據樣本進行學習的方法還有決策樹歸納演算法等。

支持向量機的應用實例

支持向量機是一種監督模式識別和機器學習方法，採用最大分類間隔准則實現有限訓練樣本情況下推廣能力的優化。

通過核函數間接實現非線性分類或函數回歸，支持向量機通常簡寫作SVM。

支持向量機使用鉸鏈損失函數計算經驗風險並在求解系統中加入了正則化項以優化結構風險，是一個具有稀疏性和穩健性的分類器。

支持向量機可以通過核方法進行非線性分類，是常見的核學習方法之一。

支持向量機在人像識別、文本分類等模式識別問題中有得到應用。

Ⅲ 支持向量機學習演算法

支持向量機學習演算法主要有以下五種：

（1）獲取學習樣本（xⁱ，yⁱ），i=1，2…，其中xⁱ∈Rⁿ，y∈任 ｛1，-1｝^l，對樣本進行預處理；

（2）選擇進行非線性變換的核函數及對錯分（誤差）進行懲罰的懲罰因子c；

（3）形成二次優化問題用優化方法（如：Chuknlng演算法、內點演算法、SMO演算法）；

（4）獲得a，a^*及b₀的值，代入方程中，獲得分類或函數擬合的支持向量機；

（5）將需預測或分類的數據代入支持向量機方程中獲得結果。

基坑降水環境影響評價參數選取降水方式、岩土性質、水文地質邊界、基坑側壁狀態、邊載分布、後續使用年限、基礎型式、差異沉降8級，目標輸出模式對應4個級別：優等級（Ⅰ）、良好級（Ⅱ）、中等級（Ⅲ）、差級（Ⅳ）。

用一對多多類支持向量機水質分類法：有四類等級要劃分，於是在抽取訓練集的時候，分別抽取I所對應的向量作為正集，其餘所對應的向量作為負集；Ⅱ所對應的向量作為正集，其餘所對應的向量作為負集……，這四個訓練集分別進行訓練得到四個分類器。然後，利用這四個訓練結果文件對測試集分別進行測試，最後每個測試都有一個結果，最終的結果便是這四個值中最大的一個。

利用支持向量機進行基坑降水環境影響評價就是尋找影響基坑降水環境系統和孕災環境系統的指標和基坑降水環境影響等級之間的關系，可建立以下四個分類函數：

基坑降水工程的環境效應與評價方法

Ⅳ 支持向量機

支持向量機(Suport Vector Machine,常簡稱為SVM），是一個監督式學習的方式。支持向量機屬於一般化線性分類器，這類分類器的特點是能夠同時最小化經驗誤差與最大化幾何邊緣區，因此支持向量機機也被稱為最大邊緣區分類器。

藍色和紅色的線圈出來的點就是所謂的支持向量，離分界線最近的點，如果去掉這些點，直線多半要改變位置。Classifier Boundary就是決策函數f(x)，在兩個類的中間。紅色和藍色之間的間隙就是我們要的最大化分類的間隙。

有拉格朗日乘子法的地方，必然是一個組合優化問題。比如

這是一個帶等式約束的優化問題，有目標值，有約束條件，不能直接求導。可以使用拉格朗日方法，把這個約束乘以一個系數加到目標函數中去，這樣相當與既考慮了原目標函數，也考慮了約束條件。然後分別對x求導等於0，

把它帶點菜約束條件中去，可以看到，2個變數兩個等式，最終可再帶回去求x就可以了。更高一層，帶有不等式的約束問題怎麼辦？需要用更一般化的拉格朗日乘子法，即KKT條件，來求解這個問題。

任何原始問題約束條件無非最多三種，等式約束，大於號約束，小於號約束，而這三種最終通過將約束方程簡化成兩類：約束方程等於0和約束方程小於0。

假設原始問題約束條件為下例所示：

那麼把約束條件變個樣子

現在拿到目標函數中去變成

那麼KKT條件的定理是什麼呢？就是如果一個優化問題在轉變成

其中g是不等式約束，h是等式約束。那麼KKT條件就是函數的最優值，它必定滿足下面條件：

這三個等式很好理解，重點是第三個句子不好理解，因為我們知道在約束條件變完或，所有的 ，且求和還要為0。那麼為什麼KKT的條件是這樣的呢？

某次的g(x)在為最優解起作用，那麼它的系數值（可以）不為0，如果某次g(x)沒有為下一次的最優解起作用，那麼它的系數就必須為0。

函數間隔
對於給定的訓練數據集T合超平面(w,b)，定義超平面(w,b)關於樣本點 的函數間隔為

函數間隔可以表示分類預測的正確性及確信度。但是選擇超平面時，只有函數間隔是不夠的，因子只要成比較改變 和b，超平面並沒有改變，但函數間隔卻擴大了。

幾何間隔
對於給定的訓練數據集T和超平面 ，定義超平面 關於樣本點 的幾何間隔為 ,其中 為 的 范數。

如果 ，那麼函數間隔和幾何間隔相等。如果超平面參數 成比例地改變（超平面沒有改變），函數間隔也成比例改變，而幾何間隔不變。

支持向量機的基本想法是求解能夠正確分訓練數據集並且幾何間隔最大的分離超平面。對線性可分的訓練數據集而言，線性可分分離超平面有無窮多個（等價於感知機），但是幾何間隔最大的分離超平面時唯一的。這里的間隔最大化被稱為硬間隔最大化。

間隔最大化的直觀解釋是：對訓練數據集找到幾何間隔最大的超平面意味著以充分大的確信度對訓練數據進行分類。也就是說，不僅將正負實例點分開，而且對最難分的實例點（離超平面最近的點）也有足夠大的確信度將他們分開。這樣的超平面應該對未知的新實例有很好的分類預測能力。

下面考慮如何求一個幾何間隔最大的分離超平面，即最大間隔分離超平面。具體地，這個問題可以表示為下面的約束最優化問題：

即我們希望最大化超平面 關於訓練數據集的集合間隔 ，約束條件表示的是超平面 關於每個訓練樣本點的集合間隔至少是

考慮幾何間隔和函數間隔的關系式，可將這個問題改成為

函數間隔 並不影響最優化問題的解。事實上，假設將 成比例改變為 ,這時函數間隔變成 。函數間隔的改變對最優化問題的不等式約束沒有影響，對目標函數的優化也沒有影響，也就事實說，它產生一個等價的最優化問題。這樣，就可以取 。將 代入上面的最優化問題。注意最大化 和最小化 是一樣的。

於是就得到下面的線性可分支持向量機學習的最優化問題

這是一個凸二次規劃問題(contex quadratic programming)問題。
凸優問題是指約束最優化問題

其中，目標函數 和約束函數 都是 上的可連續可微的凸函數，約束函數 是 的仿射函數。當木匾函數是 是二次函數且約束函數 是仿射函數時，上述的凸優化問題成為凸二次規劃問題。
如果求出約束最優化問題的解 ，那麼就可以得出最大間隔分離超平面 及決策函數 ，即線性可分支持向量機模型。

為了求解線性可分支持向量機的最優化問題，將它作為原始最優化問題，應用到拉格朗日對偶性，通過求解對偶問題得到原始問題的最優解，這就是線性可支持向量機的對偶演算法(al algorithm)。這樣做的優點，一是對偶問題往往根據容易求解；二是自然引入核函數，進而推廣到非線性可分類問題。

首先構建拉格朗日函數(Lagrange function)。為此，對每一個不等式約束引入拉格朗日乘子(Lagrange multiplier) 定義拉格朗日函數：

其中 為拉格朗日乘子向量。

根據拉格朗日對偶性，原始問題的對偶問題是極大極小問題

為了得到對偶函數問題的解，需要先求 對 的極小，再求 的極大
(1)求
將拉格朗日函數 分別對 求偏導數並令其等於0

將（1）代入拉格朗日函數，並利用(2)，即可得

即

(2)求 對 的極，即對偶問題


將公式(3)的目標函數由極大值轉換成求極小，就得到下面與之等價的對偶最優化問題

(3)解
假設 是對偶最優化問題的解，則存在下標使得 ，並求按下式求得原始最優化的解

根據KKT條件成立，即得

因此

,且至少存在一個 ，假設 ,那麼 不是原始問題的解,所以

那麼分離的超平面可以寫成

決策函數可以寫成

由此可以看出，分類決策函數只依賴於輸入x和訓練樣本輸入的內積，式（8）稱為線性可分支持向量機的對偶形式。

案例
訓練數據正例點是 ，負例點是 ，試用線性可分支持向量機
解：根據所給數據，對偶問題是

解這一優化問題，將 代入目標函數並記為

對 求偏導令其為0，易知 處取極值，該點不滿足約束條件 ，所以最小值應在邊界上達到。

當 ，當 ，於是

這樣, 對應的實例點 是支持向量，計算可得 ,

分離超平面為
分離決策函數為

線性可分問題的支持向量機學習方法，對線性不可分訓練數據是不適用的，因為這時上述方法中的不等式約束不能都成立。 線性不可分意味著不能滿足函數間隔大於等於1的約束條件 。為了解決這個問題，對每個樣本點 都引入一個鬆弛變數 ，使得函數間隔加上變數大於等於1，這樣約束條件變為

同時對於每個鬆弛變數 ，支付一個代價 ,目標函數由原來的 變成

C>0為懲罰參數，一般由應用問題解決，C值大時對誤分類的懲罰增大，C值小時對誤分類的懲罰減小。最小化木匾函數有2層意思：使得 盡量小，即間隔盡量大，同時使誤分類點的個數盡量小，C是調和兩者的系數

非線性分類問題是指通過非線性模型才能很好地進行分類的問題。非線性問題往往不好求解，希望通過線性分類問題的方法解決這個問題，所採取的方法是進行一個非線性變換，將非線性問題變成線性問題，通過解變換後的線性問題的方法求解原來的非線性問題。

用線性分類方法求解非線性分類問題分兩步：首先使用一個變換將原來空間的數據映射到新空間；然後在新空間里用線性分類學習方法從訓練數據中學習分類模型。核技巧就屬於這樣的方法。

設X是輸入空間（歐氏空間 的子集或離散集合），又設H為特徵向量（希伯而空間H），如果存在一個從X到H的映射

使得對所有 ，函數 滿足條件

則稱K(x,z)為核函數， 為映射函數， 。通常計算K(x,z)比較容易，而通話 計算K(x,z)並不容易。

是輸入空間到特徵空間的迎神，特徵空間一般是高維的，甚至是無窮維，可以看到，對於給定的核K(x,z)，特徵空間H和映射函數 的取法並不唯一，可以取不同的特徵空間，即便是在同一特徵空間也可以取不同的映射。

在對偶目標函數中的內積 可以用核函數 來代替，此時對偶問題的目標函數成為

這等價於經過映射函數 將原來的輸入空間變換到一個新的特徵空間，將輸入空間中的內積 變換成特徵空間中的內積 ，在新的特徵空間里從訓練樣本中學習線性支持向量機。學習是隱式地在特徵空間進行的，不需要顯式地定義特徵空間和營業日函數。在實際應用中，往往依賴領域知識直接選擇核函數。

對應的支持向量機是一個p次多項式分類器，在此情形下，分類決策函數成為

對應的支持向量機是高斯徑向基函數(radial basis function)分類器。在此情形下，分類決策函數成為

核函數不僅可以定義在歐式空間，還可以定義在離散數據的集合上。比如，字元串核函數是定義在字元串集合上的核函數。字元串核函數在文本分類、信息檢索、生物信息學等方面都有應用。

兩個字元串s和t上的字元串核函數是基於映射 的特徵空間中的內積：


字元串核函數 給出了字元串s和t中長度等於n的所有子串組成的特徵向量的餘弦相似度。直觀上看，兩個字元串相同的字串越多，它們就越相似，字元串核函數的值就越大。字元串核函數可以由動態規劃快速地計算。

支持向量機的學習問題可以形式化為求解凸二次規劃問題，這樣的凸二次規劃問題具有全局最優解，並且有許多最優化演算法可以用於這一問題的求解。但是當訓練樣本容量很大時，這些演算法往往變得非常低效，以至無法使用。

序列最小最優化(sequential minimal optimization,SMO)演算法，是一種啟發式演算法，其基本思路是：如果所有變數的解都滿足此最優化問題的KKT條件，那麼這個最優化問題的解就得到了。因為KKT條件是該最優化問題的充分必要條件。否則，選擇兩個變數，固定其他變數，針對這兩個變數構建一個二次規劃問題。這個二次規劃問題的目標是使函數值變得更小。重要的是，這時子問題可以通過解析方法求解，這樣就可以大大提高整個演算法的計算速度。子問題有兩個變數，一個是違反KKT條件最嚴重的那一個，另一個由約束條件自動確定。如此，SMO演算法將原問題不斷分解為子問題並對子問題求解，進而達到求解原問題的目的。

假設兩個變數是 ，其他變數 是固定的，於是SNO的最優化問題的子問題可以寫成。

其中， 是常數，目標函數中省略不含 的常數項。

為了求解兩個變數的二次規劃問題，約束可以用二維空間中的圖形表示

不等式約束(7.3)使得 在盒子[0,C] [0,C]內，等式約束(7.2)使 在平行於盒子[0,C] [0,C]的對角線的直線上。因此要求的是目標函數在一條平行於對角線的線段上最優值。這使得兩個變數的最優化問題成為實質上的單變數最優化文圖，不訪考慮為變數 的最優化問題。

假設初始化可行解為 ，最優化解為 ，並且假設沿著約束方向未經剪輯時 的最優解為

由於 需滿足不等式約束(7.3)，所以最優值 的取值范圍必須滿足條件

其中，L與H是 所在對角線段端點的界，如果

如果 ，則

下面首先要求沿著約束方向未經剪輯即未考慮不等式約束(7.3)時 的最優解 ，然後在解決剪輯後 的解 ，我們用定理來描述這個結果

令

當i=1,2時， 為函數g(x)對輸入 的預測值與真實輸出 之差

定理 最優化問題(7.1)~(7.3)沿著約束方向未經剪輯時的解是

其中
是輸入空間到特徵空間的映射

經剪輯後的 的解是

由 是

Ⅳ 數據挖掘-支持向量機

支持向量機（support vector machine，SVM）是一種出色的分類技術，也可以用於回歸分析（SVR）。這種技術可以很好的應用於高維數據，避免維度災難等問題。

SVM有一個特點就是使用訓練集中的一個子集來表示決策邊界，該子集稱作 支持向量 。

SVM的核心目標是找到分類中的最大邊緣超平面，讓其作為決策邊界，那麼什麼是最大邊緣超平面呢？

但是可以發現，這種超平面有無數多個（圖中就能看到有好多個），如果有一些未知的點需要預測分類，那麼他們可能未必會被這些超平面完美的分隔：

以最下側的超平面為例，如果我們有未知的點按照藍色排布，那麼可以看到，最下側的這個超平面完全不能分類所有藍色點的「-」號，那麼如果它作為決策邊界，泛化能力就不是很好。

我們肯定要從這些超平面中選一個最合理的作為決策邊界，使得未知的點盡量的能被正確預測分類，那麼肯定是上圖中間的這個超平面最好了，我們目測就可以得到結果，因為 它離兩邊這些點的距離圍成的面積應該是最大的，而且兩邊的面積基本是差不多的 。（個人理解）所以應該能裝得下更多的未知點，也就能得到最好的泛化效果。

為了不用肉眼觀測，能量化的得到這個結果，我們可以定義 最大邊緣超平面 。
下圖中有兩個決策邊界， 和 ，其中每個決策邊界都對應著兩個超平面(記作 )。其中 是由 進行兩側平移，直到接觸到最近的一個訓練集的點停止，生成的，同理 也是。
我們把兩個超平面（同一個決策邊界生成的）之間的距離叫做分類器的邊緣，那麼下圖中，顯然 生成的兩個超平面距離應該是最大的， 就叫做 最大邊緣超平面 （ 雖然是決策邊界，但是決策邊界都是超平面）。

通常來說，較大邊緣的超平面具有更好的泛化誤差，如果邊緣比較小，那麼決策邊界的輕微擾動都可能對分類產生顯著影響。

SVM演算法的核心就是設計最大化決策邊界邊緣的分類器，以保證最壞情況下泛化誤差最小 。

假設有一個包含 個訓練樣本的二元分類問題，每個樣本表示為一個二元組 , 其中 ，對應於第i個樣本的屬性集（一個樣本有多個屬性/特徵）,設y有-1和1兩個類別，則一個 線性分類器的決策邊界 可以寫成如下形式：

其中的 為參數， 是法向量（垂直於決策邊界）的向量，代表著超平面的方向，而 代表超平面與原點之間的距離（可以用一次函數的公式來理解）。

為什麼 一定會垂直於決策邊界呢？我們設有兩個點 是決策邊界上的兩點，那麼有：

二者相減有：

因為 肯定是平行於決策邊界的，那麼為了保證內積為0， 肯定要垂直於決策邊界。

根據以上的決策邊界，則肯定有：

如果上方的點是1類，下方是-1類，則有：

如果我們能得到 ，那麼就可以用這個公式對未知點進行預測分類。代入公式，如果 就是1類，反之則為-1類。

接下來我們的任務就是如何求這兩個參數，首先，既然是求最大邊緣超平面，我們要把決策邊界的邊緣算出來。

根據上圖，考慮那些離決策邊界最近的方形和圓形，我們可以得到兩個平行的超平面表示如下：


決策邊界的邊緣就是這兩個超平面的距離。
參考上圖的 ，不難得出邊緣 為：
其中 是w的2范數。

很顯然，我們想要讓這個 最大，那麼就要讓 最小。

於是，接下來我們的求參數目標就明確了。

由於 肯定是非負的，我們可以改寫一下
這個式子，讓它變成求 的最小值。

既然要求最小值，就需要有另外一個約束條件，否則是沒辦法求的，我們來看之前總結的線性SVM分類器的公式：
由於 和 是決策邊界的兩個超平面，我們從上圖中可以看出，所有的點（除了這兩個超平面經過的點以外，經過的點是離決策邊界最近的點），都肯定有 和 。

我們把y引入進來，那麼這兩個式子就能合到一起寫為：

注意不要和之前總結的公式中的 弄混，那個條件是最終預測分類的公式，也就是表明只要在決策邊界的上方就可以進行分類，而現在的>=1是在已知訓練集的情況下求模型的參數。

綜合以上的式子，我們可以得到求參數的基本式：

目標函數是二次的，而約束在參數 和 上是線性的，因此這是一個凸優化問題， 不存在局部優化的問題 。

求這一套公式的最小值，需要用到 拉格朗日乘數法 ，這個我也不是很明白，就按照網路的定義往裡套：

雖然我們這里的附加條件是大於等於1的，不過不妨改寫一下試試，則有：

其中的 就是 拉格朗日乘子 ，理論上來說，拉格朗日乘子可以為任何值。

如果約束條件是=0的話，我們就可以直接對 和 求偏導數，讓他們等於0，就能求得參數。

但是目前條件並不是等於0的，而是大於等於0的。

處理不等式約束一種方法就是變換成一組等式約束，根據KKT條件，可以限制拉格朗日乘子飛赴，把之前的約束變換為：

該約束表明，除非訓練樣本滿足方程 ，否則拉格朗日乘子必須為0。

結合上面展示決策邊界和超平面的圖，我們可以想到，滿足這個方程的樣本，肯定都在決策邊界生成的兩個超平面上。這些樣本處的拉格朗日乘子肯定夠大於0，而其他樣本的拉格朗日乘子，肯定等於0，因此問題得到簡化。 因為參數的確定僅依賴於這些在超平面上的樣本。

這些在超平面上的樣本，被稱作 支持向量 ，這也就是支持向量機的命名緣由。

有了以上的修改後的約束，我們可以在 對 和 求偏導，並讓他們等於0.

我們已知，這個時候的 和 是有滿足條件的最優解的，把這兩個式子代入原公式，就能得到 的最小值（當然此時因為不知道拉格朗日乘子，我們是求不出來的），代入公式可得：

該函數叫做對偶拉格朗日函數。

用這個函數，就是把之前求w和b的公式變換成了求拉格朗日乘子的公式，同時需要注意，這個式子中是求拉格朗日對偶函數的最大化問題。

我們可以用二次規劃法或者SMO方法來求拉格朗日乘子。
二次規劃演算法比較通用，但是計算量比較大，SMO演算法的核心就是把復雜的式子變換成比較簡易的之後，用二次規劃來計算。

SMO的基本思路是：先固定 之外的所有參數，然後求 上的極值，由於存在約束 ，如果固定了 之外的其他變數，則能求出 。
那麼對偶函數里有兩個λ，我們就可以固定這兩個λ之外的參數，之後求解 。
其中有一個λ不滿足KKT條件，則目標函數就會在迭代後減小，違背程度越大，變數更新後導致的目標函數值就越大。 所以SMO先選取違背KKT條件最大的變數，第二個變數選擇使目標函數值見效最快的變數，使選取的兩個變數對應樣本之間的間隔最大。
然後可以變換為簡單的二次規劃問題：

找到一組λ後，就可以用原公式求得 的解，決策邊界可以表示為：
之後b可以通過 求解。
因為λ通過數值計算得到，因此可能存在誤差，則b可能不唯一。通常我們可以用b的 平均值 作為決策邊界的參數。

如圖所示，這組數據集有兩個特徵 和一個 標簽，我們要對其進行建模分類，可以得到有兩個拉格朗日乘子（支持向量上的），其他的均為0.
我們可以得到 有：

第一個 是針對 的參數，以此類推。
有了 ，可以求得 有：


可以根據兩個b求平均值，得到b=7.93，因此就能得到分類的模型。

如果需要做預測，把對應點的x向量代入到模型中，求得結果為1的話，就是方形類，其他為圓形類。

上面討論的模型最終都會生成一條直線，也就是線性的模型，那麼往往需要判斷非線性的如何處理呢，這里需要引入核函數的技術。

要把SVM應用到非線性決策邊界的數據集上，就要把數據集從原來的坐標空間x變換到新的坐標空間中。
我們假定存在一個合適的函數 來變化給定的數據集，那麼變換之後，我們就可以根據 來構建線性決策邊界（類似於換元法，回憶一下）。變換之後，線性決策邊界具有以下的形式：
根據線性SVM的參數計算公式，我們把公式裡面的 換成 ，即可求解。
不過這種方式往往會涉及到向量對的點積，計算比較麻煩，當特徵數較多時，可能會造成維度災難的問題，因此我們要引入核函數。

核函數是一種使用原屬性集計算變換後的空間中的相似度的方法，簡而言之就是，我們如果按照上一段說的演算法，則我們需要先計算 ，然後再計算參數，而我們運用核函數，可以直接計算oldsymbol{x}就可以達到變換屬性集的目的。
我們令 ，這樣就可以把映射的函數變成了原屬性集的計算。 就是核函數。

但是這個 一般我們是不知道的，因此我們要找尋幾種通用的函數，讓他們可以實現 的功能，以便模擬非線性的決策邊界。

這里我們引入一個 Mercer定理 ， 所有的核函數都必須滿足Mercer定理。

通常有如下幾種核函數：

我們也可以通過核函數的組合來形成新的核函數：

我們直到一般演算法都要防止過擬合，防止雜訊帶來的模型泛化能力下降，那麼SVM的防止過擬合方法就是軟邊緣。

此外，根據KKT條件，可以變換約束如下：


注意，上述三個式子中的 是非零的，當且僅當訓練樣本位於直線 上或者 。另外對於誤分類的訓練樣本， 都為0.

我們按照正常優化的演算法，對 , , 求偏導數，可以得到參數：

代入原公式，可以得到只包括拉格朗日乘子的對偶拉格朗日函數。

這個式子看上去跟不加軟邊緣的對偶函數是一樣的，但是約束是不同的。
軟邊緣的對偶函數約束為

之後就可以用二次規劃或者SOM求參數值了，從而得到模型。
這就是帶軟邊緣的SVM。

以上提到的都是二元分類的辦法，那麼多分類可以參考常用的多分類處理，用一對一方法，如果有多分類問題，我們可以分解為K（K-1）/2個二類分類器，每一個分類器用來區分一對類 。（注意這里的y都是單獨的類，不是一堆類別的集合）
當為 構建分類器時，其他不屬於這兩類的點都被忽略掉。
之後針對需要預測分類的樣本，我們用不同的分類器進行分類，最後進行投票，得到結果。

以上就是SVM（用於分類的支持向量機）的內容，最後看看該演算法的特點：

Ⅵ 支持向量機原理講解（一）

支持向量機(Support Vector Machine,以下簡稱SVM)，作為傳統機器學習的一個非常重要的分類演算法，它是一種通用的前饋網路類型，最早是由Vladimir N.Vapnik 和 Alexey Ya.Chervonenkis在1963年提出，目前的版本（soft margin）是Corinna Cortes 和 Vapnik在1993年提出，1995年發表。深度學習（2012）出現之前，如果不考慮集成學習的演算法，不考慮特定的訓練數據集，在分類演算法中的表現SVM說是排第一估計是沒有什麼異議的。

SVM本來是一種線性分類和非線性分類都支持的二元分類演算法，但經過演變，現在也支持多分類問題，也能應用到了回歸問題。本篇文章重點講解線性支持向量機的模型原理和目標函數優化原理。

在講解SVM模型之前，我們可以先簡單了解感知機模型的原理，因為這兩個模型有一些相同的地方。在二維平面中，感知機模型是去找到一條直線，盡可能地將兩個不同類別的樣本點分開。同理，在三維甚至更高維空間中，就是要去找到一個超平面。定義這個超平面為wTx+b=0（在二維平面中，就相當於直線w_1 x+w_1 y+b=0），而在超平面上方的點，定義為y=1，在超平面下方的點，定義為y=-1。而這樣的超平面可能是不唯一的，那麼感知機是怎麼定期最優超平面呢？從感知機模型的目標函數中，我們了解到它是希望讓所有誤分類的點(定義為M)到超平面的距離和最小。其目標函數如下：

(註：加入 是因為點若在超平面下， 為負數，需要乘上對應的 )

當w和b成比例增加了之後，比如都擴大N倍，會發現，分子和分母都會同時擴大N倍，這對目標函數並不影響。因此，當我們將W擴大或縮小一定倍數使得，||w||=1，分子也會相應的擴大或縮小，這樣，目標函數就能簡化成以下形式：

這個思想將會應用到支持向量機的目標函數優化上，後文將會詳細講解。

正如上文所說，線性支持向量機的思想跟感知機的思想很相似。其思想也是對給定的訓練樣本，找到一個超平面去盡可能的分隔更多正反例。不同的是其選擇最優的超平面是基於正反例離這個超平面盡可能遠。

從上圖可以發現，其實只要我們能保證距離超平面最近的那些點離超平面盡可能遠，就能保證所有的正反例離這個超平面盡可能的遠。因此，我們定義這些距離超平面最近的點為支持向量（如上圖中虛線所穿過的點）。並且定義正負支持向量的距離為Margin。

對SVM思想有一定理解之後，設超平面為 。我們講解一下函數間隔和幾何間隔的區別。

給定一個樣本 ， 表示點x到超平面的距離。通過觀察 和 是否同號，我們判斷分類是否正確。所以函數間隔定義 為：

而函數間隔不能正常反應點到超平面的距離，因為當我們等比例擴大 和 的時候，函數間隔也會擴大相應的倍數。因此，我們引入幾何間隔。

幾何間隔就是在函數間隔的基礎下，在分母上對 加上約束（這個約束有點像歸一化），定義為 ：

其實參考點到直線的距離，我們可以發現幾何間隔就是高維空間中點到超平面的距離，才能真正反映點到超平面的距離。

根據SVM的思想，我們可以知道是要取最大化支持向量到超平面的幾何間隔，所以目標函數可以表示為：

在感知機模型最後，我們知道當同時擴大w和b，分子分母都會同樣擴大，對目標函數不影響，所以在這里我們將分子(支持向量到超平面的函數間隔)擴大或壓縮等於1，則目標函數可以轉化為：

但是上式並不是凸函數，不好求解，再進一步轉化為：

上式就是一個凸函數，並且不等式約束為仿射函數，因此可以使用拉格朗日對偶去求解該問題。

根據拉格朗日乘子法，引入拉格朗日乘子α，且α≥0我們可以知道，先不考慮min，(2)問題等價於：

然後再考慮min，則有：

應用拉格朗日對偶性，通過求解對偶問題得到最優解，則對偶問題的目標函數為：

這就是線性可分條件下支持向量機的對偶演算法。這樣做的優點在於：一是原問題的對偶問題往往更容易求解，二者可以自然的引入核函數，進而推廣到非線性分類問題。

從(4)中，我們可以先求目標函數對於 和 的極小值，再求拉格朗日乘子 的極大值。

首先，分別對 和 分別求偏導數，並令為0：

得：

將(5)和(6)代入(4)得到：

對(7)取反得到：

只要我們可以求出(8)中極小化的 向量，那麼我們就可以對應的得到 和 ，而求解 需要使用SMO演算法，由於該演算法比較復雜，我們將在下一篇文章專門講解。假設我們現在已經使用SMO演算法得到了最優的 值，記為

再求 ：

對於任一樣本 有：

注意到任一樣本都有 ，則將右式的1用 代：

將(9)代入上式，可以得到：

這樣，我們就能夠求解得到線性支持向量機的目標函數的各個參數，進而得到最優的超平面，將正負樣本分隔開。但是在上文中我們沒有講解求 向量的SMO演算法，在下篇文章，將會詳細講解SMO演算法，歡迎繼續關注。