一、支持向量机介绍

支持向量机是一种分类方法,它适用于二分类,但是实际使用时可以通过多个支持向量机的组合实现多分类。

在下图中的二分类问题中,我们可以看到,有效划分两个类别的分解线(二维为分界面,多维为超平面)有很多,我们需要评估哪一种分界线的效果更好。

1.1 最大间隔

衡量分界线(超平面)的有效性,需要同时衡量分界线(超平面)距离分类样本的距离,即被划分不同种类样本之间的间隔,间隔越大效果越好。

1.2 支持向量和支持向量机

线性代数知识是处理大量数据的有效工具,在线性代数思想中数据分布在多维空间中,空间中的每个样本有且只有一个坐标与之相对应,由此,我们可以将支持样本空间中的每个样本点用向量表示,这也是支持向量机中向量的由来。

在二分类问题划分界限时,只有a、b、c、d、e决定着最有分界线(超平面),所以被称之为支持向量,由此得到的二分类器被称作为支持向量机。

综上所述,支持向量机通俗来讲就是针对二分类问题给定可分类样本,寻找最优分界线(超平面)的算法,而这个最优分界面应该是间隔最大化的。

二、算法求解过程

2.1 基本概念

训练集T:

T=(x1,y1),(x2,y2),...,(xN,yN)T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}

其中,样本xi=(xi1,xi2,...,xin)x_i=(x_{i}^{1},x_{i}^{2},...,x_{i}^{n})是n维的向量,表示一个样本由n个特征组成,整个数据集中含有N个样本;标记yi(1,+1)y_i{\in}(-1,+1)表示二分类,只有两种结果。

最优分界面(超平面方程):

wx+b=0w^*·x+b^*=0

其中,w^\*,x是向量,b^\*是标量,加\*表示最优。w^\*=(w_{1}^{\*},w_{2}^{\*},...,w_{n}^{\*},),x=(x(1),x(2),...,x(n))x=(x^{(1)},x^{(2)},...,x^{(n)})

决策函数:

f(x)=sign(wx+b)f(x)=sign(w^*·x+b^*)

f(x)={+1正类1负类f(x)=\begin{cases} +1 & 正类 \\ -1 & 负类 \\ \end{cases}

样本到超平面(w,b)的函数间隔:

函数间隔γ(xi)\gamma^-(x_i)定义为:

γ(xi)=yi(wxi+b)\gamma^-(x_i)=y_i·(w·x_i+b)

其中yi(1,+1)y_i\in(-1, +1),则M(xi)0M(x_{i})\geq0

函数间隔的特点:同一个超平面可以对应不同的函数间隔(乘以常数C)。

几何间隔:

几何间隔实际上就是点到平面的欧氏距离

归一化的函数间隔:

γ(xi)=yi(wwxi+bw)\gamma(x_i)=y_i·(\frac{w}{||w||}·x_i+\frac{b}{||w||})

其中w||w||表示ww范数:

w=w12+w22+...+wn2||w||=\sqrt{w_{1}^{2}+w_{2}^{2}+...+w_{n}^{2}}

归一化的函数间隔不会再因为同一个超平面(乘以常数C)再变得可大可小。

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

γ(xi)=γ(xi)w\gamma^{-}(x_i)=\frac{\gamma(x_i)}{||w||}

训练集T到超平面(w,b)的函数间隔:

γ=mini(γ(xi))\gamma=min_{i}(\gamma^-(x_i))

训练集T到超平面(w,b)的几何间隔:

γ=mini(γ(xi))\gamma=min_{i}(\gamma(x_i))