那些平台可以给网站做外链,wordpress开启缓存,网站页面统计代码,WordPress如何设置站点名称支持向量机#xff0c;可以看着是升级版的感知机#xff0c;与感知机相比。他们都是找到一个超平面对数据集进行分割#xff0c;区别在于#xff0c;感知机模型得到的超平面空间中可以有无穷个超平面#xff0c;但支持向量机仅含有一个#xff0c;这一个超平面与样本点的…支持向量机可以看着是升级版的感知机与感知机相比。他们都是找到一个超平面对数据集进行分割区别在于感知机模型得到的超平面空间中可以有无穷个超平面但支持向量机仅含有一个这一个超平面与样本点的间隔是最大化的。
支持向量机学习方法包含三种模型
线性可分支持向量机要求训练集线性可分通过硬间隔最大化得到超平面。线性支持向量机要求训练集近似线性可分通过软间隔最大化获得超平面非线性支持向量机训练集线性不可分可通过使用核函数将线性不可分的训练集转换为线性可分的数据集并通过软间隔最大化获得超平面。
线性可分支持向量机
对于线性可分的数据集学习的目标是在特征空间中找到一个分离超平面能将实例分到不同的类。分离超平面将特征空间划分为两部分一部分是正类一部分是负类。分离超平面的法向量指向的一侧为正类另一侧为负类。
并且要求这个分离超平面距离最近的两个点的距离之和最大这个分离超平面被称为间隔最大分离超平面。
线性可分支持向量机的数学模型为 f ( x ) s i g n ( w ∗ ∗ x b ∗ ) f(x)sign(w^**xb^*) f(x)sign(w∗∗xb∗)
其中 w ∗ ∗ x b ∗ 0 w^**xb^* 0 w∗∗xb∗0就是间隔最大分离超平面。
我们所需要求得的模型就是这个间隔最大的分离超平面。
函数间隔和几何间隔
函数间隔
一般来说一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面 w ∗ x b 0 w*xb0 w∗xb0确定的情况下 ∣ w ∗ x b ∣ |w*xb| ∣w∗xb∣能够相对地表示点x距离超平面的远近。而 w ∗ x b w*xb w∗xb的符号与类标记 y y y的符号是否一致能够表示分类是否正确。因为在二分类问题中 y y y要么为1要么为-1所以可用 y ( w ∗ x b ) y(w*xb) y(w∗xb)来表示分类的正确性及确信度这就是函数间隔的概念。
定义超平面关于样本点 ( x i , y i ) (x_i,y_i) (xi,yi)的函数间隔为 γ ^ i y i ( w ⋅ x i b ) \hat{\gamma}_iy_i(w \cdot x_ib) γ^iyi(w⋅xib) 定义超平面 ( w , b ) (w,b) (w,b)关于训练数据集 T T T的函数间隔为超平面 ( w , b ) (w,b) (w,b)关于 T T T中所有样本点 ( x i , y i ) (x_i,y_i) (xi,yi)的函数间隔的最小值 γ ^ min i 1 , . . . , N γ ^ i \hat{\gamma} \min_{i1,...,N}\hat{\gamma}_i γ^i1,...,Nminγ^i 但是选择分离超平面时只有函数间隔还不够。因为只要成比例改变 w w w和 b b b超平面并没有改变函数间隔却改变了。
几何间隔
因为函数间隔无法确定 w w w和 b b b所以可以对 w w w施加约束如规范化 ∣ ∣ w ∣ ∣ 1 ||w||1 ∣∣w∣∣1这样函数间隔就成为几何间隔。
定义超平面关于样本点 ( x i , y i ) (x_i,y_i) (xi,yi)的几何间隔为 γ i y i ( w ∣ ∣ w ∣ ∣ ⋅ x i b ∣ ∣ w ∣ ∣ ) \gamma_i\quad y_i\left( \frac{w}{||w||} \cdot x_i\frac{b}{||w||} \right) γiyi(∣∣w∣∣w⋅xi∣∣w∣∣b)
定义超平面w,b关于训练数据集T的几何间隔为超平面w,b关于T中所有样本点xi,yi的几何间隔的最小值 γ min i 1 , . . . , N γ i \gamma\min_{i1,...,N}\gamma_i γi1,...,Nminγi
几何间隔与函数间隔的关系 γ γ ^ ∣ ∣ w ∣ ∣ \gamma\frac{\hat{\gamma}}{||w||} γ∣∣w∣∣γ^
最大间隔法
求一个最大间隔分离超平面可以用约束最优化问题的形式来表示 max w , b γ s . t . y i ( w ∣ ∣ w ∣ ∣ ⋅ x i b ∣ ∣ w ∣ ∣ ) ≥ γ , i 1 , 2 , . . . , N \begin{aligned} \max_{w,b}\gamma \\ s.t. \quad y_i\left( \frac{w}{||w||} \cdot x_i\frac{b}{||w||} \right)\geq \gamma,\quad i1,2,...,N \end{aligned} w,bmaxγs.t.yi(∣∣w∣∣w⋅xi∣∣w∣∣b)≥γ,i1,2,...,N 我们可以通过几何间隔和函数间隔的关系代入上面的公式 max w , b γ ^ ∣ ∣ w ∣ ∣ s . t . y i ( w ⋅ x i b ) ≥ γ ^ , i 1 , 2 , . . . , N \begin{aligned} \max_{w,b}\frac{\hat{\gamma}}{||w||} \\ s.t.\quad y_i\left( w \cdot x_ib \right)\geq \hat{\gamma},\quad i1,2,...,N \end{aligned} w,bmax∣∣w∣∣γ^s.t.yi(w⋅xib)≥γ^,i1,2,...,N 因为函数间隔对w和b按比例改变函数间隔也按此比例改变的特性w和b的改变并不会影响上式中的目标函数的优化和约束条件因此我们可以对函数间隔随意取值为了方便我们取 γ ^ 1 \hat{\gamma}1 γ^1
另外我们可以将最大化问题转换为最小化问题即将 max 1 ∣ ∣ w ∣ ∣ \max \frac{1}{||w||} max∣∣w∣∣1转换为 min ∣ ∣ w ∣ ∣ \min ||w|| min∣∣w∣∣这样得到的问题为 min w , b ∣ ∣ w ∣ ∣ s . t . y i ( w ⋅ x i b ) − 1 ≥ 0 , i 1 , 2 , . . . , N \begin{aligned} \min_{w,b}||w|| \\ s.t.\quad y_i\left( w \cdot x_ib \right)-1\geq 0,\quad i1,2,...,N \end{aligned} w,bmin∣∣w∣∣s.t.yi(w⋅xib)−1≥0,i1,2,...,N 可以使用拉格朗日乘数法求解。
同时为了之后的计算方便我们可以将问题转变为 min w , b 1 2 ∣ ∣ w ∣ ∣ 2 s . t . y i ( w ⋅ x i b ) − 1 ≥ 0 , i 1 , 2 , . . . , N \begin{aligned} \min_{w,b}\frac12||w||^2 \\ s.t.\quad y_i\left( w \cdot x_ib \right)-1\geq 0,\quad i1,2,...,N \end{aligned} w,bmin21∣∣w∣∣2s.t.yi(w⋅xib)−1≥0,i1,2,...,N 因为 ∣ ∣ w ∣ ∣ ≥ 0 ||w||\geq 0 ∣∣w∣∣≥0因此平方后再乘以一个系数不会对最小化问题产生影响。
上述的问题是一个凸二次规划问题。
现在我们只需解答上述问题得到最优特征向量 w ∗ w^* w∗和最优偏置 b ∗ b^* b∗就可以得到最大间隔分离超平面和决策函数。问题在于如何求解该问题。
对偶算法
可以参考最大熵模型使用过拉格朗日乘数法和对偶法解决约束条件下的最优化问题。
这里和最大熵模型使用的拉格朗日乘子法的不同在于最大熵模型中的约束条件是等式约束条件而这里是不等式约束条件对于这样的情况可以应用KKT条件去求得最优值。
构建拉格朗日函数 L ( w , b , a ) 1 2 ∣ ∣ w ∣ ∣ 2 − ∑ i 1 N a i ( y i ( w ⋅ x i b ) − 1 ) 1 2 ∣ ∣ w ∣ ∣ 2 − ∑ i 1 N a i y i ( w ⋅ x i b ) ∑ i 1 N a i L(w,b,a)\frac12||w||^2-\sum_{i1}^Na_i(y_i(w \cdot x_ib)-1)\frac12||w||^2-\sum_{i1}^Na_i y_i(w \cdot x_ib)\sum_{i1}^Na_i L(w,b,a)21∣∣w∣∣2−i1∑Nai(yi(w⋅xib)−1)21∣∣w∣∣2−i1∑Naiyi(w⋅xib)i1∑Nai 其中 α ( α 1 , α 2 , … , α N ) α(α_1,α_2,…,α_N) α(α1,α2,…,αN)为拉格朗日乘子向量。
原始问题为 min w , b max a L ( w , b , a ) \min_{w,b}\max_{a}L(w,b,a) w,bminamaxL(w,b,a) 其对偶问题为 max a min w , b L ( w , b , a ) \max_a\min_{w,b}L(w,b,a) amaxw,bminL(w,b,a) 现在求对偶问题的内部最小化。
我们对w和b分别求偏导并令偏导数等于0。 ∇ w L ( w , b , a ) w − ∑ i 1 N a i y i x i 0 ∇ b L ( w , b , a ) − ∑ i 1 N a i y i 0 \nabla_wL(w,b,a)w-\sum_{i1}^Na_iy_ix_i0 \\ \nabla_b L(w,b,a)-\sum_{i1}^Na_iy_i0 ∇wL(w,b,a)w−i1∑Naiyixi0∇bL(w,b,a)−i1∑Naiyi0 得到 w ∑ i 1 N a i y i x i ∑ i 1 N a i y i 0 w\sum_{i1}^Na_iy_ix_i \\ \sum_{i1}^Na_iy_i0 wi1∑Naiyixii1∑Naiyi0 将上面的结论代入到拉格朗日函数之中 min w , b L ( w , b , a ) 1 2 ∑ i 1 N ∑ j 1 N a i a j y i y j ( x i ⋅ x j ) − ∑ i 1 N a i y i ( ( ∑ j 1 N a j y j x j ) ⋅ x i b ) ∑ i 1 N a i 1 2 ∑ i 1 N ∑ j 1 N a i a j y i y j ( x i ⋅ x j ) − ∑ i 1 N ∑ j 1 N a i a j y i y j ( x i ⋅ x j ) − ∑ i 1 N a i y i b ∑ i 1 N a i − 1 2 ∑ i 1 N ∑ j 1 N a i a j y i y j ( x i ⋅ x j ) ∑ i 1 N a i \begin{align*} \min_{w,b}L(w,b,a)\frac12\sum_{i1}^N\sum_{j1}^Na_ia_jy_iy_j(x_i \cdot x_j)-\sum_{i1}^Na_iy_i\left(\left(\sum_{j1}^Na_jy_jx_j\right) \cdot x_ib \right)\sum_{i1}^Na_i \\ \frac12\sum_{i1}^N\sum_{j1}^Na_ia_jy_iy_j(x_i \cdot x_j)-\sum_{i1}^N\sum_{j1}^Na_ia_jy_iy_j(x_i \cdot x_j)-\sum_{i1}^Na_iy_ib\sum_{i1}^Na_i \\ -\frac12\sum_{i1}^N\sum_{j1}^Na_ia_jy_iy_j(x_i \cdot x_j)\sum_{i1}^Na_i \end{align*} w,bminL(w,b,a)21i1∑Nj1∑Naiajyiyj(xi⋅xj)−i1∑Naiyi((j1∑Najyjxj)⋅xib)i1∑Nai21i1∑Nj1∑Naiajyiyj(xi⋅xj)−i1∑Nj1∑Naiajyiyj(xi⋅xj)−i1∑Naiyibi1∑Nai−21i1∑Nj1∑Naiajyiyj(xi⋅xj)i1∑Nai 接下来求对偶问题中的外部极大化问题
我们可以通过在右侧乘以一个-1将最大化问题转换为求最小化的问题 min a 1 2 ∑ i 1 N ∑ j 1 N a i a j y i y j ( x i ⋅ x j ) − ∑ i 1 N a i s . t . ∑ i 1 N a i y i 0 a i ≥ 0 , i 1 , 2 , . . . , N \begin{aligned} \min_a\frac12\sum_{i1}^N\sum_{j1}^Na_ia_jy_iy_j(x_i \cdot x_j)-\sum_{i1}^Na_i \\ s.t.\quad \sum_{i1}^Na_iy_i0 \\ a_i \geq 0,i1,2,...,N \end{aligned} amin21i1∑Nj1∑Naiajyiyj(xi⋅xj)−i1∑Nais.t.i1∑Naiyi0ai≥0,i1,2,...,N 通过约束条件我们可以得到α的各个分量之间的关系代入原式后对 α i α_i αi求偏导并使偏导数为0求得α向量。
利用KKT求最优w和b
线性可分支持向量机中的原问题和对偶问题互相之间是强对偶关系而KKT是强对偶关系的充要条件。
因为原始问题和对偶问题是强对偶关系所以一定满足KKT条件 ∇ w L ( w ∗ , b ∗ , a ∗ ) w ∗ − ∑ i 1 N a i ∗ y i x i 0 (1) \nabla_wL(w^*,b^*,a^*)w^*-\sum_{i1}^Na_i^*y_ix_i0 \tag{1} ∇wL(w∗,b∗,a∗)w∗−i1∑Nai∗yixi0(1) ∇ b L ( w ∗ , b ∗ , a ∗ ) − ∑ i 1 N a i ∗ y i 0 (2) \nabla_b L(w^*,b^*,a^*)-\sum_{i1}^Na_i^*y_i0 \tag{2} ∇bL(w∗,b∗,a∗)−i1∑Nai∗yi0(2) a i ∗ ( y − i ( x i b ∗ ) − 1 ) 0 , i 1 , 2 , . . . , N (3) a_i^*(y-i(x_ib^*)-1)0,i1,2,...,N \tag{3} ai∗(y−i(xib∗)−1)0,i1,2,...,N(3) y i ( w ∗ ⋅ x i b ∗ ) − 1 ≥ 0 , i 1 , 2 , . . . N (4) y_i(w^* \cdot x_i b^*)-1 \geq0,i1,2,...N \tag{4} yi(w∗⋅xib∗)−1≥0,i1,2,...N(4) a i ∗ ≥ 0 , i 1 , 2 , . . . N (5) a_i^* \geq 0,i1,2,...N \tag{5} ai∗≥0,i1,2,...N(5)
在上面的五个KKT条件中上标星号表示为最优解。等式(1)和等式(2)是我们之前在内部极小化拉格朗日函数的时候求得的剩下的三个式子是KKT条件需要满足的。
那么根据等式(1)我们可以很容易的得到 w ∗ ∑ i a i ∗ y i x i w^*\sum_{i}a_i^*y_ix_i w∗i∑ai∗yixi 主要来看b主要关注于式(3)(4)和(5)。
当 a i ∗ ≥ 0 a_i^* \geq 0 ai∗≥0时 y i ( w ∗ ⋅ x i b ∗ ) − 1 0 y_i(w^* \cdot x_i b^*)-1 0 yi(w∗⋅xib∗)−10此时 $|w^* \cdot x_i b^*|1 $。
而函数距离就是通过 ∣ w ⋅ x b ∣ |w·xb| ∣w⋅xb∣来得到。
也就是说当 a i ∗ ≥ 0 a_i^* \geq 0 ai∗≥0时我们找到了距离超平面的函数距离最小的样本点这样的样本点我们称之为支持向量。
而当 a i ∗ 0 a_i^* 0 ai∗0时 y i ( w ∗ ⋅ x i b ∗ ) − 1 y_i(w^* \cdot x_i b^*)-1 yi(w∗⋅xib∗)−1 可以是大于等于0即这些样本点与超平面的函数距离大于支持向量同时因为 a i ∗ 0 a_i^* 0 ai∗0 说明这些样本点在我们的模型中并未被考虑进去也就是说它们对最大距离分离超平面的确定没有关系。
于是存在一个样本点 ( x i , y i ) (x_i,y_i) (xi,yi)使 a i ∗ ≥ 0 a_i^* \geq 0 ai∗≥0 根据 y i ( w ∗ ⋅ x i b ∗ ) − 1 0 y_i(w^* \cdot x_i b^*)-10 yi(w∗⋅xib∗)−10 可以得到 y i 2 ( w ∗ ⋅ x i b ∗ ) y i → b ∗ y i − w ∗ ⋅ x i → b ∗ y i − ∑ i a i ∗ y i x i ⋅ x j y_i^2(w^* \cdot x_i b^*)y_i\rightarrow b^*y_i-w^* \cdot x_i \rightarrow b^*y_i-\sum_ia_i^*y_ix_i \cdot x_j yi2(w∗⋅xib∗)yi→b∗yi−w∗⋅xi→b∗yi−i∑ai∗yixi⋅xj
现在我们得到了最优 w ∗ w^* w∗和 b ∗ b^* b∗同时 α i ∗ α_i^* αi∗也在上一节通过求偏导得到于是也就得到了最大距离分离超平面和决策函数 ∑ i i N a i ∗ y i ( x ⋅ x i ) b ∗ 0 f ( x ) s i g n ( ∑ i 1 N a i ∗ y i ( x ⋅ x i ) b ∗ ) \sum_{ii}^Na_i^*y_i(x \cdot x_i)b^*0 \\ f(x)sign\left( \sum_{i1}^Na_i^*y_i(x \cdot x_i)b^* \right) ii∑Nai∗yi(x⋅xi)b∗0f(x)sign(i1∑Nai∗yi(x⋅xi)b∗)
线性支持向量机
在线性不可分的数据集中一个超平面不可能把所有样本点都正确分类因此至少存在一个样本点 ( x k , y k ) (x_k,y_k) (xk,yk)使 ( y k ) ( w ⋅ ( x k ) b ) 0 (yk)(w·(xk)b)0 (yk)(w⋅(xk)b)0所以 ( y k ) ( w ⋅ ( x k ) b ) − 1 0 (y_k)(w·(x_k)b)-10 (yk)(w⋅(xk)b)−10与不等式约束矛盾。
在线性支持向量机中我们将线性可分支持向量机的硬间隔最大化改为软间隔最大化就可以在近似线性可分的数据集中运用支持向量机了。
所谓近似线性可分的数据集就是训练数据中有一些样本点将这些样本点去除后就可以得到线性可分的数据集。这些样本点我们称其为特异点。
特异点不满足函数间隔大于等于1的约束条件这时我们对每个样本点引入一个松弛变量 ξ ≥ 0 \xi \geq 0 ξ≥0 使函数间隔加上松弛变量大于等于1于是约束条件变为 y i ( w ⋅ x i b ) ≥ 1 − ξ y_i(w \cdot x_i b) \geq 1- \xi yi(w⋅xib)≥1−ξ 同时将原来的目标函数变为 1 2 ∣ ∣ w ∣ ∣ 2 C ∑ i 1 N ξ i \frac12||w||^2C\sum_{i1}^N\xi_i 21∣∣w∣∣2Ci1∑Nξi 其中 C 0 C0 C0为惩罚参数C值大时对误分类的惩罚增大反之对误分类的惩罚减小。于是最小化上式可以理解为使前一项尽量小即间隔尽量大并且使误分类点的数量尽量小也就是让后一项尽量小。参数C在两者之间有调和作用。这种间隔最大化的方法称为软间隔最大化。
比较直观的理解松弛变量就是松弛变量的加入不再要求特异点与分离超平面的函数距离大于等于1但与此同时也需要给予最小化式子惩罚以此来限制过于松弛的情况而系数C则是用来调节间隔的软硬程度。
这样我们就可以和训练线性可分的数据集一样来训练近似线性可分的数据集了。于是我们得到的问题为 min w , b , ξ 1 2 ∣ ∣ w ∣ ∣ 2 C ∑ i 1 N ξ i s . t . y i ( w ⋅ x i b ) ≥ 1 − ξ i , i 1 , 2 , . . . , N ξ i ≥ 0 , i 1 , 2 , . . . , N \begin{aligned} \min_{w,b,\xi}\frac12||w||^2C\sum_{i1}^N\xi_i \\ s.t.\quad y_i(w \cdot x_ib) \geq 1-\xi_i,i1,2,...,N \\ \xi_i \geq 0,i1,2,...,N \end{aligned} w,b,ξmin21∣∣w∣∣2Ci1∑Nξis.t.yi(w⋅xib)≥1−ξi,i1,2,...,Nξi≥0,i1,2,...,N 从上面的问题中可以看出来线性可分支持向量机是线性支持向量机中的一种特殊情况如果数据集中没有特异点则对于每个样本点来说松弛变量都为0则近似线性可分转变为线性可分的情况。
线性支持向量机最后得到的超平面和决策函数为 w ∗ ⋅ x i b ∗ 0 f ( x ) s i g n ( w ∗ ⋅ x b ∗ ) w^* \cdot x_i b^* 0 \\ f(x)sign(w^* \cdot x b^*) w∗⋅xib∗0f(x)sign(w∗⋅xb∗)
对偶算法
首先建立拉格朗日函数 L ( w , b , ξ , a , μ ) 1 2 ∣ ∣ w ∣ ∣ 2 C ∑ i 1 N ξ i − ∑ i 1 N a i ( y i ( w ⋅ x i b ) − 1 ξ i ) − ∑ i 1 N μ i ξ i L(w,b,\xi,a,\mu)\frac12||w||^2C\sum_{i1}^N\xi_i-\sum_{i1}^Na_i(y_i(w \cdot x_ib)-1\xi_i)-\sum_{i1}^N\mu_i\xi_i L(w,b,ξ,a,μ)21∣∣w∣∣2Ci1∑Nξi−i1∑Nai(yi(w⋅xib)−1ξi)−i1∑Nμiξi 其中拉格朗日乘数 α i ≥ 0 α_i≥0 αi≥0 μ i ≥ 0 \mu_i≥0 μi≥0。
原始问题为 min w , b , ξ max a , μ L ( w , b , ξ , a , μ ) \min_{w,b,\xi}\max_{a,\mu}L(w,b,\xi,a,\mu) w,b,ξmina,μmaxL(w,b,ξ,a,μ) 对偶问题为 max a , μ min w , b , ξ L ( w , b , ξ , a , μ ) \max_{a,\mu}\min_{w,b,\xi}L(w,b,\xi,a,\mu) a,μmaxw,b,ξminL(w,b,ξ,a,μ) 首先对于内部极小化问题对求偏导并使偏导数等于0 ∇ w L ( w , b , ξ , a , μ ) w − ∑ i 1 N a i y i x i 0 (1) \nabla_wL(w,b,\xi,a,\mu)w-\sum_{i1}^Na_iy_ix_i0 \tag{1} ∇wL(w,b,ξ,a,μ)w−i1∑Naiyixi0(1) ∇ b L ( w , b , ξ , a , μ ) − ∑ i 1 N a i y i 0 (2) \nabla_bL(w,b,\xi,a,\mu)-\sum_{i1}^Na_iy_i0 \tag{2} ∇bL(w,b,ξ,a,μ)−i1∑Naiyi0(2) ∇ ξ L ( w , b , ξ , a , μ ) C − a i − μ i 0 (3) \nabla_\xi L(w,b,\xi,a,\mu)C-a_i-\mu_i0 \tag{3} ∇ξL(w,b,ξ,a,μ)C−ai−μi0(3)
得到 w ∑ i 1 N a i y i x i w\sum_{i1}^Na_iy_ix_i wi1∑Naiyixi ∑ i 1 N a i y i 0 \sum_{i1}^Na_iy_i0 i1∑Naiyi0 C − a i − μ i 0 C-a_i-\mu_i0 C−ai−μi0
再将上面三个等式代回至拉格朗日函数中 min w , b , ξ L ( w , b , ξ , a , μ ) − 1 2 ∑ i 1 N ∑ j 1 N a i a j y i y j ( x i ⋅ x j ) ∑ i 1 N a i \min_{w,b,\xi}L(w,b,\xi,a,\mu)-\frac12\sum_{i1}^N\sum_{j1}^Na_ia_jy_iy_j(x_i \cdot x_j)\sum_{i1}^Na_i w,b,ξminL(w,b,ξ,a,μ)−21i1∑Nj1∑Naiajyiyj(xi⋅xj)i1∑Nai 再解对偶问题的外部极大化问题得到问题 max a − 1 2 ∑ i 1 N ∑ j 1 N a i a j y i y j ( x i ⋅ x j ) ∑ i 1 N a i ∑ i 1 N a i y i 0 s . t . C − a i − μ i 0 μ i ≥ 0 , i 1 , 2 , . . . , N \max_a-\frac12\sum_{i1}^N\sum_{j1}^Na_ia_jy_iy_j(x_i \cdot x_j)\sum_{i1}^Na_i \\ \sum_{i1}^Na_iy_i0 \\ s.t.\quad C-a_i-\mu_i0 \\ \mu_i \geq 0,i1,2,...,N amax−21i1∑Nj1∑Naiajyiyj(xi⋅xj)i1∑Naii1∑Naiyi0s.t.C−ai−μi0μi≥0,i1,2,...,N 在约束条件中我们可以利用后面三个式子将μi消去因为 μ i C − α i \mu_iC-α_i μiC−αi且 μ i ≥ 0 μ_i\geq 0 μi≥0所以 C − α i ≥ 0 C-α_i \geq 0 C−αi≥0又因为 α i ≥ 0 α_i\geq 0 αi≥0所以 C ≥ α i ≥ 0 C \geq α_i \geq 0 C≥αi≥0。
并且我们将最大化问题通过乘以一个-1转换为最小化问题。
于是上述问题转变为 min a 1 2 ∑ i 1 N ∑ j 1 N a i a j y i y j ( x i ⋅ x j ) − ∑ i 1 N a i s . t . ∑ i 1 N a i y i 0 0 ≤ a i ≤ C , i 1 , 2 , . . . , N \begin{aligned} \min_a\frac12\sum_{i1}^N\sum_{j1}^Na_ia_jy_iy_j(x_i \cdot x_j)-\sum_{i1}^Na_i \\ s.t. \quad \sum_{i1}^Na_iy_i0 \\ 0\leq a_i \leq C,i1,2,...,N \end{aligned} amin21i1∑Nj1∑Naiajyiyj(xi⋅xj)−i1∑Nais.t.i1∑Naiyi00≤ai≤C,i1,2,...,N 此时根据约束条件中α的各个分量的关系代入极小化的式子中并对每一个αi求偏导并令偏导数为0即可得到α向量。
线性支持向量机的KKT条件
与线性可分支持向量机相似由于原始问题和对偶问题之间满足强对偶关系因此可以利用KKT条件对 w ∗ w^* w∗和 b ∗ b^* b∗进行求解。以下是线性支持向量机的KKT条件 ∇ w L ( w ∗ , b ∗ , ξ ∗ , a ∗ , μ ∗ ) w ∗ − ∑ i 1 N a i ∗ y i x i 0 (1) \nabla_wL(w^*,b^*,\xi^*,a^*,\mu^*)w^*-\sum_{i1}^Na_i^*y_ix_i0 \tag{1} ∇wL(w∗,b∗,ξ∗,a∗,μ∗)w∗−i1∑Nai∗yixi0(1) ∇ b L ( w ∗ , b ∗ , ξ ∗ , a ∗ , μ ∗ ) − ∑ i 1 N a i ∗ y i 0 (2) \nabla_bL(w^*,b^*,\xi^*,a^*,\mu^*)-\sum_{i1}^Na_i^*y_i0 \tag{2} ∇bL(w∗,b∗,ξ∗,a∗,μ∗)−i1∑Nai∗yi0(2) ∇ ξ L ( w ∗ , b ∗ , ξ ∗ , a ∗ , μ ∗ ) C − a i ∗ − μ i ∗ 0 (3) \nabla_\xi L(w^*,b^*,\xi^*,a^*,\mu^*)C-a_i^*-\mu_i^*0 \tag{3} ∇ξL(w∗,b∗,ξ∗,a∗,μ∗)C−ai∗−μi∗0(3) a i ∗ ( y i ( w ∗ ⋅ x i b ∗ ) − 1 ξ i ∗ ) 0 (4) a_i^*(y_i(w^* \cdot x_i b^*)-1\xi_i^*)0 \tag{4} ai∗(yi(w∗⋅xib∗)−1ξi∗)0(4) μ i ∗ ξ i ∗ 0 (5) \mu_i^*\xi_i^*0 \tag{5} μi∗ξi∗0(5) y i ( w ∗ ⋅ x i b ∗ ) − 1 ξ i ∗ ≥ 0 (6) y_i(w^* \cdot x_i b^*)-1\xi_i^* \geq 0 \tag{6} yi(w∗⋅xib∗)−1ξi∗≥0(6) ξ i ∗ ≥ 0 (7) \xi_i^* \geq 0 \tag{7} ξi∗≥0(7) a i ∗ ≥ 0 (8) a_i^* \geq 0 \tag{8} ai∗≥0(8) μ i ∗ ≥ 0 , i 1 , 2 , . . . , N (9) \mu_i^* \geq 0 ,i1,2,...,N \tag{9} μi∗≥0,i1,2,...,N(9)
若存在 α m C α_mC αmC则根据式(3)可得 μ m 0 μ_m0 μm0根据式(4)可得 y m ( w ∗ ⋅ x m b ∗ ) − 1 ξ m ∗ ≥ 0 y_m(w^* \cdot x_m b^*)-1\xi_m^* \geq 0 ym(w∗⋅xmb∗)−1ξm∗≥0 则无法确定 b ∗ b^* b∗根据式(5)可得 ξ m ∗ 0 \xi_m^* 0 ξm∗0 可知该点为特异点。
若存在 α k 0 α_k0 αk0则根据式(3)可得 μ k C μ_kC μkC根据式(4)可得 y k ( w ∗ ⋅ x k b ∗ ) − 1 ξ k ∗ 0 y_k(w^* \cdot x_k b^*)-1\xi_k^* 0 yk(w∗⋅xkb∗)−1ξk∗0 则无法确定 b ∗ b^* b∗根据式(5)可得$ \xi_k^*0$ 所以 y k ( w ∗ ⋅ x k b ∗ ) − 1 0 y_k(w^* \cdot x_k b^*)-1 0 yk(w∗⋅xkb∗)−10 可知该点为普通样本点。
若存在 0 α j C 0α_jC 0αjC则根据式(3)可得 μ j ≠ 0 μ_j \ne 0 μj0根据式(4)可得 y k ( w ∗ ⋅ x k b ∗ ) − 1 ξ k ∗ 0 y_k(w^* \cdot x_k b^*)-1\xi_k^* 0 yk(w∗⋅xkb∗)−1ξk∗0 且根据式(5)可得$ \xi_k^*0 $所以 y k ( w ∗ ⋅ x k b ∗ ) − 1 0 y_k(w^* \cdot x_k b^*)-1 0 yk(w∗⋅xkb∗)−10 样本点落在间隔边界上可确定 b ∗ b^* b∗。
由此可得 b ∗ y i − ∑ i i N y i a i ∗ ( x i ⋅ x j ) b^*y_i-\sum_{ii}^Ny_ia_i^*(x_i \cdot x_j) b∗yi−ii∑Nyiai∗(xi⋅xj) 由式(1)可得 w ∗ ∑ i 1 N a i ∗ y i x i w^*\sum_{i1}^Na_i^*y_ix_i w∗i1∑Nai∗yixi 再代入之前求得的 α ∗ α^* α∗可得线性支持向量机的分离超平面和分类决策函数。
线性支持向量机的支持向量
我们将 a i 0 a_i0 ai0时对应的样本点称为线性支持向量机的支持向量。 软间隔的支持向量 x i x_i xi或者在间隔边界上或者在间隔边界与分离超平面之间或者在分离超平面误分一侧。
合页损失函数
线性支持向量机还可以通过最小化合页损失函数来获得分离超平面。
合页损失函数为 ∑ i 1 N [ 1 − y i ( x ⋅ x i b ) ] λ ∣ ∣ w ∣ ∣ 2 \sum_{i1}^N[1-y_i(x \cdot x_ib)]_\lambda||w||^2 i1∑N[1−yi(x⋅xib)]λ∣∣w∣∣2 其中第一项是经验损失下标表示 [ Z ] { z , z 0 0 , z ≤ 0 [Z]_ \begin{cases} z, \quad z0 \\ 0, \quad z \leq 0 \end{cases} [Z]{z,z00,z≤0 放在SVM的情况中 1 − y i ( x ⋅ x i b ) 0 1-y_i(x \cdot x_ib) 0 1−yi(x⋅xib)0 时 y i ( x ⋅ x i b ) 1 y_i(x \cdot x_ib)1 yi(x⋅xib)1函数距离小于1该样本点要么是被正确分类的但位于分离超平面和间隔边界之间要么是特异点损失就是 1 − y i ( x ⋅ x i b ) 1−y_i(x \cdot x_ib) 1−yi(x⋅xib)若 1 − y i ( x ⋅ x i b ) 0 1−y_i(x \cdot x_ib)0 1−yi(x⋅xib)0 代表该样本点被正确分类且在间隔边界之外损失为0。
合页损失函数的第二项为正则化项是用来防止过拟合的。
现在证明为何原始最优化问题等价于合页损失函数最小化。
原始最优化问题 min w , b , ξ 1 2 ∣ ∣ w ∣ ∣ 2 C ∑ i 1 N ξ i s . t . y i ( w ⋅ x i b ) ≥ 1 − ξ i , i 1 , 2 , . . . , N ξ i ≥ 0 , i 1 , 2 , . . . , N \begin{aligned} \min_{w,b,\xi}\frac12||w||^2C\sum_{i1}^N\xi_i \\ s.t. \quad y_i(w \cdot x_i b )\geq 1-\xi_i, i1,2,...,N \\ \xi_i \geq 0,i1,2,...,N \end{aligned} w,b,ξmin21∣∣w∣∣2Ci1∑Nξis.t.yi(w⋅xib)≥1−ξi,i1,2,...,Nξi≥0,i1,2,...,N 在合页损失函数最小化中我们令 [ 1 − y i ( x ⋅ x i b ) ] ξ i [1-y_i(x \cdot x_ib)]_\xi_i [1−yi(x⋅xib)]ξi 则约束条件中 ξ i ≥ 0 \xi_i \geq 0 ξi≥0 成立。
且当 1 − y i ( x ⋅ x i b ) 0 1-y_i(x \cdot x_ib)0 1−yi(x⋅xib)0 时 1 − y i ( x ⋅ x i b ) ξ i 1-y_i(x \cdot x_ib) \xi_i 1−yi(x⋅xib)ξi 则$1-\xi_i y_i(x \cdot x_ib) $。
当 1 − y i ( x ⋅ x i b ) ≤ 0 1-y_i(x \cdot x_ib) \leq 0 1−yi(x⋅xib)≤0时 ξ i 0 \xi_i0 ξi0所以 $y_i(x \cdot x_ib) \geq 1-\xi_i $ 于是约束条件中的 $y_i(x \cdot x_ib) \geq 1-\xi_i $ 成立。
所以合页损失最小化可以转变为 min w , b ∑ i 1 N ξ i λ ∣ ∣ w ∣ ∣ 2 \min_{w,b}\sum_{i1}^N\xi_i\lambda ||w||^2 w,bmini1∑Nξiλ∣∣w∣∣2 因为 λ \lambda λ是正则化项的系数用于调节模型的拟合程度为超参数在学习模型时可将其视作常数因此可以用 1 2 C \frac12C 21C来代替。
于是转变为 min w , b 1 C ( 1 2 ∣ ∣ w ∣ ∣ 2 C ∑ i 1 N ξ i ) \min_{w,b}\frac1C\left(\frac12||w||^2C\sum_{i1}^N\xi_i\right) w,bminC1(21∣∣w∣∣2Ci1∑Nξi) 括号外的 1 C \frac1C C1是一个常数不影响最小化过程可忽略因此我们得到线性支持向量机的原始最优化问题。
将合页损失函数直观地表现出来为 其中横轴为函数间隔虚线为感知机的合页损失函数。线性支持向量机与感知机的差别在于线性支持向量机不仅需要将样本点正确分类而且与分离超平面的函数距离需要超过1才没有损失因此线性支持向量机对分类更为严格。
非线性支持向量机
对于一组既非线性可分也非近似线性可分的数据集我们称其为线性不可分的下图展示了线性可分近似线性可分和线性不可分的数据集。
书中介绍了核方法的技术将线性不可分的数据集转换为线性可分的数据集。
核方法
非线性转换为线性
对于线性不可分数据集比如下图左侧无法使用一条直线将正负实例分开但可以使用椭圆曲线将其分开在其它可能的线性不可分数据集中也许可以使用其它类型的曲线正确分类这样的曲线称之为超曲面这样的问题称之为非线性可分问题。 -home.csdnimg.cn/images/20230724024159.png?origin_url.%5Cimages%5C7.8.pngpos_idimg-oqjmgl81-1708431465859)
对于这一类问题我们可以将实例进行非线性变换从线性不可分上图左侧变成线性可分上图右侧。
我们可以用数学语言对其进行表达以上图的椭圆曲线为例设原空间为 x ⊂ R 2 , z ( x ( 1 ) , x ( 2 ) ) T ∈ X x\subset R^2,z(x^{(1)},x^{(2)})^T \in X x⊂R2,z(x(1),x(2))T∈X新空间为 z ⊂ R 2 , z ( z ( 1 ) , z ( 2 ) ) T ∈ Z z\subset R^2,z(z^{(1)},z^{(2)})^T \in Z z⊂R2,z(z(1),z(2))T∈Z那么原空间到新空间的映射为 z ϕ ( x ) ( ( x ( 1 ) ) 2 , ( x ( 2 ) ) 2 ) T z\phi(x)((x^{(1)})^2,(x^{(2)})^2)^T zϕ(x)((x(1))2,(x(2))2)T 经过变换原空间 X ⊂ R 2 X\subset R^2 X⊂R2 变换为新空间 Z ⊂ R 2 Z\subset R^2 Z⊂R2原空间中的点相应地变换为新空间中的点。原空间中的椭圆可以表示为 w 1 ( x ( 1 ) ) 2 w 2 ( x ( 2 ) ) 2 b 0 w_1(x^{(1)})^2w_2(x^{(2)})^2b0 w1(x(1))2w2(x(2))2b0
变换成为新空间中的直线 w 1 ( z ( 1 ) ) 2 w 2 ( z ( 2 ) ) 2 b 0 w_1(z^{(1)})^2w_2(z^{(2)})^2b0 w1(z(1))2w2(z(2))2b0
在变换后的新空间里可以用一条直线将变换后的正负实例点正确分开。这样原空间的非线性可分问题就变成了新空间的线性可分问题。这样的转换都是从低维的原空间向更高维的新空间进行转换也就是将原本用较少数量的特征可以代表的样本点转换为用较多的特征代表的样本点。
我们将原空间称为输入空间X映射后的新空间称为特征空间H。
核函数
线性可分或者近似线性可分的情况下使用了拉格朗日对偶问题需要计算样本点的内积会导致需要大量的计算量。而非线性可分问题进行了输入空间X到特征空间H的映射后其特征数量将从输入空间的M个特征转变为特征空间中更大的数量对样本点内积的计算量变得更大。
为了解决这个问题提出了核技巧的方法也就是利用核函数绕过暴力计算样本点内积的过程而直接求得最终的内积。
核函数的定义
如果存在一个从X到H的映射 ϕ ( x ) : x → H \phi(x):x\rightarrow H ϕ(x):x→H 使得对所有 x , z ∈ X x,z \in X x,z∈X 函数 K ( x , z ) K(x,z) K(x,z)满足条件 K ( x , z ) ϕ ( x ) ⋅ ϕ ( z ) K(x,z)\phi(x) \cdot \phi(z) K(x,z)ϕ(x)⋅ϕ(z) 则称 K ( x , z ) K(x,z) K(x,z)为核函数。其中 ϕ ( x ) \phi(x) ϕ(x) 为映射函数表示一个X中的样本点转换到H空间后的特征向量。
可通过直接计算核函数得到H空间中的所有样本点的内积。对于给定的核函数 K ( x , z ) K(x,z) K(x,z)特征空间H核映射函数可以是不同的但其核函数是相同的。
于是之前拉格朗日对偶问题可以转变为 min a 1 2 ∑ i 1 N ∑ j 1 N a i a j y i y j K ( x i , x j ) − ∑ i 1 N a i \min_a\frac12\sum_{i1}^N\sum_{j1}^Na_ia_jy_iy_jK(x_i,x_j)-\sum_{i1}^Na_i amin21i1∑Nj1∑NaiajyiyjK(xi,xj)−i1∑Nai 其中K为核函数 K ( x i , x j ) K(x_i,x_j) K(xi,xj)为 x i x_i xi和 x j x_j xj的内积。
判断是否为核函数正定核
通常所说的核函数就是正定核函数。
要使一个函数为正定核函数的充要条件是满足对称性 K ( x , z ) K ( z , x ) K(x,z)K(z,x) K(x,z)K(z,x)以及正定性即满足对任意 x i ∈ X , i 1 , 2 , . . . , m x_i \in X,i1,2,...,m xi∈X,i1,2,...,m K ( x , z ) K(x,z) K(x,z)对应的Gram矩阵 K [ K ( x i , x j ) ] m × m K[K(x_i,x_j)]_{m \times m} K[K(xi,xj)]m×m是半正定矩阵。
首先证明对称性 K ( x , z ) ϕ ( x ) ⋅ ϕ ( z ) K ( z , x ) ϕ ( z ) ⋅ ϕ ( x ) K(x,z)\phi(x) \cdot \phi(z) \\ K(z,x)\phi(z) \cdot \phi(x) K(x,z)ϕ(x)⋅ϕ(z)K(z,x)ϕ(z)⋅ϕ(x) 因为内积 ϕ ( x ) ⋅ ϕ ( z ) ϕ ( z ) ⋅ ϕ ( x ) \phi(x) \cdot \phi(z) \phi(z) \cdot \phi(x) ϕ(x)⋅ϕ(z)ϕ(z)⋅ϕ(x)所以 K ( x , z ) K ( z , x ) K(x,z)K(z,x) K(x,z)K(z,x)。对称性得证。
接着证明正定性。
如果 K ( x , z ) K(x,z) K(x,z)是正定核函数想要证明Gram矩阵是半正定矩阵只需要证明存在n维实数向量 a , a T K a ≥ 0 a,a^TKa \geq 0 a,aTKa≥0 即可这是证明一个矩阵是半正定矩阵的方法。
首先构造Gram矩阵 [ K i j ] m × m [ K ( x i , x j ) ] m × m [K_{ij}]_{m \times m} [K(x_i,x_j)]_{m \times m} [Kij]m×m[K(xi,xj)]m×m
其中 K i j K_{ij} Kij代表Gram矩阵中 x i x_i xi和 x j x_j xj的内积。
对任意m维向量 α ( α 1 α 2 … α m ) ∈ R α(α_1α_2…α_m) \in R α(α1α2…αm)∈R有 a T K a ( a 1 a 2 ⋯ a n ) ( K 11 K 12 ⋯ K 1 N ⋯ ⋯ K N 1 K N 2 ⋯ K N N ) ( a 1 a 2 ⋯ a N ) ∑ i 1 N ∑ j 1 N a i a j K i j ∑ i 1 N ∑ j 1 N a i a j ϕ ( x i ) T ϕ ( x j ) ∑ i 1 N a i ϕ ( x i ) T ∑ j 1 N a j ϕ ( x j ) ( ∑ i 1 N a i ϕ ( x i ) ) T ( ∑ j 1 N a j ϕ ( x j ) ) ∣ ∣ ∑ i 1 N a i ϕ ( x i ) ∣ ∣ 2 ≥ 0 \begin{aligned} a^TKa (\begin{matrix} a_1 a_2 \cdots a_n \end{matrix}) (\begin{matrix} K_{11} K_{12} \cdots K_{1N} \\ \cdots \cdots \\ K_{N1} K_{N2} \cdots K_{NN} \end{matrix}) (\begin{matrix} a_1 \\ a_2 \\ \cdots \\ a_N \end{matrix}) \\ \sum_{i1}^N\sum_{j1}^Na_ia_jK_{ij} \\ \sum_{i1}^N\sum_{j1}^Na_ia_j\phi(x_i)^T\phi(x_j) \\ \sum_{i1}^Na_i\phi(x_i)^T \sum_{j1}^Na_j\phi(x_j) \\ \left( \sum_{i1}^Na_i\phi(x_i) \right)^T\left( \sum_{j1}^Na_j\phi(x_j) \right) \\ ||\sum_{i1}^Na_i\phi(x_i)||^2 \geq 0 \end{aligned} aTKa(a1a2⋯an)(K11⋯KN1K12KN2⋯⋯K1N⋯KNN)(a1a2⋯aN)i1∑Nj1∑NaiajKiji1∑Nj1∑Naiajϕ(xi)Tϕ(xj)i1∑Naiϕ(xi)Tj1∑Najϕ(xj)(i1∑Naiϕ(xi))T(j1∑Najϕ(xj))∣∣i1∑Naiϕ(xi)∣∣2≥0 证明的等价定义对于构造核函数时特别有用但检验一个函数是否为核函数时很难因为需要对于任意的 x i ∈ X , i 1 , 2 , ⋯ , m x_i \in X, i1,2, \cdots ,m xi∈X,i1,2,⋯,m检验对应的Gram矩阵难点就在任意二字。因此在实际问题中一般使用已有的核函数。
常用核函数
线性核 K ( x , z ) x ⋅ z c K(x,z)x \cdot z c K(x,z)x⋅zc 线性核函数是所有核函数中最简单的。
多项式核函数 K ( x , z ) ( a x ⋅ z c ) p K(x,z)(ax \cdot z c )^p K(x,z)(ax⋅zc)p 其中ac和p都是实系数线性核就是多项式核函数的一个特例。
高斯核函数 K ( x , z ) e x p ( − ∣ ∣ x − z ∣ ∣ 2 2 σ 2 ) K(x,z)exp(-\frac{||x-z||^2}{2\sigma^2}) K(x,z)exp(−2σ2∣∣x−z∣∣2) 高斯核函数可以将输入空间映射到无穷维的特征空间中。我们知道非线性可分的低维的样本点在更高维空间中线性可分在无穷维的空间中一定线性可分因此高斯核函数是在非线性支持向量机中一定要尝试的核函数。
幂指数核 K ( x , z ) e x p ( − ∣ ∣ x − z ∣ ∣ 2 σ 2 ) K(x,z)exp(-\frac{||x-z||}{2\sigma^2}) K(x,z)exp(−2σ2∣∣x−z∣∣) 拉普拉斯核 K ( x , z ) e x p ( − ∣ ∣ x − z ∣ ∣ σ ) K(x,z)exp(-\frac{||x-z||}{\sigma}) K(x,z)exp(−σ∣∣x−z∣∣)
核函数的选择
对一个具体问题我们需要选择一个核函数以达到获得最好的模型但如何快速做出选择并没有一个具体的方法在很多问题上需要尝试各个核函数每个核函数中的参数也需要大量尝试最后经过对比找到一个效果最好的核函数也就得到最终的分离超曲面和决策函数。
非线性支持向量机模型学习步骤
依据下式求得 α ∗ α^* α∗ min a 1 2 ∑ i 1 N ∑ j 1 N a i a j y i y j K ( x i , x j ) − ∑ i 1 N a i s . t . ∑ i 1 N a i y i 0 0 ≤ a i ≤ C , i 1 , 2 , . . . , N s . t . \begin{aligned} \min_a\frac12\sum_{i1}^N\sum_{j1}^Na_ia_jy_iy_jK(x_i,x_j)-\sum_{i1}^Na_i \\ s.t. \quad \sum_{i1}^Na_iy_i0 \\ 0 \leq a_i \leq C,i1,2,...,N \end{aligned} s.t. amin21i1∑Nj1∑NaiajyiyjK(xi,xj)−i1∑Nais.t.i1∑Naiyi00≤ai≤C,i1,2,...,Ns.t.
该步骤需要选择合适的核函数和参数C。
依据下式求得 b ∗ b^* b∗ b ∗ y i − ∑ i i N y i a i ∗ K ( x i ⋅ x j ) b^*y_i-\sum_{ii}^Ny_ia_i^*K(x_i \cdot x_j) b∗yi−ii∑Nyiai∗K(xi⋅xj)
该步骤需要选择一个合适的 α ∗ α^* α∗分量 0 a j ∗ C 0 a_j^* C 0aj∗C
获得决策函数 f ( x ) s i g n ( ∑ i i N a i ∗ y i K ( x i ⋅ x j ) b ∗ ) f(x)sign\left( \sum_{ii}^Na_i^*y_iK(x_i \cdot x_j) b^* \right) f(x)sign(ii∑Nai∗yiK(xi⋅xj)b∗)
代码
import numpy as np
import pandas as pd
from sklearn import datasets
from sklearn.model_selection import train_test_split
import math
from tqdm import tqdm# 加载鸢尾花数据集
iris datasets.load_iris()
df pd.DataFrame(iris.data)
df[label] iris.target
df.columns [sepal_length, sepal_width, petal_length, petal_width, label]# 提取前100条数据
data np.array(df.iloc[0:100, [0, 1, -1]])
# 得到x(特征向量)、y(分类标签)
x, y data[:, :-1], data[:, -1]# 将两类分类标签分别替换为1与-1便于感知机处理
y np.array([1 if i 1 else -1 for i in y])# 划分训练集和测试集
x_train, x_test, y_train, y_test train_test_split(x, y, test_size0.3, random_state100)class Model:def __init__(self, train_data, train_label, sigma, C, toler, itertime):self.train_data train_data # 训练集数据self.train_label train_label # 训练集标记self.m, self.n np.shape(train_data) # self.m为训练集样本容量self.n为特征数量self.sigma sigma # 高斯核分母上的超参数self.kernal self.kernalMatrix() # 高斯核矩阵self.alpha np.zeros(self.m) # 初始化拉格朗日向量长度为训练集样本容量self.b 0 # 初始化参数bself.C C # 惩罚参数self.toler toler # 松弛变量self.itertime itertime # 迭代次数self.E [float(-1 * y) for y in self.train_label] # 初始化Elist因为alpha和b初始值为0因此E的初始值为训练集标记的值# 高斯核矩阵def kernalMatrix(self):# 初始化高斯核矩阵矩阵为m*m大小matrix [[0 for i in range(self.m)] for j in range(self.m)]# 遍历每一个样本for i in range(self.m):# 首先得到一个样本的数据X self.train_data[i]# 仅遍历从i到self.m的样本因为Kij和Kji的值相同所以只需要计算一次for j in range(i, self.m):# 得到另一个样本的数据Z self.train_data[j]# 计算核函数K np.exp(-1 * np.dot(X - Z, X - Z) / (2 * np.square(self.sigma)))# 存储在核矩阵中对称的位置matrix[i][j] Kmatrix[j][i] Kmatrix np.array(matrix)return matrixdef calgxi(self, i):indexs [index for index, value in enumerate(self.alpha) if value ! 0]gxi 0for index in indexs:gxi self.alpha[index] * self.train_label[index] * self.kernal[i][index]gxi gxi self.breturn gxi# 判断是否符合KKT条件def isSatisfyKKT(self, i):# 获得alpha[i]的值alpha_i self.alpha[i]# 计算yi * g(xi)gxi self.calgxi(i)yi self.train_label[i]yi_gxi yi * gxi# 判断是否符合KKT条件if -1 * self.toler alpha_i self.toler and yi_gxi 1:return Trueelif -1 * self.toler alpha_i self.C self.toler and math.fabs(yi_gxi - 1) self.toler:return Trueelif self.C - self.toler alpha_i self.C self.toler and yi_gxi 1:return Truereturn Falsedef SMO(self):# 迭代t 0parameterchanged 1pbar tqdm(totalself.itertime)while t self.itertime and parameterchanged 0:t 1parameterchanged 0选择两个alphapbar.update(1)# 外层循环选择第一个alphafor i in range(self.m):# 判断是否符合KKT条件如果不满足则选择该alpha为alpha1# 如果满足则继续外层循环TorF self.isSatisfyKKT(i)if TorF False:alpha1 self.alpha[i]# 从Earray得到alpha1对应的E1E1 self.E[i]# 复制一个EMatrix并令E1的位置为nan# 这样在接下来找最大值和最小值时将不会考虑E1# 这里需要使用copy如果不用copy改变EM_temp也会同时改变EMatrixEM_temp np.copy(self.E)EM_temp[i] np.nan# 我们需要使|E1-E2|的值最大由此选择E2# 首先初始化maxE1_E2和E2及E2的下标jmaxE1_E2 -1E2 np.nanj -1# 内层循环# 遍历EM_temp中的每一个Ei得到使|E1-E2|最大的E和它的下标for j_temp, Ej in enumerate(EM_temp):if math.fabs(E1 - Ej) maxE1_E2:maxE1_E2 math.fabs(E1 - Ej)E2 Ejj j_temp# alpha2为E2对应的alphaalpha2 self.alpha[j]求最优alpha1和alpha2y1 self.train_label[i]y2 self.train_label[j]# 计算ηK11 self.kernal[i][i]K22 self.kernal[j][j]K12 self.kernal[i][j]eta K11 K22 - 2 * K12# 计算alpha2_newif eta 0:alpha2_new alpha2 y2 * (E1 - E2) / etaelse:alpha2_new alpha2# 计算上限H和下限Lif y1 ! y2:L max([0, alpha2 - alpha1])H min([self.C, self.C alpha2 - alpha1])else:L max([0, alpha2 alpha1 - self.C])H min([self.C, alpha2 alpha1])# 剪切alpha2_newif alpha2_new H:alpha2_new Helif alpha2_new L:alpha2_new L# # 如果HL说明不需要更新# if H L:# continue# 得到alpha1_newalpha1_new alpha1 y1 * y2 * (alpha2 - alpha2_new)更新b# 计算b1_new和b2_newb1_new -1 * E1 - y1 * K11 * (alpha1_new - alpha1) - y2 * K12 * (alpha2_new - alpha2) self.bb2_new -1 * E2 - y1 * K12 * (alpha1_new - alpha1) - y2 * K22 * (alpha2_new - alpha2) self.b# 根据alpha1和alpha2的范围确定b_newif 0 alpha1_new self.C and 0 alpha2_new self.C:b_new b1_newelse:b_new (b1_new b2_new) / 2更新E# 首先需要更新两个alpha和bself.alpha[i] alpha1_newself.alpha[j] alpha2_newself.b b_new# 计算Ei_new和Ej_newE1_new self.calgxi(i) - y1E2_new self.calgxi(j) - y2# 更新Eself.E[i] E1_newself.E[j] E2_newif math.fabs(alpha2_new - alpha2) 0.000001:parameterchanged 1pbar.update(self.itertime-t)pbar.close()# 最后遍历一遍alpha大于0的下标即对应支持向量VecIndex [index for index, value in enumerate(self.alpha) if value 0]# 返回支持向量的下标之后在预测时还需要用到return VecIndex计算bdef OptimizeB(self):for j, a in enumerate(self.alpha):if 0 a self.C:breakyj self.train_label[j]summary 0for i in range(self.alpha):summary self.alpha[i] * self.train_label[i] * self.KernalMatrix[i][j]optimiezedB yj - summaryself.b optimiezedB计算单个核函数def CalSingleKernal(self, x, z):SingleKernal np.exp(-1 * np.dot(x - z, x - z) / (2 * np.square(self.sigma)))return SingleKernal单个新输入实例的预测def predict(self, x, VecIndex):# 决策函数计算# 求和项初始化summary 0# Index中存储着不为0的alpha的下标for i in VecIndex:alphai self.alpha[i]yi self.train_label[i]Kernali self.CalSingleKernal(x, self.train_data[i])summary alphai * yi * Kernali# 最后b# np.sign得到符号result np.sign(summary self.b)return result测试模型def test(self, test_data, test_label, VecIndex):# 测试集实例数量TestNum len(test_label)errorCnt 0# 对每一个实例进行预测for i in range(TestNum):result self.predict(test_data[i], VecIndex)if result ! test_label[i]:errorCnt 1Acc 1 - errorCnt / TestNumreturn Accperceptron Model(x_train,y_train, 10, 200, 0.001, 100)VecIndex perceptron.SMO()Acc perceptron.test(x_test, y_test, VecIndex)
print(Accurate: , Acc)
