LibSVM面向数码领域的垃圾评论信息的识别研究(6)
3.1 SVM算法
支持向量机（Support Vector Machines, SVM）是Vapink等人根据统计学习理论中的结构风险最小化提出的[26-28]。SVM能够尽量提高学习机的推广能力，即使由有限数据集得到的判别函数对独立的测试集仍能够得到较小的误差。近几年来，SVM方法已经在信号处理、基因图谱识别和图像识别等方面凭借其优势得到了成功的应用。
3.1.1 SVM基本思想
SVM是从线性可分情况下的最优分类面发展而来的，其基本思想可以用图3.1来说明[29]。
图3.1 最优分类面示意图
图3.1中实心点和空心点代表两类数据样本 ，H为分类线，H1、H2分别为过各类中离分类线最近的数据样本且平行于分类线的直线，它们之间的距离叫做分类间隔（margin）。所谓的最优分类线，就是要求分类线不但能将两类正确分开我，使训练错误率为0，而且还要使分类间隔最大。推广到高文空间，最优分类线就成为最优分类面了。下面对最优分类面进行简单的介绍：
设 为两类线性可分的样本集合。对应的线性判别函数的一般形式为 ，对应的分类方程如下：
（1）
将判别函数进行归一化，使所有样本都满足 ，此时离分类面最近的样本 ，要求分类面对所有样本都能正确分类，既满足：
（2）
此时分类间隔等于 ，间隔最大等价于 最小。最优分类线H就是满足（2）式且使 最小的分类面。
过两类数据样本中离分类面最近的样本且平行于分类面H的超平面H1、H2上的数据样本就是式（2）中使等号成立的那些数据样本，这些数据样本叫做支持向量（Support Vector，SV）。
由上可知，最优分类面问题可以表示为约束优化的问题，在式（2）的约束下，求如下函数的最小值：
（3）
为此，定义如下Lagrange函数：
（4）
式中， 为Lagrange乘子，想要求（4）的最小值，对各个参数求偏导数，且偏导数为0，结果如下:
依据式（2）和（5）的约束条件，可以将上述最优分类面的求解问题转化为如下凸二次规划寻优的对偶问题：
式中， 为对应的Lagrange乘子，这是一个二次寻优问题，存在唯一解。若 为最优解，则有：
式中， 不为零的样本，即为支持向量。因此，最优分类面的权系数向量是支持向量的线性组合。
为分类阈值，可有约束条件 求解，解上述问题后得到的最优分类面函数为
（8）
若 ， 就属于该类，否则不属于该类。当最优分类面不能把两类点完全分开时，如果希望在经验风险和推广性之间求得某种均衡，则可以通过引入松弛因子，在求解最优解过程中，限制条件中加入对松弛因子的惩罚函数。
概括地说，支持向量机就是首先通过用内积函数定义的非线性变换将输入空间变换到一个高文空间，然后在这个空间中求广义的最优分类面。
3.1.2 核函数
对非线性分类问题，若在原始空间中的简单最优分类面不能得到满意的分类结果，则可以通过非线性变换转化为某个高文空间中的线性问题，变换空间求最优分类面。但是变换过程比较复杂，而SVM通过核函数变换巧妙的解决了这个问题[30]。
核函数的基本思路就是用非线性变换 将 文矢量空间中的矢量 映射到高文空间，然后在高文特征空间中设计线性学习算法，若其中各坐标分量间的相互作用仅限于内积，则不需要知道非线性变换 的具体形式，只要用满足Mercer条件的核函数替换线性算法中的内积，就能得到原输入空间中对应的线性算法[31]。