1、第五章 支持向量机内容提要n1 引言n2 统计学习理论n3 线性支持向量机n4 非线性支持向量机n5 支持向量回归n6 支持向量聚类1 引言引言一一. SVM (Support Vector Machine)的历史的历史n神经网络分类器，Bayes分类器等是基于大样本大样本学习的分类器。nVapnik 等从19601960年开始关于统计学习理论统计学习理论的研究。统统计学习理论计学习理论是关于小样本小样本的机器学习理论。n19921992年支持向量机支持向量机首次被引入。19951995年Vapnik发展了支持向量机支持向量机理论。支持向量机支持向量机是基于统计学习理论统计学习理论的一种实用的
2、机器学习机器学习方法。二二. SVM 的发展的发展 SVM理论的发展理论的发展: 最小二乘支持向量机(LS SVM) 多分类支持向量机(M-SVM) 支持向量回归(SVR) 支持向量聚类(SVC) SVM与计算智能的融合与计算智能的融合: 神经网络+支持向量机 模糊逻辑+支持向量机 遗传算法+支持向量机 小波分析+支持向量机 主分量分析+支持向量机 粗糙集理论+支持向量机三三. SVM的应用的应用 数据与文本分类 系统建模及预测 模式识别(图像及语音识别，生物特征识别) 异常检测(入侵检测，故障诊断) 时间序列预测2 统计学习理论统计学习理论 一一. 两两分类问题分类问题n给定 l 个观测值:
3、 , i = 1, 2, ., l Rnn 每个观测值与一个标记相连: , i = 1, 2, ., l 土土1 n对于 (2-类) 分类, 建立一个函数: : 表示函数的参数 使得 f 能正确地分类未学习过的样本iy 1 R :nfixixiy第 2 类第 1 类二二.期望风险与实验风险期望风险与实验风险n期望风险最小化期望风险最小化 其中 x, y的联合概率 P(x, y) 是未知的n实验风险最小化实验风险最小化 实验风险是由在训练集上测得的平均误差所确定的n如果训练样本的个数是有限的,则实验风险最小化的方法不保证有高推广能力 liiiempxfylfR1 21 yxdPxfyfR,21三
4、三. 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维数刻画了“可能近似正确”意义上的学习能力。ff例:VC维数四四. 结构风险最小化结构风险最小化 VC 理论引入期望风险的边界, 它依赖于实验风险与 F的能力。n这些边界的最小化导出结构
5、风险最小化原理结构风险最小化原理:实验风险与实验风险与 VC 可信度之和可信度之和为最小为最小其中其中 h 与与VC 维数有关维数有关,是能力概念的一种测度是能力概念的一种测度n支持向量机是基于结构风险最小化原理支持向量机是基于结构风险最小化原理构造的一种学习机构造的一种学习机) 4/(log) 1)/2(log()()(lhlhfRfRemp3 线性支持向量机线性支持向量机一一. 两分类问题两分类问题: 线性分割情形线性分割情形第 1 类第 2 类n许多决策边界可以分割这许多决策边界可以分割这些数据点出为两类些数据点出为两类 n我们选取哪一个我们选取哪一个?坏的决策边界的例子坏的决策边界的例
6、子第 1 类第 2 类第 1 类第 2 类好的决策边界好的决策边界: 间隔大间隔大n决策边界离两类数据应尽可能远 n最大化间隔 m第 1 类第 2 类m二二. 最优化问题最优化问题n设 x1, ., xn 为数据集, yi 1,-1 为xi 的类标记要求决策边界正确地分类所有的点 于是得到一个带有约束的优化问题将上述最优化问题转换成其对偶问题对偶问题:取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
7、=0 w=n i=1 iyixi于是得到于是得到对偶问题对偶问题n这是一个二次规划二次规划 (QP) 问题问题n i的全局最大值总可以求得nW的计算解得*=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)三三. 解的性质解的性质n许多的许多的 i 为零为零nw 只是少数数据的线性组合n具有非零 i 的 xi 称为支持向量支持向量 (SV)n决策边界仅由SV确定 n设 tj (j=1, ., s) 为支持向量的指标,于是 n为了检
8、测一个新数据为了检测一个新数据 zn计算 如果 WTZ+ b 0, 则 z 属于第一类;否则,属于第二类。6=1.4四四. 几何解释几何解释第1类第2类1=0.82=03=04=05=07=08=0.69=010=04 非线性支持向量机线性支持向量机 一一. 非线性分割问题非线性分割问题n关键思想关键思想: 为了解决非线性分割问题, 将 xi 变换到一个高维空间。 n输入空间: xi 所在的空间n特征空间: 变换后 f(xi) 的空间n如何变换如何变换 ?n利用一个适当的变换f, 使分类变得容易些。 n特征空间中的线性算子等价于输入空间中的非线性算子。 n变换可能出现的问题变换可能出现的问题n
9、难以得到一个好的分类且计算开销大nSVM同时解决这两个问题同时解决这两个问题 n最小化 |w|2 能得到好的分类n利用核函数技巧可以进行有效的计算 f( )f( )f( )f( )f( )f( )f( )f( )f()f( )f( )f( )f( )f( )f( )f( )f( )f( )f( )特征空间输入空间n变换举例变换举例 定义核函数定义核函数 K (x,y) 如下如下 考虑下列变换考虑下列变换n内积可由内积可由 K 计算计算, 不必通过映射不必通过映射 f f()计算计算二二. 核函数技巧核函数技巧n核函数 K 与映射 f(.) 之间的关系是n作为核函数技巧这是已知的n在应用中, 我
10、们指定K, 从而间接地确定 f() ，以代替选取f() 。n直观地, K (x,y) 表示我们对数据 x 和 y 之间相似性的一种描述， 且来自我们的先验知识 。n为了f() 存在， K (x,y) 需要满足 Mercer 条件。n核函数举例核函数举例nd 阶多项式核阶多项式核n具有宽度具有宽度 s s的径向基函数核的径向基函数核n相当接近于径向基函数神经网络n具有参数具有参数 k k and q q 的的Sigmoid 核核n对所有的k 和 q，它不满足 Mercer 条件 三三.非线性非线性SVM算法算法n将所有的将所有的内积改为核函数内积改为核函数 n训练算法训练算法:线性的线性的 非线
11、性的非线性的n检测算法检测算法:线性的线性的非线性的非线性的n 对于一个新数据对于一个新数据z ，如果如果f 0，则分到第则分到第1类类； 如果如果 f0，则分到第则分到第2类类。例题例题 设有设有 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先求先求 i (i=1, , 5) :n利用利用 QP 求解求解 , 得到n1=0, 2=2.5, 3=
12、0, 4=7.333, 5=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描述函数的值描述函数的值12456第第2类类第第1类类第第1类类5 支持向量回归支持向量回归一一. .最小二乘法最小二乘法 YXwXXTT 0dwdLossxf(x) bwxxf2YbwXLoss ii求求 解解: :二二. 线性支持向量回归线性支持向量回归 (SVR) 约束约束: :iiTiTiybxwbxwy+-0wwMinT21 求解求解:
13、 :xf(x) bwxxf线性线性支持向量回归支持向量回归 (SVR)NiiiTCww1*21 最小化最小化: :xf(x) bwxxf+-0* 约束约束: :0,*iiiiiTiiTiybxwbxwyLagrange Lagrange 最优化最优化NiiiTCwwL1*21NiiTiiibxwy1NiiTiiibxwy1*Niiiii1*目标函数目标函数约束条件约束条件回归公式回归公式回归回归公式公式: :性质性质: :冗余性冗余性全局的且唯一的全局的且唯一的非线性推广非线性推广 bxxxyNiiii1*,三三. 非线性非线性支持向量支持向量回归回归f(x)x x+-0f(x) ( (x)x
14、)+-0输入空间特征空间回归公式回归公式线性的: bxxxyNiiii1*,非线性的: bxxxyNiiii1*,一般的: bxxKxyNiiii1*,多项式型:核函数的类型核函数的类型线性型:径向基函数型:iixxxxK,),(diixxxxK,),(222exp),(siixxxxK指数径向基函数型:22exp),(siixxxxK几点说明几点说明nSVM 基本上是一个两分类器,修改 QP 公式, 以允许多类别分类。n常用的方法: 以不同的方式智能地将数据集分为两部分, 对每一种分割方式用 SVM训练,多类别分类的结果, 由所有的SVM分类器的输出经组合后得到 (多数规则) 。n“一对一一
15、对一”策略策略这种方法对N 类训练数据两两组合,构建C2N = N (N - 1) /2个支持向量机。最后分类的时候采取“投票”的方式决定分类结果。n“一对其余一对其余”策略策略这种方法对N分类问题构建N个支持向量机,每个支持向量机负责区分本类数据和非本类数据。最后结果由输出离分界面距离wx + b最大的那个支持向量机决定。软件软件n关于 SVM 的实现可以在下列网址找到www.kernelmachines.org/software.htmlnSVMLight 是最早的 SVM 软件之一nSVM 的各种 Matlab toolbox 也是可利用的nLIBSVM 可以进行多类别分类nCSVM 用
16、于SVM分类nrSVM 用于SVM回归nmySVM 用于SVM分类与回归nM-SVM 用于SVM多类别分类6 支持向量聚类 一一. 发展简介发展简介nVapnik (1995): 支持向量机支持向量机nTax & Duin (1999): 利用利用SV 表示高维分表示高维分布的特征布的特征nScholkopf et al. (2001):利用利用SV计算封闭计算封闭数据点的轮廓线的集合数据点的轮廓线的集合 nBen-Hur et al. (2001):利用利用SV系统地搜系统地搜索聚类解索聚类解 二二. 方法的基本思想方法的基本思想n利用高斯核函数将数据点映射到高维特征空间利用高斯核函数将数据
17、点映射到高维特征空间n在特征空间内寻找封闭数据点的像点的最小球在特征空间内寻找封闭数据点的像点的最小球面面n将球面映射回数据空间将球面映射回数据空间，构成封闭数据点的轮构成封闭数据点的轮廓线的集合廓线的集合 n被每条轮廓线所封闭的点即属于与同一个聚类被每条轮廓线所封闭的点即属于与同一个聚类n减小高斯核函数的宽度减小高斯核函数的宽度，增加，增加轮廓线的数目轮廓线的数目n用一个大的软间隙值处理重迭的聚类用一个大的软间隙值处理重迭的聚类映射到高维特征空间映射到高维特征空间三三. 主要步骤主要步骤n 球分析球分析n 聚类分析聚类分析设 为一具有N个点的数据集 用一个非线性变换映射到高维特征空间寻求由限
18、制的中心为a且半径为R的最小闭球球分析球分析 ixd 22|()|jxaRj22|()|jjxaRj引入引入 Lagrangian函数函数:引入松弛变量引入松弛变量j0 给出给出: j 0 与与 j0 为为Lagrange 乘子乘子, C 为常为常数数， Cj 为惩罚项为惩罚项n利用利用KKT (Karush-Kuhn-Tucker) 完备性完备性条件给出条件给出: 球球n由球心到像点的距离:n当 R = D(xj)时，则 xj 为支持向量n在数据空间中封闭点的轮廓线为轮廓线为集合集合 x | D(x) = R22() |()|jjDxxa 支持向量支持向量n满足i=0 的点xi 的像点位于特
19、征空间之外或在边界上n如果 0 i R的点y的弧段。 n所有点的邻接矩阵 Aij Aij = 1，如果对于弧段上所有的y ，D(y) R Aij = 0，如果对于弧段上至少1个y ，D(y) R聚类分析聚类分析:邻接矩阵邻接矩阵计算主要部分的伪代码计算主要部分的伪代码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参数参数聚类水平由两个参数控制聚类水平由两个参数控制: 1) q
20、Gaussian 核的宽度参数。q 增加，不相连的轮廓线增加，聚类的个数增加。 2) C 软间隙常数。它允许特征空间中的球不封闭所有的点。没有没有BSV的例的例有有BSV的例的例. 外点的个数由参数C控制nbsv = 1/C其中 nbsv 为 BSV的个数， C 为软间隙常数。p = 1/NC1/NC 为BSV一部分的上界。支持向量支持向量 图4说明没有BSV轮廓线分开的数据与要求利用BSV的数据之间的不同。 如果不存在BSV，两个概率分布之间的小的重迭所产生的数据足以防止轮廓线分开。例例Iris 数据数据 数据集考虑150 个实例，每个实例由iris 花的4个测量数据组成。 存在3种类型的花
21、，每一种由50个实例描述。变动变动 p 与与 q 从q 的初始值开始，在这一尺度所有的点对生成所得到的单一聚类中可估计的核值。在这个值没有外点是需要的，于是选取 C = 1. 如果 q 是增加的，则单个或一些点的聚类破坏或者聚类边界变的很粗糙。为了研究BSV什么时候允许出现，则让p增加。 较低个数的 SV 保证光滑的边界。 当 q增加时， SV的个数也增加。如果SV的个数太多，则让 p 增加，其中许多 SV可能转入BSV，并且光滑的聚类或核边界就显现出来，如图3b 。 沿着一个方向系统地增加 q 与 p 就能保证最小个数的SV。 2,1max|i jijqxx关于关于 Iris 的结果的结果问题问题n计算复杂度计算复杂度 ( O(n2m)n最优最优 q 值对于每个数据库是不同的值对于每个数据库是不同的，并且，并且很难调好。很难调好。n聚类分析中聚类分析中:n 计算邻接矩阵计算邻接矩阵n 分配标记到分配标记到BSV也存在某些问题也存在某些问题。 谢谢大家!
