机器学习之SVM算法

SVM简介

支持向量机（support vector machines, SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；SVM还包括核技巧，这使它成为实质上的非线性分类器。SVM的的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。SVM的的学习算法就是求解凸二次规划的最优化算法。

SVM 基本概念

将实例的特征向量（以二维为例）映射为空间中的一些点，就是如下图的红色点和黄色点，它们属于不同的两类。

那么 SVM 的目的就是想要画出一条线，以“最好地”区分这两类点，以至如果以后有了新的点，这条线也能做出很好的分类。

能够画出多少条线对样本点进行区分？
线是有无数条可以画的,区别在于泛化能力。比如绿线就比其他两条线区分效果好，我们希望找到的这条效果最好的线叫作划分超平面；

为什么要叫作“超平面”呢？
因为样本的特征很可能是高维的，此时样本空间的划分就需要“超平面”；

什么才叫这条线的效果好？
SVM 将会寻找可以区分两个类别并且能使边际（margin）最大的超平面，如下图的两条虚线直接的距离叫做边际（margin），虚线是由距离中央实线最近的点所确定出来的；

为什么要让 margin 尽量大？
因为大 margin 泛化能力强；
如下图所示即为分离超平面，对于线性可分的数据集来说，这样的超平面有无穷多个（即感知机），但是几何间隔最大的分离超平面却是唯一的。

以上图为例，超平面为 $\omega x + b = 0$ ,超平面以上的数据Label为+1，超平面以下的数据Label为-1，则分类正确需要满足:
$\left\{\begin{matrix} & \frac{\omega x + b}{\left \| \omega \right \|}\geqslant d \quad \forall y^{i} = 1 & \\ & \frac{\omega x + b}{\left \| \omega \right \|}\leqslant -d \quad \forall y^{i} = -1 & \end{matrix}\right.$
不等式两边同时除一个d，又因为 $\left \| \omega \right \|*d$ 为一个大于0的数据，可以将式子化简为：
$\left\{\begin{matrix} & \omega x + b\geqslant 1 \quad \forall y^{i} = 1 & \\ & \omega x + b\leqslant -1 \quad \forall y^{i} = -1 & \end{matrix}\right.$
注意：此时的 $\omega \$ 和 b 与原有的 $\omega \$ 和 b放大了 $\left \| \omega \right \|*d$ 倍简写成 $\omega \$ 和 b，这项距离（书上一般写的是几何间隔）是不会变的，我们做出了一个强硬的化简： $y^{i}(\omega x + b) \geqslant 1$
为什么可以这样做呢？实际上我们求距离是用几何间隔，缩放函数间隔不影响几何间隔，举个例子,样本点𝑥1是离超平面最近的点 $y^{i}(\omega x_1+ b) = 5$ ,我们把 $\omega \$ 和 b同时放缩5倍， $y^{i}(\omega x + b) =1$ ，几何间隔和以前没变的一样，因为上下是同时缩放的，我们再来看看超平面 $\omega x + b = 0$ ，也没什么变化，5𝑥+5=0和𝑥+1=0还是代表同一个超平面。这样缩放后， $magin(\omega , b) = \frac{1}{\left \| \omega \right \|}$ ,参数b不见了，可以去掉b好了，最小函数间隔为1，所以约束条件也发生了变化。这样简化后，我们再来看看模型变成啥样了

$max\frac{1}{\left \| \omega \right \|}$
$s.t. \quad y^{i}(\omega x + b) \geqslant 1$
等价于最大化 $\frac{1}{\left \| \omega \right \|}$ ，也就等价于最小化 $\frac{1}{2}\left \| \omega \right \|^{2}$ ,是为了后面求导以后形式简洁，不影响结果），因此SVM模型的求解最大分割超平面问题又可以表示为以下约束最优化问题:
$min\frac{1}{2}\left \| \omega \right \|^{2}$
$s.t. \quad y^{i}(\omega x + b) \geqslant 1$

支持向量
支持向量（support vector）就是刚好贴在边际所在的平面上的点，它们是用来定义边际的，是距离划分超平面最近的点。训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。只要支持向量没变，其他的数据不影响。

左边是60个点的结果，右边的是120个点的结果

#Author:Sunshine丶天
from sklearn.datasets.samples_generator import make_blobs
from sklearn.svm import SVC
import matplotlib.pyplot as plt
import numpy as np

# 绘图函数
def plot_svc_decision_function(model, ax=None, plot_support=True):
    """Plot the decision function for a 2D SVC"""
    if ax is None:
        ax = plt.gca()
    xlim = ax.get_xlim()
    ylim = ax.get_ylim()

    # create grid to evaluate model
    x = np.linspace(xlim[0], xlim[1], 30)
    y = np.linspace(ylim[0], ylim[1], 30)
    Y, X = np.meshgrid(y, x)
    xy = np.vstack([X.ravel(), Y.ravel()]).T
    P = model.decision_function(xy).reshape(X.shape)

    # plot decision boundary and margins
    ax.contour(X, Y, P, colors='k',
               levels=[-1, 0, 1], alpha=0.5,
               linestyles=['--', '-', '--'])

    # plot support vectors
    if plot_support:
        ax.scatter(model.support_vectors_[:, 0],
                   model.support_vectors_[:, 1],
                   s=300, linewidth=1, facecolors='none')
    ax.set_xlim(xlim)
    ax.set_ylim(ylim)

def plot_svm(N=10, ax=None):
    X, y = make_blobs(n_samples=200, centers=2,
                      random_state=0, cluster_std=0.60)
    X = X[:N]
    y = y[:N]
    model = SVC(kernel='linear', C=1E10)
    model.fit(X, y)

    ax = ax or plt.gca()
    ax.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')
    ax.set_xlim(-1, 4)
    ax.set_ylim(-1, 6)
    plot_svc_decision_function(model, ax)


fig, ax = plt.subplots(1, 2, figsize=(16, 6))
fig.subplots_adjust(left=0.0625, right=0.95, wspace=0.1)
for axi, N in zip(ax, [60, 120]):
    plot_svm(N, axi)
    axi.set_title('N = {0}'.format(N))

plt.show()

软间隔
到这里都是基于训练集数据线性可分的假设下进行的，但是实际情况下几乎不存在完全线性可分的数据，为了解决这个问题，引入了“软间隔”的概念，即允许某些点不满足约束
$s.t. \quad y^{i}(\omega x + b) \geqslant 1$
采用hinge损失，将原优化问题改写为
$min\frac{1}{2}\left \| \omega \right \|^{2} + C\sum \varepsilon _{i}$
$s.t. \quad y^{i}(\omega x + b) \geqslant 1 - \varepsilon _{i}$
$\varepsilon _{i} > 0$
其中 $\varepsilon _{i}$ 为“松弛变量” $\varepsilon _{i} = max(0, 1-y^{i}(\omega x + b))$ ，即一个hinge损失函数。每一个样本都有一个对应的松弛变量，表征该样本不满足约束的程度。C > 0称为惩罚参数，C值越大，对分类的惩罚越大。跟线性可分求解的思路一致。

左边是C=10的结果，右边的是C=0.1的结果

#Author:Sunshine丶天
from sklearn.datasets.samples_generator import make_blobs
from sklearn.svm import SVC
import matplotlib.pyplot as plt
import numpy as np

# 绘图函数
def plot_svc_decision_function(model, ax=None, plot_support=True):
    """Plot the decision function for a 2D SVC"""
    if ax is None:
        ax = plt.gca()
    xlim = ax.get_xlim()
    ylim = ax.get_ylim()

    # create grid to evaluate model
    x = np.linspace(xlim[0], xlim[1], 30)
    y = np.linspace(ylim[0], ylim[1], 30)
    Y, X = np.meshgrid(y, x)
    xy = np.vstack([X.ravel(), Y.ravel()]).T
    P = model.decision_function(xy).reshape(X.shape)

    # plot decision boundary and margins
    ax.contour(X, Y, P, colors='k',
               levels=[-1, 0, 1], alpha=0.5,
               linestyles=['--', '-', '--'])

    # plot support vectors
    if plot_support:
        ax.scatter(model.support_vectors_[:, 0],
                   model.support_vectors_[:, 1],
                   s=300, linewidth=1, facecolors='none')
    ax.set_xlim(xlim)
    ax.set_ylim(ylim)

X, y = make_blobs(n_samples=100, centers=2,
                  random_state=0, cluster_std=0.8)

fig, ax = plt.subplots(1, 2, figsize=(16, 6))
fig.subplots_adjust(left=0.0625, right=0.95, wspace=0.1)

for axi, C in zip(ax, [10.0, 0.1]):
    model = SVC(kernel='linear', C=C).fit(X, y)
    axi.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')
    plot_svc_decision_function(model, axi)
    axi.scatter(model.support_vectors_[:, 0],
                model.support_vectors_[:, 1],
                s=300, lw=1, facecolors='none')
    axi.set_title('C = {0:.1f}'.format(C), size=14)

plt.show()

非线性SVM算法原理

对于输入空间中的非线性分类问题，可以通过非线性变换将它转化为某个维特征空间中的线性分类问题，在高维特征空间中学习线性支持向量机。由于在线性支持向量机学习的对偶问题里，目标函数和分类决策函数都只涉及实例和实例之间的内积，所以不需要显式地指定非线性变换，而是用核函数替换当中的内积。核函数表示，通过一个非线性转换后的两个实例间的内积。具体地， $K(x,z)$ 是一个函数，或正定核，意味着存在一个从输入空间到特征空间的映射 $\phi (x)$ ，对任意输入空间中的 $x,z$ 有 $K(x,z) = \phi (x)\phi (z)$

#Author:Sunshine丶天
import numpy as np
import matplotlib.pyplot as plt
from sklearn  import datasets
from sklearn.preprocessing import StandardScaler, PolynomialFeatures
from sklearn.svm import LinearSVC
from sklearn.pipeline import Pipeline

X, y = datasets.make_moons(noise=0.15)

def plot_decision_boundary(model, axis):
    x0, x1 = np.meshgrid(
        np.linspace(axis[0], axis[1], int(axis[1] - axis[0]*100)).reshape(-1),
        np.linspace(axis[2], axis[3], int(axis[3] - axis[2] * 100)).reshape(-1)
    )
    x_new = np.c_[x0.ravel(), x1.ravel()]

    y_predict = model.predict(x_new)
    zz = y_predict.reshape(x0.shape)

    from matplotlib.colors import ListedColormap
    custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
    plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

# 使用多项式特征svm
def PolynomialSVC(degree, C=1.0):
    return Pipeline([
        ('poly', PolynomialFeatures(degree=degree)),
        ('std_scaler', StandardScaler()),
        ('LinearSVC', LinearSVC(C=C))
    ])

# ploy_svc = PolynomialSVC(degree=3)
# ploy_svc.fit(X, y)
#
# plot_decision_boundary(ploy_svc, axis=[-1.5, 2.5, -1.0, 1.5])
# plt.scatter(X[y==0, 0], X[y==0, 1],color='red')
# plt.scatter(X[y==1, 0], X[y==1, 1],color='blue')
# plt.show()

# =====================多项式核
# from sklearn.svm import SVC

# def PolynomialKernelSVC(degree, C=1.0):
#     return Pipeline([
#         ('std_scaler', StandardScaler()),
#         ('kernelSVC',SVC(kernel='poly', degree=degree, C=C)),
#     ])
#
# ploy_kernel_svc = PolynomialKernelSVC(degree=3, C=1000)
# ploy_kernel_svc.fit(X, y)
#
# plot_decision_boundary(ploy_kernel_svc, axis=[-1.5, 2.5, -1.0, 1.5])
# plt.scatter(X[y==0, 0], X[y==0, 1],color='red')
# plt.scatter(X[y==1, 0], X[y==1, 1],color='blue')
# plt.show()


# =====================高斯核
from sklearn.svm import SVC

def RBFKernelSVC(gamma=1.0):
    return Pipeline([
        ('std_scaler', StandardScaler()),
        ('kernelSVC',SVC(kernel='rbf', gamma=gamma)),
    ])
rbfSVC = RBFKernelSVC(gamma=1.0)
rbfSVC.fit(X, y)

plot_decision_boundary(rbfSVC, axis=[-1.5, 2.5, -1.0, 1.5])
plt.scatter(X[y==0, 0], X[y==0, 1],color='red')
plt.scatter(X[y==1, 0], X[y==1, 1],color='blue')
plt.show()

参考文章：
https://zhuanlan.zhihu.com/p/31886934
https://www.cnblogs.com/fydeblog/p/9440474.html

最后编辑于：2020.04.14 12:04:22

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,324评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,303评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,192评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,555评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,569评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,566评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,927评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,583评论 0赞 257
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,827评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,590评论 2赞 320
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,669评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,365评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,941评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,928评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,159评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,880评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,399评论 2赞 342

机器学习之SVM算法

SVM简介

SVM 基本概念

非线性SVM算法原理

推荐阅读更多精彩内容