西瓜书第六章支持向量机

这一章的数学公式有点多，一直不知道要怎么写，看着也有点乱，我个人觉得吴恩达老师的机器学习第十二章关于的向量机的解释要更容易懂一些，如果看不懂这一章的建议去看视频。附上链接：吴恩达机器学习第十二章。
我下面的内容会结合这个视频来说说我自己的理解。

6.1间隔与支持向量

支持向量机用来处理非线性分类问题，将获得更好的效果。

20730902-37068a01862dabd4.webp.jpg

通过这幅图我们可以看出来每一条线其实都能将正负类完全分开，而支持向量机它则是选择最中间的黑线来作为划分的平面，所以支持向量机又被称为大间隔分类器。而为什么每条线都能完全的将训练集分类，偏偏选择最中间的呢？我们可以看得出来最中间的与各个实例的间隔最大，这就使得该分类器有较好的泛化能力，如果选择的是其他间隔小的作为分类平面，一旦我们的测试集波动较大则很容易出现测试错误。
而对于上面的划分平面可以用下面的线性方程来表示：

$w^Tx+b=0$
这里的 $w$ 是决策平面的法向量，b则是决策平面到原点的距离。

对于任意点也就是我们要测试的点，到决策平面的距离： $r=\frac{|w^Tx+b|}{||w||}$

$r=\frac{|w^Tx+b|}{||w||}$ 如何得到这一个公式的，我简单说明一下，假设我们有一个点 $x_0$ 在决策平面上 $(故w^Tx_0+b=0)$ ，这里我们用向量法来计算距离，用任意点到平面上一点的向量来乘以平面法向量再除以法向量的模长，平面外任意一点 $x$ 到平面的距离： $\frac{|w^T(x-x_0)|}{||w||}=\frac{|w^Tx-w^Tx_0|}{||w||}=\frac{|w^Tx-(-b)|}{||w||}=\frac{|w^Tx+b|}{||w||}$ 。
$||w||$ 表示法向量的模长

由于我们将平面的公式记为： $w^Tx+b=0$ ，所以只要空间中任意的点代入这个公式后 $w^Tx_i+b>0$ 则我们可以认为其 $y_=+1$ 为正类，反之为负类。但是向量机要找的是最大间隔的分类平面，所以其条件更为严格：

$\begin{cases}{w^Tx_i+b≥+1,y_i=+1};\\w^Tx_i+b≤-1,y_i=-1.\end{cases}$

刚好到平面距离为1的样本点被称为“支持向量”，而两个异类支持向量到平面的距离之和被称为“间隔”( $\gamma={\frac{2}{||w||}}$ )

支持向量与间隔.jpg

刚刚也说了支持向量机就是找间隔最大，所以要求得最大化间隔，我们可以求下面的式子最小化：

$\min_{w,b} \frac{1}{2}||w||^2$ （式子1）
$s.t. y_i(w^Tx_i+b)≥1,i=1,2,...,m$ .
【注：s.t.指式子1的约束条件】

这便是支持向量机(SVM)的基本型。
到这里我们对支持向量机也有一个大概的认识了，接下来就是我们要如何求得 $w，b$ 来得到我们的决策平面,而西瓜书通过纯数学的推导来让我们知道如何计算这两个参数，吴恩达老师则是通过逻辑回归来推出支持向量机的代价函数，得到与上面相同的式子求最小值，在吴恩达老师的视频中并没有明确的告诉我们如何求出 $w$ (视频中一直成为θ都一样的)，因为在实际应用中我们不可能自己亲自去写出最小化向量距离的代码，这样效率很低，老师推荐我们引用前辈已经写好的代码来直接求得最小化的 $w$ ，但是西瓜书把这一原理写了出来，所以我们也来看一下吧。如果看不懂我觉得也没关系，只要知道最后要求的模型的公式，在实际应用中会有很多写好的代码包来解决这一过程的。

6.2对偶问题

首先理清一下，我们要得到的决策平面是 $f(x)=w^Tx+b$ ，而 $w$ 则可以通过刚刚求得的式子1来获得；为了更高效的求解式子1，我们为每个约束条件引入拉格朗日乘子 $a_i≥0$ ，则得到式子1的拉格朗日函数：

$L(w,b,a)={\frac{1}{2}}||w||^2+\sum_{i=1}^ma_i(1-y_i(w^Tx_i+b)),$ (式子2)
其中 $a=(a_1;a_2;...;a_m)$
对 $w,b$ 分别求偏导得： $w=\sum_{i=1}^{m}a_iy_ix_i,$     (对w求导)
                                       $0=\sum_{i=1}^ma_iy_i,$          (对b求导)
将求导的结果代入式子2可以得到式子1的对偶问题：
$\max_a \sum_{i=1}^ma_i-{\frac{1}{2}}{\sum_{i=1}^m}{\sum_{j=1}^ma_ia_jy_iy_jx_i^Tx_j}$
$s.t.\sum_{i=1}^ma_iy_i=0,$
        $a_i≥0,i=1,2,...,m.$
解出a后，求出 $w,b$ 就可以得到模型： $f(x)=w^Tx+b=\sum_{i=1}^ma_iy_ix_i^T+b$

理一下思路，我们要通过式子1来求得 $w$ ，于是引入拉格朗日乘子以便更高效的求解，所以就得到了式子1拉格朗日函数式子2，通过对式子2求偏导代入消去未知量，得到对偶问题，最终使得求 $w$ 变成求拉格朗日乘子。
那么要如何求得拉格朗日乘子呢？要知道上面的 $a_i≥0$ 且式子1本身有约束条件的，所以我们上面的对偶问题满足kkT条件：

$\begin{cases}{a_i≥0};\\y_if(x_i)-1≥0;\\a_i(y_if(x_i)-1)=0.\end{cases}$

在了解其约束条件后我们可以通过SMO算法来求解拉格朗日乘子,SMO算法思路：每次选择两个拉格朗日乘子，其他的拉格朗日乘子固定，所以对偶问题就只有两个未知数，即我们选择的两个拉格朗日乘子，通过约束条件来消掉其中一个，剩下一个未知数求最优解，实现对拉格朗日乘子的优化更新。下面我用一次更新来说明一下这个过程:

1、选取一对要更新的变量 $a_i,a_j,$ 如何选呢？选择违背KKT条件程度最大的，更新后收益最高。
2、固定除了 $a_i,a_j$ 外的参数，求解对偶问题来获得更新后的 $a_i,a_j.$
由于只有两个未知数，所以对偶问题中的约束条件重新写为：
$a_iy_i+a_jy_j=c，a_i≥0，a_j≥0$ ，其中 $c=-\sum_{k≠i,j}a_ky_k$ (c是已知的，因为除了 $a_i,a_j$ 其他都是固定的)
所以通过重新写的约束条件，我们可以代入对偶问题消去 $a_j$ ，最后求得 $a_i与a_j$ 。

通过对拉格朗日乘子的不断更新直到收敛，我们就得到了最优的 $a$ ，距离我们要求的决策平面只要得到b就行了，那么如何求b呢？

对于任意的支持向量 $（x_s,y_s）都有y_sf(x_s)=1$ ,即
$y_s(\sum_{i∈S}a_iy_ix_i^Tx_s+b)=1,$
其中S为所有支持向量的下标集。
这是b的理论求法，而实际中我们是直接将所有支持向量的解的平均值作为b(可看作上面式子的变形)：
$b={\frac{1}{|S|}\sum_{s∈S}(1/y_s-\sum_{i∈S}a_iy_ix_i^Tx_s)}$

这一节如果看不懂也没什么关系，可以跳过。

6.3核函数

前面的支持向量机其实是线性可分的，但是我们最开始提到过支持向量机最主要的是处理非线性问题，这就需要用到核函数了。
原理：核函数通过对原先的特征进行处理，产生新的特征，使样本空间从原始空间映射到更高维度的特征空间，使得在原始空间非线性问题在新空间中线性可分。
具体如何操作呢？我们来看一下：

令 $∅(x)$ 表示将 $x$ 映射后的特征向量，所以我们前面的所有式子全部特征 $x$ 用 $∅(x)$ 替代掉可得：
原式子1变为; $\min_{w,b}{\frac{1}{2}||w||^2}$
                     $s.t.y_i(w^T∅(x_i)+b)≥1,i=1,2,...,m.$
其对偶问题： $\max_a\sum_{i=1}^ma_i-{\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^{m}a_ia_jy_iy_j∅(x_i)^T∅(x_j)}$
                       $s.t.\sum_{i=1}^ma_iy_i=0,$
                              $a_i≥0,i=1,2,...,m.$
令 $\kappa(x_i,x_j)={\langle}∅(x_i),∅(x_j){\rangle}=∅(x_i)^T∅(x_j)$ ，其中 $\kappa(.,.)$ 被称为核函数。（我们可以将经过核处理后的变量当做一个新的特征，这在吴恩达老师的机器学习中有解释，我就不做说明了，我个人认为那个解释更容易理解。）在这里我们可以认为核函数就是为了计算 $x_i,x_j$ 映射到特征空间后的内积就可以了。
所以，对偶问题： $\max_a\sum_{i=1}^ma_i-{\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^{m}a_ia_jy_iy_j{\kappa(x_i,x_j)}}$
                              $s.t.\sum_{i=1}^ma_iy_i=0,$
                                     $a_i≥0,i=1,2,...,m.$
最终求解得到: $f(x)=w^T∅(x)+b=\sum_{i=1}^ma_iy_i∅(x)^T∅(x)+b=\sum_{i=1}^ma_iy_i{\kappa(x_i,x_j)+b.}$

下面是常见的核函数。

常见核函数.jpg

6.4软间隔与正则化

前面我们所介绍的支持向量机要求所有的样本到决策平面的距离都等于间隔的一半，这样的间隔我们称为硬间隔，但是在实际任务中往往不可能这么完美的划分，所以我们允许个别的样本不满足条件，该间隔则称为软间隔。

图例.jpg

软间隔：
当然我们是希望不满足条件的样本越少越好，而由于不满足条件的样本存在，所以我们需要对式子施加一点惩罚，所以引入松弛变量。

对于式子1,施加惩罚后： $\min_{w,b,\xi_i}\frac{1}{2}||w||^2+C\sum_{i=1}^m\xi_i$       （为了使该式子最小，不满足条件的点要尽量少）
                                        $s.t.y_i(w^Tx_i+b)≥1-\xi_i$
                                                 $\xi_i≥0,i=1,2,..,m.$
这就是常用的“软间隔支持向量机。”

它的计算方法与上面的一样，引入拉格朗日乘子，求偏导得到对偶问题最后在KKT条件下用SMO算法来迭代得到最优解。

拉格朗日函数： $L(w,b,a,\xi,u)=\frac{1}{2}||w||^2+C\sum_{i=1}^m\xi_i+\sum_{i=1}^ma_i(1-\xi_i-y_i(w^Tx_i+b))-\sum_{i=1}^mu_i\xi_i,其中a_i≥0,u_i≥0是拉格朗日乘子。$
对偶问题： $\max_a\sum_{i=1}^ma_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^ma_ia_jy_iy_jx_i^Tx_j$
$s.t.\sum_{i=1}^ma_iy_i=0,$
$0≤a_i≤C,i=1,2,...,m.$

其KKT条件要求如下;

$\begin{cases}{a_i≥0,u_i≥0,}\\y_if(x_i)-1+\xi_i,\\a_i(y_if(x_i)-1+\xi_i)=0,\\\xi_i≥0,u_i\xi_i=0.\end{cases}$

正则化问题： $\min_f\Omega(f)+C\sum_{i=1}^m\zeta(f(x_i),y_i)$ ，其中 $\zeta()为损失函数$ ， $\Omega(f)称为“结构风险”或正则化项，\sum_{i=1}^m\zeta(f(x_i),y_i)为“经验风险”，C为正则化常数。$

6.5支持向量回归(SVR)

对于传统回归模型一定要预测的值f(x)等于y才可以，但是支持向量回归则允许其预测存在误差 $\epsilon$ ，即当f(x)与y之间差别大于 $\epsilon$ 才计算损失。

在虚线中间的样本不计算损失.jpg

SVR问题可视化为：

$\min_{w,b}{\frac{1}{2}}||w||^2+C\sum_{i=1}^m\zeta_{\epsilon}(f(x_i)-y_i)$
其中 $\zeta_{\epsilon}$ 为 $\epsilon$ -不敏感损失函数：
$\zeta_{\epsilon}(z)={\begin{cases}0,if|z|≤\epsilon;\\|z|-\epsilon,otherwise\end{cases}}$
引入松弛变量 $\xi_i,\hat{\xi_i}$ ,
$\min_{w,b,\xi_i,\hat{\xi_i}}\frac{1}{2}||w||^2+C\sum_{i=1}^m(\xi_i+\hat{\xi_i})$
              $s,t,f(x_i)-y_i≤\epsilon+\xi_i,$
                      $y_i-f(x_i)≤\epsilon+\hat{\xi_i},$
                      $\xi_i≥0,\hat{\xi_i}≥0,i=1,2,...,m.$

接下来的过程与SVM相似，引入拉格朗日乘子，得到拉格朗日函数求偏导得到对偶问题，由KKT条件利用SMO算法进行迭代得到最优解。

6.6核方法

核方法：基于核函数的学习方法，统称为核方法
最常见的是引入核函数将线性学习器拓展为非线性学习器，像上面我们所提及的支持向量机，我们便是通过引入核函数将原本非线性问题转化为线性问题，用线性学习器来预测。这是一个问题正反两面，也可以认为引入核函数使得线性学习器变成了非线性学习器从而能过进行预测非线性的样本。

【补充例子：】LogisticRegression,SGDClassifier对比，通过随机分配数据集来对比两种算法的不同，通过固定数据集来比较当C调整时LogisticRegression算法的变化。结果表明SGDClassifier算法无论是否固定数据集其表现都很一般，我找不到哪里错误了，欠拟合很多评分在0.2左右很让人不满意，而LogisticRegression算法通过调整C能得到勉强合格的评分0.8左右，当C=1000时评分最高可达0.91，这里的C如果大家有看吴恩达老师的视频就知道C其实决定了支持向量机的分隔线能否取得间隔最大，当c很大时其分隔极小，c很小时其分类效果很差，所以合适的C对该算法很重要，下面是我的实验代码，结果并没有截图，因为太多了，我测试了很多种情况。

#利用乳腺癌数据，来比较LogisticRegression（逻辑斯蒂回归）,SGDClassifier（sgd训练支持向量机）对比
#引入需要的库与数据
from sklearn.datasets import load_breast_cancer  #引入乳腺癌数据
from sklearn.cross_validation import train_test_split as tsplit   #引入交叉验证中常用的函数，将数据随机分为训练和测试集。、
from sklearn.preprocessing import StandardScaler   #用于将数据集标准化
from sklearn.linear_model import LogisticRegression,SGDClassifier    #引入两种分类方法
from sklearn.metrics import classification_report as crt     #引入函数用于显示分类指标文本报告
import numpy as np
import pandas as pd
import time

breast_cancer = load_breast_cancer()     #取乳腺癌数据

x_train,x_text,y_train,y_text = tsplit(breast_cancer.data,breast_cancer.target,test_size=0.2)

sts = StandardScaler()

#数据标准化
x_train_sts = sts.fit_transform(x_train)
x_text_sts = sts.transform(x_text)
print(x_train_sts.shape,x_text_sts.shape)    #将数据向量化


sgdc = SGDClassifier()

ts1 = time.time()
log100=LogisticRegression(C=1000).fit(x_train,y_train)      #用数据拟合分类模拟器
te1 = time.time()
print(te1-ts1)              #输出训练出逻辑回归模型所需的时间

ts2 = time.time()
sgdc.fit(x_train,y_train)
te2 = time.time()
print(te2-ts2)

#输出两个分类的准确率
score1 = log100.score(x_text_sts,y_text)
score2 = sgdc.score(x_text_sts,y_text)
print(score1,score2)

lr_pre1 = log100.predict(x_text_sts)     #用逻辑斯蒂回归对测试数据进行预测

score1 = crt(y_text,lr_pre1,target_names=["0","1"])     #将测试的结果与真实结果比较形成文本报告
print(score1)

lr_pre2 = sgdc.predict(x_text_sts)

score2 = crt(y_text,lr_pre2,target_names=["0","1"])
print(score2)

【代码参考】(https://blog.csdn.net/xiaosongshine/article/details/89606023)
代码中StandardScaler函数的作用
 Logistic Regression回归函数
 SGDClassifier梯度下降分类方法
 classification_report解释
 Python sklearn中的.fit与.predict的作用
 python中的train_test_split方法

最后编辑于：2020.02.27 23:56:29

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

西瓜书 第六章 支持向量机