文章目录
支持向量机(SVM)详解
1. 最优化问题
- 无约束条件：变量求导，令其为0，求得极值
- 等式约束：拉格朗日乘子法
- 等式约束和不等式约束：KKT条件
1.1 拉格朗日乘子法
等式约束时，需构建拉格朗日函数，将有约束的问题转为无约束的优化问题
即构建拉格朗日函数，引入拉格朗日乘子，将原始优化问题表示为：
拉格朗日函数对 x x x求偏导的结果为0时，即为最优解
1.2 KKT条件
既有等式约束（拉格朗日乘子法），又有不等式约束时，利用KKT条件将有约束的问题转为无约束的优化问题
即构建拉格朗日函数，同时引入拉格朗日乘子和KKT乘子【注：KKT乘子是大于0的】，将原始优化问题表示为：
KKT条件:
【注：f(x)和g(x)都是凸函数】
1.3 对偶问题
原优化问题：
构建的拉格朗日函数：
对上面构建的拉格朗日函数先最大化再最小化：
在满足KKT条件的情况下，该式和原优化问题是等价的
解释过程：
将上式分为两部分：
-
可行解区域内：原优化问题的约束条件都满足。因 h i ( x ) = 0 {{\rm{h}}_i}\left( x \right) = 0 hi?(x)=0，所以不管 α \alpha α如何变化，必然有 α h i ( x ) = 0 \alpha {{\rm{h}}_i}\left( x \right) = 0 αhi?(x)=0； g i ( x ) < 0 {{\rm{g}}_i}\left( x \right) < 0 gi?(x)<0且限定了 β j > 0 {\beta _j} > 0 βj?>0，则 β j g i ( x ) {\beta _j}{{\rm{g}}_i}\left( x \right) βj?gi?(x)最大值为0
-
可行解区域外：原优化问题的约束条件未满足。若 h i ( x ) ≠ 0 {{\rm{h}}_i}\left( x \right) \ne 0 hi?(x)?=0，则最大化后为 ∞ \infty ∞；若 g i ( x ) > 0 {{\rm{g}}_i}\left( x \right) > 0 gi?(x)>0，则最大化也为 ∞ \infty ∞
综上所述，f(x)在可行解区域内最小化，等价于
的最小化，为原优化问题的最优解
定义：
则最小化原始问题和原问题有相同的解：
定义对偶优化问题如下：
【注：
】
证明过程：
定义：
为原始最小化问题的值
为对偶问题最大化的值
两式满足定理：
只有在KKT条件时，才有：
，此时，才可通过求解对偶问题来求解原始问题
2. SVM原理
基本思想：找到一个超平面，使得它能够尽可能多地将两类数据点正确分开，同时使分开的两类数据点距离分类面最远
2.1 线性可分支持向量分类机
构造的超平面是硬间隔超平面
SVM的数学模型：
支持向量机的优化问题可以写为：
为了最大化间隔，仅需最大化 ∥ ω ∥ ? 1 {\left\| \omega \right\|^{{\rm{ - }}1}} ∥ω∥?1，这等价于最小化 ∥ ω ∥ 2 {\left\| \omega \right\|^2} ∥ω∥2：
可以将约束条件写为 ：
可以将优化问题拉格朗日化：
欲构造对偶问题，先对拉格朗日化的原问题求最小值来计算各变量(
w
w
w和
b
b
b)的值，利用各变量求一阶偏导数置0，可得：
将各变量( w w w和 b b b)代回至拉格朗日化的原问题，可得：
【注：
∥
ω
∥
2
=
ω
T
ω
{\left\| \omega \right\|^2}{\rm{ = }}{\omega ^T}\omega
∥ω∥2=ωTω】
【注：
x
(
i
)
{x^{(i)}}
x(i)和
x
(
j
)
{x^{(j)}}
x(j)都是一维向量，一维向量是数，即
(
x
(
i
)
)
T
x
(
j
)
=
(
x
(
j
)
)
T
x
(
i
)
=
x
(
i
)
x
(
j
)
=
?
x
(
i
)
,
x
(
j
)
?
{\left( {{x^{(i)}}} \right)^T}{x^{(j)}} = {\left( {{x^{(j)}}} \right)^T}{x^{(i)}} = { {x^{(i)}}}{x^{(j)}} =\langle {x^{(i)}},{x^{(j)}}\rangle
(x(i))Tx(j)=(x(j))Tx(i)=x(i)x(j)=?x(i),x(j)?】
现在可以构造对偶问题，对其进行求最大值：
由KKT条件可得：
即
y
(
i
)
(
w
T
x
(
i
)
+
b
)
?
1
=
0
{{\rm{y}}^{(i)}}({w^T}{x^{(i)}}{\rm{ + b}}) - 1 = 0
y(i)(wTx(i)+b)?1=0
两边同时乘以 y ( i ) {{\rm{y}}^{(i)}} y(i)，得： ( y ( i ) ) 2 ( w T x ( i ) + b ) ? y ( i ) = 0 {({{\rm{y}}^{(i)}})^2}({w^T}{x^{(i)}}{\rm{ + b}}) - {{\rm{y}}^{({\rm{i}})}} = 0 (y(i))2(wTx(i)+b)?y(i)=0
【注：
(
y
(
i
)
)
2
{({{\rm{y}}^{(i)}})^2}
(y(i))2=1】，得：
(
w
T
x
(
i
)
+
b
)
?
y
(
i
)
=
0
({w^T}{x^{(i)}}{\rm{ + b}}) - {{\rm{y}}^{(i)}} = 0
(wTx(i)+b)?y(i)=0
解出 b b b的值为： b = y ( i ) ? w T x ( i ) b = {{\rm{y}}^{(i)}} - {w^T}{x^{(i)}} b=y(i)?wTx(i)= y ( i ) ? ∑ j = 1 n α j y ( j ) x ( j ) x ( i ) {y^{(i)}} - \sum\limits_{{\rm{j}} = 1}^n {{\alpha _j}{y^{(j)}}{x^{(j)}}} {x^{(i)}} y(i)?j=1∑n?αj?y(j)x(j)x(i)
SVM的决策函数如下，嵌套符号函数sgn可得到分类函数【值的符号为类别】：
2.2 线性支持向量分类机
引入松弛变量，构造的超平面是软间隔超平面
引入松弛变量的数学模型：
引入松弛变量的优化问题：
约束条件：
拉格朗日化：
先对拉格朗日化的原问题求最小值来计算各变量，利用各变量求一阶偏导数置0，可得：
将各变量代回至拉格朗日化的原问题，可得：
对偶问题求最大值：
KKT条件：满足以下条件的
α
i
{\alpha _i}
αi?的集合就是优化问题的解：
2.3 C-支持向量分类机
将输入空间映射到高维特征空间，核函数【作用：避免在高维特征空间进行复杂的运算】的软间隔超平面
核函数：
- 核函数：是映射关系 ? ( x ) \phi(x) ?(x)的内积/数量积/点积
- 核函数和映射没有关系
- 核函数只是用来计算映射到高维空间之后的内积/数量积/点积的一种简便方法
直接扩展到高维的问题：
- 增大了计算量：计算量与数据量和每一条数据的维度正相关
- 没办法增加到无限维
采用核函数的对偶问题求最大值：
约束条件：
核函数的充要条件：
Mercer定理：任何半正定对称函数都可作为核函数
常见的核函数：
-
线性核（Linear Kernel）
-
多项式核（Polynomial Kernel）
-
高斯核/径向基核（RBF Kernel）
-
余弦相似性核（Cosine Similarity Kernel）
-
卡方核（Chi-squared Kernel）
3. 使用SVM的步骤
- 原始数据预处理：提取已分类和待分类的数据，并转化为SVM算法的数据格式
- 数据标准化：防止样本中不同特征数值大小相差较大影响分类器性能
- 核函数的选取：不知使用什么核函数时，优先考虑使用
RBF【最常用】 - 利用交叉验证网格搜索寻找最优参数：交叉验证防止过拟合，网格搜索在指定范围内寻找最优参数
- 使用最优参数来训练模型
- 模型验证/测试：计算已知样本点的误判率
- 预测待分类样本的类别
4. Matlab中SVM的命令
训练SVM分类器的函数fitcvsm- 调用格式：
线性SVM：s=fitcsvm(train_data,train_labels)或s=fitcsvm(train_data,train_labels,‘KernelFunction’,‘linear’)非线性SVM：s=fitcvsm(train_data,train_labels,‘Standardize’,true,‘KernelFunction’,‘rbf’,‘KernelScale’,‘auto’)- 使用高斯核/径向基核(rbf)训练 SVM 分类器，让软件计算核函数的缩放值，对预测变量进行标准化
- s是经过训练的ClassificationSVM分类器
- train_data为已知的训练样本，train_labels为已知样本点的类别标号
- 默认核函数是线性核，不知使用什么核函数时，优先考虑使用
RBF【最常用】
- 调用格式：
使用SVM分类器分类的函数predict- 调用格式：check=predict(s,train_data)或solution=predict(s,predict_data)
5. 总结
- SVM专注于找最优分界线，用于减小过拟合
- 核函数的应用使得SVM可以高效的用于非线性可分的情况
优势：
- 理论非常完美
- 支持不同的核函数，用于调参，进而寻找最优参数
缺点：当数据量特别大时，训练比较慢
6. SVM实例—螨虫的分类判别
%% I.清空环境
clc
clear
close all
%% II.导入数据
% a=load('mite.txt');
a=[1.24 1.27
1.36 1.74
1.38 1.64
1.38 1.82
1.38 1.90
1.40 1.70
1.48 1.82
1.54 1.82
1.56 2.08
1.14 1.82
1.18 1.96
1.20 1.86
1.26 2.00
1.28 2.00
1.30 1.96
1.24 1.80
1.28 1.84
1.40 2.04];
%% III.数据预处理
a=a';
% 提取数据
training=a(:,[1:15]); % 已分类数据
predicting=a(:,[16:end]); % 待分类数据
% 数据标准化mapstd
% mapstd(training)：将训练数据的每一行映射为0均值1方差的数据
[trains,ps]=mapstd(training); % 已分类数据的标准化
% mapstd('apply',predicting,ps)：对验证/测试数据进行预处理，利用训练数据中均值和方差进行处理
predicts=mapstd('apply',predicting,ps); % 待分类数据的标准化
trains=trains';
predicts=predicts';
% 已知样本点的类别标号
group=[ones(9,1);-1*ones(6,1)];
%% IV.训练SVM分类器
% 非线性SVM：使用高斯核/径向基核(rbf)训练 SVM 分类器，让软件计算核函数的缩放值，对预测变量进行标准化
% s=fitcsvm(trains,group,'Standardize',true,'KernelFunction','rbf','KernelScale','auto')
% sv_index=find(s.IsSupportVector)
% alpha=s.Alpha
% b=s.Bias
% 线性SVM：s=fitcsvm(trains,group) 或 s=fitcsvm(trains,group,'KernelFunction','linear')
s=fitcsvm(trains,group)
sv_index=find(s.IsSupportVector) % 返回支持向量的标号
alpha=s.Alpha % 返回经过训练的Lagrange乘数(分类函数的权系数)
b=s.Bias % 返回分类函数的常数项b
%% V.验证/测试SVM分类器
check=predict(s,trains) % 验证已知样本点
error_rate=1-sum(group==check)/length(group) % 计算已知样本点的误判率
%% VI.SVM分类器预测分类
solution=predict(s,predicts) % 预测待判样本点进行分类