分类和预测SVM

第四章分类和预测主讲教师：魏宏喜(博士，副教授)E-mail:[e-mail]2第四章分类和预测4.1分类和预测的定义4.2数据分类方法决策树神经网络SVM贝叶斯网络4.3数据预测方法线性回归非线性回归3SupportVectorMachineSVM概述SVM的基本原理线性可分——硬间隔SVM线性不可分——软间隔SVM非线性——核函数SVM多分类问题SVM工具4SupportVectorMachineSVM概述SVM的基本原理线性可分——硬间隔SVM线性不可分——软间隔SVM非线性——核函数SVM多分类问题SVM工具5SVM概述支持向量机(SupportVectorMachine,SVM)是由Cortes(科尔特斯)和Vapnik(瓦普尼克)于1995年首先提出。V.Vapnik6SVM概述支持向量机(SupportVectorMachine,SVM)是由Cortes(科尔特斯)和Vapnik(瓦普尼克)于1995年首先提出。SVM在解决小样本、非线性等分类问题中表现出许多特有的优势，并能够推广到函数拟合等有关数据预测的应用中。手写数字识别人脸识别文本分类……7SupportVectorMachineSVM概述SVM的基本原理线性可分——硬间隔SVM线性不可分——软间隔SVM非线性——核函数SVM多分类问题SVM工具8SVM的基本原理SVM是在两类线性可分情况下，从获得最优分类面问题中提出的。例如：有如下图所示一个两类分类问题，其中“红色空心圆圈”表示一类，“绿色实心正方形”表示另一类。问题：如何在二维平面上寻找一条直线，将这两类分开。9SVM的基本原理Findalinearhyperplane(decisionboundary)thatwillseparatethedata10SVM的基本原理OnePossibleSolutionB111SVM的基本原理AnotherpossiblesolutionB212SVM的基本原理OtherpossiblesolutionsB213SVM的基本原理Whichoneisbetter?B1orB2?Howdoyoudefinebetter?B1B214SVM的基本原理SVM是在两类线性可分情况下，从获得最优分类面问题中提出的。最优分类面就是要求分类面(二维情况下是分类线、高维情况下是超平面)不但能将两类正确分开，而且应使分类间隔最大。15SVM的基本原理SVM是在两类线性可分情况下，从获得最优分类面问题中提出的。分类间隔：假设H代表分类线，H1和H2是两条平行于分类线H的直线，并且它们分别过每类中离分类线H最近的样本，H1和H2之间的距离叫做分类间隔(margin)。MarginH2H1Hw16SVM的基本原理SVM是在两类线性可分情况下，从获得最优分类面问题中提出的。SVM就是要在满足条件的众多分类面中，寻找一个能使分类间隔达到最大的那个分类面(二维情况下是分类线、高维情况下是超平面)。17SVM的基本原理Findhyperplanemaximizesthemargin=B1isbetterthanB2B1B2b11b12b21b22marginMargin越大，对新样本的分类(抗干扰)能力越强。18SVM的基本原理Findhyperplanemaximizesthemargin=B1isbetterthanB2B1B2b11b12b21b22marginMargin越大，分类面可移动的范围更大。19SVM的基本原理问题：在给定的训练数据集上，如何求得具有最大分类间隔的分类面？设：两类线性可分样本集{(x1,y1),(x2,y2),…,(xn,yn)}，其中：xi∈Rd，yi∈{+1,-1}是类别标号，i=1,2,…,n。对于线性可分问题，分类超平面的定义如下：其中，w和b是分类超平面的参数，且w={w1,w2,…,wd}是分类超平面的法向量，b是偏差。0wxb20SVM的基本原理问题：在给定的训练数据集上，如何求得具有最大分类间隔的分类面？设：两类线性可分样本集{(x1,y1),(x2,y2),…,(xn,yn)}，其中：xi∈Rd，yi∈{+1,-1}是类别标号，i=1,2,…,n。在分类超平面上方的样本，满足如下条件：在分类超平面下方的样本，满足如下条件：0,for1iiwxby0,for1iiwxby21SVM的基本原理问题：在给定的训练数据集上，如何求得具有最大分类间隔的分类面？设：两类线性可分样本集{(x1,y1),(x2,y2),…,(xn,yn)}，其中：xi∈Rd，yi∈{+1,-1}是类别标号，i=1,2,…,n。将上面两个公式合并，对所有样本的分类应满足如下公式：1,0()(1,2,...,)1,0iiiiwxbysignwxbinwxb()0iiywxb22SVM的基本原理问题：在给定的训练数据集上，如何求得具有最大分类间隔的分类面？设：两类线性可分样本集{(x1,y1),(x2,y2),…,(xn,yn)}，其中：xi∈Rd，yi∈{+1,-1}是类别标号，i=1,2,…,n。为了处理方便，假设所有样本数据(xi,yi)，i=1,2,…,n，到分类超平面的距离至少为1，则对所有样本数据都满足：1iwxb()1iiwxby满足不等式等号条件的样本数据被称为“支持向量”23SVM的基本原理B1b11b120bxw1bxw1bxw1bxwif11bxwif1)(xfMargin是多少？24SVM的基本原理B1b11b120bxw1bxw1bxw∵每个样本到分类超平面的距离为yi*(w*xi+b)/||w||∴Margin=2*支持向量到超平面的距离=2/||w||Margin是多少？SVM找出使得Margin达到最大的参数对(w,b)。25SVM的基本原理在线性可分情况下，SVM通常被描述成一个带有约束条件的优化问题：,1min2..()10,1,...,wbiiwstyxwbin26SVM的基本原理样本数据是线性不可分时，该怎么办？27,11min{}2..()1,1,...,0niwbiiiiiwCstyxwbinSVM的基本原理样本数据是线性不可分时，该怎么办？解决方法1：通过引入松弛变量(slackvariables)，来构建软间隔SVM，带约束条件的最优化问题形式如下：惩罚因子，C通常取值为大于0的常数28SVM的基本原理样本数据是线性不可分时，该怎么办？解决方法1：通过引入松弛变量(slackvariables)，来构建软间隔SVM，带约束条件的最优化问题形式如下：29SVM的基本原理观察惩罚因子C的不同取值对分类的影响原始数据30SVM的基本原理观察惩罚因子C的不同取值对分类的影响C=10031SVM的基本原理观察惩罚因子C的不同取值对分类的影响C=1,00032SVM的基本原理观察惩罚因子C的不同取值对分类的影响C=100,000C越大分类超平面越向离群点移动，最终的分类超平面由离群点决定。33SVM的基本原理样本数据是线性不可分时，该怎么办？解决方法2：将样本数据转换到高维空间中，在高维空间中寻找分类超平面。34SVM的基本原理样本数据是线性不可分时，该怎么办？解决方法2：将样本数据转换到高维空间中，在高维空间中寻找分类超平面。35SVM的基本原理样本数据是线性不可分时，该怎么办？解决方法2：将样本数据转换到高维空间中，在高维空间中寻找分类超平面。数据变换到高维空间可分的理由：当维度增加到无限维的时候，一定可以让任意两个物体可分。举一个哲学的例子：世界上本来没有两个完全一样的物体，对于所有的两个物体，可通过增加维度来让他们最终有所区别。比如：两本书，从(颜色，内容)两个维度来说，可能是一样的，可以加上作者这个维度，实在不行还可以加入页码，拥有者，购买地点……36SVM的基本原理样本数据是线性不可分时，该怎么办？解决方法2：将样本数据转换到高维空间中，在高维空间中寻找分类超平面。使用一种非线性变换，可将原数据映射到高维空间中。左图中的点可被映射成三维空间中的某个点37SVM的基本原理样本数据是线性不可分时，该怎么办？解决方法2：将样本数据转换到高维空间中，在高维空间中寻找分类超平面。使用一种非线性变换，可将原数据映射到高维空间中。非线性变换的形式是什么样的？38SVM的基本原理样本数据是线性不可分时，该怎么办？解决方法2：将样本数据转换到高维空间中，在高维空间中寻找分类超平面。,11min{}2..()1,1,...,0niwbiiiiiwCstyxwbin通过拉格朗日乘子，可得到其对偶问题。两个样本数据的点积39SVM的基本原理样本数据是线性不可分时，该怎么办？解决方法2：将样本数据转换到高维空间中，在高维空间中寻找分类超平面。使用一种非线性变换，可将原数据映射到高维空间中。非线性变换的形式是什么样的？在数学上，数据的点积等价于使用一个核函数K(Xi,Xj)，即：K(Xi,Xj)=Φ(Xi)Φ(Xj)。40SVM的基本原理样本数据是线性不可分时，该怎么办？解决方法2：将样本数据转换到高维空间中，在高维空间中寻找分类超平面。常用的核函数形式如下：多项式核高斯核S型核41SVM的基本原理在核函数的作用下，SVM相当于如下形式的网络结构：S个支持向量参与核变换。1((,))siiiiysignayKxx42SVM的基本原理优点：有严格的数学推理；小样本分类器；特别适合处理复杂的非线性分类问题。缺点：训练时间非常长；无法直接处理多分类问题。43SupportVectorMachineSVM概述SVM的基本原理线性可分——硬间隔SVM线性不可分——软间隔SVM非线性——核函数SVM多分类问题SVM工具44SVM多分类问题对于N(N2)类分类问题，有两种解决办法：1vs(N–1)：需要训练N个分类器，第i个分类器用于判断样本数据是否属于第i类；1vs1：需要训练N*(N–1)/2个分类器，分类器(i,j)能够判断样本数据是属于第i类，还是第j类。在实际中，通常采用1vs(N-1)方式解决多分类问题。45美国贝尔实验室对邮政手写数字库进行如下实验（多分类问题）：分类器错误率人工2.5%决策树C4.516.2%两层神经网络5.9%SVM4.0%SVM多分类问题——应用实例46SupportVectorMachineSVM概述SVM的基本原理线性可分——硬间隔SVM线性不可分——软间隔SVM非线性——核函数SVM多分类问题SVM工具47SVM工具libsvm由国立台湾大学林智仁教授带领的团队开发，版本众多，包括：Matlab版，Java版，C++版等等。~cjlin/libsvm/index.html函数：svm-train,svm-predict,svm-scaleSVMlight函数：svm_learn,svm_classify48SVM工具——libsvmMatlab环境下，配置libsvm。第一步，下载最新的libsvm版本；第二步，将下载下来的.zip文件解压缩，并将整个文件夹放到Matlab的toolbox文件夹内；第三步，在Matlab命令窗口中，键入如下命令：mexsetupWouldyoulikemextolocateinstalledcompliers[y]/n?y根据系统提示，选择所需要