支持向量机（2）

简单的说，支持向量机就是通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。（引自刘知行）

支持向量机分类特点

假设给定一个训练数据集 $T=\lbrace(x_1,y_1),(x_2,y_2),\cdots ,(x_n,y_n)\rbrace$ 。同时，假定已经找到样本空间中的分割平面，其划分公式可以通过以下线性方程来描述： $wx+b=0\tag{1}$ 使用一条直线对线性可分数据集进行分类的过程中，我们已经知道这样的直线可能有很多条：

如何确定最优的分类方法？支持向量机给出了一种直观的方法：

图中

wx+b=0

为分割直线，我们通过这条直线将数据点分开。与此同时，分割时会在直线的两边再设立两个互相平行的虚线，这两条虚线与分割直线的距离一致。这里的距离往往也被我们称之为「间隔」，而支持向量机的分割特点在于，要使得分割直线和虚线之间的间隔最大化。同时也就是两虚线之间的间隔最大化。

对于线性可分的正负样本点而言，位于 $wx+b=1$ 虚线外的点就是正样本点，而位于 $wx+b=-1$ 虚线外的点就是负样本点。另外，正好位于两条虚线上方的样本点就被我们称为支持向量，这也就是支持向量机的名字来源。

硬间隔表示及求解

对于线性可分数据而言，几何间隔最大的分离超平面是唯一的，这里的间隔也被我们称之为「硬间隔」，而间隔最大化也就称为硬间隔最大化。上图实际上就是硬间隔的典型例子。
最大间隔分离超平面，我们希望最大化超平面 $(w,b)$ 关于训练数据集的几何间隔 $\gamma$ ，满足以下约束条件：每个训练样本点到超平面 $(w,b)$ 的几何间隔至少都是 $\gamma$ ，因此可以转化为以下的约束最优化问题：
$\max\limits_{w,b}\gamma =\frac{2}{\left \|w\right \|} \tag{2a}$ $\textrm s.t. y_i(\frac{w}{\left \|w\right \|}x_i+\frac{b}{\left \|w\right \|})\geq \frac{\gamma}{2} \tag{2b}$ 实际上， $\gamma$ 的取值并不会影响最优化问题的解，同时，我们根据数学对偶性原则，可以得到面向硬间隔的线性可分数据的支持向量机的最优化问题：
$\min\limits_{w,b}\frac{1}{2}\left \|w\right \|^2 \tag{3a}$ $\textrm s.t. y_i(wx_i+b)-1\geq 0\tag{3b}$ 我们通常使用拉格朗日乘子法来求解最优化问题，将原始问题转化为对偶问题，通过解对偶问题得到原始问题的解。对公式（3）使用拉格朗日乘子法可得到其「对偶问题」。具体来说，对每条约束添加拉格朗日乘子 $\alpha_i \geq 0$ ，则该问题的拉格朗日函数可写为：
$L(w,b,\alpha)=\frac{1}{2}\left \| w\right \|^2+\sum\limits_{i=1}^{m}\alpha_i(1-y_i(wx_i+b)) \tag{4}$ 我们通过将公式（4）分别对 $w$ 和 $b$ 求偏导为 0 并代入原式中，可以将 $w$ 和 $b$ 消去，得到公式（3）的对偶问题：
$\max\limits_{\alpha} \sum\limits_{i=1}^{N}\alpha_i-\frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_i \alpha_j y_i y_j x_i x_j$ $s.t. \sum\limits_{i=1}^{N}\alpha_i y_i=0,$ $\alpha_i \geq 0,i=1,2,\cdots,N$ 解出最优解 $\alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)$ 后，基于此我们可以求得最优解 $w^*$ , $b^*$ ，由此得到分离超平面：
$w^*x+b^*=0$ 使用符号函数求得正负类之间的分类决策函数为：
$f(x)=sign(w^*x+b^*)$

软间隔表示及求解

当数据集变成严格意义上的线性不可分，如下图所示，在实心点和空心点中各混入了零星的不同类别的「噪声」数据点，造成线性不可分的原因往往是因为包含「噪声」数据，它同样可以被看作是不严格条件下的线性可分。
当我们使用支持向量机求解这类问题时，就会把最大间隔称之为最大「软间隔」，而软间隔就意味着可以容许零星噪声数据被误分类。

当出现上图所示的样本点不是严格线性可分的情况时，某些样本点 $(x_i,y_i)$ 就不能满足函数间隔 $\geqslant 1$ 的约束条件，即公式（3b）中的约束条件。为了解决这个问题，可以对每个样本点 $(x_i,y_i)$ 引入一个松弛变量 $\xi_i \geq 0$ ，使得函数间隔加上松弛变量 $\geqslant 1$ ，即约束条件转化为：
$y_i(wx_i+b) \geq 1-\xi_i$ 同时，对每个松弛变量 $\xi_i$ 支付一个代价 $\xi_i$ ，目标函数由原来的 $\frac{1}{2}||w||^2$ 变成：
$\frac{1}{2}\left \| w \right \|^2+C\sum\limits_{j=1}^{N}\xi_i$ 这里， $C>0$ 称为惩罚参数，一般根据实际情况确定。 $C$ 值越大对误分类的惩罚增大，最优化问题即为：
$\min\limits_{w,b,\xi} \frac{1}{2}\left \| w \right \|^2+C\sum\limits_{i=1}^{N}\xi_i$ $s.t. y_i(wx_i+b) \geq 1-\xi_i,i=1,2,...,N$ $\xi_i\geq 0,i=1,2,...,N$ 这就是软间隔支持向量机的表示过程。同理，我们可以使用拉格朗日乘子法将其转换为对偶问题求解：
$\max\limits_{\alpha} \frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i*x_j)-\sum\limits_{i=1}^{N}\alpha_i$ $s.t. \sum\limits_{i=1}^{N}\alpha_iy_i=0$ $0 \leq \alpha_i \leq C ,i=1,2,...,N$ 解出最优解 $\alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)$ 后，基于此我们可以求得最优解 $w^*$ , $b^*$ ，由此得到分离超平面：
$w^*x+b^*=0$ 使用符号函数求得正负类之间的分类决策函数为：
$f(x)=sign(w^*x+b^*)$

非线性分类支持向量机

对于线性不可分的数据集，我们也可以通过支持向量机去完成分类。但是需要通过一些方法把线性不可分数据转换为线性可分数据之后，再完成分类。

我们把这种数据转换的方法称作「核技巧」，实现数据转换的函数称之为「核函数」。

核技巧与核函数

核技巧的关键在于空间映射，即将低维数据映射到高维空间中，使得数据集在高维空间能被线性可分。
如上图所示，假设我们在二维空间中有蓝色和红色代表的两类数据点，很明显无法使用一条直线把这两类数据分开。此时，如果我们使用核技巧将其映射到三维空间中，就变成了可以被平面线性可分的状态。

对于「映射」过程，我们还可以这样理解：分布在二维桌面上的红蓝小球无法被线性分开，此时将手掌拍向桌面（好疼），小球在力的作用下跳跃到三维空间中，这也就是一个直观的映射过程。
同时，「映射」的过程也就是通过核函数转换的过程。这里需要补充说明一点，那就是将数据点从低维度空间转换到高维度空间的方法有很多，但往往涉及到庞大的计算量，而数学家们从中发现了几种特殊的函数，这类函数能大大降低计算的复杂度，于是被命名为「核函数」。也就是说，核技巧是一种特殊的「映射」技巧，而核函数是核技巧的实现方法。

几种常见的核函数：

线性核函数(linear)
$k\left ( x_i, x_j \right )=x_i*x_j$
多项式核函数(poly)
$k\left ( x_i, x_j \right )=\left ( x_i*x_j \right )^d, d \geq 1$
高斯径向基核函数(rbf)
$k\left ( x_i, x_j \right ) = \exp \left(-{\frac {\left \|{\mathbf {x_i}}-{\mathbf {x_j}}\right \|_{2}^{2}}{2\sigma ^{2}}}\right)=exp\left ( -\gamma * \left \| x_i-x_j \right \|_{2} ^2 \right ), \gamma>0$
Sigmoid 核函数
$k\left ( x_i, x_j \right )=tanh\left ( \beta * x_ix_j+\theta \right ), \beta > 0 , \theta < 0$

此外，核函数还可以通过函数组合得到，例如：
若 $k_1$ 和 $k_2$ 是核函数，那么对于任意正数 $\lambda_1,\lambda_2$ ，其线性组合：
$\lambda_1 k_1+\lambda_2 k_2$

引入核函数的间隔表示及求解

我们通过直接引入核函数 $k(x_i,x_j)$ ，而不需要显式的定义高维特征空间和映射函数，就可以利用解线性分类问题的方法来求解非线性分类问题的支持向量机。引入核函数以后，对偶问题就变为：
$\max\limits_{\alpha} \frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_i\alpha_jy_iy_jk(x_i*x_j)-\sum\limits_{i=1}^{N}\alpha_i$ $s.t. \sum\limits_{i=1}^{N}\alpha_iy_i=0$ $0 \leq \alpha_i \leq C ,i=1,2,...,N$ 同样，解出最优解 $\alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)$ 后，基于此我们可以求得最优解 $w^*$ , $b^*$ ，由此得到分离超平面：
$w^*x+b^*=0$ 使用符号函数求得正负类之间的分类决策函数为：
$f(x)=sign(w^*x+b^*)$

scikit-learn SVC分类器

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

主要参数说明：

C: 软间隔支持向量机对应的惩罚参数，C越大，相当于惩罚松弛变量，希望松弛变量接近0，即对误分类的惩罚增大，趋向于对训练集全分对的情况，这样对训练集测试时准确率很高，但泛化能力弱。C值小，对误分类的惩罚减小，允许容错，将他们当成噪声点，泛化能力较强。
kernel: linear, poly, rbf, sigmoid等核函数，默认为rbf
degree: poly 多项式核函数的指数（维度），默认是3，选择其他核函数时会被忽略
gamma: ‘rbf’,‘poly’ 和‘sigmoid’的核函数参数。默认是’auto’，则会选择1/n_features
coef0: 核函数的常数项。对于‘poly’和 ‘sigmoid’有用。
probability: 是否采用概率估计？.默认为False
shrinking: 是否采用shrinking heuristic方法，默认为true
tol: 收敛停止的容许误差值大小，默认为1e-3
cache_size: 核函数cache缓存大小，默认为200
class_weight: 类别的权重，字典形式传递。设置第几类的参数C为weight * C(C-SVC中的C)
verbose: 允许冗余输出
max_iter: 最大迭代次数。-1为无限制。
decision_function_shape: ‘ovo’, ‘ovr’ or None, default=None3
random_state: 数据洗牌时的种子值，int值

最后编辑于：2019.02.09 16:28:39

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