支持向量机分析.ppt

第五章支持向量机 内容提要 1引言 2统计学习理论 3线性支持向量机 4非线性支持向量机 5支持向量回归 6支持向量聚类 1引言 一 SVM SupportVectorMachine 的历史神经网络分类器 Bayes分类器等是基于大样本学习的分类器 Vapnik等从1960年开始关于统计学习理论的研究 统计学习理论是关于小样本的机器学习理论 1992年支持向量机首次被引入 1995年Vapnik发展了支持向量机理论 支持向量机是基于统计学习理论的一种实用的机器学习方法 二 SVM的发展 SVM理论的发展 最小二乘支持向量机 LS SVM 多分类支持向量机 M SVM 支持向量回归 SVR 支持向量聚类 SVC SVM与计算智能的融合 神经网络 支持向量机模糊逻辑 支持向量机遗传算法 支持向量机小波分析 支持向量机主分量分析 支持向量机粗糙集理论 支持向量机 三 SVM的应用数据与文本分类系统建模及预测模式识别 图像及语音识别 生物特征识别 异常检测 入侵检测 故障诊断 时间序列预测 2统计学习理论 一 两分类问题给定l个观测值 i 1 2 l Rn每个观测值与一个标记相连 i 1 2 l 土1 对于 2 类 分类 建立一个函数 表示函数的参数使得f能正确地分类未学习过的样本 第2类 第1类 二 期望风险与实验风险期望风险最小化其中x y的联合概率P x y 是未知的实验风险最小化实验风险是由在训练集上测得的平均误差所确定的如果训练样本的个数是有限的 则实验风险最小化的方法不保证有高推广能力 三 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维数 四 结构风险最小化VC理论引入期望风险的边界 它依赖于实验风险与F的能力 这些边界的最小化导出结构风险最小化原理 实验风险与VC可信度之和为最小其中h与VC维数有关 是能力概念的一种测度支持向量机是基于结构风险最小化原理构造的一种学习机 3线性支持向量机一 两分类问题 线性分割情形 第1类 第2类 许多决策边界可以分割这些数据点出为两类我们选取哪一个 坏的决策边界的例子 第1类 第2类 第1类 第2类 好的决策边界 间隔大 决策边界离两类数据应尽可能远最大化间隔m 第1类 第2类 m 二 最优化问题 设 x1 xn 为数据集 yi 1 1 为xi的类标记要求决策边界正确地分类所有的点 于是得到一个带有约束的优化问题 将上述最优化问题转换成其对偶问题 取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 于是得到对偶问题这是一个二次规划 QP 问题ai的全局最大值总可以求得W的计算 解得 argmin 1 2 ni 1 ni 1 i jyiyj nk 1 kw ni 1 iyixi b 1 2其中Xr与xs满足xr xs 0 yr 1 ys 1则f x sgn b 三 解的性质 许多的ai为零w只是少数数据的线性组合具有非零ai的xi称为支持向量 SV 决策边界仅由SV确定设tj j 1 s 为支持向量的指标 于是为了检测一个新数据z计算如果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非线性支持向量机一 非线性分割问题 关键思想 为了解决非线性分割问题 将xi变换到一个高维空间 输入空间 xi所在的空间特征空间 变换后f xi 的空间如何变换 利用一个适当的变换f 使分类变得容易些 特征空间中的线性算子等价于输入空间中的非线性算子 变换可能出现的问题难以得到一个好的分类且计算开销大SVM同时解决这两个问题最小化 w 2能得到好的分类利用核函数技巧可以进行有效的计算 f 特征空间 输入空间 变换举例定义核函数K x y 如下考虑下列变换内积可由K计算 不必通过映射f 计算 二 核函数技巧核函数K与映射f 之间的关系是作为核函数技巧这是已知的在应用中 我们指定K 从而间接地确定f 以代替选取f 直观地 K x y 表示我们对数据x和y之间相似性的一种描述 且来自我们的先验知识 为了f 存在 K x y 需要满足Mercer条件 核函数举例d阶多项式核具有宽度s的径向基函数核相当接近于径向基函数神经网络具有参数kandq的Sigmoid核对所有的k和q 它不满足Mercer条件 三 非线性SVM算法将所有的内积改为核函数训练算法 线性的 非线性的 检测算法 线性的 非线性的 对于一个新数据z 如果f 0 则分到第1类 如果f 0 则分到第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 利用2阶多项式核K x y xy 1 2C取为100先求ai i 1 5 利用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 描述函数的值 1 2 4 5 6 第2类 第1类 第1类 5支持向量回归一 最小二乘法 求解 二 线性支持向量回归 SVR 约束 线性支持向量回归 SVR Lagrange最优化 回归公式 回归公式 性质 冗余性全局的且唯一的非线性推广 三 非线性支持向量回归 输入空间 特征空间 回归公式 线性的 非线性的 一般的 多项式型 核函数的类型 线性型 径向基函数型 指数径向基函数型 几点说明 SVM基本上是一个两分类器 修改QP公式 以允许多类别分类 常用的方法 以不同的方式智能地将数据集分为两部分 对每一种分割方式用SVM训练 多类别分类的结果 由所有的SVM分类器的输出经组合后得到 多数规则 一对一 策略这种方法对N类训练数据两两组合 构建C2N N N 1 2个支持向量机 最后分类的时候采取 投票 的方式决定分类结果 一对其余 策略这种方法对N分类问题构建N个支持向量机 每个支持向量机负责区分本类数据和非本类数据 最后结果由输出离分界面距离w x b最大的那个支持向量机决定 软件 关于SVM的实现可以在下列网址找到www kernelmachines org software htmlSVMLight是最早的SVM软件之一SVM的各种Matlabtoolbox也是可利用的LIBSVM可以进行多类别分类CSVM用于SVM分类rSVM用于SVM回归mySVM用于SVM分类与回归M SVM用于SVM多类别分类 6支持向量聚类 一 发展简介Vapnik 1995 支持向量机Tax Duin 1999 利用SV表示高维分布的特征Scholkopfetal 2001 利用SV计算封闭数据点的轮廓线的集合Ben Huretal 2001 利用SV系统地搜索聚类解 二 方法的基本思想利用高斯核函数将数据点映射到高维特征空间在特征空间内寻找封闭数据点的像点的最小球面将球面映射回数据空间 构成封闭数据点的轮廓线的集合被每条轮廓线所封闭的点即属于与同一个聚类减小高斯核函数的宽度 增加轮廓线的数目用一个大的软间隙值处理重迭的聚类 映射到高维特征空间 三 主要步骤 球分析 聚类分析 设为一具有N个点的数据集用一个非线性变换 映射到高维特征空间寻求由限制的中心为a且半径为R的最小闭球 球分析 引入Lagrangian函数 引入松弛变量 j 0给出 j 0与 j 0为Lagrange乘子 C为常数 C j为惩罚项 利用KKT Karush Kuhn Tucker 完备性条件给出 球 由球心到像点的距离 当R D xj 时 则xj为支持向量在数据空间中封闭点的轮廓线为集合 x D x R 支持向量 满足 i 0的点xi的像点位于特征空间之外或在边界上如果0 i C 它的像点位于特征空间球的曲面上这些都是支持向量 有界支持向量 满足 i 0及 i 0的点xi的像点位于特征空间之外 这样的点有 i 0 因此 i C这些是有界支持向量 BSVs 当C 1时 不存在有界支持向量 支持向量小结 SVs位于聚类边界上BSVs位于聚类边界之外所有其它的点位于聚类边界之内 数据空间 聚类分析 聚类分配观察 给定不同聚类中的一对数据点 任一连接它们的轨线必定走出特征空间中的球 即这条轨线包含使得D y R的点y的弧段 所有点的邻接矩阵 Aij Aij 1 如果对于弧段上所有的y D y RAij 0 如果对于弧段上至少1个y D y R 聚类分析 邻接矩阵 计算主要部分的伪代码 GetAdjacentMatrix A 初始化矩阵A 各元素清零fori 2tonforj 1toi 1ifjR 则跳出循环ifd Rthena i j a j i 1endendendend 参数 聚类水平由两个参数控制 1 q Gaussian核的宽度参数 q增加 不相连的轮廓线增加 聚类的个数增加 2 C 软间隙常数 它允许特征空间中的球不封闭所有的点 没有BSV的例 有BSV的例 外点的个数由参数C控制 nbsv 1 C 其中nbsv为BSV的个数 C为软间隙常数 p 1 NC 1 NC为BSV一部分的上界 支持向量 图4说明没有BSV轮廓线分开的数据与要求利用BSV的数据之间的不同 如果不存在BSV 两个概率分布之间的小的重迭所产生的数据足以防止轮廓线分开 例 Iris数据 数据集考虑150个实例 每个实例由iris花的4个测量数据组成 存在3种类型的花 每一种由50个实例描述 变动 p 与 q 从q的初始值开始 在这一尺度所有的点对生成所得到的单一聚类中可估计的核值 在这个值没有外点是需要的 于是选取C 1 如果q是增加的 则单个或一些点的