[理学]支持向量机算法.ppt

,支持向量机 简介,统计决策方法,支持向量机是数据挖掘中的一项新技术，是借助于最优化方法解决机器学习的问题的新工具，它由Vapnik等根据提出的一种新的机器学习方法，它以结构风险最小为原则，它本质上是求解凸二次规划问题，在解决小样本、非线性和高维模式识别问题中有较大优势。,基本原理,问题转化为寻找映射f(x,w)：,它是评价预测准确度的一种度量，不同的学习问题有不同形式的损失函数。例,给定样本,其中,损失函数。,基本原理,定义经验风险Remp(w):,如果采用损失函数(1)，则min(Remp(w)表示错判率达最小；,如果采用损失函数(2)，则min(Remp(w)即是最小二乘法；,如果采用损失函数(3)，则min(Remp(w)即是极大似然法；,经验风险最小化存在的问题： （1）Remp(w)R(w)，推广能力或泛化能力受影响； （2）所需样本容量大； （3）某些情况下，当经验风险过小时，推广能力反而下降；经验风险和期望风险的最小点不一致。,需要一种在有限的样本条件下建立有效的学习和推广方法的理论，统计学习理论的发展和完善对解决上面的问题，提供了坚实的理论基础与有效的学习方法。,统计学习理论,统计学习理论主要包括VC理论、泛化性的界、结构风险最小化等。,1. VC维的直观定义：对于一个指示函数集，如果存在k个样本能被函数集中的函数按所有可能的2k种形式分开，则称函数集能把k个样本打散；,VC维反映了函数集的一种学习能力。VC维越大则学习机越复杂。,统计学习理论,VC维：23=8,平面上任何一条直线都不能正确划分,统计学习理论,2. 推广性的界,统计学习理论研究了对于各种类型的函数集，经验风险和实际风险之间的关系，即推广性的界。对于两分类的问题，推广性的界是指对指示函数集中的所有函数f，经验风险和实际风险之间至少以1-p的概率满足如下关系：,其中h是函数集的VC维，n是样本数。,实际风险由两部分组成：一部分是经验风险，另一部分称作置信范围，它和学习机的VC维和样本数有关。,统计学习理论,3. 结构风险最小化原则,基本思想：要使实际风险最小，就需要使得不等式中两项相互平衡，共同趋于极小。统计学习理论中提出了一种新的策略，即把函数集合构造为一个函数子集序列：,各个子集按照VC维的大小排序：,统计学习理论,4.支持向量机的基本思想,通过最大化分类边界及最小化VC维，在保证经验风险最小的基础上最小化置信范围，从而达到最小化结构风险的目的。,（1）线性可分情形,支持向量机,引入Lagrange函数：,对偶问题：,注意：求解过程涉及到了样本的内积运算。,算法步骤：,（1）设训练集,（2）求解最优化问题(1.1)，得最优解：,（3）计算,并选择 的正分量，计算,（4）构造线性最优分类超平面，得出决策函数：,支持向量机,情形1：当训练样本线性不可分时，允许有不满足约束条件 的样本点存在。,支持向量机,通过引入松弛变量，“软化”约束条件,得到如下优化问题：,转化为对偶问题：,支持向量机,情形2：当训练集线性不可分时，可以通过非线性映射将原始空间的样本映射到高维特征空间中，即寻找非线性变换：,支持向量机,由于内积运算是在相对的高维空间中进行，容易引起维数灾难。为此引入核函数K(.)，满足,支持向量机,即,注意：还可以引入松弛变量到优化问题中。,支持向量机,常见的核函数：,（1）多项式核 （2）高斯径向基核 （3）Sigmoid核 （4）Fourier核函数 ,支持向量机,核函数的性质： 封闭性 对称性 复合性,针对问题，如何选择核函数？,支持向量机算法的改进,问题： 1. 对于核函数及其参数的选择没有形成一个统一的模式，只能凭经验、实验对比、大范围的搜索或交叉验证等方法进行寻优。 2. 当样本数很大时，一般的二次规划求解方法不再适用，需要用到“分块”或“分解”的近似算法，但所耗内存空间大，迭代次数多，训练时间长等。,支持向量机算法的改进,1）v-SVM 特点：克服了SVM中C参数难以确定问题。同时还可以减少两类样本不平衡问题。适用于样本不均衡问题。,2）LS-SVM 特点：通过映射将原空间的不等式约束转化为特征空间中的等式约束，转化后的对偶问题为求解一组线性方程组。优点：计算代价小，泛化性能好，不易陷入局部极小。,支持向量机算法的改进,3）GSVM 当数据线性不可分时，SVM要求满足Mercer条件，即正定核条件。GSVM突破了这一限制。,4）Smooth SVM 特点：通过一定的变形技巧，使其转化为光滑的无约束问题，再利用经典的最优化方法求解。,支持向量机算法的改进,5）Possibilistic SVM 结合输入数据的几何分布，每个数据有一个可能性隶属值，反映对本类的隶属度，有效克服SVM中对每个数据平等对待的缺点。当样本点个数小于维数时，能有效解决过拟合问题。,6）Semi Supervised SVM 适用于训练集规模比工作集大得多的情况。加进约束条件：两类中的误分误差情形，有效地增强了它的泛化能力。 ,基本思想：,构造映射的svm,对原样本进行特征提取，引入距离映射或条件概率映射，将高维空间的样本x转化为二维空间的样本 引入核函数：,1.距离映射,马氏距离,定义映射,由此定义核函数：,构造映射的svm,2. 条件概率映射,构造映射的svm,构造映射的svm,构造映射的svm,构造映射的svm,构造映射的svm,构造映射的svm,支持向量机多分类问题,1. 一对多分类方法,基本思路： 对k个类别的分类问题，构造k个两分类的支持向量分类机。 在构建第j个分类器中时，将训练集中属于第j类的样本标为+1， 属于其它类的样本标为-1。这样第i个分类器的最优化问题：,求出k个决策函数,