数据挖掘---支持向量机（SVM）

╰+哭是因爲堅強的太久メ 2022-05-21 13:11 559阅读 0赞

### •1.SVM 的基本思想： ###

•SVM把分类问题转换成寻求分类平面的问题，并通过最大化分类边界点到分类平面的距离来实现分类。通俗的讲支持向量机的解决的问题是找到最好的分类超平面。支持向量机（Support vector machine)通常用来解决二分类问题

![70][]

### 2.构造目标函数 ###

类似于点到直线的距离，可以得到点到超平面的距离为

![d=\\frac\{\\left | w^\{t\}X+b \\right |\}\{\\left \\| w \\right \\|\}][d_frac_left _ w_t_X_b _right _left _ w _right]

![70 1][]

•在Logistic回归算法，我们是把数据分成0类和 1 类，而同样为了推导式子的方便性，采用-1 和 1 两类。

可以将红色框的式子转换成：

![70 2][]

•目标方程：

![70 3][]

![70 4][]

我们需要求的是：两数据集中几个数据最近的点的最大的距离。

在满足约束条件（即样本点为支持向量）下，最大的几何间隔中取最小的值。max L(w,b,a) 是得到支持向量的样本点，然后再这些样本点中找到min 1/2 || w ||2 的最小值（最大间隔）。

•可以得到有条件约束的最优化问题，通常引入拉格朗日函数简化上述问题，称此类问题为对偶问题（The wolfe dualproblem）。

•使用拉格朗日乘数法用来解决等式约束下的最优化问题：

![70 5][]

•对偶问题的求解：

•步骤1 ：固定 α ，然后L（ω, b, α）对 ω 、b 求偏导，令其偏导数等于0。

![70 6][]

•把上述2式带入到L（ω, b, α）当中：

![70 7][]

•步骤2 ：对 α 求极大，通过步骤1 已经把变量 ω 、b 消去，函数只有 α。

•在式子前面加个 - 负号，是求极大值转换成求极小值：

![70 8][]

**线性可分SVM算法过程：**

输入是线性可分的m个样本![\{(x\_1,y\_1), (x\_2,y\_2), ..., (x\_m,y\_m),\}][x_1_y_1_ _x_2_y_2_ ..._ _x_m_y_m]其中 x 为 n 维特征向量。y 为二元输出，值为 1，或者 -1。

输出是分离超平面的参数![W^\{\*\}，b ^\{\*\}][W_b]， ![b^\{\*\}][b]和分类决策函数。

算法过程如下：

1）构造约束优化问题：

![\\underbrace\{min\}\_\{\\alpha\} \\frac\{1\}\{2\}\\sum\\limits\_\{i=1\}^\{m\}\\sum\\limits\_\{j=1\}^\{m\}\\alpha\_i\\alpha\_jy\_iy\_j(x\_i \\bullet x\_j) - \\sum\\limits\_\{i=1\}^\{m\} \\alpha\_i][underbrace_min_alpha_ _frac_1_2_sum_limits_i_1_m_sum_limits_j_1_m_alpha_i_alpha_jy_iy_j_x_i _bullet x_j_ - _sum_limits_i_1_m_ _alpha_i]

![s.t. \\; \\sum\\limits\_\{i=1\}^\{m\}\\alpha\_iy\_i = 0][s.t. _ _sum_limits_i_1_m_alpha_iy_i _ 0]

![\\alpha\_i \\geq 0 \\; i=1,2,...m][alpha_i _geq 0 _ i_1_2_...m]

结合：![70 6][]

![y\_s(w^Tx\_s+b) = y\_s(\\sum\\limits\_\{i=1\}^\{m\}\\alpha\_iy\_ix\_i^Tx\_s+b) = 1][y_s_w_Tx_s_b_ _ y_s_sum_limits_i_1_m_alpha_iy_ix_i_Tx_s_b_ _ 1]

2）用SMO算法求出上式最小时对应的α 向量的值α∗ 向量.

3) 计算 ![w^\{\*\} = \\sum\\limits\_\{i=1\}^\{m\}\\alpha\_i^\{\*\}y\_ix\_i][w_ _ _sum_limits_i_1_m_alpha_i_y_ix_i]

4） 找出所有的S个支持向量,即满足![\\alpha\_s > 0][alpha_s _ 0] 对应的样本（![X\_\{s\}, y\_\{s\}][X_s_ y_s]）， 通过![y\_s(\\sum\\limits\_\{i=1\}^\{m\}\\alpha\_iy\_ix\_i^Tx\_s+b) = 1][y_s_sum_limits_i_1_m_alpha_iy_ix_i_Tx_s_b_ _ 1] 计算出每个支持向量![X\_\{s\}, y\_\{s\}][X_s_ y_s] 对应的![b\_s^\{\*\}][b_s] ,计算出这些![b\_s^\{\*\} = y\_s - \\sum\\limits\_\{i=1\}^\{m\}\\alpha\_iy\_ix\_i^Tx\_s][b_s_ _ y_s - _sum_limits_i_1_m_alpha_iy_ix_i_Tx_s]，

所有的![b\_s^\{\*\}][b_s] 对应的平均值即为最终的 ![b^\{\*\} = \\frac\{1\}\{S\}\\sum\\limits\_\{i=1\}^\{S\}b\_s^\{\*\}][b_ _ _frac_1_S_sum_limits_i_1_S_b_s]

但是，线性可分SVM的学习方法对于非线性的数据集是无法使用的。

from：[刘建平blog][blog]

### 3.软间隔 ###

如果存在噪声的话，会影响模型的泛化能力。

![format_png][]

•实际遇到的问题数据总是有噪音的，也就是说可能存在一两个可忽略的特殊点使margin大大减小，也可能有一两个特殊点导致集合线性不可分（如下图），所以我们需要允许模型犯一定的错误来过滤掉噪音，即允许间隔的调整称为软间隔。

![70 9][]

这里,C>0 为惩罚参数，可以理解为我们一般回归和分类问题正则化时候的参数。C越大，对误分类的惩罚越大，C 越小，对误分类的惩罚越小。C 是协调两者关系的正则化惩罚系数。在实际应用中，需要调参来选择。

![70 10][]

这个式子和我们线性可分SVM相同，唯一不同的是约束条件。我们依然可以通过SMO算法来求上式极小化时对应的α 向量就可以求出 w 和 b 。

![70 11][]

对于SVM线性不可分的低维特征数据，我们可以将其映射到高维，就能线性可分

### •4.核函数kernel ###

（多项式核函数）（高斯核函数计算花销大：gamma越大会形成过拟合，越小则会欠拟合）（升维）

•设χ是输入空间（欧氏空间或离散集合），Η为特征空间（希尔伯特空间），如果存在一个从χ到Η的映射

•φ(x):χ→Η

那么如果存在函数 ![K(x,z)][K_x_z] ，对于任意 ![x, z \\in \\chi][x_ z _in _chi]，都有：

![K(x, z) = \\phi(x\_i) \\bullet \\phi(x\_j)][K_x_ z_ _ _phi_x_i_ _bullet _phi_x_j]

则称 ![K(x,z)][K_x_z] 为核函数，φ(x)为映射函数，φ(x)∙φ(z)为x,z映射到特征空间上的内积。

我们遇到线性不可分的样例时，常用做法是把样例特征映射到高维空间中去， 但是遇到线性不可分的样例，一律映射到高维空间，那么这个维度大小是会高到令人恐怖的。此时，核函数就体现出它的价值了，核函数的价值在于它虽然也是将特征进行从低维到高维的转换，但核函数好在它在低维上进行计算，而将实质上的分类效果（利用了内积）表现在了高维上，这样避免了直接在高维空间中的复杂计算，真正解决了SVM线性不可分的问题。

![70 12][]

scikit-learn中默认可选的就是下面几个核函数：

1.线性核函数(Linear Kernel )

2.多项式核函数（Polynomial Kernel）是线性不可分SVM常用的核函数之一，表达式为：

![K(x, z) = (\\gamma x\\cdot z + r )^\{d\}][K_x_ z_ _ _gamma x_cdot z _ r _d]

其中 ![\\gamma ,d, r][gamma _d_ r] 都是要调参的

3. 高斯核函数（Gaussian Kernel），在SVM中也称为径向基核函数（Radial Basis Function,RBF），它是非线性分类SVM最主流的核函数。libsvm默认的核函数就是它。表达式为：

![K(x, z) = exp(-\\gamma||x-z||^2)][K_x_ z_ _ exp_-_gamma_x-z_2]

其中 ![\\gamma > 0][gamma _ 0] 需要调参

4.Sigmoid核函数（Sigmoid Kernel）也是线性不可分SVM常用的核函数之一，表达式为：

![K(x, z) = tanh(\\gamma x \\cdot z + r)][K_x_ z_ _ tanh_gamma x _cdot z _ r]

其中 ![\\gamma , r][gamma _ r] 需要调参

结合软间隔和核函数 ， 所以算法第一步应该为：

1）选择适当的核函数 ![K(x,z)][K_x_z] 和一个惩罚系数C>0 , 构造约束优化问题

![\\underbrace\{ min \}\_\{\\alpha\} \\frac\{1\}\{2\}\\sum\\limits\_\{i=1,j=1\}^\{m\}\\alpha\_i\\alpha\_jy\_iy\_jK(x\_i,x\_j) - \\sum\\limits\_\{i=1\}^\{m\}\\alpha\_i][underbrace_ min _alpha_ _frac_1_2_sum_limits_i_1_j_1_m_alpha_i_alpha_jy_iy_jK_x_i_x_j_ - _sum_limits_i_1_m_alpha_i]

![s.t. \\; \\sum\\limits\_\{i=1\}^\{m\}\\alpha\_iy\_i = 0][s.t. _ _sum_limits_i_1_m_alpha_iy_i _ 0]

![0 \\leq \\alpha\_i \\leq C][0 _leq _alpha_i _leq C]

2）用SMO算法求出上式最小时对应的α 向量的值α∗ 向量.

![70 13][]

### 5.SMO（Sequential Minimal Optimization, 序列最小优化）算法解析: ###

SVM，有许多种实现方式，SMO算法实现是一种。

1998年，由Platt提出的序列最小最优化算法(SMO)可以高效的求解上述SVM问题，它把原始求解N个参数二次规划问题分解成很多个子二次规划问题分别求解，每个子问题只需要求解2个参数，方法类似于坐标上升，节省时间成本和降低了内存需求。每次启发式选择两个变量进行优化，不断循环，直到达到函数最优值。

[可参考支持向量机 SVM 的ppt][SVM _ppt]

[SMO算法剖析][SMO]

--------------------

![20200423152511164.PNG][]

### 6.支持向量机的参数解析，SVC ###

from sklearn.svm import SVC

SVC(C, kernel, degree, gamma, coef0, shrinking, probability, tol, cache_size, class_weight, verbose, 
    max_iter, decision_function_shape, random_state)

> 1.  C : 错误项的惩罚系数,C越大，即对分错样本的惩罚程度越大，因此在训练样本中准确率越高，但是泛化能力降低，易于过拟合
> 2.  **kernel**: str参数 默认为‘rbf’
>     
>     算法中采用的核函数类型，可选参数有：
>     
>     ‘linear’:线性核函数
>     
>     ‘poly’：多项式核函数
>     
>     ‘rbf’：径向核函数/高斯核
>     
>     ‘sigmod’:sigmod核函数
>     
>     ‘precomputed’:核矩阵
> 3.  degree: int型参数 默认为3, 这个参数只对多项式核函数 ' poly ' 有用
> 4.  **gamma**：float参数 默认为auto, 核函数系数，只对‘rbf’,‘poly’,‘sigmod’有效。如果gamma为auto，代表其值为样本特征数的倒数，即1/n\_features. 高斯核函数中，gamma越大，高斯分布越窄，相当于gamma=1/2 方差 ;原高斯分布 方差越大，越宽，与之相反。当gamma越大时，模型复杂度越大，倾向于过拟合；当gamma越小时，模型复杂度越小，倾向于欠拟合
> 5.  **coef0** : float参数 默认为0.0, 核函数中的独立项，只有对‘poly’和‘sigmod’核函数有用，是指其中的参数 c
> 6.  **probability**：bool参数 默认为False, 是否启用概率估计。 这必须在调用fit()之前启用，并且会fit()方法速度变慢。
> 7.  **shrinking**：bool参数 默认为True,是否采用启发式收缩方式
> 8.  **tol**: float参数 默认为1e^-3, svm停止训练的误差精度
> 9.  **cache\_size**：float参数 默认为200,指定训练所需要的内存，以MB为单位，默认为200MB。
> 10. **class\_weight**：字典类型或者‘balance’字符串。默认为None
>     
>     给每个类别分别设置不同的惩罚参数C，如果没有给，则会给所有类别都给C=1，即前面参数指出的参数C.
>     
>     如果给定参数‘balance’，则使用y的值自动调整与输入数据中的类频率成反比的权重。
> 11. **verbose** ：bool参数 默认为False
>     
>     是否启用详细输出。 此设置利用libsvm中的每个进程运行时设置，如果启用，可能无法在多线程上下文中正常工作。一般情况都设为False，不用管它
> 12. **max\_iter** ：int参数 默认为-1
>     
>     最大迭代次数，如果为-1，表示不限制

SVC 中的属性：

> svc.n\_support\_：各类各有多少个支持向量
> 
> svc.support\_：各类的支持向量在训练样本中的索引
> 
> svc.support\_vectors\_：各类所有的支持向量

参考：[刘建平的blog][blog 1]

[SVM支持向量机推导][SVM]

[支持向量机（1）（2）（3）（4）][1_2_3_4]

[70]: /images/20220521/3f3545d9f18c43caa6a06cd4ef738f3a.png
[d_frac_left _ w_t_X_b _right _left _ w _right]: https://private.codecogs.com/gif.latex?d%3D%5Cfrac%7B%5Cleft%20%7C%20w%5E%7Bt%7DX&plus;b%20%5Cright%20%7C%7D%7B%5Cleft%20%5C%7C%20w%20%5Cright%20%5C%7C%7D
[70 1]: /images/20220521/a31ab18315aa4b3087543c0dc7f3cf12.png
[70 2]: /images/20220521/e58c6283489e4b19a8d3fe9d9d4a3857.png
[70 3]: /images/20220521/ea471549e7e34c4ca2d61a82bb341864.png
[70 4]: /images/20220521/02efe30e6d9a4dd9b528788c40dd674b.png
[70 5]: /images/20220521/948da8212df2403e8f80dff846696fc1.png
[70 6]: /images/20220521/42e1d61d998c48248d61cfb12df0a7bd.png
[70 7]: /images/20220521/378323224fa04f3ebe386c5b3687c269.png
[70 8]: /images/20220521/7abd25c6ee1d410681820a4691efbb0e.png
[x_1_y_1_ _x_2_y_2_ ..._ _x_m_y_m]: https://private.codecogs.com/gif.latex?%7B%28x_1%2Cy_1%29%2C%20%28x_2%2Cy_2%29%2C%20...%2C%20%28x_m%2Cy_m%29%2C%7D
[W_b]: https://private.codecogs.com/gif.latex?W%5E%7B*%7D%25uFF0Cb%20%5E%7B*%7D
[b]: https://private.codecogs.com/gif.latex?b%5E%7B*%7D
[underbrace_min_alpha_ _frac_1_2_sum_limits_i_1_m_sum_limits_j_1_m_alpha_i_alpha_jy_iy_j_x_i _bullet x_j_ - _sum_limits_i_1_m_ _alpha_i]: https://private.codecogs.com/gif.latex?%5Cunderbrace%7Bmin%7D_%7B%5Calpha%7D%20%5Cfrac%7B1%7D%7B2%7D%5Csum%5Climits_%7Bi%3D1%7D%5E%7Bm%7D%5Csum%5Climits_%7Bj%3D1%7D%5E%7Bm%7D%5Calpha_i%5Calpha_jy_iy_j%28x_i%20%5Cbullet%20x_j%29%20-%20%5Csum%5Climits_%7Bi%3D1%7D%5E%7Bm%7D%20%5Calpha_i
[s.t. _ _sum_limits_i_1_m_alpha_iy_i _ 0]: https://private.codecogs.com/gif.latex?s.t.%20%5C%3B%20%5Csum%5Climits_%7Bi%3D1%7D%5E%7Bm%7D%5Calpha_iy_i%20%3D%200
[alpha_i _geq 0 _ i_1_2_...m]: https://private.codecogs.com/gif.latex?%5Calpha_i%20%5Cgeq%200%20%5C%3B%20i%3D1%2C2%2C...m
[y_s_w_Tx_s_b_ _ y_s_sum_limits_i_1_m_alpha_iy_ix_i_Tx_s_b_ _ 1]: https://private.codecogs.com/gif.latex?y_s%28w%5ETx_s&plus;b%29%20%3D%20y_s%28%5Csum%5Climits_%7Bi%3D1%7D%5E%7Bm%7D%5Calpha_iy_ix_i%5ETx_s&plus;b%29%20%3D%201
[w_ _ _sum_limits_i_1_m_alpha_i_y_ix_i]: https://private.codecogs.com/gif.latex?w%5E%7B*%7D%20%3D%20%5Csum%5Climits_%7Bi%3D1%7D%5E%7Bm%7D%5Calpha_i%5E%7B*%7Dy_ix_i
[alpha_s _ 0]: https://private.codecogs.com/gif.latex?%5Calpha_s%20%3E%200
[X_s_ y_s]: https://private.codecogs.com/gif.latex?X_%7Bs%7D%2C%20y_%7Bs%7D
[y_s_sum_limits_i_1_m_alpha_iy_ix_i_Tx_s_b_ _ 1]: https://private.codecogs.com/gif.latex?y_s%28%5Csum%5Climits_%7Bi%3D1%7D%5E%7Bm%7D%5Calpha_iy_ix_i%5ETx_s&plus;b%29%20%3D%201
[b_s]: https://private.codecogs.com/gif.latex?b_s%5E%7B*%7D
[b_s_ _ y_s - _sum_limits_i_1_m_alpha_iy_ix_i_Tx_s]: https://private.codecogs.com/gif.latex?b_s%5E%7B*%7D%20%3D%20y_s%20-%20%5Csum%5Climits_%7Bi%3D1%7D%5E%7Bm%7D%5Calpha_iy_ix_i%5ETx_s
[b_ _ _frac_1_S_sum_limits_i_1_S_b_s]: https://private.codecogs.com/gif.latex?b%5E%7B*%7D%20%3D%20%5Cfrac%7B1%7D%7BS%7D%5Csum%5Climits_%7Bi%3D1%7D%5E%7BS%7Db_s%5E%7B*%7D
[blog]: http://www.cnblogs.com/pinard/p/6097604.html
[format_png]: /images/20220521/5976a5c22c57465a88f287a4b059e882.png
[70 9]: /images/20220521/f0e4e51aa8be46739ec208abeef00942.png
[70 10]: /images/20220521/59126e952d184ce7bc3f877c9bebb620.png
[70 11]: /images/20220521/2725bc35fb7840b9a675b39e2ec6f184.png
[K_x_z]: https://private.codecogs.com/gif.latex?K%28x%2Cz%29
[x_ z _in _chi]: https://private.codecogs.com/gif.latex?x%2C%20z%20%5Cin%20%5Cchi
[K_x_ z_ _ _phi_x_i_ _bullet _phi_x_j]: https://private.codecogs.com/gif.latex?K%28x%2C%20z%29%20%3D%20%5Cphi%28x_i%29%20%5Cbullet%20%5Cphi%28x_j%29
[70 12]: /images/20220521/c6af316f9f074d9e8b0d4e81af2acf3a.png
[K_x_ z_ _ _gamma x_cdot z _ r _d]: https://private.codecogs.com/gif.latex?K%28x%2C%20z%29%20%3D%20%28%5Cgamma%20x%5Ccdot%20z%20&plus;%20r%20%29%5E%7Bd%7D
[gamma _d_ r]: https://private.codecogs.com/gif.latex?%5Cgamma%20%2Cd%2C%20r
[K_x_ z_ _ exp_-_gamma_x-z_2]: https://private.codecogs.com/gif.latex?K%28x%2C%20z%29%20%3D%20exp%28-%5Cgamma%7C%7Cx-z%7C%7C%5E2%29
[gamma _ 0]: https://private.codecogs.com/gif.latex?%5Cgamma%20%3E%200
[K_x_ z_ _ tanh_gamma x _cdot z _ r]: https://private.codecogs.com/gif.latex?K%28x%2C%20z%29%20%3D%20tanh%28%5Cgamma%20x%20%5Ccdot%20z%20&plus;%20r%29
[gamma _ r]: https://private.codecogs.com/gif.latex?%5Cgamma%20%2C%20r
[underbrace_ min _alpha_ _frac_1_2_sum_limits_i_1_j_1_m_alpha_i_alpha_jy_iy_jK_x_i_x_j_ - _sum_limits_i_1_m_alpha_i]: https://private.codecogs.com/gif.latex?%5Cunderbrace%7B%20min%20%7D_%7B%5Calpha%7D%20%5Cfrac%7B1%7D%7B2%7D%5Csum%5Climits_%7Bi%3D1%2Cj%3D1%7D%5E%7Bm%7D%5Calpha_i%5Calpha_jy_iy_jK%28x_i%2Cx_j%29%20-%20%5Csum%5Climits_%7Bi%3D1%7D%5E%7Bm%7D%5Calpha_i
[0 _leq _alpha_i _leq C]: https://private.codecogs.com/gif.latex?0%20%5Cleq%20%5Calpha_i%20%5Cleq%20C
[70 13]: /images/20220521/1bf6680146ec4636911af7ead49a4140.png
[SVM _ppt]: https://wenku.baidu.com/view/35ec70029ec3d5bbfc0a74ab.html
[SMO]: https://blog.csdn.net/luoshixian099/article/details/51227754
[20200423152511164.PNG]: /images/20220521/da8f9e32a2f74b5ca7bcb89068eaa4df.png
[blog 1]: https://www.cnblogs.com/pinard/p/6103615.html
[SVM]: https://www.cnblogs.com/yueshangzuo/p/7852326.html
[1_2_3_4]: http://www.cnblogs.com/pursued-deer/p/7858122.html