数据挖掘算法学习(七)SVM

SVM,支持向量机。数据挖掘中的一个经典算法,博主学了挺久,把学到的一些东西跟大家分享一下。

支持向量机(SVM,Support Vector Machine)是在高维特征空间使用线性函数假设空间的学习系统,它由一个来自最优化理论的学习算法训练,该算法实现了一个由统计学习理论到处的学习偏置.此学习策略由Vapnik和他的合作者提出,是一个准则性的 并且强有力的方法.在它提出来的若干年来,在范围广大的应用中,SVM的性能胜过其他大多数的学习系统。

一、主要思想

建立一个最优决策超平面,使得该平面两侧距离平面最近的两类样本之间的距离最大化,从而对分类问题提供良好的泛化能力。说白了就是:当样本点的分布无法用一条直线或几条直线分开时(即线性不可分)SVM提供一种算法,求出一个曲面用于划分。这个曲面,就称为最优决策超平面。而且,SVM采用二次优化,因此最优解是唯一的,且为全局最优。前面提到的距离最大化就是说,这个曲面让不同分类的样本点距离最远,即求最优分类超平面等价于求最大间隔。

放一张图直观感受下超平面。



二、求解过程

(针对线性可分情况)

很多人学习了半天,看着公式推导了一大堆,最后都没明白到底是为了求什么,接下来就先看看,我们到底要推导什么。

前文说过的最优分类超平面,我们这样表示:

当我们求出W和b之后,对于待分类的点,带入公式 注意:X是待分类点向量,W与X做向量积。然后我们通过判断结果的符号,就可以将点进行分类。

接下来言归正传。









(针对非线性可分情况)

对非线性可分情况,SVM采用如下方法:将输入向量映射到一个高维特征向量空间。引入核函数可以在解决非线性问题的同时,避免维度灾难。


三、一个例子

输入向量x

期望的响应d

-1-1

-1

-1+1

+1

+1-1

+1

+1+1

-1

a.核函数



b.基函数

根据核函数的展开式,我们得到基函数,也就是输入向量在高维空间中的映射,在此例中,输入为二维空间,通过基函数映射到六维空间。


根据此特征函数,分别计算出每个样本映射到六维空间中的向量


其他三个向量具体计算略


c.目标函数



d.求得W



e.最优超平面



四、小结

SVM的优势:

最大间隔的思想-更好的泛化能力,有助于解决过度拟合

核函数-解决非线性问题的同时避免维度灾难

二次优化-存在唯一解,并且可以找到全局最优

稀疏性-支持向量个数相对数据集小得多,易于存储

不足:

运算效率低

计算时占用资源过大


郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。