机器学习之支持向量机 SVM 及代码示例

一、线性可分SVM

SVM算法最初是用来处理二分类问题的，是一种有监督学习的分类算法。

对于线性可分的二分类问题，我们可以找到多个超平面，将两类样本进行区分。(超平面在一维中是一个点；在二维中是一条线；在三维中是一个面……)

在上面的多个超平面中，它们都可以成功将样本集划分两边，但哪一个超平面更好？ 
一般来说，当样本点离超平面越近，样本的标签为某类型的概率应该为0.5左右，而样本点离超平面越远，样本的标签为某类型的概率越大。

而SVM所寻找的最优超平面就是要尽可能的远离所有类别的数据点，使得间隔（margin）最大。间隔的定义如下图所示：

一般来说，间隔（Margin）中间是无点区域。为了偏袒于某一类样本，超平面到两类样本点集合的最小距离都是相等的，即间隔等于超平面到两类样本集的最小距离*2。对于Margin越大的超平面，分类犯错的机率就越小。

二、超平面和间隔

接下来，需要做的就是将间隔(Margin)进行最大化，来寻找最优超平面。在这之前，需要对超平面进行定义，以便于计算点到超平面距离。

可将超平面定义为  其中为了给超平面添加个常数项，b为常数；向量w垂直于超平面，这样方便于计算点到超平面的距离 ； 向量x为样本的特征向量。而向量x 点乘 向量w 可理解为向量x 在 向量w 上未进行归一化的投影。（两个向量点乘的结果是一个标量）

通过这样定义超平面后，由图可以发现：所有在超平面右上方的点都有  进一步，我们可以通过等比例缩放  其中， 具体效果如图所示：

而“支持向量”就是所有落在间隔两边的超平面H1、H2上的点，分界的超平面”支超平面H1、H2上的任意一点的距离为  具体的公式推导如下：

三、最大化间隔

在上面，我们找到了间隔(margin)的表达式为  为了方便之后的计算，这里将 最大化间隔  即最后可变换为：在约束条件  而  正好可以解决这个问题。由拉格朗日乘子法，可以得到一个新的函数如下：

将上面得出的两个式子代入L函数中，有：

可以发现，函数L与训练集中样本的特征向量的两两点乘有关。

接下来，根据强对偶KKT条件，将原问题转换为对偶问题：

因此需要求得L函数对alpha的极大，不过这里先对L函数取个负号，即需要求得 -L 函数对 alpha 的极小，所需要求解的约束最优化问题为：

通过求解，可得到最优的alpha。

得到最优alpha之后，我们得到了间隔的最大值为  当向量  因此超平面可以表示为： 当将  四、软间隔的目标函数

有些时候，当存在噪声样本时，训练集的样本集并不能被严格地线性可分（即使使用了后面的核函数）。如图所示： 
硬间隔”( hard margin )分类法，因为它硬性地要求所有样本点都满足和分类平面间的距离必须大于某个值。

从图中可看出，硬间隔的分类法容易受少数点的控制，为了解决这种控制，可以允许一些点到分类平面的距离不满足原先的要求。

原先我们的硬约束条件为： 为了引入容错性，对每个样本点引入一个松弛变量  当某些点比较特殊时（比较离群），新的约束条件意味着我们放弃了对这些点的精确分类，而这对分类器来说是种损失。但损失这些特殊点也带来了一些好处，那就是使超平面不必向这些点的方向移动，因而可以得到更大的间隔margin。

因为为了权衡这种损失和好处，即减小损失且又扩大间隔，我们的目标函数也需要发生改变，即我们需要最小化的函数为：惩罚因子C，C是模型的一个超参数 。这种方法也叫作 一阶软间隔分类器 。 
当公式中的 二阶软间隔分类器 。

当惩罚因子C越大时，模型就越不想丢弃那些离群的样本点。上面的公式中，所有样本点共用了一个惩罚因子，当然，也可以是不同的样本点可以对应不同的惩罚因子。

五、从线性到非线性

上面只是说明了线性可分的情况，而针对线性不可分的情况： 
训练集的样本在当前维度的空间对应的向量找不到一个超平面来区分开。对于这种情况，一种处理方法是 对特征向量进行非线性映射，映射到一个更高维的空间，然后再在高维空间中寻找最优超平面，但计算内积时算法复杂度非常高；另一种处理方法为 核方法（kernel trick），非线性映射函数的内积，解决复杂度的问题。

具体例子可如下图所示：

若用f表示这个非线性的映射，那么核函数等同于经f映射之后的两个向量的内积：  复杂度的比较例子如下图所示：

常见的核函数有：

h度多项式核函数： 高斯核函数RBF： 一般根据先验知识来选择相应的核函数，可尝试不同的核函数，根据实验结果来确定。

六、从二分类到多分类

在上面，我们讨论的都是使用SVM来二分类问题。对于多分类问题，可以通过扩展SVM，通过one-vs-rest的方法来解决多分类问题，这样的解决方法一般会有很多个SVM：有多少类标签，就会有多少个SVM。

七、代码示例

import numpy as np import matplotlib.pyplot from sklearn import svm

np.random.seed(8) # 保证随机的唯一性

# 线性可分： array = np.random.randn(20,2)
X = np.r_[array-[3,3],array+[3,3]]
y = [0]*20+[1]*20 print X[0] print X[20] print y

[-2.90879528 -1.90871727]
[ 3.09120472 4.09128273]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 

# 建立svm模型 clf = svm.SVC(kernel='linear')
clf.fit(X,y)

SVC(C=1.0, cache_size=200, class_weight=None, coef0=0.0,
  decision_function_shape=None, degree=3, gamma='auto', kernel='linear',
  max_iter=-1, probability=False, random_state=None, shrinking=True,
  tol=0.001, verbose=False) 

x1_min, x1_max = X[:,0].min(), X[:,0].max(),
x2_min, x2_max = X[:,1].min(), X[:,1].max(),
xx1, xx2 = np.meshgrid(np.linspace(x1_min, x1_max), np.linspace(x2_min, x2_max)) # 得到向量w  : w_0x_1+w_1x_2+b=0 w = clf.coef_[0]
f = w[0]*xx1 + w[1]*xx2 + clf.intercept_[0]+1 # 加1后才可绘制 -1 的等高线 [-1,0,1] + 1 = [0,1,2] plt.contour(xx1, xx2, f, [0,1,2], colors = 'r') # 绘制分隔超平面、H1、H2 plt.scatter(X[:,0],X[:,1],c=y,cmap=plt.cm.Paired) 
plt.scatter(clf.support_vectors_[:,0],clf.support_vectors_[:,1],color='k') # 绘制支持向量点 plt.show()

# 非线性可分： from sklearn import datasets

# 加载数据 iris = datasets.load_iris() X = iris.data y = iris.target print iris.target_names

['setosa' 'versicolor' 'virginica'] 

from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=1/3.) # 分割训练集和测试集

from sklearn.preprocessing import StandardScaler # 标准化 scaler = StandardScaler()
X_train_std = scaler.fit_transform(X_train)
X_test_std = scaler.transform(X_test)

from sklearn.grid_search import GridSearchCV

# 交叉验证，调整参数 param_grid = {'C':[1e1,1e2,1e3, 5e3,1e4,5e4], 'gamma':[0.0001,0.0008,0.0005,0.008,0.005,]}
clf = GridSearchCV(svm.SVC(kernel='rbf',class_weight='balanced'),param_grid,cv=10)
clf = clf.fit(X_train_std,y_train) print clf.best_estimator_

SVC(C=10.0, cache_size=200, class_weight='balanced', coef0=0.0,
  decision_function_shape=None, degree=3, gamma=0.005, kernel='rbf',
  max_iter=-1, probability=False, random_state=None, shrinking=True,
  tol=0.001, verbose=False) 

clf.score(X_test_std,y_test)

1.0 

y_pred = clf.predict(X_test_std)

from sklearn.metrics import classification_report from sklearn.metrics import confusion_matrix

print(classification_report(y_test,y_pred,target_names=iris.target_names))
print(confusion_matrix(y_test,y_pred,labels=range(iris.target_names.shape[0])))

 precision    recall  f1-score   support

     setosa 1.00 1.00 1.00 18 versicolor 1.00 1.00 1.00 17 virginica 1.00 1.00 1.00 15 avg / total 1.00 1.00 1.00 50 [[18  0  0]
 [ 0 17  0]
 [ 0  0 15]] 纵坐标表示预测的是谁，横坐标表示标准的是谁。对角线的值越大，预测能力越好。