概念

• 支持向量机是数据挖掘中的一项新技术，是借助最优化方法来解决机器学习的新工具，成为克服“维数灾难”和“过学习”等困难的强有力手段。其主要思想是找到一个超平面，使得它能够尽可能多地将两类数据点正确分开，同时使分开地两类数据点距离分类面最远。

基本原理和推导(硬间隔)

• 设数据集$T=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\}\in (\Omega \times Y)$，$x_i$为样本，有很多特征（是一个向量），$y_i$为分类结果， y i ∈ Y = { − 1 , 1 } y_i\in Y=\{-1,1\} yi​∈Y={−1,1}。
• 现在我们需要得到一个决策函数$g(x)$，从而得到分类函数$f(x)=sgn(g(x))$对未知样本进行分类。

1. 决策方程为$y(x)={\omega }^{T}x+b$

{ y ( x i ) > 0 y i = 1 y ( x i ) < 0 y i = − 1 ⇒ y i y ( x i ) > 0

\Rightarrow y_iy(x_i)>0 {y(xi​)>0y(xi​)<0​yi​=1yi​=−1​⇒yi​y(xi​)>0

2. 该模型地目标是要找到一个超平面${\omega }^{T}x+b=0$，使得一群数据点中距离该平面最近的点到该平面的距离最大，即

arg ⁡ ω , x max ⁡ { 1 ∣ ∣ ω ∣ ∣ min ⁡ i [ y i ( ω T x i + b ) ] }

argω,x​max{∣∣ω∣∣1​imin​[yi​(ωTxi​+b)]}​​
注：点到平面的距离：$\frac{|{\omega }^T{x}_i+b|}{||\omega ||}$

3. 对于决策方程，可以通过放缩$\omega ，b$使得其结果$|y|\ge 1$，所以$y_i({\omega }^T{x}_i+b)\ge 1$，(1)式转化为${\arg }_{\omega ,x}\max \frac{1}{||\omega ||}$。

目标： max ⁡ ω , b 1 ∣ ∣ ω ∣ ∣ 约束条件： y i ( ω T x i + b ) ≥ 1 ⇒ 目标： min ⁡ ω , b 1 2 ∣ ∣ ω ∣ ∣ 2 约束条件： y i ( ω T x i + b ) ≥ 1

\Rightarrow 目标：约束条件：​ω,bmax​∣∣ω∣∣1​yi​(ωTxi​+b)≥1​⇒目标：约束条件：​ω,bmin​21​∣∣ω∣∣2yi​(ωTxi​+b)≥1​
注：此时的超平面称为规范超平面
此目标规划是凸优化（二次规划），数据量和维数较少时，可以用matlab中的quadprog函数求解

4. 引入拉格朗日函数，把带约束问题转化为无约束问题：

min ⁡ ω , b max ⁡ α L ( ω , b , α ) α i ≥ 1 , i = 1 , . . . , n

ω,bmin​αmax​L(ω,b,α)αi​≥1,i=1,...,n​
其中，$L(\omega ,b,\alpha )=\frac{1}{2}||\omega |{|}^2+{\sum }_{i=1}^n{\alpha }_i(1-y_i({\omega }^T{x}_i+b))$，${\alpha }_i$是拉格朗日乘子
注：可以这样理解两个问题是等价的：
若$1-y_i({\omega }^T{x}_i+b)>0,\max L=\frac{1}{2}||\omega |{|}^2+\infty =\infty$
若$1-y_i({\omega }^T{x}_i+b)\le 0,\max L=\frac{1}{2}||\omega |{|}^2+0=\frac{1}{2}||\omega |{|}^2$
所以 min ⁡ ω , b max ⁡ α L ( ω , b , α ) = min ⁡ ω , b { ∞ , 1 2 ∣ ∣ ω ∣ ∣ 2 } = min ⁡ ω , b 1 2 ∣ ∣ ω ∣ ∣ 2 \min_{\omega,b}\max_{\alpha}L(\omega,b,\alpha)=\min_{\omega,b}\{\infty,\frac{1}{2}||\omega||^2\}=\min_{\omega,b}\frac{1}{2}||\omega||^2 minω,b​maxα​L(ω,b,α)=minω,b​{∞,21​∣∣ω∣∣2}=minω,b​21​∣∣ω∣∣2，而且无约束问题的解$(\omega ,b)$满足$1-y_i({\omega }^T{x}_i+b)\le 0$

5. 上面的无约束问题的强对偶问题为：

max ⁡ α min ⁡ ω , b L ( ω , b , α ) α i ≥ 1 , i = 1 , . . . , n

αmax​ω,bmin​L(ω,b,α)αi​≥1,i=1,...,n​
由 { ∂ L ∂ b = 0 ∂ L ∂ ω = 0

{∂L∂b=0∂L∂ω=0" role="presentation" style="position: relative;">{∂L∂b=0∂L∂ω=0$$\{\begin{array}{l}\frac{\mathrm{\partial }L}{\mathrm{\partial }b}=0\\ \frac{\mathrm{\partial }L}{\mathrm{\partial }\omega }=0\end{array}$$

{∂b∂L​=0∂ω∂L​=0​得到${\sum }_{i=1}^n{\alpha }_i{y}_i=0,\omega ={\sum }_{i=1}^n{\alpha }_i{x}_i{y}_i$，代入优化问题，得
min ⁡ α 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 n α i { ∑ i = 1 n α i y i = 0 α i ≥ 0 \min_{\alpha}\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_j y_i y_j(x_i\cdot x_j)-\sum_{i=1}^n\alpha_i \\

{∑i=1nαiyi=0αi≥0" role="presentation" style="position: relative;">{∑ni=1αiyi=0αi≥0$$\{\begin{array}{l}\sum _{i=1}^n{\alpha }_i{y}_i=0\\ {\alpha }_i\ge 0\end{array}$$

αmin​21​i=1∑n​j=1∑n​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑n​αi​{∑i=1n​αi​yi​=0αi​≥0​

6. 求解上述最优化问题得${\alpha }^{\ast }=[{\alpha }_1^{\ast },{\alpha }_2^{\ast },...,{\alpha }_n^{\ast }{]}^T$，计算

$${\omega }^{\ast }=\sum _{i=1}^n{\alpha }_i^{\ast }{x}_i{y}_i$$

7. 由KKT互补条件知

$${\alpha }_i^{\ast }(1-y_i({\omega }^{\ast }\cdot x_i+b^{\ast }))=0$$
由此推断可知，当$x_i$为支持向量时（$1-y_i({\omega }^{\ast }\cdot x_i+b^{\ast })=0$），对应得${\alpha }_i$为正；当$x_i$不为支持向量时（$1-y_i({\omega }^{\ast }\cdot x_i+b^{\ast })<0$），对应得${\alpha }_i$为0；
并可以计算得
$$b^{\ast }=y_j-\sum _{i=1}^n{\alpha }_i^{\ast }{y}_i(x_i\cdot x_j)$$
注：支持向量可以理解为支撑起超平面的点，如果再增加一些边界之外的点，是不影响超平面的，即超平面由支持向量决定。如下图：

8. 构造分类超平面$w^{\ast }\cdot x+b^{\ast }=0$，并由此可以得到

决策方程
$$g(x)={\omega }^{\ast }\cdot x+b^{\ast }=\sum _{i=1}^n{\alpha }_i^{\ast }{y}_i(x_i\cdot x)+b^{\ast }$$
分类函数
$$f(x)=sgn(g(x))=sgn(\sum _{i=1}^n{\alpha }_i^{\ast }{y}_i(x_i\cdot x)+b^{\ast })$$

软间隔

• 当训练集的两类样本近似可分时，即允许存在不满足约束条件$y_i(\omega \cdot x+b)\ge 1$的样本点，但仍然能使用超平面进行划分。即在两个分类边界$\omega \cdot x+b=\pm 1$之间允许出现样本点。

1. 为了解决这种情况，引入松弛变量${\xi }_i\ge 0,i=1,...,n$，得到“软化”的约束条件

$$y_i(\omega \cdot x+b)\ge 1-{\xi }_i,i=1,...,n$$
避免${\xi }_i$取太大的值，为此要在目标函数中对它进行惩罚，得到如下的二次规划问题：
min ⁡ 1 2 ∣ ∣ ω ∣ ∣ 2 + C ∑ i = 1 n ξ i s . t . { y i ( ω ⋅ x + b ) ≥ 1 − ξ i ξ i ≥ 0 , i = 1 , . . . , n

​min21​∣∣ω∣∣2+Ci=1∑n​ξi​s.t.{yi​(ω⋅x+b)≥1−ξi​ξi​≥0,i=1,...,n​​
注：$C$越大，${\xi }_i$越小，说明要求分类得更准确，$C\to \infty$时，${\xi }_i=0$，就是绝对准确，即硬间隔；$C$越小，说明有更大的错误容忍。
$C$是一个常数，可以用K折交叉验证来选择合适的$C$。

2. 和硬间隔的步骤一样，最终得优化问题：

min ⁡ α 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 n α i { ∑ i = 1 n α i y i = 0 0 ≤ α i ≤ C , i = 1 , . . . , n

​αmin​21​i=1∑n​j=1∑n​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑n​αi​{∑i=1n​αi​yi​=00≤αi​≤C,i=1,...,n​​

3. 求解上述最优化问题得${\alpha }^{\ast }=[{\alpha }_1^{\ast },{\alpha }_2^{\ast },...,{\alpha }_n^{\ast }{]}^T$，计算

$${\omega }^{\ast }=\sum _{i=1}^n{\alpha }_i^{\ast }{x}_i{y}_i$$
$$b^{\ast }=y_j-\sum _{i=1}^n{\alpha }_i^{\ast }{y}_i(x_i\cdot x_j)$$
$$f(x)=sgn(g(x))=sgn(\sum _{i=1}^n{\alpha }_i^{\ast }{y}_i(x_i\cdot x)+b^{\ast })$$

核函数

• 当两类样本点得重合区域很大时，无法使用线性划分。但我们可以将样本点映射到更高维得空间，以使得两类样本点可分。如下：

• 此时得目标就是找到一种变换的方法$\varphi (x)$

1. 此时得二次规划问题：

min ⁡ 1 2 ∣ ∣ ω ∣ ∣ 2 y i ( ω T ϕ ( x i ) + b ) ≥ 1 , i = 1 , . . . , n

​min21​∣∣ω∣∣2yi​(ωTϕ(xi​)+b)≥1,i=1,...,n​
核函数$K(x_i,x_j)=\varphi (x_i)\cdot \varphi (x_j)$，可以避免在高维特征空间进行复杂得运算，不同得核函数形成不同得算法。
主要的核函数：

1. 线性内核函数$K(x_i,x_j)=x_i\cdot x_j$
2. 多项式核函数 $K(x_i,x_j)=(x_i\cdot x_j+1{)}^q$
3. 径向基核函数（高斯核函数，RBF） K ( x i , x j ) = exp ⁡ { − ∣ ∣ x i − x j ∣ ∣ 2 2 σ 2 } K(x_i,x_j)=\exp \{-\frac{||x_i-x_j||^2}{2\sigma^2}\} K(xi​,xj​)=exp{−2σ2∣∣xi​−xj​∣∣2​}
4. 和硬间隔的步骤一样，最终得优化问题：

min ⁡ α 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j K ( x i ⋅ x j ) − ∑ i = 1 n α i { ∑ i = 1 n α i y i = 0 α i ≥ 0 , i = 1 , . . . , n

​αmin​21​i=1∑n​j=1∑n​αi​αj​yi​yj​K(xi​⋅xj​)−i=1∑n​αi​{∑i=1n​αi​yi​=0αi​≥0,i=1,...,n​​

3. 求解上述最优化问题得${\alpha }^{\ast }=[{\alpha }_1^{\ast },{\alpha }_2^{\ast },...,{\alpha }_n^{\ast }{]}^T$，计算

$$b^{\ast }=y_j-\sum _{i=1}^n{\alpha }_i^{\ast }{y}_{i}K(x_i\cdot x_j)$$
$$f(x)=sgn(g(x))=sgn(\sum _{i=1}^n{\alpha }_i^{\ast }{y}_{i}K(x_i\cdot x)+b^{\ast })$$

核函数和软间隔结合

• 当映射到高维空间也不能硬性划分时，也需要对约束条件进行软化。
• 同理得到优化问题

min ⁡ α 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j K ( x i ⋅ x j ) − ∑ i = 1 n α i { ∑ i = 1 n α i y i = 0 0 ≤ α i ≤ C , i = 1 , . . . , n

​αmin​21​i=1∑n​j=1∑n​αi​αj​yi​yj​K(xi​⋅xj​)−i=1∑n​αi​{∑i=1n​αi​yi​=00≤αi​≤C,i=1,...,n​​
$$b^{\ast }=y_j-\sum _{i=1}^n{\alpha }_i^{\ast }{y}_{i}K(x_i\cdot x_j)$$
$$f(x)=sgn(g(x))=sgn(\sum _{i=1}^n{\alpha }_i^{\ast }{y}_{i}K(x_i\cdot x)+b^{\ast })$$

一个matlab例子

a0=load('fenlei.txt');
a=a0';
b0=a(:,1:27);%已分类的数据，一列就是一个样本点
dd0=a(:,28:end);%未分类的数据
[b,ps]=mapstd(b0);%b是已分类数据标准化处理后的矩阵，sp是标准化处理的设置
dd=mapstd('apply',dd0,ps);%未分类的数据按照上述标准化处理
group=[ones(20,1);2*ones(7,1)];%已知样本点的类别标号
s=fitcsvm(b',group);%训练向量机
sv_index=s.SupportVectorLabels%返回支持向量的标号
beta=s.Alpha%权系数
bb=s.Bias%常数项
check=predict(s,b')%验证已知样本点
err_rate=1-sum(group==check)/length(group)%计算已知样本点的错判率
solution=predict(s,dd')%对待判样本点进行分类
1
2
3
4
5
6
7
8
9
10
11
12
13
14