支持向量机分析课件

第五章 支持向量机第五章 支持向量机1内容提要n1 引言n2 统计学习理论n3 线性支持向量机n4 非线性支持向量机n5 支持向量回归n6 支持向量聚类内容提要1 引言21 引言引言一一.SVM(Support Vector Machine)的历史的历史n神经网络分类器，Bayes分类器等是基于大样本大样本学习的分类器。nVapnik 等从19601960年开始关于统计学习理论统计学习理论的研究。统统计学习理论计学习理论是关于小样本小样本的机器学习理论。n19921992年支持向量机支持向量机首次被引入。19951995年Vapnik发展了支持向量机支持向量机理论。支持向量机支持向量机是基于统计学习理论统计学习理论的一种实用的机器学习机器学习方法。1 引言一.SVM(Support Vector 3二二.SVM 的发展的发展 SVM理论的发展理论的发展:最小二乘支持向量机(LS SVM)多分类支持向量机(M-SVM)支持向量回归(SVR)支持向量聚类(SVC)SVM与计算智能的融合与计算智能的融合:神经网络+支持向量机 模糊逻辑+支持向量机 遗传算法+支持向量机 小波分析+支持向量机 主分量分析+支持向量机 粗糙集理论+支持向量机二.SVM 的发展 SVM理论的发展:4三三.SVM的应用的应用 数据与文本分类 系统建模及预测 模式识别(图像及语音识别，生物特征识别)异常检测(入侵检测，故障诊断)时间序列预测三.SVM的应用52 统计学习理论统计学习理论 一一.两分类问题两分类问题n给定 l 个观测值:,i=1,2,.,l Rnn 每个观测值与一个标记相连:,i=1,2,.,l 土土1 n对于(2-类)分类,建立一个函数:表示函数的参数 使得 f 能正确地分类未学习过的样本第 2 类第 1 类2 统计学习理论 一.两分类问题第 2 类第 1 类6二二.期望风险与实验风险期望风险与实验风险n期望风险最小化期望风险最小化 其中 x,y的联合概率 P(x,y)是未知的n实验风险最小化实验风险最小化 实验风险是由在训练集上测得的平均误差所确定的n如果训练样本的个数是有限的,则实验风险最小化的方法不保证有高推广能力二.期望风险与实验风险7三三.VC理论理论VC(Vapnik-Chervonenkis)维数维数n分类函数 的集合F的VC维数 p=VCdim(F)定义(VapnikChervonenkis).函数 的集合F的VC 维数是p,当且仅当存在点集 xipi=1 使得这些点能够被所有 2p 种可能的分类方式分开,且不存在集合 xiqi=1 (q p)满足这一性质。n在 n 维空间中,超平面集合的VC维数等于n+1。nVC维数刻画了“可能近似正确”意义上的学习能力。三.VC理论8例:VC维数例:VC维数9支持向量机分析课件10四四.结构风险最小化结构风险最小化 VC 理论引入期望风险的边界,它依赖于实验风险与 F的能力。n这些边界的最小化导出结构风险最小化原理结构风险最小化原理:实验风险与实验风险与 VC 可信度之和可信度之和为最小为最小其中其中 h 与与VC 维数有关维数有关,是能力概念的一种测度是能力概念的一种测度n支持向量机是基于结构风险最小化原理支持向量机是基于结构风险最小化原理构造的一种学习机构造的一种学习机四.结构风险最小化113 线性支持向量机线性支持向量机一一.两分类问题两分类问题:线性分割情形线性分割情形第 1 类第 2 类n许多决策边界可以分割这许多决策边界可以分割这些数据点出为两类些数据点出为两类 n我们选取哪一个我们选取哪一个?3 线性支持向量机一.两分类问题:线性分割情形第 12坏的决策边界的例子坏的决策边界的例子第 1 类第 2 类第 1 类第 2 类坏的决策边界的例子第 1 类第 2 类第 1 类第 2 类13好的决策边界好的决策边界:间隔大间隔大n决策边界离两类数据应尽可能远 n最大化间隔 m第 1 类第 2 类m好的决策边界:间隔大决策边界离两类数据应尽可能远 第 1 14二二.最优化问题最优化问题n设 x1,.,xn 为数据集,yi 1,-1 为xi 的类标记要求决策边界正确地分类所有的点 于是得到一个带有约束的优化问题二.最优化问题设 x1,.,xn 为数据集,15将上述最优化问题转换成其对偶问题对偶问题:取Lagrange函数 (w,b;)=1/2w2 n i=1 i(yi(w,xi)+b 1)则对偶问题由 max W()=max(minw,b(w,b;)给出。由 minw,b(w,b;)得 /b=0 n i=1 iyi=0 /w=0 w=n i=1 iyixi将上述最优化问题转换成其对偶问题:16于是得到于是得到对偶问题对偶问题n这是一个二次规划二次规划(QP)问题问题na ai的全局最大值总可以求得nW的计算于是得到对偶问题17解得*=argmin 1/2n i=1n i=1 i jyiyj n k=1 k w*=n i=1 iyixi,b*=1/2其中Xr 与xs满足 xr,xs 0,yr=1,ys=1 则 f(x)=sgn(+b)解得*=argmin 1/2n i=1n i=1 18三三.解的性质解的性质n许多的许多的 a ai 为零为零nw 只是少数数据的线性组合n具有非零 ai 的 xi 称为支持向量支持向量(SV)n决策边界仅由SV确定 n设 tj(j=1,.,s)为支持向量的指标,于是 n为了检测一个新数据为了检测一个新数据 zn计算 如果 WTZ+b 0,则 z 属于第一类;否则,属于第二类。三.解的性质许多的 ai 为零19a6=1.4四四.几何解释几何解释第1类第2类a1=0.8a2=0a3=0a4=0a5=0a7=0a8=0.6a9=0a10=0a6=1.4四.几何解释第1类第2类a1=0.8a2=0a204 非线性支持向量机线性支持向量机 一一.非线性分割问题非线性分割问题4 非线性支持向量机 一.非线性分割问题21n关键思想关键思想:为了解决非线性分割问题,将 xi 变换到一个高维空间。n输入空间:xi 所在的空间n特征空间:变换后 f(xi)的空间n如何变换如何变换?n利用一个适当的变换f,使分类变得容易些。n特征空间中的线性算子等价于输入空间中的非线性算子。关键思想:22n变换可能出现的问题变换可能出现的问题n难以得到一个好的分类且计算开销大nSVM同时解决这两个问题同时解决这两个问题 n最小化|w|2 能得到好的分类n利用核函数技巧可以进行有效的计算 f()f()f()f()f()f()f()f()f()f()f()f()f()f()f()f()f()f()f()特征空间输入空间变换可能出现的问题f()f()f()f()f23n变换举例变换举例 定义核函数定义核函数 K(x,y)如下如下 考虑下列变换考虑下列变换n内积可由内积可由 K 计算计算,不必通过映射不必通过映射 f f()计算计算变换举例24二二.核函数技巧核函数技巧n核函数 K 与映射 f(.)之间的关系是n作为核函数技巧这是已知的n在应用中,我们指定K,从而间接地确定 f()，以代替选取f()。n直观地,K(x,y)表示我们对数据 x 和 y 之间相似性的一种描述，且来自我们的先验知识。n为了f()存在，K(x,y)需要满足 Mercer 条件。二.核函数技巧25n核函数举例核函数举例nd 阶多项式核阶多项式核n具有宽度具有宽度 s s的径向基函数核的径向基函数核n相当接近于径向基函数神经网络n具有参数具有参数 k k and q q 的的Sigmoid 核核n对所有的k 和 q，它不满足 Mercer 条件 核函数举例26三三.非线性非线性SVM算法算法n将所有的将所有的内积改为核函数内积改为核函数 n训练算法训练算法:线性的线性的 非线性的非线性的三.非线性SVM算法线性的 非线性的27n检测算法检测算法:线性的线性的非线性的非线性的n 对于一个新数据对于一个新数据z，如果如果f 0，则分到第则分到第1类；类；如果如果 f0，则分到第，则分到第2类类。检测算法:线性的非线性的 对于一个新数据z，如果f 0，28例题例题 设有设有 5个个 1 维数据点维数据点:x1=1,x2=2,x3=4,x4=5,x5=6,其中1,2,6 为第1类,而4,5 为第2类 y1=1,y2=1,y3=-1,y4=-1,y5=1。n利用利用 2 阶多项式核阶多项式核nK(x,y)=(xy+1)2nC 取为 100n先求先求 a ai(i=1,5):例题 设有 5个 1 维数据点:29n利用利用 QP 求解求解,得到na1=0,a2=2.5,a3=0,a4=7.333,a5=4.833n注意到确实满足约束条件n支持向量为 x2=2,x4=5,x5=6n描述函数为描述函数为n确定确定b当 x2,x4,x5 位于 上时,f(2)=1,f(5)=-1,f(6)=1,由此解得 b=9利用 QP 求解,得到30描述函数的值描述函数的值12456第第2类类第第1类类第第1类类描述函数的值12456第2类第1类第1类315 支持向量回归支持向量回归一一.最小二乘法最小二乘法 xf(x)i i求求 解解:5 支持向量回归一.最小二乘法 xf(x)i求 解:32二二.线性支持向量回归线性支持向量回归(SVR)约束约束:+-0 求解求解:xf(x)二.线性支持向量回归(SVR)约束:+-0 求解:33线性线性支持向量回归支持向量回归(SVR)最小化最小化:xf(x)+-0*约束约束:线性支持向量回归(SVR)最小化:xf(x)+-034Lagrange Lagrange 最优化最优化目标函数目标函数约束条件约束条件Lagrange 最优化目标函数约束条件35回归公式回归公式回归回归公式公式:性质性质:冗余性冗余性全局的且唯一的全局的且唯一的非线性推广非线性推广回归公式回归公式:性质:36三三.非线性非线性支持向量回归支持向量回归f(x)x x+-0f(x)(x)x)+-0输入空间特征空间三.非线性支持向量回归f(x)x+-0f(x)(37回归公式回归公式线性的:非线性的:一般的:回归公式线性的:非线性的:一般的:38多项式型:核函数的类型核函数的类型线性型:径向基函数型:指数径向基函数型:多项式型:核函数的类型线性型:径向基函数型:指数径向基函数型39几点说明几点说明nSVM 基本上是一个两分类器,修改 QP 公式,以允许多类别分类。n常用的方法:以不同的方式智能地将数据集分为两部分,对每一种分割方式用 SVM训练,多类别分类的结果,由所有的SVM分类器的输出经组合后得到(多数规则)。n“一对一一对一”策略策略这种方法对N 类训练数据两两组合,构建C2N=N(N-1)/2个支持向量机。最后分类的时候采取“投票”的方式决定分类结果。n“一对其余一对其余”策略策略这种方法对N分类问题构建N个支持向量机,每个支持向量机负责区分本类数据和非本类数据。最后结果由输出离分界面距离wx+b最大的那个支持向量机决定。几点说明40软件软件n关于 SVM 的实现可以在下列网址找到www.kernelmachines.org/software.htmlnSVMLight 是最早的 SVM 软件之一nSVM 的各种 Matlab toolbox 也是可利用的nLIBSVM 可以进行多类别分类nCSVM 用于SVM分类nrSVM 用于SVM回归nmySVM 用于SVM分类与回归nM-SVM 用于SVM多类别分类软件416 支持向量聚类 一一.发展简介发展简介nVapnik(1995):支持向量机支持向量机nTax&Duin(1999):利用利用SV 表示高维分表示高维分布的特征布的特征nScholkopf et al.(2001):利用利用SV计算封闭计算封闭数据点的轮廓线的集合数据点的轮廓线的集合 nBen-Hur et al.(2001):利用利用SV系统地搜系统地搜索聚类解索聚类解 6 支持向量聚类 一.发展简介42二二.方法的基本思想方法的基本思想n利用高斯核函数将数据点映射到高维特征空间利用高斯核函数将数据点映射到高维特征空间n在特征空间内寻找封闭数据点的像点的最小球在特征空间内寻找封闭数据点的像点的最小球面面n将球面映射回数据空间将球面映射回数据空间，构成封闭数据点的轮构成封闭数据点的轮廓线的集合廓线的集合 n被每条轮廓线所封闭的点即属于与同一个聚类被每条轮廓线所封闭的点即属于与同一个聚类n减小高斯核函数的宽度，增加轮廓线的数目减小高斯核函数的宽度，增加轮廓线的数目n用一个大的软间隙值处理重迭的聚类用一个大的软间隙值处理重迭的聚类二.方法的基本思想43映射到高维特征空间映射到高维特征空间映射到高维特征空间44三三.主要步骤主要步骤n 球分析球分析n 聚类分析聚类分析三.主要步骤45设 为一具有N个点的数据集 用一个非线性变换映射到高维特征空间寻求由限制的中心为a且半径为R的最小闭球球分析球分析设 为46引入引入 Lagrangian函数函数:引入松弛变量引入松弛变量j0 给出出:j 0 与与 j0 为Lagrange 乘子乘子,C 为常常数数，Cj 为惩罚项引入 Lagrangian函数:引入松弛变量j0 给出:47支持向量机分析课件48n利用利用KKT(Karush-Kuhn-Tucker)完备性完备性条件给出条件给出:支持向量机分析课件49球球球50n由球心到像点的距离:n当 R=D(xj)时，则 xj 为支持向量n在数据空间中封闭点的轮廓线为轮廓线为集合集合 x|D(x)=R由球心到像点的距离:51支持向量支持向量n满足i=0 的点xi 的像点位于特征空间之外或在边界上n如果 0 i R的点y的弧段。n所有点的邻接矩阵 Aij Aij=1，如果对于弧段上所有的y，D(y)R Aij=0，如果对于弧段上至少1个y，D(y)R聚类分析聚类分配56聚类分析聚类分析:邻接矩阵邻接矩阵聚类分析:邻接矩阵57计算主要部分的伪代码计算主要部分的伪代码Get Adjacent Matrix(A)n初始化矩阵A,各元素清零nfor i 2 to nnfor j 1 to i-1nif j R,则跳出循环nif d R then a(i,j)=a(j,i)1nendnendnendnend计算主要部分的伪代码Get Adjacent Matrix 58参数参数聚类水平由两个参数控制聚类水平由两个参数控制:1)q Gaussian 核的宽度参数。q 增加，不相连的轮廓线增加，聚类的个数增加。2)C 软间隙常数。它允许特征空间中的球不封闭所有的点。参数聚类水平由两个参数控制:59没有没有BSV的例的例没有BSV的例60有有BSV的例的例.外点的个数由参数C控制nbsv=1/C其中 nbsv 为 BSV的个数，C 为软间隙常数。p=1/NC1/NC 为BSV一部分的上界。有BSV的例.外点的个数由参数C控制nbsv=1/C61支持向量支持向量 图4说明没有BSV轮廓线分开的数据与要求利用BSV的数据之间的不同。如果不存在BSV，两个概率分布之间的小的重迭所产生的数据足以防止轮廓线分开。支持向量 图4说明没有BSV轮廓线分开的数据与62例例例63Iris 数据数据 数据集考虑150 个实例，每个实例由iris 花的4个测量数据组成。存在3种类型的花，每一种由50个实例描述。Iris 数据 数据集考虑150 个实例，每个64变动变动 p 与与 q 从q 的初始值开始，在这一尺度所有的点对生成所得到的单一聚类中可估计的核值。在这个值没有外点是需要的，于是选取 C=1.如果 q 是增加的，则单个或一些点的聚类破坏或者聚类边界变的很粗糙。为了研究BSV什么时候允许出现，则让p增加。较低个数的 SV 保证光滑的边界。当 q增加时，SV的个数也增加。如果SV的个数太多，则让 p 增加，其中许多 SV可能转入BSV，并且光滑的聚类或核边界就显现出来，如图3b。沿着一个方向系统地增加 q 与 p 就能保证最小个数的SV。变动 p 与 q 从q 的初始值开始，65关于关于 Iris 的结果的结果关于 Iris 的结果66问题问题n计算复杂度计算复杂度(O(n2m)n最优最优 q 值对于每个数据库是不同的，并且值对于每个数据库是不同的，并且很难调好。很难调好。n聚类分析中聚类分析中:n 计算邻接矩阵计算邻接矩阵n 分配标记到分配标记到BSV也存在某些问题。也存在某些问题。问题计算复杂度(O(n2m)67 谢谢大家!谢谢大家!68