支持向量机
优点:泛化错误率底,计算开销不大,结果易解释。
缺点:对参数调节和核函数的选择敏感,原始分类器不加修改仅适用于处理二分类问题。
适用数据类型:数值型、标称型。
1、 基于最大间隔分隔数据
如果数据集是N维的,那么需要一个N-1维的对象来对数据进行分隔,该对象被称为超平面,也就是分类的决策边界。
间隔:点到分隔面的距离。
最优分隔超平面:找到距离分隔面最近的点,确保它们离分隔面的距离尽可能远。(原因是希望分类器尽可能健壮)
支持向量:离分隔超平面最近的那些点。
2、寻找最大间隔
分隔超平面的形式化表示:wTx+b;点A到超平面的距离:|wTA+b|/||w||
(1)分类器求解的优化问题
工作原理:输入数据给分类器会输出一个类别标签。详解可见:https://blog.csdn.net/DP323/article/details/80535863
分类器:使用类似单位阶跃函数的函数对wTx+b作用得到f(wTx+b),其中当u<0时,f(u)=-1,反之输出+1。
类别标签采用-1和+1,而不是0和1的原因:由于-1和+1仅仅相差一个符号,方便数学上的处理。可以通过一个统一公式来表示间隔或者数据点到分隔超平面的距离,同时不必担心数据属于哪一类。
点到分隔面的函数间隔:label*(wTx+b);点到分隔面的几何间隔:label*(wTx+b)/||w||
目标求出w和b:需要找到支持向量,对间隔最大化。argmaxw,b{minn(label·(wTx+b))/||w||}
该问题是一个带约束条件的优化问题,约束条件是label*(wTx+b)>=1.0。这类问题可以用拉格朗日乘子法求解。
g(x)=wTx+b=<w,x>+b=<sum(αiyixi)1...n,x>+b=sum(αiyi<xi,x>)+b推导过程可见:https://blog.csdn.net/qq_40778406/article/details/79879434
优化目标函数最后可以写成:maxα[sum(αi)i=1...m-0.5*sum(label(i)·label(j)·αi·αj<x(i),x(j)>)i,j=1...m],其中尖括号表示两个向量的内积,约束条件为:α>=0,和sum(αi·label(i))i=1...m=0(数据必须100%线性可分)。引入松弛变量,允许有些数据点可以处于分隔面错误的一侧,新的约束条件为:
C>=α>=0,和sum(αi·label(i))i=1...m=0,常数C用于控制“最大化间隔”和“保证大部分点的函数间隔小于1.0”这两个目标的权重。SVM主要工作就是求解这些alpha。
3、SMO高效优化算法(序列最小优化)
工作原理:每次循环中选择两个alpha进行优化处理。一旦找到一对合适的alpha,那么就增大其中一个同时减小另一个。“合适“指两个alpha必须满足(1)要在间隔边界之外;(2)还没有进行过区间化处理或者不在边界上。
4、核函数
将数据映射到高维空间,将线性不可分问题转换为线性可分问题。
常用核函数:https://blog.csdn.net/zhangbaoanhadoop/article/details/82084035