# 支持向量機（四）-- 核函數
> 來源：http://blog.csdn.net/u011067360/article/details/25503073
**一、核函數的引入**
問題1：
SVM顯然是線性分類器，但數據如果根本就線性不可分怎么辦？
解決方案1：
數據在原始空間（稱為輸入空間）線性不可分，但是映射到高維空間（稱為特征空間）后很可能就線性可分了。
問題2：
映射到高維空間同時帶來一個問題：在高維空間上求解一個帶約束的優化問題顯然比在低維空間上計算量要大得多，這就是所謂的“維數災難”。
解決方案2：
于是就引入了“核函數”，核函數的價值在于它雖然也是講特征進行從低維到高維的轉換。
**二、實例說明**
例如圖中的兩類數據，分別分布為兩個圓圈的形狀，不論是任何高級的分類器，只要它是線性的，就沒法處理，SVM 也不行。因為這樣的數據本身就是線性不可分的。
從上圖我們可以看出一個理想的分界應該是一個“圓圈”而不是一條線（超平面）。如果用?X1?和?X2?來表示這個二維平面的兩個坐標的話，我們知道一條二次曲線（圓圈是二次曲線的一種特殊情況）的方程可以寫作這樣的形式：
```
a1X1+a2X21+a3X2+a4X22+a5X1X2+a6=0
```
注意上面的形式，如果我們構造另外一個五維的空間，其中五個坐標的值分別為?Z1=X1,?Z2=X21,?Z3=X2,?Z4=X22,?Z5=X1X2，那么顯然，上面的方程在新的坐標系下可以寫作：
```
∑i=15aiZi+a6=0
```
關于新的坐標?Z?，這正是一個超平面?的方程！也就是說，如果我們做一個映射??:R2→R5?，將?X?按照上面的規則映射為?Z?，那么在新的空間中原來的數據將變成線性可分的，從而使用之前我們推導的線性分類算法就可以進行處理了。這正是 Kernel 方法處理非線性問題的基本思想。
**三、詳細分析**
還記得之前我們用內積這里是二維模型，但是現在我們需要三維或者更高的維度來表示樣本。這里我們假設是維度是三；
那么首先需要將特征x擴展到三維，然后尋找特征和結果之間的模型。我們將這種特征變換稱作特征映射（feature mapping）。映射函數稱作，在這個例子中
我們希望將得到的特征映射后的特征應用于SVM分類，而不是最初的特征。這樣，我們需要將前面公式中的內積從，映射到。?
為什么需要映射后的特征而不是最初的特征來參與計算，一個重要原因是樣例可能存在線性不可分的情況，而將特征映射到高維空間后，往往就可分了。
**核函數的定義：**
將核函數形式化定義，如果原始特征內積是，映射后為，那么定義核函數（Kernel）為
現在有了以上的概念，我們現在要計算K(x,z)只要簡單的計算，然后計算，在求出它們的內積。但是現在有一個問題，那是計算K(x,z)的時間復雜度是提高了。即使是計算也是很復雜的。那現在怎么解決呢？
現在我們假設：x，z都是n維，同時有
展開
發現我們可以只計算原始特征x和z內積的平方（時間復雜度是O(n)），就等價與計算映射后特征的內積。也就是說我們不需要時間了。?
現在看一下映射函數（n=3時），根據上面的公式，得到
也就是說核函數只能在選擇這樣的作為映射函數時才能夠等價于映射后特征的內積。
**再看一個核函數**
對應的映射函數（n=3時）是
更一般地，核函數對應的映射后特征維度為。
**四、如何映射到核函數**
現在介紹了核函數之后那到底怎么來使用核函數到樣本了？
設超平面實際的方程是這個樣子（圓心在?X2?軸上的一個正圓）：
```
a1X21+a2(X2?c)2+a3=0
```
因此我只需要把它映射到?Z1=X21,?Z2=X22,?Z3=X2?這樣一個三維空間中即可，下圖是映射之后的結果，將坐標軸經過適當的旋轉，就可以很明顯地看出，數據是可以通過一個平面來分開的：
現在讓我們再回到 SVM 的情形，假設原始的數據時非線性的，我們通過一個映射??(?)?將其映射到一個高維空間中，數據變得線性可分了，這個時候，我們就可以使用原來的推導來進行計算，只是所有的推導現在是在新的空間，而不是原始空間中進行。
我們上一次得到的最終的分類函數是這樣的：
現在則是在映射過后的空間，即：
而其中的?α?也是通過求解如下 dual 問題而得到的：
回到我們之前構造的一個五維的空間：到現在貌似我們還沒有用到核函數，但是現在我們可以看出，數據映射到新空間后，因為新空間是多維的，計算量肯定是增加了不少了，現在就只能用核函數來解決了。
不妨還是從最開始的簡單例子出發，設兩個向量和??，而?(\*)?即是到前面說的五維空間的映射，
五個坐標的值分別為?Z1=X1,?Z2=X21,?Z3=X2,?Z4=X22,?Z5=X1X2，
因此映射過后的內積為：
根據我們之前簡介的核函數的實現，具體來說，上面這個式子的計算結果實際上映射了
這樣一來計算的問題就算解決了，避開了直接在高維空間中進行計算，而結果卻是等價的。
**五、高斯核函數**
再看另外一個核函數
這時，如果x和z很相近（），那么核函數值為1，如果x和z相差很大（），那么核函數值約等于0。由于這個函數類似于高斯分布，因此稱為高斯核函數，也叫做徑向基函數(Radial Basis Function 簡稱RBF)。它能夠把原始特征映射到無窮維。
既然高斯核函數能夠比較x和z的相似度，并映射到0到1，回想[logistic回歸](http://blog.csdn.net/u011067360/article/details/22318261)，sigmoid函數可以，因此還有sigmoid核函數等等。?
注意，使用核函數后，怎么分類新來的樣本呢？線性的時候我們使用SVM學習出w和b，新來樣本x的話，我們使用來判斷，如果值大于等于1，那么是正類，小于等于是負類。在兩者之間，認為無法確定。如果使用了核函數后，就變成了，是否先要找到，然后再預測？答案肯定不是了，找很麻煩，回想我們之前說過的
只需將替換成，然后值的判斷同上。?
總結：對于非線性的情況，SVM 的處理方法是選擇一個核函數?κ(\*)?，通過將數據映射到高維空間，來解決在原始空間中線性不可分的問題。由于核函數的優良品質，這樣的非線性擴展在計算量上并沒有比原來復雜多少，這一點是非常難得的。當然，這要歸功于核方法——除了 SVM 之外，任何將計算表示為數據點的內積的方法，都可以使用核方法進行非線性擴展。
參考文檔：（?主要的參考文檔來自4個地方）
1、[支持向量機: Kernel](http://blog.pluskid.org/?p=685)
2、[JerryLead關于核函數的講解](http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988406.html)
3、[?支持向量機通俗導論（理解SVM的三層境界](http://blog.csdn.net/v_july_v/article/details/7624837)
4、斯坦福大學機器學習的公開課。
