[深度学习]Part2 支持向量机（SVM）Ch09-2—

本文主要是介绍[深度学习]Part2 支持向量机（SVM）Ch09-2——【DeepBlue学习笔记】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文仅供学习使用
本章需要提前学习拉格朗日乘子法、KKT条件、原问题与对偶问题（优化方法）

支持向量机（SVM）Ch09-2

- 1.4 SMO
- 1.5 SVR
2. scitit-learn SVM算法库概述
- 2.1 分类算法——SVC
- 2.2 回归算法
3. 核方法

线性核SVM迄今仍是文本分类的首选技术——若将每个单词作为文本数据的一个属性，则该属性空间维度很高，冗余度很大，其描述能力足以将不同文档打散。
支持向量机的求解通常是借助于凸优化技术
支持向量机是针对二分类任务设计的，对多分类任务要进行专门的推广
· 核函数直接决定了支持向量机与核方法的最终性能，但遗憾的是，核函数的选择是一个未决问题。 多核学习（mutliple kernel learning）使用多个核函数并通过学习获得其最优凸组合作为最终的核函数——集成学习机制
损失函数在机器学习中被广泛使用，但通过求解替代损失函数得到的是否仍是原问题的解？这在理论上称为替代损失的一致性（consistency）问题（亦称相合性），前人已给出了基于替代损失进行经验风险最小化的一致性充要条件。

1.4 SMO

序列最小优化算法(Sequential minimal optimization, SMO)是一种用于解决SVM训练过程中所产生的优化问题的算法，于1998年由John Platt发明。

先固定βi之外的所有参数，然后求βi上的极值。由于存在约束 $\sum\limits_{i=1}^{m}{{{\beta }_{i}}{{y}_{i}}}=0$ ，若固定βi之外的其他变量，则βi可由其他变量导出。于是，SMO每次选择两个变量βi和βj，并固定其他参数，这样，在参数初始化后，SMO不断执行直至收敛——SMO先选取违背KKT条件程度最大的变量，第二个变量选择一个使目标函数值增长最快的变量。——启发式：使选取的两变量所对应样本之间的间隔最大。

假定存在一个β*=(β1,β2,…,βm)是我们最终的最优解，那么根据KKT条件我们可以计算出w和b的最优解，如下： $w=\sum\limits_{i=1}^{m}{{{\beta }_{i}}{{y}^{(i)}}{{x}^{(i)}}},b=y-\sum\limits_{i=1}^{m}{{{\beta }_{i}}{{y}^{(i)}}K({{x}^{(i)}},x)}$
进而我们可以得到最终的分离超平面为: $g(x)=wx+b=\sum\limits_{i=1}^{m}{{{\beta }_{i}}{{y}^{(i)}}K({{x}^{(i)}},x)}+b$
拉格朗日乘子法和KKT的对偶互补条件为： ${{\beta }_{i}}({{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)-1+{{\xi }_{i}})=0,{{\mu }_{i}}{{\xi }_{i}}=0$
β、μ和C之间的关系为： $C+{{\beta }_{i}}-{{\mu }_{i}}=0$
根据这个对偶互补条件，我们有如下关系式：
$\begin{matrix} {{\beta }_{i}}=0\Rightarrow {{\mu }_{i}}>0\Rightarrow {{\xi }_{i}}=0\Rightarrow {{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)>1 \\ 0<{{\beta }_{i}}<C\Rightarrow {{\mu }_{i}}>0\Rightarrow {{\xi }_{i}}=0\Rightarrow {{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)=1 \\ {{\beta }_{i}}=C\Rightarrow {{\mu }_{i}}=0\Rightarrow {{\xi }_{i}}>0\Rightarrow {{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)<1 \\ \end{matrix}\Rightarrow {{y}^{(i)}}g({{x}^{(i)}})=\left\{ \begin{matrix}>1,\{({{x}^{(i)}},{{y}^{(i)}})|{{\beta }_{i}}=0\} \\ =1,\{({{x}^{(i)}},{{y}^{(i)}})|0<{{\beta }_{i}}<C\} \\ <1,\{({{x}^{(i)}},{{y}^{(i)}})|{{\beta }_{i}}=C\} \\ \end{matrix} \right.$
也就是说我们找出的最优的分割超平面必须满足下列的目标条件(g(x)):
${{y}^{(i)}}g({{x}^{(i)}})=\left\{ \begin{matrix}>1,\{({{x}^{(i)}},{{y}^{(i)}})|{{\beta }_{i}}=0\} \\ =1,\{({{x}^{(i)}},{{y}^{(i)}})|0<{{\beta }_{i}}<C\} \\ <1,\{({{x}^{(i)}},{{y}^{(i)}})|{{\beta }_{i}}=C\} \\ \end{matrix} \right.$
拉格朗日对偶化要求的两个限制的初始条件为：
$\sum\limits_{i=1}^{m}{{{\beta }_{i}}{{y}^{(i)}}}=0,0\le {{\beta }_{i}}\le C,i=1,2,...,m$
从而可以得到解决问题的思路如下：

首先，初始化后一个β值，让它满足对偶问题的两个初始限制条件；
然后不断优化这个β值，使得由它确定的分割超平面满足g(x)目标条件；而且在优化过程中，始终保证β值满足初始限制条件。
备注：这个求解过程中，和传统的思路不太一样，不是对目标函数求最小值，而是让g(x)目标条件尽可能的满足。

在这样一个过程中，到底如何优化这个β值呢？整理可以发现β值的优化必须遵循以下两个基本原则：

每次优化的时候，必须同时优化β的两个分量；因为如果只优化一个分量的话，新的β值就没法满足初始限制条件中的等式约束条件了。
每次优化的两个分量应该是违反g(x)目标条件比较多的。也就是说，本来应当是大于等于1的，越是小于1违反g(x)目标条件就越多。

或者换一种思路来理解，因为目标函数中存在m个变量，直接优化比较难，利用启发式的方法/EM算法的思想，每次优化的时候，只优化两个变量，将其它的变量看成常数项，这样SMO算法就将一个复杂的优化算法转换为一个比较简单的两变量优化问题了。

认为β1、β2是变量，其它β值是常量，从而将目标函数转换如下(C是常数项)：
$\left\{ \begin{matrix} \underset{{{\beta }_{1}},{{\beta }_{2}}}{\mathop{\min }}\,\frac{1}{2}{{K}_{11}}{{\beta }_{1}}^{2}+\frac{1}{2}{{K}_{22}}{{\beta }_{2}}^{2}+{{K}_{12}}{{y}^{(1)}}{{y}^{(2)}}{{\beta }_{1}}{{\beta }_{2}}-{{\beta }_{1}}-{{\beta }_{2}}+{{y}^{(1)}}{{\beta }_{1}}\sum\limits_{i=3}^{m}{{{y}^{(i)}}{{\beta }_{i}}{{K}_{i1}}}+{{y}^{(2)}}{{\beta }_{2}}\sum\limits_{i=3}^{m}{{{y}^{(i)}}{{\beta }_{i}}{{K}_{i2}}}+C \\ s.t:{{\beta }_{1}}{{y}^{(1)}}+{{\beta }_{2}}{{y}^{(2)}}=-\sum\limits_{i=3}^{m}{{{\beta }_{i}}{{y}^{(i)}}=k,0<{{\beta }_{i}}<C,i=1,2} \\ \end{matrix} \right.$
由于 ${{\beta }_{1}}{{y}^{(1)}}+{{\beta }_{2}}{{y}^{(2)}}=k$ ，并且 ${{y}^{(2)}}=1$ ，也就是我们使用β2来表示β1的值：
将上式带入目标优化函数，就可以消去β1，从而只留下仅仅包含β2的式子。令： ${{v}_{j}}=\sum\limits_{i=3}^{m}{{{y}^{(i)}}{{\beta }_{i}}{{K}_{i1}}}$
$W({{\beta }_{2}})=\frac{1}{2}{{K}_{11}}{{(k-{{\beta }_{2}}{{y}^{(2)}})}^{2}}+\frac{1}{2}{{K}_{22}}{{\beta }_{2}}^{2}+{{K}_{12}}{{y}^{(2)}}(k-{{\beta }_{2}}{{y}^{(2)}}){{\beta }_{2}}-{{y}^{(1)}}(k-{{\beta }_{2}}{{y}^{(2)}})-{{\beta }_{2}}+(k-{{\beta }_{2}}{{y}^{(2)}}){{v}_{1}}+{{y}^{(2)}}{{\beta }_{2}}{{v}_{2}}$
求解β2的值：
$\frac{\partial W}{\partial {{\beta }_{2}}}={{K}_{11}}{{\beta }_{2}}-{{K}_{11}}k{{y}^{(2)}}+{{K}_{22}}{{\beta }_{2}}+{{K}_{12}}k{{y}^{(2)}}-2{{K}_{12}}{{\beta }_{2}}+{{y}^{(1)}}{{y}^{(2)}}-1-{{y}^{(2)}}{{v}_{1}}+{{y}^{(2)}}{{v}_{2}}\overset{\frac{\partial W}{\partial {{\beta }_{2}}}=0}{\mathop{\to }}\,$
$({{K}_{11}}+{{K}_{22}}-2{{K}_{12}}){{\beta }_{2}}={{y}^{(2)}}({{y}^{(2)}}-{{y}^{(1)}}+k{{K}_{11}}-k{{K}_{12}}+{{v}_{1}}-{{v}_{1}})={{y}^{(2)}}({{y}^{(2)}}-{{y}^{(1)}}+k{{K}_{11}}-k{{K}_{12}}+(g({{x}_{1}})-\sum\limits_{i=1}^{2}{{{\beta }_{i}}{{y}^{(i)}}{{K}_{i1}}}-b)-(g({{x}_{2}})-\sum\limits_{i=1}^{2}{{{\beta }_{i}}{{y}^{(i)}}{{K}_{i2}}}-b))$
$\overset{{{\beta }_{1}}{{y}^{(1)}}+{{\beta }_{2}}{{y}^{(2)}}=k}{\mathop{\to }}\,({{K}_{11}}+{{K}_{22}}-2{{K}_{12}}){{\beta }_{2}}={{y}^{(2)}}({{y}^{(2)}}-{{y}^{(1)}}+{{\beta }_{1}}^{old}{{y}^{(1)}}{{K}_{11}}+{{\beta }_{2}}^{old}{{y}^{(2)}}{{K}_{11}}-{{\beta }_{1}}^{old}{{y}^{(1)}}{{K}_{12}}-{{\beta }_{2}}^{old}{{y}^{(2)}}{{K}_{12}})+{{y}^{(2)}}(g({{x}_{1}})-\sum\limits_{i=1}^{2}{{{\beta }_{i}}{{y}^{(i)}}{{K}_{i1}}}-b)-{{y}^{(2)}}(g({{x}_{2}})-\sum\limits_{i=1}^{2}{{{\beta }_{i}}{{y}^{(i)}}{{K}_{i2}}}-b)$
$={{y}^{(2)}}(({{K}_{11}}+{{K}_{22}}-2{{K}_{12}}){{\beta }_{2}}^{old}{{y}^{(2)}}+{{y}^{(2)}}-{{y}^{(1)}}+g({{x}^{(1)}})-g({{x}^{(2)}}))=({{K}_{11}}+{{K}_{22}}-2{{K}_{12}}){{\beta }_{2}}^{old}+{{y}^{(2)}}((g({{x}^{(1)}})-{{y}^{(1)}})-(g({{x}^{(2)}})-{{y}^{(2)}}))$
$({{K}_{11}}+{{K}_{22}}-2{{K}_{12}}){{\beta }_{2}}=({{K}_{11}}+{{K}_{22}}-2{{K}_{12}}){{\beta }_{2}}^{old}+{{y}^{(2)}}((g({{x}^{(1)}})-{{y}^{(1)}})-(g({{x}^{(2)}})-{{y}^{(2)}}))\overset{{{E}_{i}}=g({{x}^{(i)}})-{{y}^{(i)}}}{\mathop{\to }}\,{{\beta }_{2}}^{new,unt}={{\beta }_{2}}={{\beta }_{2}}^{old}+\frac{{{y}^{(2)}}({{E}_{1}}-{{E}_{3}})}{{{K}_{11}}+{{K}_{22}}-2{{K}_{12}}}$
考虑β1和β2的取值限定范围，假定新求出来的β值是满足我们的边界限制的，即： $L\le {{\beta }_{2}}^{new}\le H$
当y1=y2的时候，β1+β2=k；由于β的限制条件，我们可以得到：
$\left\{ \begin{matrix} 0\le k-{{\beta }_{2}}^{new}\le C \\ 0\le {{\beta }_{2}}^{new}\le C \\ \end{matrix} \right.\Rightarrow \left\{ \begin{matrix} L=\max (0,{{\beta }_{2}}^{old}+{{\beta }_{1}}^{old}-C) \\ L=\min (C,{{\beta }_{2}}^{old}+{{\beta }_{1}}^{old}) \\ \end{matrix} \right.$
当y1≠y2的时候，β1-β2=k；由于β的限制条件，我们可以得到：
$\left\{ \begin{matrix} 0\le k+{{\beta }_{2}}^{new}\le C \\ 0\le {{\beta }_{2}}^{new}\le C \\ \end{matrix} \right.\Rightarrow \left\{ \begin{matrix} L=\max (0,{{\beta }_{2}}^{old}-{{\beta }_{1}}^{old}) \\ L=\min (C,C+{{\beta }_{2}}^{old}-{{\beta }_{1}}^{old}) \\ \end{matrix} \right.$
结合β的取值限制范围以及函数W的β最优解，我们可以得带迭代过程中的最优解为：
${{\beta }_{2}}^{new}=\left\{ \begin{matrix} H;{{\beta }_{2}}^{new,unt}>H \\ {{\beta }_{2}}^{new,unt};L\le {{\beta }_{2}}^{new}\le H \\ L;{{\beta }_{2}}^{new,unt}<L \\ \end{matrix} \right.$
然后根据β1和β2的关系，从而可以得到迭代后的β1的值：
${{\beta }_{1}}^{old}{{y}^{(1)}}+{{\beta }_{2}}^{old}{{y}^{(2)}}={{\beta }_{1}}^{new}{{y}^{(1)}}+{{\beta }_{2}}^{new}{{y}^{(2)}}\Rightarrow {{\beta }_{1}}^{new}={{\beta }_{1}}^{old}+{{y}^{(1)}}{{y}^{(2)}}({{\beta }_{2}}^{old}-{{\beta }_{2}}^{new})$

可以发现SMO算法中，是选择两个合适的β变量做迭代，其它变量作为常量来进行优化的一个过程，那么这两个变量到底怎么选择呢???

每次优化的时候，必须同时优化β的两个分量；因为如果只优化一个分量的话，新的β值就没法满足初始限制条件中的等式约束条件了。
每次优化的两个分量应该是违反g(x)目标条件比较多的。也就是说，本来应当是大于等于1的，越是小于1违反g(x)目标条件就越多。

第一个β变量的选择：
SMO算法在选择第一个β变量的时候，需要选择在训练集上违反KKT条件最严重的样本点。一般情况下，先选择0<β<C的样本点(即支持向量)，只有当所有的支持向量都满足KKT条件的时候，才会选择其它样本点。因为此时违反KKT条件越严重，在经过一次优化后，会让变量β尽可能的发生变化，从而可以以更少的迭代次数让模型达到g(x)目标条件。
${{y}^{(i)}}g({{x}^{(i)}})=\left\{ \begin{matrix}>1,\{({{x}^{(i)}},{{y}^{(i)}})|{{\beta }_{i}}=0\} \\ =1,\{({{x}^{(i)}},{{y}^{(i)}})|0<{{\beta }_{i}}<C\} \\ <1,\{({{x}^{(i)}},{{y}^{(i)}})|{{\beta }_{i}}=C\} \\ \end{matrix} \right.$

第二个β变量的选择：
在选择第一个变量β1后，在选择第二个变量β2的时候，希望能够按照优化后的β1和β2有尽可能多的改变来选择，也就是说让 |E1-E2| 足够的大，当E1为正的时候，选择最小的Ei作为E2；当E1为负的时候，选择最大的Ei作为E2。
备注：如果选择的第二个变量不能够让目标函数有足够的下降，那么可以通过遍历所有样本点来作为β2，直到目标函数有足够的下降，如果都没有足够的下降的话，那么直接跳出循环，重新选择β1；

计算阈值b和差值Ei：

在每次完成两个β变量的优化更新之后，需要重新计算阈值b和差值Ei。当 $0<{{\beta }_{1}}^{new}<C$ 时，有： ${{y}^{(1)}}-\sum\limits_{i=1}^{m}{{{\beta }_{i}}{{y}^{(i)}}{{K}_{i1}}}-{{b}_{1}}=0$
化简可得：
${{b}_{1}}^{new}={{y}^{(1)}}-\sum\limits_{i=3}^{m}{{{\beta }_{i}}{{y}^{(i)}}{{K}_{i1}}}-{{\beta }_{1}}^{new}{{y}^{(1)}}{{K}_{11}}-{{\beta }_{2}}^{new}{{y}^{(2)}}{{K}_{12}}$
$\therefore {{E}_{1}}=g({{x}^{(1)}})-{{y}^{(1)}}=\sum\limits_{i=3}^{m}{{{\beta }_{i}}{{y}^{(i)}}{{K}_{i1}}}+{{\beta }_{1}}^{old}{{y}^{(1)}}{{K}_{11}}+{{\beta }_{2}}^{old}{{y}^{(2)}}{{K}_{12}}+{{b}^{old}}-{{y}^{(1)}}$
$\therefore {{b}_{1}}^{new}=-{{E}_{1}}-{{y}^{(1)}}{{K}_{11}}({{\beta }_{1}}^{new}-{{\beta }_{1}}^{old})-{{y}^{(2)}}{{K}_{12}}({{\beta }_{2}}^{new}-{{\beta }_{2}}^{old})+{{b}^{old}}$
同样的当β2的取值为: 0<β2<C的时候，我们也可以得到
$\therefore {{b}_{2}}^{new}=-{{E}_{2}}-{{y}^{(1)}}{{K}_{12}}({{\beta }_{1}}^{new}-{{\beta }_{1}}^{old})-{{y}^{(2)}}{{K}_{22}}({{\beta }_{2}}^{new}-{{\beta }_{2}}^{old})+{{b}^{old}}$
最终计算出来的b为： ${{b}^{new}}=\frac{{{b}_{1}}^{new}+{{b}_{2}}^{new}}{2}$
当更新计算阈值b后，就可以得到差值Ei为：
${{E}_{i}}=g({{x}^{(i)}})-{{y}^{(i)}}=\sum\limits_{j=3}^{m}{{{\beta }_{j}}{{y}^{(j)}}{{K}_{ij}}}+{{\beta }_{1}}^{old}{{y}^{(1)}}{{K}_{11}}+{{\beta }_{2}}^{old}{{y}^{(2)}}{{K}_{12}}+{{b}^{new}}-{{y}^{(1)}}$

输入线性可分的m个样本数据{(x1,y1),(x2,y2),…,(xm,ym)}，其中x为n维的特征向量，y为二元输出，取值为+1或者-1；精度为e。

取初值β0=0，k=0；
选择需要进行更新的两个变量: β1k和β2k，计算出来新的β2new,unt；
${{\beta }_{2}}^{new,unt}={{\beta }_{2}}^{k}+\frac{{{y}^{(2)}}({{E}_{1}}-{{E}_{2}})}{{{K}_{11}}+{{K}_{22}}-2{{K}_{12}}}$
按照下列式子求出具体的β2k+1;
${{\beta }_{2}}^{k+1}=\left\{ \begin{matrix} H;{{\beta }_{2}}^{new,unt}>H \\ {{\beta }_{2}}^{new,unt};L\le {{\beta }_{2}}^{new}\le H \\ L;{{\beta }_{2}}^{new,unt}<L \\ \end{matrix} \right.$
按照β1k和β2k的关系，求出β1k+1的值： ${{\beta }_{1}}^{k+1}={{\beta }_{1}}^{k}+{{y}^{(1)}}{{y}^{(2)}}({{\beta }_{2}}^{k}-{{\beta }_{2}}^{k+1})$
按照公式计算bk+1和Ei的值：
${{b}^{new}}=\frac{{{b}_{1}}^{new}+{{b}_{2}}^{new}}{2}$
${{E}_{i}}=g({{x}^{(i)}})-{{y}^{(i)}}=\sum\limits_{j=3}^{m}{{{\beta }_{j}}{{y}^{(j)}}{{K}_{ij}}}+{{\beta }_{1}}^{old}{{y}^{(1)}}{{K}_{11}}+{{\beta }_{2}}^{old}{{y}^{(2)}}{{K}_{12}}+{{b}^{new}}-{{y}^{(1)}}$
检查函数y(i)*Ei的绝对值是否在精度范围内，并且求解出来的β解满足KKT相关约束条件，那么此时结束循环，返回此时的β解即可，否则继续迭代计算β2new,unt的值。

1.5 SVR

支持向量回归（Support Vector Regression.简称SVR）假设能容忍的f(x)与y之间最多有 $\varepsilon$ 的偏差，当且仅当f(x)与y之间的差别绝对值大于 $\varepsilon$ 时才计算损失——相当于以f(x)为中心，构建了一个宽度为 $2\varepsilon$ 的间隔带，若训练样本落入此间隔带，则被认为预测正确。
在这里插入图片描述

SVM和决策树一样，可以将模型直接应用到回归问题中；在 SVM的分类模型 (SVC) 中，目标函数和限制条件如下：
$\left\{ \begin{matrix} \underset{w,b}{\mathop{\min }}\,\frac{1}{2}\left\| w \right\|_{2}^{2}+C\sum\limits_{i=1}^{m}{{{\xi }_{i}}} \\ s.t:{{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)\ge 1-{{\xi }_{i}},{{\xi }_{i}}\ge 0,i=1,2,...,m \\ \end{matrix} \right.$
在SVR中，目的是为了尽量拟合一个线性模型y=wx+b；从而我们可以定义常量eps>0，对于任意一点(x,y)，如果|y-wx-b|≤eps，那么认为没有损失—— $\varepsilon$ -不敏感损失($\varepsilon$-insensitive loss)函数:
${{\ell }_{\varepsilon }}(z)=\left\{ \begin{matrix} 0 & if\text{ }|z|\le \varepsilon \\ |z|-\varepsilon & otherwise \\ \end{matrix} \right.$

在这里插入图片描述

从而我们可以得到目标函数和限制条件如下：
$\left\{ \begin{matrix} \underset{w,b}{\mathop{\min }}\,\frac{1}{2}\left\| w \right\|_{2}^{2} \\ s.t:|{{y}^{(i)}}-{{w}^{T}}{{x}^{(i)}}-b|\le \varepsilon ,i=1,2,...,m \\ \end{matrix} \right.$
加入松弛因子ξ>0，从而我们的目标函数和限制条件变成：——间隔带两侧的松弛程度可以不同
$\left\{ \begin{matrix} \underset{w,b}{\mathop{\min }}\,\frac{1}{2}\left\| w \right\|_{2}^{2}+C\sum\limits_{i=1}^{m}{({{\xi }_{i}}^{\vee }+{{\xi }_{i}}^{\wedge })} \\ s.t:-\varepsilon +{{\xi }_{i}}^{\vee }\le {{y}^{(i)}}-{{w}^{T}}{{x}^{(i)}}-b\le \varepsilon +{{\xi }_{i}}^{\wedge },{{\xi }_{i}}^{\vee }\ge 0,{{\xi }_{i}}^{\wedge }\ge 0,i=1,2,...,m \\ \end{matrix} \right.$
构造拉格朗日函数：
$L(w,b,{{\xi }^{\vee }},{{\xi }^{\wedge }},{{\beta }^{\vee }},{{\beta }^{\wedge }},{{\mu }^{\vee }},{{\mu }^{\wedge }})=\frac{1}{2}\left\| w \right\|_{2}^{2}+C\sum\limits_{i=1}^{m}{({{\xi }_{i}}^{\vee }+{{\xi }_{i}}^{\wedge })}+\sum\limits_{i=1}^{m}{{{\beta }_{i}}^{\vee }(-\varepsilon -{{\xi }_{i}}^{\vee }-{{y}^{(i)}}+{{w}^{T}}{{x}^{(i)}}+b)}+\sum\limits_{i=1}^{m}{{{\beta }_{i}}^{\wedge }(-\varepsilon -{{\xi }_{i}}^{\wedge }+{{y}^{(i)}}-{{w}^{T}}{{x}^{(i)}}-b)}-\sum\limits_{i=1}^{m}{{{\mu }_{i}}^{\vee }{{\xi }_{i}}^{\vee }}-\sum\limits_{i=1}^{m}{{{\mu }_{i}}^{\wedge }{{\xi }^{\wedge }}}$
$s.t:{{\beta }_{i}}^{\vee },{{\beta }_{i}}^{\wedge },{{\mu }_{i}}^{\vee },{{\mu }_{i}}^{\wedge }\ge 0,i=1,2,...,m$
拉格朗日函数对偶化：
$\underset{w,b,{{\xi }^{\vee }},{{\xi }^{\wedge }}}{\mathop{\min }}\,\underset{{{\beta }^{\vee }},{{\beta }^{\wedge }},{{\mu }^{\vee }},{{\mu }^{\wedge }}}{\mathop{\max }}\,L(w,b,{{\xi }^{\vee }},{{\xi }^{\wedge }},{{\beta }^{\vee }},{{\beta }^{\wedge }},{{\mu }^{\vee }},{{\mu }^{\wedge }})\Leftrightarrow \underset{{{\beta }^{\vee }},{{\beta }^{\wedge }},{{\mu }^{\vee }},{{\mu }^{\wedge }}}{\mathop{\max }}\,\underset{w,b,{{\xi }^{\vee }},{{\xi }^{\wedge }}}{\mathop{\min }}\,L(w,b,{{\xi }^{\vee }},{{\xi }^{\wedge }},{{\beta }^{\vee }},{{\beta }^{\wedge }},{{\mu }^{\vee }},{{\mu }^{\wedge }})$
首先来求优化函数对于w、b、ξ的极小值，通过求导可得：
$\frac{\partial L}{\partial w}=0\Rightarrow w=\sum\limits_{i=1}^{m}{({{\beta }_{i}}^{\wedge }-{{\beta }_{i}}^{\vee }){{x}^{(i)}}}$
$\frac{\partial L}{\partial b}=0\Rightarrow \sum\limits_{i=1}^{m}{({{\beta }_{i}}^{\wedge }-{{\beta }_{i}}^{\vee })}=0$
$\frac{\partial L}{\partial {{\xi }_{i}}^{\vee }}=0\Rightarrow C-{{\beta }_{i}}^{\vee }-{{\mu }_{i}}^{\vee }=0$
$\frac{\partial L}{\partial {{\xi }_{i}}^{\wedge }}=0\Rightarrow C-{{\beta }_{i}}^{\wedge }-{{\mu }_{i}}^{\wedge }=0$
将w、b、ξ的值带入函数L中，就可以将L转换为只包含β的函数，从而我们可以得到最终的优化目标函数为(备注：对于β的求解照样可以使用SMO算法来求解)
$\underset{{{\beta }^{\vee }},{{\beta }^{\wedge }}}{\mathop{\min }}\,\frac{1}{2}\sum\limits_{i=1,j=1}^{m}{({{\beta }_{i}}^{\wedge }-{{\beta }_{i}}^{\vee })({{\beta }_{j}}^{\wedge }-{{\beta }_{j}}^{\vee }){{K}_{ij}}}+\sum\limits_{i=1}^{m}{(\varepsilon -{{y}^{(i)}}){{\beta }_{i}}^{\wedge }+(\varepsilon +{{y}^{(i)}}){{\beta }_{i}}^{\vee }}$
$s.t:\sum\limits_{i=1}^{m}{({{\beta }_{i}}^{\wedge }-{{\beta }_{i}}^{\vee })}=0,0<{{\beta }_{i}}^{\wedge },{{\beta }_{i}}^{\vee }<C,i=1,2,...,m$

2. scitit-learn SVM算法库概述

scikit-learn中SVM的算法库主要分为两类，一类是分类算法，包括：SVC、NuSVC和LinearSVC这三个类，另外一类是回归算法，包括：SVR、NuSVR和LinearSVR这三个类；除此之外，用的比较多的SVM模型还有OneClassSVM类(主要功能是：异常点检测)。
详见：http://scikit-learn.org/0.18/modules/classes.html#module- sklearn.svm
在这里插入图片描述

2.1 分类算法——SVC

在这里插入图片描述

OneClassSVM是一种异常点检测的算法，算法原理：先使用SVM算法，对正常数据进行模型训练，找出正常数据的数据特性(eg: 数据集中在哪儿？)，也就是找出数据中分割面(也就是正常数据的边界)，以边界作为算法找到的支持向量。预测的时候，如果样本点落在支持向量内部，那就认为属于正常样本，否则就认为属于异常样本。
在这里插入图片描述

不同分类器比较：

import numpy as np
import pandas as pd
from sklearn.svm import SVC, SVR
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier  ##KNN
from sklearn.linear_model import LogisticRegression  ##逻辑回归
from sklearn.ensemble import RandomForestClassifier
import matplotlib.pyplot as plt
import matplotlib as mplimport time
# time.perf_counter()  # 返回系统运行时间
# time.process_time()  # 返回进程运行时间import warningswarnings.filterwarnings('ignore')data = pd.read_csv('D:\datas\iris.data', header=None)
# print(data.head())
X = data.iloc[:, :2]
Y = data.iloc[:, -1]x_train, x_test, y_train, y_test = train_test_split(X, Y, test_size=0.2, random_state=10)svc = SVC(C=0.2, kernel="rbf",decision_function_shape="ovr")
knn = KNeighborsClassifier(n_neighbors=5)
log = LogisticRegression()
rand = RandomForestClassifier(n_estimators=150, max_depth=3)
models = np.array([svc, knn, log, rand])
T = []
train_scores = []
test_scores = []
for i in models:N = time.process_time()i.fit(x_train, y_train)M = time.process_time()T.append(M - N)train_scores.append(i.score(x_train, y_train))test_scores.append(i.score(x_test, y_test))plt.figure(num=1)
plt.plot(['01svc', '02knn', '03log', '04rand'], test_scores, 'r-', label='test_score')
plt.plot(['01svc', '02knn', '03log', '04rand'], train_scores, 'g-o', label='train_score')
plt.ylim(0.5, 1.01)
plt.figure(num=2)
plt.plot(['01svc', '02knn', '03log', '04rand'], T, label='time')
plt.show()

在这里插入图片描述
通过设置 kernel参数的值来选择想用的核函数。一旦选择了一个核函数，就需要为这个核函数确定一些合适的选项值。在训练模型时，大部分情况下需要把这些参数视作超参数，然后用模型选择的技术找出能产生性能最佳的模型的参数值组合。

训练一个线性分类器

from sklearn.svm import LinearSVC
from sklearn.precrocessing import StandardScaler
标准化特征：scaler = StandardScaler()
features_standardized = scaler.fit_transform(features)
创建支持向量分类器：svc = LinearSVC(C=1.0)
训练模型：model = svc.fit(features_standardized, target)
可视化：from matplotlib import pyplot as plt
画出样本点，并根据分类上色：
color = ['black' if c == 0 else 'Lightgrey' for c in target]
plt.scatter(features_standardized[:,0], features_standardized[:,1], c=color)
创建超平面：
w = svc.coef_[0]
a = -w[0] / w[1]
xx = np.linspace(-2.5,2.5)
yy = a * xx - (svc.intercept_[0]) / w[1]
绘制超平面：
plt.plot(xx, yy)
plt.axis('off')
plt.show()
创建一个新的样本点：new_observation = [[-2, 3]]
预测新样本点的分类：svc.predict(new.observation)

需要在SVC最大化超平面两侧的间距和最小化分类错误之间取得平衡。在SVC中，后者是通过一个超参数C（分类错误时所需要接受的惩罚）来控制的。C是SVC学习器的一个参数，也是学习器讲一个样本点分类错误时被施加的罚项。当C很小时，SVC可容忍更多的样本点被错误分类（偏差大，方差小）。当C很大时，SVC会因为对数据的错误分类而被重罚，因此通过反向传播来避免对样本点的错误分类（偏差小，方差大）。

使用核函数处理线性不可分的数据

from sklearn.svm import SVC
from sklearn.precrocessing import StandardScaler
设置随机种子：np.random.seed(0)
生成两个特征：features = np.random.randn(200,2)
使用异或门创建线性不可分数据：
target_xor = np.logical_xor(features[:,0] > 0, features[:,1] > 0)
target = np.where(target_xor, 0, 1)
创建一个有径向基函数的支持向量机
svc = SVC(kernel='rbf', random_state=0, gamma=1, C=1)
训练分类器：model = svc.fit(features, target)

对于核函数：其决定了我们用什么类型的超平面来分离不同的分类，使用不同的核函数来创建不同的超平面。

可视化观察值和一个二维空间里的超平面决策边界。
画出观察值和超平面决策边界：
from matplotlib.colors import ListedClolormap
import matplotlib.pyplot as plt
# def plot_decision_regions(X,y,classifier)
# cmap = ListedColormap(('red', 'blue'))
# xx1, xx2 = np.meshgrid(np.arange(-3, 3, 0.02), np.arange(-3, 3, 0.02))
# Z = classifier.predict(np.array([xx1.ravel(), xx2.ravel()]).T) # 展平数组元素
# Z = Z.reshape(xx1.shape)
# plt.contourf(xx1, xx2, Z, alpha=0.2, cmap=cmap)
# for idx, cl in enumerate(np.unique(y))
# plt.scatter(x=X[y == cl, 0], y=X[y == cl, 1], alpha=0.8, c=cmap(idx), marker='+', label=cl)
创建一个使用线性核函数的SVC
svc_linear = SVC(kernel='linear', random_state=0, C=1)
训练模型：svc_linear.fit(features, target)
SVC(C=1, cache_size=200, class_weight=None, coef=0.0, decision_function_shape='ove', degree=3, gamma='auto', kernel='linear', max_iter=-1, probability=False, random_state=0, shrinking=True, tol=0.001, verbose=Fales)
画出观察值和超平面：
plot_decision_region(features, target, classifier=svc_linear)
plt.axis('off')
plt.show()

(可见上述分类效果很差，使用径向基核函数来替换线性核函数)
创建一个使用径向基核函数的SVC
svc = SVC(kernel='rbf', random_state=0, gamma=1. C=1)
训练这个分类器
model = svc.fit(features, target)
画出观察值与超平面
plot_decision_regions(features, target, classifier=svc)
plt.axis('off')
plt.show()

可见使用径向基核函数，可以创建一个分类效果比线性核函数好很多的决策边界。

计算预测分类的概率
设置 probablility=True ，使用 predict_proba来查看校准后的概率

from sklearn.svm import SVC
from sklearn.precrocessing import StandardScaler
标准化特征：scaler = StandardScaler()
features_standardized = scaler.fit_transform(features)
创建SVC对象：
svc = SVC(kernel='linear', probability=True, random_state=0)
训练分类器：
model = svc.fit(features_standardized, target)
创建一个新的观察值
new_observation = [[.4, .4, .4, .4]]
查看观察值被预测为不同分类的概率
model.predict_proba(new_observation)

输出校准过的分类概率：在有两个分类的SVC中可以使用Platt缩放（Platt scaling），它首先训练这个SVC，然后训练一个独立的交叉验证逻辑回归模型将SVC的输出转换为概率： $P(y=1|x)=\frac{1}{1+{{e}^{Af(x)+B}}}$ ，其中A和B是参数向量，f是第i个观察值到超平面的距离。如果数据集中不止两个分类，则使用Platt缩放的扩展。

计算预测分类的概率有两个主要问题：

因为训练了一个带交叉验证的模型，所以生成预测分类概率的过程会显著增加模型训练的时间。
因为预测的概率是通过交叉验证计算，所以它们可能不会总是与预测的分类匹配。也就是说，一个观察值可能被预测为属于分类一，但是它被预测为属于分类一的概率却小于0.5

识别支持向量
训练模型，然后使用 support_vectors_方法：

from sklearn.svm import SVC
from sklearn.precrocessing import StandardScaler
标准化特征：scaler = StandardScaler()
features_standardized = scaler.fit_transform(features)
创建SVC对象：
svc = SVC(kernel='linear', random_state=0)
训练分类器：
model = svc.fit(features_standardized, target)
查看支持向量
model.support_vectors_