机器学习之支持向量机

假设我们有两组数据都是只有两个特征：

数据

这两个特征分别成为一个坐标轴，那么每一个样本在图像中表现出来的都是坐标系中的一个点

支持向量机想要做的就是找到一个超平面来进行空间的划分。

超平面

如果这个分类不能在这个维度上用平面或者直线进行划分，那么就用高一维度的空间进行划分。
比如：

一维

我们不可能直接在一维用一个点将两种颜色的小球划分开
但是在二维

二维

我们很轻松的可以用一条直线将两者分开

这条直线就可以称为是超平面。如果读者认为将一条线称为是超平面有点难以理解。
那么一个二维的用一条直线不能很好划分的问题，可以在三维用一个平面来划分。这个平面也是一个超平面。

支持向量机的基本型

由以上的描述我们可以看出来，一切线性不可分问题都可以通过提高维度而变得线性可分
那么现在我们开始谈一谈线性的问题

对于一个二维的线性问题我们可以写成：
$w_1x_1+w_2x_2+b = 0$ 形式
对于一个三维的线性问题我们可以写成：
$w_1x_1+w_2x_2+w_3x_3+b = 0$ 形式
.....

我们希望用一个简化的形式来表现多维的线性方程
因此用矩阵的方式来完成，因此：
$w^Tx+b = 0$
$w=[w_1, w_2, w_3,...]$
$x=[x_1, x_2, x_2,...]$
相信大家高中都有学过，点到直线距离公式：
$r = \frac{|kx+b|}{|k|}$
这里更新为：
$r = \frac{|w^Tx+b|}{||w||}$
这里的 $w^Tx+b$ 在线的一侧为正，在线的另一侧为负
$r = \frac{w^Tx+b}{||w||}$ 这样就同时表现了相对于直线的方向和距离
一条直线将空间分成了两类，因此类别 $y_i =$ 1 或者 -1 代表第i个样本是这一类还是另一类，至于为什么是1和-1 而不是像以前一样的 0和-1 ，这是为了表达上的简洁，后期会说明为什么这样设定表达上会简洁
我们设定在 $w^Tx+b>0$ 这一面的类别为1， $w^Tx+b<0$ 这一面的类别为-1, 即:
$\begin{cases} w^Tx_i+b>0, & y_i = 1\\ w^Tx_i+b<0, & y_i = -1 \end{cases}$
但并不是说只有一条直线可以将样本进行划分，就像开头的第一张图一样，会有两个支持面，而两个支持面正中央的线是最优的划分
假设两个支持面之间的距离为2d, 即最优面到支持面之间的距离为d
那么，上面的式子可以进一步改写为：
$\begin{cases} r_i\ge d, & y_i = 1 \\ r_i\leq -d, & y_i = -1 \end{cases}$
也就是：
$\begin{cases} \frac{|w^Tx_i+b|}{||w||}\ge d, & y_i = 1 \\ \frac{|w^Tx_i+b|}{||w||}\leq -d, & y_i = -1 \end{cases}$
左右两边同除d
得到：
$\begin{cases} w^T_{new}x_i+b_{new}\ge 1, & y_i = 1 \\ w^T_{new}x_i+b_{new}\leq -1, & y_i = -1 \end{cases}$
其中：
$w^T_{new} = \frac{w^T}{||w||d}$
$b_{new} = \frac{b}{||w||d}$

我们可以注意到,对于 $w^Tx+b = 0$ 来说将 $w^T$ 和 $b$ 用 $w^T_{new}$ 和 $b_{new}$ 对于原方程完全没有影响

因此后面所指的 $w^T$ 和 $b$ 指的是 $w^T_{new}$ 和 $b_{new}$
方程式为： $w^Tx+b = 0$
样本满足条件为： $\begin{cases}w^Tx_i+b\ge 1, & y_i = 1 \\ w^Tx_i+b\leq -1, & y_i = -1\end{cases}$

这个时候就表现出了分类时候用 -1 和 1 来表示的优势了
因为以上样本满足的条件可以写成为：
$y_i(w^Tx_i+b)\ge 1$

可以注意到以上的操作我们都是只是在一个确定方向上寻找最优面
但是我们怎样找到一个最优的方向呢

我们的想法是：在这个方向上的支持面距离越大，说明在这个方向上两个样本分得更"开"，也就说明这个方向的划分更优
因此使得两个支持面距离最大的方向就是最优方向
也就是说使得2d最大的方向就是最优方向
d是同方向上的最优面到支持面的距离，因此：
$d = \frac{|w^Tx+b|}{||w||}$
而由于我们以上的更新操作，可以看出，支持面上的样本满足: $w^Tx+b = 1$
因此 $d = \frac{1}{||w||}$
我们想要 2d 最大，也就是想要 d 最大
也就是||w|| 最小
相信大家对于让某一个向量的模最小的处理方式已经不陌生了，一般都是做平方处理，同时，为便于求导，除以2
也就是支持向量机的基本型：
在满足 $y_i(w^Tx_i+b)\ge 1$ 的情况下（ $i = 1, 2, 3,...,m$ ），尽力让 $\frac{1}{2} ||w||^2$ 达到最小
支持向量机的基本型是一个凸二次规划问题

凸二次规划问题

凸函数：
如果一个函数上任意两个点之间的连线上的中间点高于对应横坐标的函数上的点就称为凸函数：
数学表达： $f(\frac{x_i+x_j}{2}) \leq \frac{f(x_i)+f(x_j)}{2}$

凸二次规划问题：
用于表示一类问题：约束条件为线性不等式，求一个凸二次函数的最小值问题
一般形式为：
满足 $w^Tx \leq b$ 的情况下
求 $\frac{1}{2}x^TQx+c^Tx$ 的最小值
对于这种有约束条件的求极值问题：
有一种很好的解决手段：拉格朗日乘子法

拉格朗日乘子法与KKT条件

拉格朗日乘子法是一种处理有约束条件的极值问题非常常用的手段
等式约束条件：
约束条件: $h(x_1, x_2,..) = 0$
要求的极值： $g(x_1, x_2,...)$
那么 $L(x_1,x_2,...,\lambda) = g(x_1, x_2, ...) + \lambda h(x_1, x_2,...)$
对于各个参数进行求导并让结果等于0：
$\frac{\partial g(x_1, x_2,..)}{\partial x_1} + \lambda \frac{\partial h(x_1, x_2,...)}{\partial x_1} = 0$
$\frac{\partial g(x_1, x_2,..)}{\partial x_2} + \lambda \frac{\partial h(x_1, x_2,...)}{\partial x_2} = 0$
....
且 $\lambda \ge 0$
所有条件这些条件最后能够求出结果
不等式约束条件：
这种情况就是我们在这里需要解决的情况
我们有很多的不等式约束 $h_i(x) \leq 0$
也可以有等式约束： $k(x) = 0$
求 g(x) 的极值
解决方法还是使用拉格朗日乘子法：
$L(w_1, w_2,..,a,x) = g(x) + w_1 h_1(x) + w_2 h_2(x)....a*k(x)$
$(w_1, w_2, w_3...\ge 0)$
这个时候：最优解满足KKT条件
KKT条件：
$L(w_1, w_2,...,x)$ 对 x 求导为0
$w_i h_i(x) = 0$
$k(x) = 0$
并且有 $h_i(x) \leq 0$ 的已知条件
然后正常使用拉格朗日乘子法就可以解决问题

对偶问题:
对于不等式约束条件的处理方式正常来说，以上就可以解决问题了，但是有的时候，由于方程难解，就会利用对偶的性质
由 $L(w_1, w_2,..,a,x) = g(x) + w_1 h_1(x) + w_2 h_2(x)....ak(x)$
易知： $g(x) = max_{w_1,w_2,..a}(L(w_1, w_2, w_3, ..,a, x))$
因为:
对于满足条件的x来说 $h_i(x) \leq 0$ 且 $w_i \ge 0$ 因此 $w_i h_i(x) \leq 0$ 要想达到最大，只有让 $w_i = 0$
而 $k(x) = 0$ , 因此 $g(x) = max_{w_1,w_2,..a}(L(w_1, w_2, w_3, ..,a, x))$

而不要忘了我们的目标是要求 $g(x)$ 的最小值，即 $min_{x}(g(x))$
也就是 $min_{x}(max_{w_1, w_2, w_3,...a}L(w_1, w_2, w_3,...a, x))$

它的对偶性质在于只要 $L(w_1, w_2,...,a,x)$ 满足KKT条件：
$min_{x}(max_{w_1, w_2, w_3,...a}L(w_1, w_2, w_3,...a, x)) = max_{w_1, w_2, w_3,...a}(min_x(L(w_1, w_2, w_3, ...a,x)))$

继续计算

有了以上的知识储备
我们回顾一下，支持向量机的基本型是：
在满足 $y_i(w^Tx_i+b)\ge 1$ 的情况下（ $i = 1, 2, 3,...,m$ ），尽力让 $\frac{1}{2} ||w||^2$ 达到最小
在满足KKT条件的情况下，可以使用拉格朗日乘子法可以使用对偶性质：
也就是说，我们可以从求
$min_{w, b}(max_{\alpha}L(w,b,\alpha))$
变成求：
$max_{\alpha}(min_{w, b}L(w,b,\alpha))$

先开始求 $min_{w, b}L(w,b,\alpha)$ :
$L(w,b,\alpha) = \frac{1}{2}||w||^2 + \sum_{i = 1}^{m}\alpha_i(1-y_i(w^Tx_i + b))$
$\frac{\partial L(w,b,\alpha)}{\partial w} = w - \sum_{i = 1}^{m}\alpha_iy_ix_i = 0$
$\frac{\partial L(w,b,\alpha)}{\partial b} = -\sum_{i = 1}^{m}\alpha_iy_i = 0$
将w和b消掉，因数只有 $\alpha$ ：
$L(\alpha) = \sum_{i = 1}^{m}\alpha_i-\frac{1}{2}\sum_{i = 1}^{m}\sum_{j = 1}^{m}\alpha_i\alpha_j y_i y_j x_i^T x_j$ （*）
并满足： $\sum_{i = 1}^{m}\alpha_iy_i = 0$

然后求 $max_{\alpha}L(\alpha)$ :
由KKT条件可知：
$\alpha_i(1- y_i(w^Tx_i+b)) = 0 (i = 1, 2, 3,....,m)$
还有已知条件：
$\alpha_i \ge 0$
$y_i(w^Tx_i + b) \leq 1$

因此：
可以分为 $\alpha_i = 0$ 和 $1-y_i(w^Tx_i+b) = 0$ 两种情况
但显然，如果 $\alpha_i = 0$ 代表第i个样本没有起到约束作用
因此 $1-y_i(w^Tx_i+b) = 0$
由 $\sum_{i = 1}^{m}\alpha_iy_i = 0$
设 $f(x_i) = w^Tx_i+b$
那么 $y_if(x_i) = 1$
也就是说对于 $\alpha_i \ne 0$ 的样本来说， $y_if(x_i) = 1$
由此可见，只有在支持面上的样本才起到了约束作用

修正

以上的一切推导我们都基于了一个想法：一切线性可分问题都是百分百的线性可分，但是大部分的实际情况，即使这个问题可以用线性的方式分类，即使我们找到了非常好的分割函数，我们仍然避免不了会有错误分类的样本，因此我们推导不得不对于这种情况表现出一定的容忍度。
因此，要对于以上的推导进行修正
引入参数：

惩罚参数 $C$ : 用于表现，我们对于错误分类的样本的重视程度（惩罚力度）
松弛变量 $\xi$ : 用于表现，错误分类的样本的偏离距离

也就是支持向量机的基本型更新为：
在满足 $y_i(w^Tx_i+b)+ \xi_i\ge 1$ 和 $\xi_i \ge 0$ 的情况下（ $i = 1, 2, 3,...,m$ ），尽力让 $\frac{1}{2} ||w||^2 + C\sum_{i = 1}^m \xi_i$ 达到最小

那么: $L(w, \alpha, b,\xi, \mu) = \frac{1}{2} ||w||^2 + C\sum_{i = 1}^m \xi_i + \sum_{i = 1}^m \alpha_i(1-(y_i(w^Tx_i+b)+ \xi_i))-\sum_{i =1}^m \mu_i \xi_i$
同样的更新方法：
分别对 $w,b,\xi_i$ 进行求导：
$w = \sum_{i = 1}^{m}\alpha_i y_i x_i$
$0 = \sum_{i = 1}^{m}\alpha_i y_i$
$C = \alpha_i + \mu_i$
可以得到:
$L(\alpha) = \sum_{i = 1}^{m}\alpha_i-\frac{1}{2}\sum_{i = 1}^{m}\sum_{j = 1}^{m}\alpha_i\alpha_j y_i y_j x_i^T x_j$ （*）
并满足： $\sum_{i = 1}^{m}\alpha_iy_i = 0$
但是不同于之前要求 $0 \leq \alpha_i$ 这里要求 $0 \leq \alpha_i \leq C$
根据KKT条件：
$\alpha_i \ge 0, \mu_i \ge 0, \xi_i \ge 0$
$y_if(x_i) -1 + \xi_i \ge 0$
$\alpha_i(y_if(x_i) - 1 + \xi_i) = 0$
$\mu_i \xi_i = 0$

对于第i个样本：
如果 $\alpha_i = 0$ 说明这个样本对于f(x) 没有任何影响
如果 $y_if(x_i) - 1 + \xi_i = 0$ 说明这个样本是支持向量

根据： $C = \alpha_i + \mu_i$
可知：
如果 $C > \alpha_i, \mu_i > 0$ 因此 $\xi_i = 0$ 样本恰在最大分隔边界上
如果 $C = \alpha_i, \mu_i = 0$ :

若 $\xi_i \leq 1$ 最大间隔内部
若 $\xi_i < 1$ 错误分类

SMO算法

前面已经介绍过了什么是二次规划问题
因此我们可以看出，我们的后期推导出来的形式：
$L(\alpha) = \sum_{i = 1}^{m}\alpha_i-\frac{1}{2}\sum_{i = 1}^{m}\sum_{j = 1}^{m}\alpha_i\alpha_j y_i y_j x_i^T x_j$ （*）
并满足： $\sum_{i = 1}^{m}\alpha_iy_i = 0$
这种形式，仍然是一个二次规划问题

而SMO算法是一种解决二次优化问题的常用手段，基本思想是：先认为有两个参数是变量，并认为其他参数为常数值，对这两个变量做更新

下面我们就要用SMO算法解决问题：
由： $\sum_{i = 1}^{m}\alpha_iy_i = 0$ $a_i'$ 和 $a_j'$ 为更新之后的结果
可以看出来，如果我们只认为一个参数 $\alpha_i$ 为变量，其余都为常量的话， $\alpha_i$ 的值会被直接推导出来，而非给出一种关系
因此，我们会认为有两个变量 $\alpha_i$ 和 $\alpha_j$
由： $\sum_{i = 1}^{m}\alpha_iy_i = 0$
$\alpha_i y_i + \alpha_j y_j = \zeta = \alpha_i'y_i + \alpha_j'y_j$ $\zeta$ 代表常数
由上面的： $0 \leq \alpha_i \leq C$
另 $y_i$ 和 $y_j$ 分别为1 和-1
则 $\alpha_i' - \alpha_j'=\zeta$
因此从这里计算得到 $-\zeta \leq \alpha_j' \leq C-\zeta$
本身有的限制 $0 \leq \alpha_j' \leq C$
因此下界为： $max(0, -\zeta)$
上界： $min(C, C-\zeta)$
因此取值范围如下：

图片来源自https://cuijiahua.com/blog/2017/11/ml_8_svm_1.html

同理：
如果 $y_i = 1, y_j = 1$
取值范围如下

https://cuijiahua.com/blog/2017/11/ml_8_svm_1.html

因此：L 表示上界 H 表示下界
$\begin{cases} L = max(0, \alpha_j-\alpha_i),& H = min(C, C + \alpha_i- \alpha_j), & y_i \ne y_j\\ L = max(0, \alpha_i+ \alpha_j - C), & H = min(C, \alpha_i + \alpha_j), & y_i = y_j \end{cases}$

$L(\alpha) = \sum_{i = 1}^{m}\alpha_i-\frac{1}{2}\sum_{i = 1}^{m}\sum_{j = 1}^{m}\alpha_i\alpha_j y_i y_j x_i^T x_j$ （*）
并满足： $\sum_{i = 1}^{m}\alpha_iy_i = 0$
$\alpha_r y_r + \alpha_o y_o = -\sum_{k \ne r, o}^{m} \alpha_k y_k$ (常数)
$\alpha_r y_r y_o + \alpha_o y_o^2=$ 常数
$\alpha_r y_o y_r + \alpha_o =$ 常数

设 $s = y_i y_j$
设 $s\alpha_r + \alpha_o =D$ （常数）
所以： $\alpha_o = D - s \alpha_r$

由： $L(\alpha) = \sum_{i = 1}^{m}\alpha_i-\frac{1}{2}\sum_{i = 1}^{m}\sum_{j = 1}^{m}\alpha_i\alpha_j y_i y_j x_i^T x_j$ （*）
将 $\alpha_o = D - s \alpha_r$ 带入，并对 $\alpha_r$ 求偏导

为了以下的推导方便，以上选择的i和j，用o和r代替， $\alpha_o$ 和 $\alpha_r$ 为旧参数， $\alpha_o'$ 和 $\alpha_r'$ 为新参数
$B = \sum_{i \ne i,o}^m \alpha_i y_i x_i$

$\frac{\partial L(\alpha)}{\partial \alpha_r}= 1 -s + Dsx_o^T(x_o - x_r) + By_r(x_o - x_r) - \alpha_r'(x_o^Tx_o - 2x_o^Tx_r + x_r^T x_r) = 0$

将以上带入的D B 都代回去，设 $E_i = f(x_i) - y_i$ $\eta = x_o^Tx_o - 2x_o^Tx_r + x_r^T x_r$

获得更新公式：
$\alpha_r' = \alpha + \frac{y_r(E_o - E_r)}{\eta}$

因为 $\alpha_r'$ 满足 $L \leq \alpha_r' \leq H$ 这是之前的推导
因此 $\alpha_r^{new} = \begin{cases} H,& \alpha_r' > H \\ \alpha + \frac{y_r(E_o - E_r)}{\eta}, & L \leq \alpha_r' \leq H \\ L, & \alpha_r < L \end{cases}$

根据 $\alpha_o' = D - s \alpha_r^{new}$ 可以获得 $\alpha_o'$

因为 $0 \leq \alpha_r' \leq C$ 和 $0 \leq \alpha_o' \leq C$
可见如果超出这个范围的 $\alpha$ 对应的样本是无效样本

根据前面的 $y_r(w^Tx_r+b') = 1$ 和 $w - \sum_{i = 1}^{m}\alpha_iy_ix_i = 0$
两边同时乘 $y_k$ 得到：
$w^Tx_r + b' = y_r$
$\sum_{i = 1}^{m}\alpha_iy_ix_i x_r + b' = y_r$
$\alpha_oy_ox_ox_r + \alpha_ry_rx_rx_r + \sum_{i \ne o,r}^{m}\alpha_iy_ix_i x_r + b' = y_r$
由于: $\sum_{i \ne o,r}^{m}\alpha_iy_ix_ix_r$ 没有经历过更新，可以从原式中得到:
$b' = b - E_r - y_o(\alpha_o' - \alpha_o)x_o^Tx_r - y_r(\alpha_r' - \alpha-r)x_r^Tx_r$

b得到更新

同理将换成o也可以获得更新

但是正如上面提到过的，o样本和 i样本可能无用
如果两者都可用：两者更新结果一致
如果只有一者可用：取可用者更新
如果两者都不可用：取两个更新结果的中间值

以上就是支持向量机的过程
有了这个过程，以下代码相信不难理解，但是是一个简易版本，为了提升运算效率，会引入核方法。

梳理

介绍了这么多，现在我们梳理一下流程：

判断当前这个训练数据的参数是否需要更新：
- 如果 $\alpha_i < C$ 那么根据前面的推导，有结论这个样本在最大分隔线上，但是这样的情况下， $y_i f(x_i) < 1$ 说明方向的划分存在问题，需要更新
- 如果 $y_i f(x_i) > 1$ 说明这个样本为非支持向量，但是 $\alpha_i > 0$ , 说明这个样本对训练结果有影响，显然不对，需要更新
一旦判断这个参数需要更新：
开始使用smo，因此需要另一个参数一起进行更新。
别忘了，我们后期更新后的参数需要上下界的限制：

因此先用旧的参数计算上下界：
$\begin{cases} L = max(0, \alpha_j-\alpha_i),& H = min(C, C + \alpha_i- \alpha_j), & y_i \ne y_j\\ L = max(0, \alpha_i+ \alpha_j - C), & H = min(C, \alpha_i + \alpha_j), & y_i = y_j \end{cases}$
然后用更新公式对其中一个参数进行更新：
$\alpha_r' = \alpha + \frac{y_r(E_o - E_r)}{\eta}$
$\eta = x_o^Tx_o - 2x_o^Tx_r + x_r^T x_r$
将该更新后参数用L H 剪切
用两个参数之间的关系对另一个参数进行更新：
$\alpha_o' = \alpha_o + y_oy_r(\alpha_r - alpha_r')$
判断这两个参数是否符合在0 到C 之间，符合的可以用来更新b，如果两个都不符合就取两者各自计算的b的平均值

就这样对每一个参数都检查一遍，只要存在参数不符合条件经历过，就再重新检查，知道没有参数不符合条件
这个时候对w进行更新，然后用更新后的w重复以上步骤，就这样不停迭代，直到达到预先设置好的条件

完成训练

svm.py

import random
from numpy import *
import draw

def loadDataSet(fileName):  # 加载数据集
    dataMat = []
    labelMat = []
    fr = open(fileName)
    for line in fr.readlines():
        lineArr = line.strip().split('\t')
        dataMat.append([float(lineArr[0]), float(lineArr[1])])
        labelMat.append([float(lineArr[2])])
    return dataMat, labelMat


def selectJrand(i, m):  # 获得0到m之间的随机数
    j = i
    while j == i:
        j = int(random.uniform(0, m))
    return j


def clipAlpha(aj, H, L):  # 剪切获得的更新后的aj
    if aj > H:
        aj = H
    elif L > aj:
        aj = L
    return aj


def smoSimple(dataMatIn, classLabels, C, toler, maxIter):
    dataMatrix = mat(dataMatIn)
    labelMat = mat(classLabels).T
    b = 0.0
    w = mat(zeros((1, 2)))
    m, n = shape(dataMatrix)
    alphas = mat(zeros((m, 1))).T
    iter = 0
    while iter < maxIter:  # 限制一个最多迭代次数
        alphaPairsChanged = 0
        for i in range(m):
            # print(dot(multiply(alphas, labelMat), dot(dataMatrix, dataMatrix[i, :].T)))
            # multiply 作用是可以获得对应项相乘得到的矩阵
            fXi = float(dot(multiply(alphas, labelMat), dot(dataMatrix, dataMatrix[i, :].T))) + b  # f(x_i) 项
            Ei = fXi - float(labelMat[0, i])  # 误差
            # if 中两种情况需要更新参数
            # 第一种：\alpha_i < C 由文中可知 代表 样本在最大分割线上，可是即使如此还是不能满足距离中间分割线1的距离
            # 第二种：\alpha_i > 0 由文中可知 代表 样本对f(x)有影响，可是这个样本已经在距离中间分割线超过1了，非支持向量不应该对f(x)有影响
            if (labelMat[0, i]*Ei < -toler and alphas[0, i] < C) or (labelMat[0, i]*Ei > toler and alphas[0, i] > 0):
                j = selectJrand(i, m)  # 随机选取另一个自变量
                fXj = float(dot(multiply(alphas, labelMat), dot(dataMatrix, dataMatrix[j, :].T))) + b
                Ej = fXj - float(labelMat[0, j])
                alphaIold = alphas[0, i].copy()
                alphaJold = alphas[0, j].copy()
                # 即为文章中的限制上界和下界
                if labelMat[0, i] != labelMat[0, j]:
                    L = max(0, alphas[0, j])
                    H = min(C, C + alphas[0, j] - alphas[0, i])
                else:
                    L = max(0, alphas[0, j] + alphas[0, i] - C)
                    H = min(C, alphas[0, j] + alphas[0, i])
                if L == H:
                    print("L==H")
                    continue

                eta = 2.0 * dataMatrix[i, :] * dataMatrix[j, :].T -\
                    dataMatrix[i, :] * dataMatrix[i, :].T -\
                    dataMatrix[j, :] * dataMatrix[j, :].T
                if eta >= 0:
                    print("eta >= 0")
                    continue
                alphas[0, j] -= labelMat[0, j] * (Ei - Ej)/eta  # 更新公式
                alphas[0, j] = clipAlpha(alphas[0, j], H, L)  # 由上下界剪切得到的公式
                if abs(alphas[0, j] - alphaJold) < 0.00001:  # 几乎没有实质上的更新
                    print("j not moving enough")
                    continue
                alphas[0, i] += labelMat[0, j]*labelMat[0, i]*(alphaJold - alphas[0, j])  # 由更新后的\alpha_j 对\alpha_i 进行更新
                b1 = b - Ei - labelMat[0, i] * (alphas[0, i] - alphaIold) *\
                    dot(dataMatrix[i, :], dataMatrix[i, :].T) -\
                    labelMat[0, j] * (alphas[0, j] - alphaJold) *\
                    dot(dataMatrix[i, :], dataMatrix[j, :].T)  # b 的更新公式
                b2 = b - Ej - labelMat[0, i] * (alphas[0, i] - alphaIold) * \
                     dot(dataMatrix[i, :], dataMatrix[j, :].T) -\
                     labelMat[0, j] * (alphas[0, j] - alphaJold) *\
                     dot(dataMatrix[j, :], dataMatrix[j, :].T)
                # if 0 < alphas[i] and C > alphas[i]:
                # 分情况来判断取哪一个b
                if 0 < alphas[0, i] < C:
                    b = b1
                elif 0 < alphas[0, j] < C:
                    b = b2
                else:
                    b = (b1 + b2)/2.0
                alphaPairsChanged += 1
                print("iter : %d i: %d, pairs changed %d" % (iter, i, alphaPairsChanged))
        if alphaPairsChanged == 0:  # 只有在每一个样本都做过变量且都不需要进行更新了，才会进行下一次的迭代
            iter += 1
        else:
            iter = 0
        print("iteration number: %d" % iter)
        w = dot(multiply(alphas, labelMat), dataMatrix)
    return w, b


data, label = loadDataSet("testSet.txt")
draw.draw_scatter_figure(data)
w, b = smoSimple(data, label, 0.6, 0.001, 40)
print(b)
print(w)
draw.draw_line_figure(w, b[0, 0])

draw.py

from pylab import *
import matplotlib.pyplot as plt


def draw_scatter_figure(data):
    newData = mat(data)
    X = newData[:, 0].A
    Y = newData[:, 1].A
    plt.scatter(X, Y)


def draw_line_figure(w, b):
    X = linspace(0, 12, 20, endpoint=True)
    Y = (w[0, 0] * X + b)/w[0, 1]
    print(X)
    print(Y)
    plt.plot(X, Y)
    plt.show()

效果图：

参考：

https://cuijiahua.com/blog/2017/11/ml_8_svm_1.html
《机器学习》by 周志华
及一系列数学博客

最后编辑于：2019.03.05 21:25:04

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