机器学习-7-支持向量机

Posted on | Post modified: | In
Words count in article: 7.4k

0 前言

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

线性可分支持向量机：当训练数据线性可分时，通过硬间隔最大化学习的线性分类器。

线性支持向量机：当训练数据近似线性可分时，通过软间隔最大化学习的线性分类器。

非线性支持向量机：当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。

当输入空间为欧式空间或离散集合、特征空间为希尔伯特空间时，核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的內积。通过使用核函数可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机。

1 线性可分支持向量机与硬间隔最大化

1.1 线性可分支持向量机

假设给定一个特征空间上的训练数据集

其中$x_i\in\mathcal{X} = \mathbf{R}^n$，$y_i \in \mathcal{Y}=\{+1,-1\}$。

再假设训练数据集是线性可分的。学习的目标是在特征空间中找到一个分离超平面，能将实例分到不同的类。分离超平面对应于方程$w\cdot x+b=0$，它由法向量$w$和截距$b$决定，可用$(w,b)$来表示。分离超平面将特征空间划分为两部分。

一般地，当训练数据集线性可分时，存在无穷个超平面可将两类数据正确分开。线性可分支持向量机利用间隔最大化求最优分离超平面，这时解是唯一的。

定义：线性可分支持向量机：给定线性可分训练数据集，通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为

以及相应的分类决策函数

称为线性可分支持向量机。

1.2 函数间隔

对于给定的训练数据集$T$和超平面$(w,b)$，定义超平面$(w,b)$关于样本点$(x_i, y_i)$的函数间隔为

定义超平面$(w,b)$关于训练数据集$T$的函数间隔为超平面$(w,b)$关于$T$中所有样本点$(x_i,y_i)$的函数间隔之最小值，即

函数间隔可以表示分类预测的正确性及确信度。分离超平面的法向量$w$加规范化$||w||=1$，使得间隔是确定的，这是函数间隔成为几何间隔。

几何间隔：对于给定的训练数据集$T$和超平面$(w,b)$，定义超平面$(w,b)$关于样本点$(x_i, y_i)$的几何间隔为

定义超平面$(w,b)$关于训练数据集$T$的几何间隔为超平面$(w,b)$关于$T$中所有样本点$(x_i,y_i)$的几何间隔之最小值，即

函数间隔和几何间隔的关系

如果$||w||=1$，那么函数间隔和几何间隔相等，如果超平面参数$w$和$b$成比例地改变（超平面没有改变），函数间隔也按此比例改变，而几何间隔不变。

1.3 间隔最大化

支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。（硬间隔最大化）。

间隔最大化的直观解释：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。这样的超平面对未知的新实例有很好的分类预测能力。

最大间隔分离超平面：可表示为下面的约束最优化问题。

我们希望最大化超平面$(w,b)$关于训练数据集的几何间隔$\gamma$，约束条件表示的是超平面$(w,b)$关于每一个训练样本点的几何间隔至少是$\gamma$。

考虑到几何间隔和函数间隔的关系，这个问题可改写为

函数间隔$\hat{\gamma}$的取值并不影响最优化问题的解，这里去$\hat{\gamma}=1$，注意到最大化$\frac{1}{||w||}$和最小化$\frac{1}{2} ||w||^2$是等价的，于是可以得到线性可分支持向量机学习的最优化问题

这是一个凸二次规划问题。

算法：线性可分支持向量机学习算法—最大间隔法

输入：线性可分训练数据集$T=\{(x_1,y_1), (x_2, y_2), \cdots, (x_N, y_N)\}$，其中$x_i\in\mathcal{X} = \mathbf{R}^n$，$y_i \in \mathcal{Y}=\{+1,-1\}$，$1,2,\cdots,N$

输出：最大间隔分离超平面和分类决策函数

（1）构造并求解约束最优化问题：

求得最优解$w^,b^$。

（2）由此得到分离超平面：

分类决策函数

可以证明线性可分训练集的最大间隔分离超平面是存在且唯一的。（证明略）

支持向量：在线性可分情况下，训练数据集的样本点中与分离超平面最近的样本点的实例。支持向量是使约束条件式$y_i \left( w \cdot x_i + {b} \right)-1 =0$的点。

间隔边界：超平面$H_1:w\cdot x +b=1$和$H_2:w \cdot x+b=-1$称为间隔边界。

间隔：$H_1$和$H_2$之间的距离称为间隔，等于$\frac{2}{||w||}$。

在决定分离超平面时只有支持向量起作用，而其他实例点并不起作用，如果移动支持向量将改变所求的解。但是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。支持向量的个数一般很少，所以支持向量机由很少的”重要的”训练样本确定。

1.4 学习的对偶问题

引入对偶的优点：一是对偶问题往往更容易求解，二是自然引入核函数，进而推广到非线性分类问题。

构建拉格朗日函数，对每一个不等式约束引进拉格朗日乘子$\alpha_i \ge 0, i=1,2,\cdots,N$，定义拉格朗日函数：

其中，$\alpha=(\alpha_1,\alpha_2,\cdots ,\alpha_N)^T$为拉格朗日乘子。

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：

所以，为了求解对偶问题的解，需要先求$L(w,b,\alpha)$对$w,b$的极小，然后对$\alpha$求极大。

（1）求$\min\limits_{w,b}L(w,b,\alpha)$

将拉格朗日函数$L(w,b,\alpha)$分别对$w,b$求偏导并令其等于0。

得

将以上两式代入拉格朗日函数，得

即

（2）求$\min\limits_{w,b} L(w,b,\alpha)$对$\alpha$的极大，即是对偶问题：

将以上目标函数由求极大转换成求极小，就得到下面与之等价的对偶最优化问题：

以上最优化的解的形式为：

因此分离超平面可以写成

分类决策函数可以写成

分类决策函数只依赖于输入$x$和训练样本输入的內积，上式称为线性可分支持向量机的对偶形式。

$KTT$条件：$KKT$条件给出了判断某点是否为最优解的必要条件。

算法：线性可分支持向量学习算法

输入：线性可分训练数据集$T=\{(x_1,y_1), (x_2, y_2), \cdots, (x_N, y_N)\}$，其中$x_i\in\mathcal{X} = \mathbf{R}^n$，$y_i \in \mathcal{Y}=\{+1,-1\}$，$1,2,\cdots,N$

输出：最大间隔分离超平面和分类决策函数

（1）构造并求解约束最优化问题：

求得最优解$\alpha^=(\alpha_1^,\alpha_2^,\cdots ,\alpha_N^)^T$。

（2）计算：

并选择$\alpha^$的一个正分量$\alpha_j^ > 0$，计算

（3）求得分离超平面

分类决策函数：

在线性可分支持向量机中，$w^$和$b^$只依赖于训练数据中对应于$\alpha_i^>0$的样本点$(x_i,y_i)$，这些样本点称为支持向量，而其他样本点对$w^$和$b^*$没有影响。

2 线性支持向量机与软间隔最大化

2.1 线性支持向量机

线性可分问题的支持向量机学习方法，对线性不可分训练数据是不适用的，需要修改硬间隔最大化，使其称为软间隔最大化，从而扩展到线性不可分问题。

假定训练数据集不是线性可分的，训练数据中有一些特异点，将这些特异点去除后，剩下大部分的样本点组成的集合是线性可分的。
线性不可分意味着某些样本点$(x_i,y_i)$不能满足函数间隔大于等于1的约束条件，为了解决这个问题，可以对每个样本点$(x_i,y_i)$引入一个松弛变量$\xi_i \ge 0$，使函数间隔加上松弛变量大于等于1，约束条件变为：

同时，对每个松弛变量$\xi_i$，支付一个代价$\xi_i$，目标函数由原来 $\frac{1}{2} ||w||^2$变为：

其中$C>0$是惩罚参数，一般由应用问题决定，$C$值大时对误分类的惩罚增大，$C$值小时对误分类的惩罚减小，以上目标函数包含两层含义：使$\frac{1}{2}||w||^2$尽量小即间隔尽量大，同时使误分类点的个数尽量小，$C$是调和二者的系数。

因此，可以和训练数据集线性可分时一样来考虑训练数据集线性不可分的线性支持向量机学习问题。称为软间隔最大化。

学习问题为：

求得分离超平面

分类决策函数为

称为线性支持向量机。

2.2 学习的对偶算法

上节中学习的原始问题的对偶问题是：

推导过程：

原始最优化问题的拉格朗日函数是：

其中，$\alpha_i \ge 0, \mu_i \ge 0$。

对偶问题是拉格朗日函数的极大极小问题，首先求$L(w, b, \xi, \alpha, \mu)$对$w,b,\xi$的极小，由

得

将以上三式代入原始最优化问题的拉格朗日函数中，得

再对$\min \limits _{w, b, \xi} L(w, b, \xi, \alpha, \mu)$求$\alpha$的极大，即得对偶问题：

利用等式约束$C-\alpha_i-\mu_i=0$消去$\mu_i$，从而只留下变量$\alpha_i$，并将以上后三个约束条件写成：

再对目标函数求极大转换为求极小，即可得到原始问题的对偶问题。

$KKT条件$：

因此分离超平面可以写成

分类决策函数可以写成

上式即为线性支持向量机的对偶形式。

输入：线性支持向量机学习算法

输入：线性可分训练数据集$T=\{(x_1,y_1), (x_2, y_2), \cdots, (x_N, y_N)\}$，其中$x_i\in\mathcal{X} = \mathbf{R}^n$，$y_i \in \mathcal{Y}=\{+1,-1\}$，$1,2,\cdots,N$

输出：最大间隔分离超平面和分类决策函数

（1）构造并求解约束最优化问题：

求得最优解$\alpha^=(\alpha_1^,\alpha_2^,\cdots ,\alpha_N^)^T$。

（2）计算：

并选择$\alpha^$的一个正分量$0 < \alpha_j^ < C$，计算

（3）求得分离超平面

分类决策函数：

在步骤（2）中，对任一适合条件$0 < \alpha_j^ < C$的$\alpha_j^$，都可以求出$b^*$，但是由于原始问题对$b$的解并不唯一，所以实际计算时可以取在所有符合条件的样本点上的平均值。

2.3 支持向量

如下图所示，软间隔的支持向量要比线性可分的情况复杂一些。分离超平面由实线表示，间隔边界由虚线表示，正例点由o表示，负例点由x表示。

mark

软间隔的支持向量$x_i$或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分一侧。若$\alpha_i^ <C$，则$\xi_i=0$，支持向量恰好落在间隔边界上；若$\alpha_i^ =C$，$0<\xi_i<1$，则分类正确，支持向量在间隔边界与分离超平面之间；若$\alpha_i^* =c$，$\xi_i="1$，则支持向量在分离超平面上；若$\alpha_i^*">1$，则支持向量位于分离超平面误分一侧。

2.4 合页损失函数

线性支持向量机学习还有另一种解释，就是最小化以下目标函数：

目标函数的第一项是经验损失或者经验风险，函数

称为合页损失函数（hinge loss）。下标$+$表示大于0取自身，小于等于0取0。这就是说，当样本点$(x_i,y_i)$被正确分类且函数间隔$y_i(w\cdot x_i + b)$大于1时，损失时0，否则损失是$1-y_i(w \cdot x_i + b)$。目标函数第二项是系数为$\lambda$的$w$的$L_2$的范数，是正则化项。

即 线性支持向量机原始最优化问题：

等价于

如下图，0-1损失函数是二类分类问题的真正的损失函数，而合页损失函数是0-1损失函数的上界。由于0-1损失函数不是连续可导的，直接优化由其构成的目标函数比较困难，可以认为线性支持向量机是优化由0-1损失函数的上界构成的目标函数。

mark

上图中虚线显示的是感知机的损失函数$\left[y_{i}\left(w \cdot x_{i}+b\right)\right]_{+}$。这时，当样本点$(x_i, y_i)$合页损失被正确分类时，损失是0，否则损失是$-y_{i}\left(w \cdot x_{i}+b\right)$。相比之下，合页损失函数不仅要分类正确，而且确信度足够高时损失才是0。也就是说，合页损失函数对学习有更高的要求。

3 非线性支持向量机与核函数

3.1 核技巧

非线性分类问题

非线性分类问题是指通过利用非线性模型才能很好地进行分类的问题。

mark

非线性问题往往不好求解，所以希望能用解线性分类问题的方法解决这个问题。所采取的方法是进行一个非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。如上图，通过变换，将左图中椭圆变换成右图中的直线，从而将非线性分类问题变换为线性分类问题。

设原空间为$\mathcal{X} \subset \mathbf{R}^2, x=(x^{(1)}, x^{(2)})^T \in \mathcal{X}$，新空间$\mathcal{Z} \subset \mathbf{R}^2, z=(z^{(1)}, z^{(2)})^T \in \mathcal{Z}$，定义从原空间到新空间的变换（映射）：

经过变换，原空间$\mathcal{X} \subset \mathbf{R}^2$变换为新空间$\mathcal{Z} \subset \mathbf{R}^2$，原空间中的点响应地变换为新空间中的点，原空间中的椭圆

变换成新空间中的直线

在变换后的新空间里，直线$ {w_{1} z^{(1)}+w_{2} z^{(2)}+b=0}$可以将变换后的正负实例点正确分开。这样，原空间的非线性可分问题就变成了新空间的线性可分问题。

用线性分类的方法求解非线性分类问题分为两步：首先使用一个变换将原空间的数据映射到新空间；然后在新空间中用线性分类学习方法从训练数据中学习分类模型。核技巧就属于这样的方法。

核函数的定义

设$\mathcal{X}$是输入空间（欧式空间$R^n$的子集或离散集合），又设$\mathcal{H}$为特征空间（希尔伯特空间），如果存在一个从$\mathcal{X}$到$\mathcal{H}$的映射

使得对所有$x,z\in \mathcal{X}$，函数$K(x,z)$满足条件

其中$K(x,z)$为核函数，$\phi(x)$为映射函数，式中$\phi(x)\cdot\phi(z)$为两者的內积。

核技巧的想法是，在学习与预测时只定义核函数$K(x,z)$，而不显式地定义映射函数$\phi$，通常，直接计算$K(x,z)$比较容易，而通过$\phi(z)$和$\phi(z)$计算$K(x,z)$并不容易，特征空间$\mathcal{H}$一般是高维的，甚至是无穷维的，对于给定的核函数，特征空间$\mathcal{H}$和映射函数$\phi$的取法并不唯一，可以取不同的特征空间，即便在同一特征空间里也可以取不同的映射。

核技巧在支持向量机中的应用

在线性支持向量机的对偶问题中，无论是目标函数还是决策函数（分离超平面）都只涉及输入实例与实例之间的內积。在对偶问题的目标函数中的內积$x_i\cdot x_j$可以用$K(x_i,x_j)=\phi(x_i)\cdot\phi(z)$来代替。此时对偶问题的目标函数成为：

同样，分类决策函数中的內积也可以用核函数代替，而分类决策函数式成为

这等价于经过映射函数$\phi$将原来的输入空间变换到一个新的特征空间，将输入空间的內积$x_i\cdot x_j$变换为特征空间的內积$\phi(x_i)\cdot \phi(x_j)$，在新的特征空间里从训练样本中学习线性支持向量机，当映射函数是非线性函数时，学习到的含有核函数的支持向量机是非线性分类模型。

3.2 正定核

正定核的充要条件：设$K:\mathcal{X} \times \mathcal{X} \rightarrow \mathbf{R}$是对称函数，则$K(x,z)$为正定核函数的充要条件是对任意$x_i \in \mathcal{X}, i=1,2,\cdots,m$，$K(x,z)$对应的$Gram$矩阵 $K=\left[K(x_i, x_j) \right]_{m\times m}$是半正定的。

3.3 常用核函数

  1. 多项式核函数

对应的支持向量机是一个$p$次多项式分类器，分类决策函数成为

  1. 高斯核函数

对应的支持向量机是高斯径向基函数分类器，分类决策函数成为

3.3 非线性支持向量机

算法：非线性支持向量机学习算法

输入：线性可分训练数据集$T=\{(x_1,y_1), (x_2, y_2), \cdots, (x_N, y_N)\}$，其中$x_i\in\mathcal{X} = \mathbf{R}^n$，$y_i \in \mathcal{Y}=\{+1,-1\}$，$1,2,\cdots,N$

输出：分类决策函数

（1）选取适当的核函数$K(x,z)$和适当的参数$C$，构造并求解最优化问题

求得最优解$\alpha^=(\alpha_1^,\alpha_2^,\cdots ,\alpha_N^)^T$。

（2）并选择$\alpha^$的一个正分量$0 < \alpha_j^ < C$，计算

（3）构造决策函数：

当$K(x,z)$是正定核函数时，最优化问题是凸二次规划问题，解是存在的。

4 序列最小最优化算法

SMO算法要解以下凸二次规划的对偶问题：

在这个问题中，变量时朗格朗日乘子，一个变量$\alpha_i$对应于一个样本点$(x_i,y_i)$。

SMO是一种启发式算法：如果所有变量的解都满足此最优化问题的KKT条件，那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因为这会使得原始二次规划问题的目标函数值变得很小。

这时子问题可以通过解析方法求解，可以大大提高整个算法的计算速度。子问题有两个变量，一个是违反KKT条件最严重的那一个，另一个由约束条件自动确定。如此，SMO算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的。

4.1 两个变量二次规划的求解方法

假设选择的两个变量是$\alpha_1, \alpha_2$，其他变量$\alpha_i(i=3,4,\cdots,N)$是固定的。于是SMO的最优化问题的子问题可以写成：

其中$K_{ij}=K(x_i, x_j)，i,j=1,2,\cdots , N$，$\zeta$是常数。忽略了不含$\alpha_1,\alpha_2$的常数项。

4.2 变量选择方法

一个是违反KKT条件最严重的那一个，另一个由约束条件自动确定。具体略。

算法：SMO算法

输入：线性可分训练数据集$T=\{(x_1,y_1), (x_2, y_2), \cdots, (x_N, y_N)\}$，其中$x_i\in\mathcal{X} = \mathbf{R}^n$，$y_i \in \mathcal{Y}=\{+1,-1\}$，$1,2,\cdots,N$，精度$\epsilon$

输出：近似解$\hat{\alpha}$。

（1）取初值$\alpha^{(0)}=0$，令$k=0$；

（2）选取最优化变量$\alpha_1^{(k)},\alpha_2^{(k)}$，解析求解两个变量的最优化问题，求得最优解$\alpha_1^{(k+1)},\alpha_2^{(k+1)}$，更新$\alpha$为$\alpha^{(k+1)}$;

（3）若在精度$\epsilon$范围内满足停止条件：

其中

则转（4），否则令$k=k+1$，转（2）。

（4）取$\hat{\alpha}=\alpha^{(k+1)}$。

实战

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
import numpy as np
import pandas as pd
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
import math

class SVM:
    def __init__(self, max_iter=100, kernel='linear'):
        self.max_iter = max_iter
        self._kernel = kernel

    def init_args(self, features, labels):
        self.m, self.n = features.shape
        self.X = features
        self.Y = labels
        self.b = 0.0

        # 将Ei保存在一个列表里
        self.alpha = np.ones(self.m)
        self.E = [self._E(i) for i in range(self.m)]
        # 松弛变量
        self.C = 0.5

    def _KKT(self, i):
        y_g = self._g(i) * self.Y[i]
        if self.alpha[i] == 0:
            return y_g >= 1
        elif 0 < self.alpha[i] < self.C:
            return y_g == 1
        else:
            return y_g <= 1

    # g(x)预测值，输入xi
    def _g(self, i):
        r = self.b
        for j in range(self.m):
            r += self.alpha[j] * self.Y[j] * self.kernel(self.X[i], self.X[j])
        return r

    # 核函数
    def kernel(self, x1, x2):
        if self._kernel == 'linear':
            return sum([x1[k] * x2[k] for k in range(self.n)])
        elif self._kernel == 'poly':
            return (sum([x1[k] * x2[k] for k in range(self.n)]) + 1) ** 2
        elif self._kernel == 'gaussian':
            return sum([math.exp(-(x1[k]-x2[k])**2 / (2)) for k in range(self.n)])
        return

    # E(x)为g(x)的预测值和y的差
    def _E(self, i):
        return self._g(i) - self.Y[i]

    def _init_alpha(self):
        # 外层循环首先遍历所有满足0<a<C的样本点，检验是否满足KKT
        index_list = [i for i in range(self.m) if 0 < self.alpha[i] < self.C]
        # 否则遍历整个训练集
        non_satisfy_list = [i for i in range(self.m) if i not in index_list]
        index_list.extend(non_satisfy_list)

        for i in index_list:
            if self._KKT(i):
                continue
            # 选择第一个变量
            E1 = self.E[i]
            # 选择第第二个变量 如果E1是+，选择最小的，如果E1是负的，选择最大的
            if E1 >= 0:
                j = min(range(self.m), key=lambda x: self.E[x])
            else:
                j = max(range(self.m), key=lambda x: self.E[x])
            return i, j

    def _compare(self, _alpha, L, H):
        if _alpha > H:
            return H
        elif _alpha < L:
            return L
        else:
            return _alpha

    def fit(self, features, labels):
        self.init_args(features, labels)

        for t in range(self.max_iter):
            # Train
            i1, i2 = self._init_alpha()
            # 边界
            if self.Y[i1] == self.Y[i2]:
                L = max(0, self.alpha[i2] + self.alpha[i1] - self.C)
                H = min(self.C, self.alpha[i2] + self.alpha[i1])
            else:
                L = max(0, self.alpha[i2] - self.alpha[i1])
                H = min(self.C, self.C + self.alpha[i2] - self.alpha[i1])

            E1 = self.E[i1]
            E2 = self.E[i2]

            eta = self.kernel(self.X[i1], self.X[i1]) + \
                  self.kernel(self.X[i2], self.X[i2]) - \
                  2 * self.kernel(self.X[i1], self.X[i2])

            if eta <= 0:
                continue

            alpha2_new_unc = self.alpha[i2] + self.Y[i2] * (E1-E2)/eta
            alpha2_new = self._compare(alpha2_new_unc, L, H)
            alpha1_new = self.alpha[i1] + self.Y[i1] * self.Y[i2] * (self.alpha[i2] - alpha2_new)

            b1_new = -E1-self.Y[i1] * self.kernel(self.X[i1], self.X[i1]) *(alpha1_new-self.alpha[i1]) -\
                        self.Y[i2] * self.kernel(self.X[i2], self.X[i1]) * (alpha2_new - self.alpha[i2]) + \
                        self.b
            b2_new = -E2-self.Y[i1] * self.kernel(self.X[i1], self.X[i2]) *(alpha1_new-self.alpha[i1]) -\
                        self.Y[i2] * self.kernel(self.X[i2], self.X[i2]) * (alpha2_new - self.alpha[i2]) + \
                        self.b

            if 0 < alpha1_new < self.C:
                b_new = b1_new
            elif 0 < alpha2_new < self.C:
                b_new = b2_new
            else:
                # 选择中点
                b_new = (b1_new + b2_new) / 2

            # 更新参数
            self.alpha[i1] = alpha1_new
            self.alpha[i2] = alpha2_new
            self.b = b_new

            self.E[i1] = self._E(i1)
            self.E[i2] = self._E(i2)

        return "train done!"

    def predict(self, data):
        r = self.b
        for i in range(self.m):
            r += self.alpha[i] * self.Y[i] + self.kernel(data, self.X[i])
        return 1 if r > 0 else -1

    def score(self, X_test, y_test):
        right_count = 0
        for i in range(len(X_test)):
            result = self.predict(X_test[i])
            if result == y_test[i]:
                right_count += 1
        return right_count / len(X_test)


def create_data():
    iris = load_iris()
    df = pd.DataFrame(iris.data, columns=iris.feature_names)
    df['label'] = iris.target
    df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']
    data = np.array(df.iloc[:100, [0, 1, -1]])
    for i in range(len(data)):
        if data[i, -1] == 0:
            data[i, -1] = -1
    return data[:, :2], data[:, -1]

if __name__ == '__main__':
    X, y = create_data()
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25)
    svm = SVM(max_iter=1000, kernel='linear')
    print(svm.fit(X_train, y_train))
    print(svm.score(X_test, y_test))

    from sklearn.svm import SVC
    clf = SVC()
    clf.fit(X_train, y_train)
    print(clf.score(X_test, y_test))

参考文献

统计学习方法. 李航
https://github.com/fengdu78/lihang-code/blob/master/%E7%AC%AC07%E7%AB%A0%20%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA/7.support-vector-machine.ipynb

Donate comment here
------------The End------------
0%