SVM与交叉验证
21 Oct 2017 | 算法
这篇文章承接上文，是对该项目中用到的一些算法进行概述。
支持向量机（Support Vector Machine,SVM)
概念
在机器学习领域,支持向量机(Support Vector Machine,SVM)是一个有监督的学习模型。通过一个非线性映射 p,把样本空间映射到一个高维乃至无穷维的特征空间中(Hilbert 空间),使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性可分。
当输入空间为欧式空间或离散集合、特征空间为希尔伯特空间时,核函数将表示将输入从输入空间映射到特征空间得到的特征向量之间的内积,通过使用核函数可以学习非线性支持向量机。
- 上述都是复制粘帖的废话。以下人话。
线性分类器是要在样本空间内寻找一个超平面，将不同类别的样本分开。最好的超平面是最中间的。
上图中被圈出来的点就是 支持向量 ，红线就是f(x)，即 Classfier Boundary ,两条虚线是支持向量所在的面。它们之间的间隙即我们要最大化的分类间的间隙。
它的基本目标，就是寻找w和b，使得gamma（即间隔margin）最大。即分类的间隙越大越好（把两个类的点分得越开越好）。若不存在一个能正确划分两类样本的超平面,则将样本从原始空间映射到一个更高维的特征空间, 使样本在这个特征空间内线性可分。
我们在支持向量所在的直线上乘上一个该点所属的类别y，就可以得到支持向量的表达式：y(wx+b)=1。(支持向量后面的那些点就可以不参加运算)
根据支持向量可求得分割函数。
将我们优化求解的表达式转化为：
这是一个带约束的二次规划问题，是一个凸问题。凸问题指不会有局部最优解。我们可以将其转化为对偶问题，用拉格朗日乘子法去解。 (略复杂，这里暂时不讨论)
现实中遇到线性不可分的情况，有两种解决方式：
- 用曲线将其完全分开（使用核函数）
- 还是用直线，不过不保证可分性，即包容分错的情况。在原函数中加入惩罚函数（这个点到其正确位置的距离）
C是一个由用户指定的系数，表示对分错的点加入多少的惩罚，当C很大时，分错的点就会很少，但是过拟合可能比较严重。如果C很小，分错的点可能会很多。
核函数
现实中很难确定合适的核函数,使训练样本在特征空间中线性可分。因此引入软间隔 (soft margin), 允许在一些样本上不满足约束。
- 文本数据常用线性核,情况不明时可先尝试高斯核
多类SVM
在进行N分类的情况下，主要有两种方式：
- 1 vs （N-1）：我们需要训练N个分类器，看第i个分类器是属于分类i还是其补集。
- 1 vs 1 : 我们需要训练 N*(N-1)/2 个分类器，分类器（i，j）能判断某个点是属于i还是属于j。
C-SVC
SVM有四种类型。包括用于分类的 C-SVC 和 nu-SVC ，以及用于回归的epsilon-SVR and nu-SVR。
C表示错误项的惩罚参数（cost parameter）。
- SVR 表示支持向量回归。
- SVC 表示支持向量分类。
Logistic Regression VS SVM
交叉验证（cross validation）
K-折交叉验证是将数据集分成 K 个子集,K 个子集中的一个作为测试集,而其余的 K-1 个数据集作为训练集,最后对 K 个数据子集的正确分类结果计算均值,获得分类准确率,K 次迭代验证是对监督学习算法的结果进行评估的方法,数据集的划分一般采用等均分或者随机划分。
以下是10折交叉验证图：
参考资料：
支持向量机基础
Andrew Ng Machine Learning mooc
南京大学机器学习周志华课件