svm支持向量机课件

前情提要1支持向量机的创新之一在于将分类面的求解看作是一个二次规划问题支持向量机的创新之二在于揭示了对分类起关键作用的只是一部分训练样本，即支持向量1.对线性支持向量机的小结2.线性支持向量机的数学模型：(),iiiiSVfxyxxb其中i通过求解如下的优化问题得到：1min(,),2wbww(,)1iiywxb1,2,,ilL..st1,11max(),2lliijijijiijWyyxx10liiiy..st2前情提要(续1)前情提要(续2)3.线性支持向量机的编程实现：(),iiiiSVfxyxxb1,11max(),2lliijijijiijWyyxx10liiiy..stMatlabCsvcoutput(trnx,trny,testx,’linear’,alpha,bias);[nsvalphabias]=svc(trnx,trny,’linear’);svm_model*svm_train(svm_problem*prob,svm_parameter*param)svm_predict(svm_model*model,svm_node*x)3SVMForNonlinearProblems求解非线性问题的SVM4第四讲41.如何解决少量非线性可分样本？5内容提要2.如何解决大量非线性可分样本？3.核函数方法（KernelTrick）54.SVM背后的统计学习理论基本思想：通过训练误差和类间宽度之间的权衡，得到一个最优超平面。1.线性SVM求解含少量非线性可分样本的思想优化目标：111min(,;,),()2lliiwbwwCL[,]1iiiywxb约束条件：0i1,2,,ilL权衡因子松弛变量61类样本：位于分类间隔之外7类似的，通过Lagrange函数，转化为对偶问题1类样本2类样本3类样本1,11max(),2lliijijijiijWyyxx0iC1,2,,ilL1..0liiisty0i0iC()1ifx()1ifx()1ifxiC2类样本：支持向量3类样本：位于分类间隔之内7不同的权衡因子得到的不同的分类面C＝10C＝100082.非线性支持向量机当线性支持向量机划分样本会产生过多训练误差时，需要考虑使用非线性分类面对两类样本进行划分。92.1寻找非线性问题的三种思路思路1:原空间法在原空间中直接求解非线性问题10•例1：XOR问题思路2:特征空间法将非线性问题的求解转换成另一个空间中的线性问题求解12(,)xxx122212312()((),(),())(,,2)xxxxxxxx(0,0,0)(1,1,2)(0,1,0)(1,0,0)(0,0)(1,1)(0,1)(1,0)11•例2：物种分类问题12寻找特征映射Ф所面临的问题：1.特征映射Ф的确定往往需要相当高的技巧和相当专业的领域知识；3.特征映射Ф往往是一个低维向高维映射的过程，这个映射过程经常面临维数灾难。2.特征映射Ф的计算可能会相当复杂；13思路3.核函数方法1,11max(),2lliijijijiijWyyxx..st0i10liiiy优化问题：判别函数：**()sgn(,)iiifxyxxb支持向量样本之间的内积结论：构建支持向量机只需要知道任意两个样本之间的内积定义，无需知道样本点自身的特征表示构建到特征空间的隐式映射142.2线性SVM通过核函数扩展为非线性SVM(),iiiiSVfxyxxb线性SVM:假设经过某种非线性特征映射后原来的非线性可分问题可以通过线性SVM来解决，则在特征空间中的判别函数可以表示为：()(),()(,)iiiiSViiiiSVfxyxxbykxxb15其中i通过求解如下的优化问题得到：1,11,11max()(),()21(,)2lliijijijiijlliijijijiijWyyxxyykxx..st10liiiy利用核函数将非线性问题转化为线性问题的手段和方法称之为核函数方法。16•例：XOR问题中我们构造了一个非线性映射实现了特征的升维：122212312()((),(),())(,,2)xxxxxxxx()12(,)()xxxx样本点在新的特征空间中的内积为：核函数描述了样本点在经过某种特征变换后，在新的特征空间中的内积。(,)kxy2(,)xy112233(),()()()()()()()xyxyxyxy171,11max()(,)2lliijijijiijWyykxx..st0i10liiiy优化问题：判别函数：线性支持向量机非线性支持向量机利用支持向量机求解异或问题的结果示意图核函数**()sgn((,))iiifxykxxb支持向量183.1核函数的定义定义核函数是一个对称函数，对所有的满足：特征空间中的内积运算的充分必要条件是，对于任意的，它是某个这里是从X到内积特征空间F的映射。,xyX()(,)(),()kxyxyMercer定理对于任意的对称函数且有(,)Kxx()0x2()xdx(,)()()0Kxxxxdxdx193核函数方法推论令X是有限输入空间，K(x,z)是X上的对称函数。那么K(x,z)是核函数的充要条件是矩阵：是半正定的。•常用的核函数：多项式核函数高斯核函数sigmoid核函数,1((,))nijijKKxx(,)(1)dijijkxxxx22(,)exp(/2)ijijkxxxx(,)tanh(,)ijikxxkxx203.2核函数的构造令K1和K2是X*X上的核，f(∙)是X上的一个实值函数。B是一个对称半正定矩阵。那么下面的函数是核函数：从核函数中构造从特征中构造从相似性度量中构造12(,)(,)(,)kxzKxzKxz1(,)(,)kxzKxz12(,)(,)(,)kxzKxzKxz(,)()()kxzfxfz(,)TkxzxBz21223.3核函数的可分性定理2：样本点D在核函数k(x,y)导出的特征映射下线性可分的充要条件是，下列方程组不存在非负解：1(1,1,,1)THX其中，111,(,)1ijijijijijnnHhhkxxyyyy233.3核函数的可分性其中，000,(,)ijijijijijnnHhhkxxyyyy推论1：当时，样本点线性可分。01()()rankHrankH推论2：对任意给定的训练样本，如果选用RBF核函数，则当宽度参数充分小时，训练样本总是线性可分的。243.4如何选择核函数问题1：何谓一个好的核函数？好的核函数能够真实反映样本间的远近关系。问题2：如何判断核函数是否真实的反映的样本间的远近关系？比较难！但是初步判断核函数是否真实反映了训练样本之间的远近关系还是可能的。核函数的选择策略：选择能够真实反映训练样本远近关系的核函数。25问题3：训练样本间的远近关系如何表达？***1,0ijijijnnijyyKkkyy物理含义：两个属于同类的样本相似度为1，不同类的样本相似度为0。问题4：核函数与训练样本间的远近关系的一致性评估利用矩阵的相似性度量：,(,),,ABSABAABB•草案：通过求解下面的优化问题进行核函数参数的选择：*)),((maxKKS问题：如果K()如下所示：1111它是一个糟糕的Gram矩阵。因为它把所有的训练样本均看作是同一类样本。而它会使目标函数取到比较大的值！例1：核函数的选择•最终方案：通过求解下面的优化问题进行核函数的选择：)'),((maxKKS其中，jijijiyyyyk11',nnijk)('K’=物理意义：一个好的核函数能够使同类的样本更加接近，而使不同类的样本更加疏远。例1：核函数的选择实验结果：采用RBF核函数，随着半径参数的变化，Thyroid数据分类正确率与相似度之间的关系。00.511.522.533.50.20.30.40.50.60.70.80.91CorrectRateSimilarityMeasure例1：用于RBF核函数半径参数的选择12345600.10.20.30.40.50.60.70.80.91CorrectRateSimilarityMeasure实验结果：采用不同的核函数，Tyroid疾病诊断数据的分类正确率与相似度之间的关系1：线性核函数；2,3：RBF核函数，半径参数分别为2、1；4,5：eRBF核函数，半径参数分别为2、16：Sigmoid核函数例1：用于核函类型的选择3.4关于核函数方法的评述功能：采用核映射技术，将非线性问题转化为一个线性问题的非线性数据处理方法。核的使用使得将数据隐式表达为特征空间并越过本来需要的特征映射的计算成为可能。适用条件：如果某个线性问题的求解过程只与样本间的点积相关，则可以采用核函数方法将该线性问题的求解过程推广到非线性问题。Kerneltrick：将所有的计算转变为向量间的点积运算。303.5核函数方法的应用示例：PCAKPCAPCA的作用：发现数据分布的主要方向•特征降维•数据压缩•去除噪声PCA的常用功能：一个PCA的例子PCA的局限性：只能得到样本分布的线性主方向31TCXXPCA求解步骤Step1：样本中心化，使得()12(,)()xxxxStep2：求解中心化后的样本的协方差矩阵Step3：求解协方差矩阵的特征值和特征向量，其中最大特征值对应的特征向量即为主方向。(1,,)iiivCvin1对应的特征向量1v为主方向32()()TCXXKPCA：基于核函数的非线性主成分分析Step1：样本中心化，使得0iStep2：求解中心化后的样本的协方差矩阵Step3：求解协方差矩阵的特征值和特征向量1()niiivx不妨设所求的特征向量为：则根据特征向量的定义，有：(),(),kkxvxCv331111(),()(),()((),())nnnikiikjjiiijxxxxxxn根据核函数的定义，有：展开后，得到：2nKK其中K为核函数对应的的Gram矩阵。考虑到其逆存在，故：nK解该方程得到即可得到特征空间中的主分量1,()(,)niiiVxkxx样本在主方向的投影可表示为：34-1.5-1-0.500.511.5-1.5-1-0.500.511.5利用PCA得到的主分量重建结果利用KPCA得到的主分量重建结果-1-0.500.51-1.5-1-0.500.511.535KPCA与其它方法的对比36KPCA的去噪功能（USPS）Patterns7291train2007testSize:16x16LinearPCAKernelPCA37KernelFisherDiscriminantAnalysisKernelK-MeansClusteringKernelIndependentComponentAnalysis……3.6核函数方法在其它方面的应用38Parameters’selectionforMulti-KernelConstructingSpecialKernelforSpecialApplicationsDataDrivenKernelConstruction3.7核函数方面的研究39问题：1.如果已知特征映射