《支持向量机.》由会员分享，可在线阅读，更多相关《支持向量机.（68页珍藏版）》请在金锄头文库上搜索。
1、第五章 支持向量机 内容提要 n1 引言 n2 统计学习理论 n3 线性支持向量机 n4 非线性支持向量机 n5 支持向量回归 n6 支持向量聚类 1 引言 一. SVM (Support Vector Machine)的历史 n神经网络分类器，Bayes分类器等是基于大样本学习 的分类器。 nVapnik 等从1960年开始关于统计学习理论的研究。统 计学习理论是关于小样本的机器学习理论。 n1992年支持向量机首次被引入。1995年Vapnik发展了 支持向量机理论。支持向量机是基于统计学习理论的 一种实用的机器学习方法。 二. SVM 的发展 SVM理论的发展: 最小二乘支持向量机(LS
2、 SVM) 多分类支持向量机(M-SVM) 支持向量回归(SVR) 支持向量聚类(SVC) SVM与计算智能的融合: 神经网络+支持向量机 模糊逻辑+支持向量机 遗传算法+支持向量机 小波分析+支持向量机 主分量分析+支持向量机 粗糙集理论+支持向量机 三. SVM的应用 数据与文本分类 系统建模及预测 模式识别(图像及语音识别，生物特征 识别) 异常检测(入侵检测，故障诊断) 时间序列预测 2 统计学习理论 一. 两分类问题 n给定 l 个观测值: , i = 1, 2, ., l Rn n 每个观测值与一个标记相连: , i = 1, 2, ., l 土1 n对于 (2-类) 分类, 建立
3、一个函数: : 表示函数的参数 使得 f 能正确地分类未学习过的样本 第 2 类 第 1 类 二.期望风险与实验风险 n期望风险最小化 其中 x, y的联合概率 P(x, y) 是未知的 n实验风险最小化 实验风险是由在训练集上测得的平均误差所确定的 n如果训练样本的个数是有限的,则实验风险最小化的方法不保证 有高推广能力 三. VC理论 VC (Vapnik-Chervonenkis)维数 n分类函数 的集合F的VC维数 p=VCdim(F) 定义 (VapnikChervonenkis). 函数 的集合F的VC 维数是p, 当且仅当存在点集 xipi=1 使得这些点能够被所有 2p 种可能
4、 的分类方式分开,且不存在集合 xiqi=1 ( q p )满足这一性质 。 n在 n 维空间中,超平面集合的VC维数等于n + 1 。 nVC维数刻画了“可能近似正确”意义上的学习能力。 例:VC维数 四. 结构风险最小化 VC 理论引入期望风险的边界, 它依赖于实验风险与 F的能力。 n这些边界的最小化导出结构风险最小化原理:实验风险与 VC 可信度之 和为最小 其中 h 与VC 维数有关,是能力概念的一种测度 n支持向量机是基于结构风险最小化原理构造的一种学习机 3 线性支持向量机 一. 两分类问题: 线性分割情形 第 1 类 第 2 类 n许多决策边界可以分割这 些数据点出为两类 n我
5、们选取哪一个? 坏的决策边界的例子 第 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
6、=1 iyi=0 / w =0 w=n i=1 iyixi 于是得到对偶问题 n这是一个二次规划 (QP) 问题 nai的全局最大值总可以求得 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许多的 ai 为零 nw 只是少数数据的线性组合 n具有非零 ai 的 xi 称为支持向量 (SV) n决策边界仅由SV确定 n设 tj (j=1, ., s) 为支持向量的指标,于是 n为了检测一
7、个新数据 z n计算 如果 WTZ+ b 0, 则 z 属于第一类;否则,属于第二类。 a6=1.4 四. 几何解释 第1类 第2类 a1=0.8 a2=0 a3=0 a4=0 a5=0 a7=0 a8=0.6 a9=0 a10=0 4 非线性支持向量机 一. 非线性分割问题 n关键思想: 为了解决非线性分割问题, 将 xi 变换到一个高维空间 。 n输入空间: xi 所在的空间 n特征空间: 变换后 f(xi) 的空间 n如何变换 ? n利用一个适当的变换f, 使分类变得容易些。 n特征空间中的线性算子等价于输入空间中的非 线性算子。 n变换可能出现的问题 n难以得到一个好的分类且计算开销大
8、 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()计算 二. 核函数技巧 n核函数 K 与映射 f(.) 之间的关系是 n作为核函数技巧这是已知的 n在应用中, 我们指定K, 从而间接地确定 f() ，以代替选取f() 。 n直观地, K
9、 (x,y) 表示我们对数据 x 和 y 之间相似性的一种描述 ， 且来自我们的先验知识 。 n为了f() 存在， K (x,y) 需要满足 Mercer 条件。 n核函数举例 nd 阶多项式核 n具有宽度 s的径向基函数核 n相当接近于径向基函数神经网络 n具有参数 k and q 的Sigmoid 核 n对所有的k 和 q，它不满足 Mercer 条件 三.非线性SVM算法 n将所有的内积改为核函数 n训练算法: 线性的 非线性的 n检测算法: 线性的 非线性的 n 对于一个新数据z ，如果f 0，则分到第1类； 如果 f R 聚类分析:邻接矩阵 计算主要部分的伪代码 Get Adjace
10、nt Matrix (A) n初始化矩阵A ,各元素清零 nfor i 2 to n nfor j 1 to i - 1 n if j R ,则跳出循环 nif d R then a( i , j) = a( j , i) 1 n end n end nend nend 参数 聚类水平由两个参数控制: 1) q Gaussian 核的宽度参数。q 增加，不相连的轮廓 线增加，聚类的个数增加。 2) C 软间隙常数。它允许特征空间中的球不封闭所有的 点。 没有BSV的例 有BSV的例 . 外点的个数由参数C控制 nbsv = 1/C 其中 nbsv 为 BSV的个数， C 为软间隙常数。 p =
11、 1/NC 1/NC 为BSV一部分的上界。 支持向量 图4说明没有BSV轮廓线分开的数据与要求利用BSV的 数据之间的不同。 如果不存在BSV，两个概率分布之间的小的重迭所产生 的数据足以防止轮廓线分开。 例 Iris 数据 数据集考虑150 个实例，每个实例由iris 花的4个测 量数据组成。 存在3种类型的花，每一种由50个实例描述。 变动 p 与 q 从q 的初始值开始，在这一尺度所有的点对生成所得到的单一聚类 中可估计的核值。在这个值没有外点是需要的，于是选取 C = 1. 如果 q 是增加的，则单个或一些点的聚类破坏或者聚类边界变的很 粗糙。为了研究BSV什么时候允许出现，则让p增加。 较低个数的 SV 保证光滑的边界。 当 q增加时， SV的个数也增加。如果SV的个数太多，则让 p 增加 ，其中许多 SV可能转入BSV，并且光滑的聚类或核边界就显现出 来，如图3b 。 沿着一个方向系统地增加 q 与 p 就能保证最小个数的SV。 关于 Iris 的结果 问题 n计算复杂度 ( O(n2m) n最优 q 值对于每个数据库是不同的，并且 很难调好。 n聚类分析中: n 计算邻接矩阵 n 分配标记到BSV 也存在某些问题。 谢谢大家!
