SVM

SVM我们都知道其经常被用来做分类问题，当计算机的能力不足时，SVM是一个最火的算法，直到多层神经网络算法的出现。

介绍

将下面的点进行分类如何划分？划分为几类呢？

220px-Svm_separating_hyperplanes_(SVG).svg.png

通过人的眼和人脑处理后，我们可以很快的分辨出是红线划分是最好的，可是计算机是如何才能知道，又如何制定规则呢？

SVM寻找区分两类的超平面（hyper plane), 使边际(margin)最大

Image [4].png

如上图所示，将数据划分开的平面有很多，图一，图二都可以将数据划分开，但是每一种方式的划分的平面又有很多个平面，比如将平面进行平移也可以将数据划分开，但是是否可以一直平移？答案是否定的，它存在上下界（指的是恰好可以分开数据），也就是存在数据点正好落在分割面上，而这些点就是支持向量。

分类

按照分割的情况将SVM分为三种：

• 硬间隔支持向量机（线性可分支持向量机）：当训练数据线性可分时，可通过硬间隔最大化学得一个线性可分支持向量机。用通用的话来说就是上图中的虚线间没有数据点。

• 软间隔支持向量机：当训练数据近似线性可分时，可通过软间隔最大化学得一个线性支持向量机。用通俗的话来讲就是上图中虚线间还存在部分数据点。

images [1].jpg

• 非线性支持向量机：当训练数据线性不可分时，可通过核方法以及软间隔最大化学得一个非线性支持向量机。无法用线性来进行划分。比如上图的情况。

算法

得到公式 Image [9].png

我们再次把这个图放出来，首先我们要证明的就是线性可分支持向量机

Image [4].png

首先我们假设中间的超平面方程为：

Image [5].png

当然如上面所言，我们可以对这个超平面进行平移，直到达到不能移动的支持向量的点。

Image [8].png

如上图公式所示，我们先证明的是二分类，让等式大于1的为正例，小于1为负例。为什么选1呢？其实你可以选任何数，同样正例与父类用（1，-1）表示也是为了计算方便。
这样我们可以很容易得出：

Image [9].png

这样两个公式就合并了，同时得出了条件了。

最大化边际

我们都知道svm就是要寻找使边际最大的那个状态的超平面，用M来表示两个边界平面间的距离，那么？

max M = ?

这时我们可以直接把公式简化为， Image [2].png

=1
两个平面间的距离公式直接可以得出，

M = |b+1-(b-1)|/sqrt(w^2+0)=2/||w||

所以M要最大，|w|就需要最小

所以我们得到的目标函数就是使 |w|最小，即|w|^2最小，为求导方便，我们设为求

1/2|w|^2

最小。

构造函数

通过以上两次分析，我们已经把问题转化为了大学的数学问题

在已知 Image [9].png

的条件下，要使得

1/2|w|^2

最小。

这就明显变为了一个目标函数和一个约束条件，组合成的拉格朗日求最小值的问题了

但是由于条件是一个不等式，同时这个条件包含所有的数据点， 利用一些数学推倒，以上公式可变为有限制的凸优化问题(convex quadratic optimization)利用 Karush-Kuhn-Tucker(KKT)条件和拉格朗日公式，可以推出MMH可以被表示为以下“决定边界“

Image [13].png

详细的推倒在下面会附上。

这里举一个例子：

Image [15].png

Sklearn SVM

1 sklearn简单例子

from sklearn import svm

X = [[2, 0], [1, 1], [2,3]]
y = [0, 0, 1]
clf = svm.SVC(kernel = 'linear')
clf.fit(X, y)  

print clf

# get support vectors
print clf.support_vectors_

# get indices of support vectors
print clf.support_ 

# get number of support vectors for each class
print clf.n_support_ 

2 sklearn画出决定界限

print(__doc__)

import numpy as np
import pylab as pl
from sklearn import svm

# we create 40 separable points
np.random.seed(0)
X = np.r_[np.random.randn(20, 2) - [2, 2], np.random.randn(20, 2) + [2, 2]]
Y = [0] * 20 + [1] * 20

# fit the model
clf = svm.SVC(kernel='linear')
clf.fit(X, Y)

# get the separating hyperplane
w = clf.coef_[0]
a = -w[0] / w[1]
xx = np.linspace(-5, 5)
yy = a * xx - (clf.intercept_[0]) / w[1]

# plot the parallels to the separating hyperplane that pass through the
# support vectors
b = clf.support_vectors_[0]
yy_down = a * xx + (b[1] - a * b[0])
b = clf.support_vectors_[-1]
yy_up = a * xx + (b[1] - a * b[0])


print "w: ", w
print "a: ", a
# print " xx: ", xx
# print " yy: ", yy
print "support_vectors_: ", clf.support_vectors_
print "clf.coef_: ", clf.coef_

# In scikit-learn coef_ attribute holds the vectors of the separating hyperplanes for linear models. It has shape (n_classes, n_features) if n_classes > 1 (multi-class one-vs-all) and (1, n_features) for binary classification.
# 
# In this toy binary classification example, n_features == 2, hence w = coef_[0] is the vector orthogonal to the hyperplane (the hyperplane is fully defined by it + the intercept).
# 
# To plot this hyperplane in the 2D case (any hyperplane of a 2D plane is a 1D line), we want to find a f as in y = f(x) = a.x + b. In this case a is the slope of the line and can be computed by a = -w[0] / w[1].




# plot the line, the points, and the nearest vectors to the plane
pl.plot(xx, yy, 'k-')
pl.plot(xx, yy_down, 'k--')
pl.plot(xx, yy_up, 'k--')

pl.scatter(clf.support_vectors_[:, 0], clf.support_vectors_[:, 1],
           s=80, facecolors='none')
pl.scatter(X[:, 0], X[:, 1], c=Y, cmap=pl.cm.Paired)

pl.axis('tight')
pl.show()