支持向量机

优点：泛化错误率底，计算开销不大，结果易解释。

缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于处理二分类问题。

适用数据类型：数值型、标称型。

1、 基于最大间隔分隔数据

如果数据集是N维的，那么需要一个N-1维的对象来对数据进行分隔，该对象被称为超平面，也就是分类的决策边界。

间隔：点到分隔面的距离。

最优分隔超平面：找到距离分隔面最近的点，确保它们离分隔面的距离尽可能远。（原因是希望分类器尽可能健壮）

支持向量：离分隔超平面最近的那些点。

2、寻找最大间隔

分隔超平面的形式化表示：w^Tx+b；点A到超平面的距离：|w^TA+b|/||w||

(1)分类器求解的优化问题

工作原理：输入数据给分类器会输出一个类别标签。详解可见：

分类器：使用类似单位阶跃函数的函数对w^Tx+b作用得到f(w^Tx+b)，其中当u<0时，f(u)=-1，反之输出+1。

类别标签采用-1和+1，而不是0和1的原因：由于-1和+1仅仅相差一个符号，方便数学上的处理。可以通过一个统一公式来表示间隔或者数据点到分隔超平面的距离，同时不必担心数据属于哪一类。

点到分隔面的函数间隔：label*(w^Tx+b)；点到分隔面的几何间隔：label*(w^Tx+b)/||w||

目标求出w和b：需要找到支持向量，对间隔最大化。argmax_w,b{min_n(label·(w^Tx+b))/||w||}

该问题是一个带约束条件的优化问题，约束条件是label*(w^Tx+b)>=1.0。这类问题可以用拉格朗日乘子法求解。

g(x)=w^Tx+b=<w,x>+b=<sum(α_iy_ix_i)_1...n,x>+b=sum(α_iy_i<x_i,x>)+b推导过程可见：

 

优化目标函数最后可以写成：max_α[sum(α_i)_i=1...m-0.5*sum(label⁽ⁱ⁾·label^(j)·α_i·α_j<x⁽ⁱ⁾,x^(j)>)_i,j=1...m]，其中尖括号表示两个向量的内积，约束条件为：α>=0，和sum(α_i·label⁽ⁱ⁾)_i=1...m=0（数据必须100%线性可分）。引入松弛变量，允许有些数据点可以处于分隔面错误的一侧，新的约束条件为：

C>=α>=0，和sum(α_i·label⁽ⁱ⁾)_i=1...m=0，常数C用于控制“最大化间隔”和“保证大部分点的函数间隔小于1.0”这两个目标的权重。

SVM主要工作就是求解这些alpha。

3、SMO高效优化算法（序列最小优化）

工作原理：每次循环中选择两个alpha进行优化处理。一旦找到一对合适的alpha，那么就增大其中一个同时减小另一个。“合适“指两个alpha必须满足（1）要在间隔边界之外；（2）还没有进行过区间化处理或者不在边界上。

python实现：

4、核函数

将数据映射到高维空间，将线性不可分问题转换为线性可分问题。

常用核函数：