支持向量机分析课件

第五章支持向量机第五章支持向量机1内容提要§1引言§2统计学习理论§3线性支持向量机§4非线性支持向量机§5支持向量回归§6支持向量聚类内容提要§1引言2§1引言一.SVM(SupportVectorMachine)的历史神经网络分类器，Bayes分类器等是基于大样本学习的分类器。Vapnik等从1960年开始关于统计学习理论的研究。统计学习理论是关于小样本的机器学习理论。1992年支持向量机首次被引入。1995年Vapnik发展了支持向量机理论。支持向量机是基于统计学习理论的一种实用的机器学习方法。§1引言一.SVM(SupportVector3二.SVM的发展

⒈SVM理论的发展:最小二乘支持向量机(LS–SVM)多分类支持向量机(M-SVM)支持向量回归(SVR)支持向量聚类(SVC)

⒉SVM与计算智能的融合:神经网络+支持向量机模糊逻辑+支持向量机遗传算法+支持向量机小波分析+支持向量机主分量分析+支持向量机粗糙集理论+支持向量机二.SVM的发展

⒈SVM理论的发展:4三.SVM的应用数据与文本分类系统建模及预测模式识别(图像及语音识别，生物特征识别)异常检测(入侵检测，故障诊断)

时间序列预测三.SVM的应用5§2统计学习理论

一.两分类问题给定

l个观测值:,i=1,2,...,l

∊Rn

每个观测值与一个标记相连:

,

i=1,2,...,l

∊

{土1}

对于(2-类)分类,建立一个函数:

:表示函数的参数

使得f能正确地分类未学习过的样本第2类第1类§2统计学习理论一.两分类问题第2类第1类6二.期望风险与实验风险期望风险最小化

其中x,y的联合概率P(x,y)是未知的实验风险最小化

实验风险是由在训练集上测得的平均误差所确定的如果训练样本的个数是有限的,则实验风险最小化的方法不保证有高推广能力二.期望风险与实验风险7三.VC理论VC(Vapnik-Chervonenkis)维数分类函数的集合F的VC维数p=VCdim(F)定义(Vapnik–Chervonenkis).函数的集合F的VC维数是p,当且仅当存在点集

{xi}pi=1

使得这些点能够被所有2p种可能的分类方式分开,且不存在集合

{xi}qi=1

(q>p)满足这一性质。在n维空间中,超平面集合的VC维数等于n+1。VC维数刻画了“可能近似正确”意义上的学习能力。三.VC理论8例:VC维数例:VC维数9支持向量机分析课件10四.结构风险最小化

VC理论引入期望风险的边界,它依赖于实验风险与F的能力。这些边界的最小化导出结构风险最小化原理:实验风险与VC可信度之和为最小其中

h与VC维数有关,是能力概念的一种测度支持向量机是基于结构风险最小化原理构造的一种学习机四.结构风险最小化11§3线性支持向量机

一.两分类问题:线性分割情形第1类第2类许多决策边界可以分割这些数据点出为两类我们选取哪一个?§3线性支持向量机

一.两分类问题:线性分割情形第12坏的决策边界的例子第1类第2类第1类第2类坏的决策边界的例子第1类第2类第1类第2类13好的决策边界:间隔大决策边界离两类数据应尽可能远最大化间隔m第1类第2类m好的决策边界:间隔大决策边界离两类数据应尽可能远第114二.最优化问题设{x1,...,xn}为数据集,yi

Î{1,-1}为xi的类标记要求决策边界正确地分类所有的点

Þ于是得到一个带有约束的优化问题二.最优化问题设{x1,...,xn}为数据集,15将上述最优化问题转换成其对偶问题:取Lagrange函数Φ(w,b;α)=1/2‖w‖2–∑ni=1

αi(yi[(w,xi)+b]

–1)则对偶问题由maxαW(α)=maxα(minw,bΦ(w,b;α))给出。由minw,bΦ(w,b;α)得

əΦ/əb=0⇒∑ni=1

αiyi=0əΦ/əw=0⇒w=∑ni=1

αiyixi将上述最优化问题转换成其对偶问题:16于是得到对偶问题这是一个二次规划(QP)问题ai的全局最大值总可以求得W的计算于是得到对偶问题17解得α*=argminα1/2∑ni=1∑ni=1

αiαjyiyj<xi,xj>–∑n

k

=1

αkw*=∑ni=1

αiyixi,b*=–1/2<w*,xr+xs>其中Xr

与xs满足

xr,xs>0,yr=–1,ys=1则

f(x)=sgn(<w*,x>+b)解得α*=argminα1/2∑ni=1∑ni=1α18三.解的性质许多的ai为零w只是少数数据的线性组合具有非零ai的xi称为支持向量(SV)决策边界仅由SV确定

设tj(j=1,...,s)为支持向量的指标,于是

为了检测一个新数据z计算如果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=0a20§4非线性支持向量机

一.非线性分割问题§4非线性支持向量机

一.非线性分割问题21关键思想:

为了解决非线性分割问题,将xi变换到一个高维空间。

输入空间:xi所在的空间特征空间:变换后f(xi)的空间如何变换?利用一个适当的变换f,使分类变得容易些。

特征空间中的线性算子等价于输入空间中的非线性算子。

关键思想:22变换可能出现的问题难以得到一个好的分类且计算开销大SVM同时解决这两个问题

最小化||w||2能得到好的分类利用核函数技巧可以进行有效的计算f()f()f()f()f()f()f()f()f(·)f()f()f()f()f()f()f()f()f()f()特征空间输入空间变换可能出现的问题f()f()f()f()f23变换举例定义核函数K(x,y)如下考虑下列变换内积可由K计算,不必通过映射f(•)计算变换举例24二.核函数技巧核函数K与映射f(.)之间的关系是作为核函数技巧这是已知的在应用中,我们指定K,从而间接地确定f(•)，以代替选取f(•)。直观地,K(x,y)表示我们对数据x和y之间相似性的一种描述，且来自我们的先验知识。为了f(•)存在，K(x,y)需要满足Mercer条件。二.核函数技巧25核函数举例d阶多项式核具有宽度s的径向基函数核相当接近于径向基函数神经网络具有参数kand

q的Sigmoid核对所有的k和q，它不满足Mercer条件

核函数举例26三.非线性SVM算法将所有的内积改为核函数

训练算法:线性的非线性的三.非线性SVM算法线性的非线性的27检测算法:线性的非线性的对于一个新数据z，如果f³0，则分到第1类；如果f<0，则分到第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。利用2阶多项式核K(x,y)=(xy+1)2C取为100先求ai

(i=1,…,5):例题设有5个1维数据点:29利用QP求解,得到a1=0,a2=2.5,a3=0,a4=7.333,a5=4.833注意到确实满足约束条件支持向量为{x2=2,x4=5,x5=6}描述函数为确定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类31§5支持向量回归

一.最小二乘法xf(x)i求解:§5支持向量回归

一.最小二乘法xf(x)i求解:32二.线性支持向量回归(SVR)

约束:+-0

求解:xf(x)二.线性支持向量回归(SVR)约束:+-0求解:33线性支持向量回归(SVR)

最小化:xf(x)+-0*

约束:线性支持向量回归(SVR)最小化:xf(x)+-034Lagrange最优化目标函数约束条件Lagrange最优化目标函数约束条件35回归公式回归公式:性质:冗余性全局的且唯一的非线性推广回归公式回归公式:性质:36三.非线性支持向量回归f(x)x+-0f(x)(x)+-0输入空间特征空间三.非线性支持向量回归f(x)x+-0f(x)(37回归公式线性的:非线性的:一般的:回归公式线性的:非线性的:一般的:38多项式型:核函数的类型线性型:径向基函数型:指数径向基函数型:多项式型:核函数的类型线性型:径向基函数型:指数径向基函数型39几点说明SVM基本上是一个两分类器,修改QP公式,以允许多类别分类。常用的方法:以不同的方式智能地将数据集分为两部分,对每一种分割方式用SVM训练,多类别分类的结果,由所有的SVM分类器的输出经组合后得到(多数规则)。“一对一”策略这种方法对N类训练数据两两组合,构建C2N=N(N-1)/2个支持向量机。最后分类的时候采取“投票”的方式决定分类结果。“一对其余”策略这种方法对N分类问题构建N个支持向量机,每个支持向量机负责区分本类数据和非本类数据。最后结果由输出离分界面距离w·x+b最大的那个支持向量机决定。几点说明40

软件关于SVM的实现可以在下列网址找到/software.htmlSVMLight是最早的SVM软件之一SVM的各种Matlabtoolbox也是可利用的LIBSVM可以进行多类别分类CSVM用于SVM分类rSVM用于SVM回归mySVM用于SVM分类与回归M-SVM用于SVM多类别分类

软件41§6支持向量聚类

一.发展简介Vapnik(1995):支持向量机Tax&Duin(1999):利用SV表示高维分布的特征Scholkopfetal.(2001):利用SV计算封闭数据点的轮廓线的集合Ben-Huretal.(2001):利用SV系统地搜索聚类解§6支持向量聚类一.发展简介42二.方法的基本思想利用高斯核函数将数据点映射到高维特征空间在特征空间内寻找封闭数据点的像点的最小球面将球面映射回数据空间，构成封闭数据点的轮廓线的集合被每条轮廓线所封闭的点即属于与同一个聚类减小高斯核函数的宽度，增加轮廓线的数目用一个大的软间隙值处理重迭的聚类二.方法的基本思想43映射到高维特征空间映射到高维特征空间44三.主要步骤

⒈球分析⒉聚类分析三.主要步骤45设为一具有N个点的数据集用一个非线性变换Φ映射到高维特征空间寻求由限制的中心为a且半径为R的最小闭球

⒈球分析设为46引入

Lagrangian函数:引入松弛变量ξj＞0给出:

βj

＞0与µj＞0为Lagrange乘子,C为常数，C∑ξj为惩罚项引入Lagrangian函数:引入松弛变量ξj＞0给出:47支持向量机分析课件48利用KKT(Karush-Kuhn-Tucker)完备性条件给出:

支持向量机分析课件49球球50由球心到像点的距离:当R=D(xj)时，则xj为支持向量在数据空间中封闭点的轮廓线为集合

{x|D(x)=R}由球心到像点的距离:51支持向量满足ξi=0的点xi的像点位于特征空间之外或在边界上如果0<βi<C,它的像点位于特征空间球的曲面上这些都是支持向量支持向量满足ξi=0的点xi的像点位于特征空间之外或在边52有界支持向量满足ξi＞0及βi

＞0的点xi的像点位于特征空间之外，这样的点有µi=0，因此βi=C这些是有界支持向量(BSVs)当C＞1时，不存在有界支持向量有界支持向量满足ξi＞0及βi＞0的点xi的像点位于特53支持向量小结SVs位于聚类边界上BSVs位于聚类边界之外所有其它的点位于聚类边界之内支持向量小结SVs位于聚类边界上54数据空间数据空间55⒉聚类分析聚类分配观察:给定不同聚类中的一对数据点，任一连接它们的轨线必定走出特征空间中的球，即这条轨线包含使得D(y)>R的点y的弧段。所有点的邻接矩阵﹛Aij﹜Aij=1，如果对于弧段上所有的y，D(y)≤

RAij=0，如果对于弧段上至少1个y，D(y)>R⒉聚类分析聚类分配56聚类分析:邻接矩阵聚类分析:邻接矩阵57计算主要部分的伪代码GetAdjacentMatrix(A)初始化矩阵A,各元素清零fori←2tonforj←1toi-1ifj<ithenifa(i,j)=1theni、j两行合并为第i行elseifa(i,j)=0then计算xi和xj之间各样点x与球心距离d,一旦有样点满足d>R,则跳出循环ifd≤Rthena(i,j)=a(j,i)←1endendendend计算主要部分的伪代码GetAdjacentMatrix58参数聚类水平由两个参数控制:

1)q—Gaussian核的宽度参数。q增加，不相连的轮廓线增加，聚类的个数增加。

2)C—软间隙常数。它允许特征空间中的球不封闭所有的点。参数聚类水平由两个参数控制:59没有BSV的例没有BSV的例60有BSV的例.外点的个数由参数C控制nbs