支持向量机分类器.docxVIP

支持向量机分类器1 支持向量机的提出与发展支持向量机( SVM, support vector machine )是数据挖掘中的一项新技术，是借助于最优化方法来解决机器学习问题的新工具，最初由V.Vapnik等人在1995年首先提出，近几年来在其理论研究和算法实现等方面都取得了很大的进展，开始成为克服“维数灾难”和过学习等困难的强有力的手段，它的理论基础和实现途径的基本框架都已形成。根据Vapnik Chervonenkis的统计学习理论 ,如果数据服从某个(固定但未知的)分布,要使机器的实际输出与理想输出之间的偏差尽可能小,则机器应当遵循结构风险最小化( SRM,structural risk minimization)原则,而不是经验风险最小化原则,通俗地说就是应当使错误概率的上界最小化。SVM正是这一理论的具体实现。与传统的人工神经网络相比,它不仅结构简单,而且泛化( generalization)能力明显提高。2 问题描述2.1问题引入假设有分布在Rd空间中的数据，我们希望能够在该空间上找出一个超平面(Hyper-pan),将这一数据分成两类。属于这一类的数据均在超平面的同侧，而属于另一类的数据均在超平面的另一侧。如下图。??????????????????????????????????????????????????????????????? 比较上图，我们可以发现左图所找出的超平面（虚线），其两平行且与两类数据相切的超平面（实线）之间的距离较近，而右图则具有较大的间隔。而由于我们希望可以找出将两类数据分得较开的超平面，因此右图所找出的是比较好的超平面。可以将问题简述如下：设训练的样本输入为xi，i=1，…，l，对应的期望输出为yi∈{+1，-1}，其中+1和-1分别代表两类的类别标识，假定分类面方程为ω﹒x+b=0。为使分类面对所有样本正确分类并且具备分类间隔，就要求它满足以下约束条件：　　　它追求的不仅仅是得到一个能将两类样本分开的分类面，而是要得到一个最优的分类面。2.2 问题的数学抽象将上述问题抽象为：根据给定的训练集其中，X 称为输入空间，输入空间中的每一个点xi由n 个属性特征组成，寻找Rn上的一个实值函数g(x)，以便用分类函数 f (x) = sgn(g(x)),推断任意一个模式x 相对应的y 值的问题为分类问题。判别函数g(x)是特征空间中某点x到超平面的距离的一种代数度量。如果g(x)0，则判定x属于C1，如果g(x)0，则判定x属于C2，如果g(x)=0，则可以将x任意分到某一类或者拒绝判定。3 支持向量机分类算法3.1 线性可分支持向量分类机3.1.1 基础理论与定理3.1.2 最优超平面的求解该分类函数只包含分类样本与训练样本中的支持向量的内积运算，可见，要解决一个特征空间中的最优线性分类问题，我们只需要知道这个空间中的内积运算即可。3.2 线性支持向量分类机3.3 可分支持向量分类机3.4 C-支持向量分类机总之，根据反函数的有关理论，只要一种核函数K（xi,xj）满足Mercer条件，它就对应某一变换空间中的内积。因此，在最优分类面中采用适当的内积函数K（xi,xj）就可以实现某一非线性变换后的线性分类，而计算复杂度却没有增加。相应的分类函数也变为概括地说，支持向量机就是首先通过用内积函数定义的非线性变换将输入空间变换到一个高维空间，在这个空间中求最优分类面。 SVM分类函数形式上类似于一个神经网络，输出是中间节点的线性组合，每个中间节点对应一个输入样本与一个支持向量的内积，因此也被叫做支持向量网络。支持向量机示意图4 支持向量机应用举例