logo资料库

SVM原理讲解.doc

发布时间：2022-06-20 发布人：admin 分类：说明书 资料大小：0.64M 资料格式：doc 举报 版权申诉
第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
资料共8页，全文预览结束
    1 软间隔最大化
    2 拉格朗日对偶
    3 最优化问题求解
    5 核函数
    6 序列最小优化 (SMO)
    SVM 原理 0 介绍 支持向量机（SVM）是常见的一种判别方法，在机器学习领域，是一个有监 督的学习模型，通常用来进行模式识别、分类以及回归分析。支持向量机(SVM) 是 90 年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结 构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而 达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。 支持向量机 SVM 方法是通过一个非线性映射 p，把样本空间映射到一个高维乃至无穷维 的特征空间中，使得在原来的样本空间中非线性可分的问题转化为在特征空间中 的线性可分的问题。简单地说，就是升维和线性化。升维，就是把样本向高维空 间做映射，一般情况下这会增加计算的复杂性，甚至会引起“维数灾难”，因而 人们很少问津。但是作为分类、回归等问题来说，很可能在低维样本空间无法线 性处理的样本集，在高维特征空间中却可以通过一个线性超平面实现线性划分 （或回归）。一般的升维都会带来计算的复杂化，SVM 方法巧妙地解决了这个难 题：应用核函数的展开定理，就不需要知道非线性映射的显式表达式；由于是在 高维特征空间中建立线性学习机，所以与线性模型相比，不但几乎不增加计算的 复杂性，而且在某种程度上避免了“维数灾难”，这一切要归功于核函数的展开 和计算理论。 SVM 原理分为软间隔最大化、拉格朗日对偶、最优化问题求解、核函数、序 列最小优化、SMO 等部分。 1 软间隔最大化 SVM 的核心思路是最大化支持向量到分隔超平面的间隔。后面所有的推导都 是以最大化此间隔为核心思想展开。一般的机器学习问题都是先得到模型的目标 函数和约束条件，然后在约束条件下对目标函数求得最优解。因此下面首先需要 推导出 SVM 模型的目标函数和约束条件。 既然要最大化间隔，那么回顾下点 x 到超平面(w,b)的距离公式： d bxw  w 超平面公式为： 由此可推出点 x 到超平面(w,b)的几何间隔为： bx  w 0
    r i  xwy  ( i w i b ) 其中 xi 代表第 i 条数据，yi 代表第 i 条数据对应的目标变量的取值， 取值有+1 和-1 两种。所以当第 i 条数据被正确分类时，y 取值和 w*x+b 取值 的正负一致，几何间隔为正；当被错误分类时，y 取值和 w*x+b 取值的正负相 反，几何间隔为负。 定义几何间隔中最小的为： 由此，可以得到间隔最大化问题的目标函数： 并遵循如下约束条件： 做如下变换： 则目标函数转换为： 相应的约束条件变为： 做如下变换： 可得目标函数和约束条件变为： 由于 w, b 成倍数变化并不会影响超平面的公式，所以： 此时得到最终的间隔最大化的目标函数和约束条件如下：
    2 拉格朗日对偶 对于凸二次优化问题，通过引入拉格朗日乘子，将目标函数和约束条件整合 到拉格朗日函数中，这样能方便求解最值问题。那么，对每个不等式约束引入拉 格朗日乘子，得到拉格朗日函数如下： 分析可知： 则原最优化问题转换成： 由于原最优化问题直接求解很困难，利用拉格朗日对偶性，可通过求解原最 优化问题的对偶问题得到原问题的最优解。原最优化问题的对偶问题为： 3 最优化问题求解 到此为止，已经将目标函数和约束条件转换成了极大极小化拉格朗日函数的 问题了。首先求解关于拉格朗日函数的极小化问题。 对三个变量分别求偏导得： 将以上三式带入拉格朗日函数中得： 那么极大极小化拉格朗日函数转换成： 为求解方便，将极大转换成极小得：
    5 核函数 对于线性不可分问题，如图 2 所示，这类问题是无法用超平面划分正负样 本数据的。倘若能将超平面换成超曲面，则可以将正负样本正确分类，如图 5 所 示。图 5. 超曲面分离正负样本 我们知道曲面的公式是： 线性不可分 映射到新坐标如下： 可将超曲面在新坐标下表示成超平面： 也就是将在二维空间(x1,x2)下线性不可分的问题转换成了在五维空间 (z1,z2,z3,z4,z5)下线性可分的问题。 得映射后新坐标下的内积： 有一核函数如下： 可知 核函数在低维空间中完成了映射到高维空间后的内积运算。这点非常有用， 利用核函数，无需先将变量一一映射到高维空间再计算内积，而是简单得在低维 空间中利用核函数完成这一操作。为什么说不用一一映射到高维空间很有用呢？ 原因就在于首先我们无法针对每种情况提供精确的映射函数，再者对于需要映射 到无穷维的情况显然无法一一映射完成。在上节中我们得到了如下目标函数： 正是因为该目标函数中包含自变量的内积运算，而映射到高维空间后的内积运算 又恰好可以通过核函数在低维空间中直接求得，故而有了核函数的由来。较常用 的核函数是高斯核，高斯核可以将低维空间映射到无穷维。 运用核函数后，最优化问题的目标函数和约束条件变为：
    6 序列最小优化 (SMO) 到目前为止，优化问题已经转化成了一个包含 N 个自变量的目标变量和两个 约束条件。由于目标变量中自变量有 N 个，为了便与求解，每次选出一对自变量 ， 然后求目标函数关于其中一个偏导，这样就可以得到这一对自变量的新值。给这 一对自变量赋上新值，然后不断重复选出下一对自变量并执行上述操作，直到达 到最大迭代数或没有任何自变量发生变化为止，这就是 SMO 的基本思想。说直 白些，SMO 就是在约束条件下对目标函数的优化求解算法。 下面是详细的 SMO 过程。假设选出了两个自变量分别是 a1 和 a2，除了这两个 自变量之外的其他自变量保持固定，则目标变量和约束条件转化为： 将约束条件中的 a1 用 a2 表示，并代入目标函数中，则将目标函数转化成只包 含 a2 的目标函数，让该目标函数对 a2 的偏导等于 0： 可求得 a2 未经修剪的值： 之所以说 a2 是未经修剪的值是因为所有 a 都必须满足大于等于 0 且小于等于 C 的约束条件，用此约束条件将 a2 进行修剪，修剪过程如下：
    由此得： 分两种情况讨论： 情况 1.当 y1 等于 y2 时，有： 情况 2.当 y1 不等于 y2 时，有： 修剪后，可得 a2 的取值如下： 由 a2 和 a1 的关系，可得： 在完成 a1 和 a2 的一轮更新后，需要同时更新 b 的值，当 a1 更新后的值满足 0
    我们得到： 若 f(x)大于 0，则新样本数据属于 1；否则，新样本数据属于-1。 易知，求出 a 后，问题的求解也就结束了。
    参考文献 [1]陈永义. 支持向量机方法应用教程[M]. 北京：气象出版社,2011. [2]王定成 .支持向量机建模预测与控制[M].北京：气象出版社,2009. [3] 程 建 峰 , 乐 俊 , 刘 丹 . 基 于 SVM 算 法 的 用 户 行 为 认 证 方 法 [J]. 计 算 机 系 统 应 用,2017,(11):176-181. [4] 梁 武 , 苏 燕 . 一 种 新 的 基 于 类 内 不 平 衡 数 据 学 习 支 持 向 量 机 算 法 [J]. 科 技 通 报,2017,33(09):109-112. [5]郭敏,曾颖明,姚金利,达小文.基于大数据样本的软件行为安全分析[J].信息网络安 全,2017,(09):153-156.
    分享到：
    赞 收藏

    相关推荐

    资料库

    大数据

    共收录841份资料，累计11个分类，关注成员有19位，主要包括：Matlab,统计分析,数据挖掘,Hbase,Hive,flink,kafka,spark,Storm,算法与数据结构,Hadoop

    热门标签

    Matlab 统计分析 数据挖掘 Hbase Hive flink kafka spark Storm 算法与数据结构 Hadoop

    最新资料