基于SMO的SVM分类器.docx-资料库

xuyan190-9536327-4744300845186786206.docx.pdf-第1页.png

第1页 / 共19页

xuyan190-9536327-4744300845186786206.docx.pdf-第2页.png

第2页 / 共19页

xuyan190-9536327-4744300845186786206.docx.pdf-第3页.png

第3页 / 共19页

xuyan190-9536327-4744300845186786206.docx.pdf-第4页.png

第4页 / 共19页

xuyan190-9536327-4744300845186786206.docx.pdf-第5页.png

第5页 / 共19页

xuyan190-9536327-4744300845186786206.docx.pdf-第6页.png

第6页 / 共19页

xuyan190-9536327-4744300845186786206.docx.pdf-第7页.png

第7页 / 共19页

xuyan190-9536327-4744300845186786206.docx.pdf-第8页.png

第8页 / 共19页

机器学习经典算法详解及 Python 实现--基于 SMO 的 SVM 分类器收藏该经验您的评价: 阅读目录  2.1 函数间隔  2.2 几何间隔  2.3 定义最大间隔分类器 Maximum Margin Classifier 支持向量机基本上是最好的有监督学习算法，因其英文名为 support vector machine，简称 SVM。通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。（一）理解 SVM 基本原理 1，SVM 的本质--分类给定一些数据点，它们分别属于两个不同的类，现在要找到一个线性分类器把这些数据分成两类--这就是最基本的线性可分。如果用 x 表示数据点、用 y 表示类别（y 可以取 1 或者-1，分别代表两个不同的类），线性分类器的学习目标便是要在 n 维的数据空间中找到一个分界使得数据可以分成两类，分界方程可以表示为（此处 wT 中的 T 代表转置，x 是一个数据点（有 m 个属性的行向量），w 也是一个大小为 m 的行向量，b 是一个常数）：在二维平面上，上述分界就是一条直线，如下图将黑点和白点分开的线。三维平面上分界就会是一个平面，而更高维平面上就会是其他的分界表现形式，因此将这个分界称为超平面（hyper plane）。

图 1 再次重申，我们假设统计样本的分布式是均匀分布的，如此在两分类分类中（类别-1 或者 1）可以将阈值设为 0。实际训练数据中，样本往往是不均衡的，需要算法来选择最优阈值（如 ROC 曲线）。因此 SVM 分类器就是学习出一个分类函数，当 f(x) 等于 0 的时候，x 便是位于超平面上的点，而 f(x)大于 0 的点对应 y=1 的数据点，f(x)小于 0 的点对应 y=-1 的点。换言之，在进行分类的时候，将新的数据点 x 代入 f(x) 中，如果 f(x)小于 0 则将 x 的类别赋为-1，如果 f(x)大于 0 则将 x 的类别赋为 1，f(x)=0 就没法分了。下面以二维平面为例阐明 SVM 的原理。不难发现能够实现分类的超平面（二维平面上就是一条直线）会有很多条，如下图 2 所示，如何确定哪个是最优超平面呢？直观而言，最优超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线距直线两边最近数据的间隔最大，也就是“使样本中离超平面最近的点到超平面的距离最远”--最大间隔。所以，得寻找有着“最大间隔”的超平面。下面的问题是--如何求“最大间隔”？

图 2 2，根据几何间隔计算“最大间隔” 2.1 函数间隔对任何一个数据点(x,y)，|wT*x+b|能够表示点 x 到距离超平面 wT*x+b=0 的远近，而 wT*x+b 的符号与类标记 y 的符号是否一致可判断是否分类正确。所以，可用 y(wT*x+b)的正负性判定或表示分类的正确性（为正才正确），引出了函数间隔（functional margin）的概念。定义函数间隔为：而超平面所有样本点(xi，yi)的函数间隔最小值便为超平面关于训练数据集的函数间隔： min i (i=1，...n) 实际上，函数间隔就是几何上点到面的距离公式。回到顶部 2.2 几何间隔假定对于一个点 x ，令其垂直投影到超平面上的对应点为 x0 ，w 是垂直于超平面的一个向量，为样本 x 到分类间隔的距离，如下图所示：

有，||w||=wT*w，是 w 的二阶泛数。又由于 x0 是超平面上的点，满足 f(x0)=0 ，代入超平面的方程即可算出：数据点到超平面的几何间隔定义为：而超平面所有样本点(xi，yi)的几何间隔最小值便为超平面关于训练数据集的函数间隔： min (i=1，...n) 几何间隔就是函数间隔除以||w||，可以理解成函数间隔的归一化。回到顶部 2.3 定义最大间隔分类器 Maximum Margin Classifier 前面已经提到，超平面离数据点的“间隔”越大，分类的确信度（confidence）也越大，为使分类的确信度尽量高，需要选择能最大化这个“间隔”值的超平面，而这个间隔就是最大间隔。

函数间隔不适合用来衡量最大化间隔值，因为超平面固定后通过等比例缩放 w 的长度和 b 的值可使任意大。但几何间隔除了，缩放 w 和 b 的时其值是不会改变的。所以几何间隔只随着超平面的变动而变动，最大间隔分类超平面中的“间隔”用几何间隔来衡量。于是最大间隔分类器（maximum margin classifier）的目标函数可以定义为：（i=1,2,...,n）, 根据前面分析过的，“使样本中离超平面最近的点到超平面的距离最远”，转化成数学表达式就变为条件：根据前面的讨论：即使在超平面固定的情况下，的值也可以随着 ∥w∥的变化而变化。为了简化计算，不妨将固定为 1（实质上就相当于式子两边同除以，则有 wT=wT‘=wT/ ,b=b'=b/ ），于是最大间隔分类器目标函数演化为为：式中，s.t.是 subject to 的意思，它导出的是约束条件。由于求的最大值相当于求（之所以这么转化是为了求解方便，系数 1/2 和平方都是后面为了利用导数求最值方便，并无实质上的含义）的最小值，所以上述目标函数等价于（w 由分母变成分子，从而也有原来的 max 问题变为 min 问题，很明显，两者问题等价）： 3，支持向量(Support Vector)的定义

SVM 叫做支持向量机,讨论了这么久,何谓'支持向量'尚未明了.从下图 3 可以看到两个支撑着中间的间隙的超平面，它们到中间分离超平面的距离(即我们所能得到的最大几何间隔 max( )相等)，而“支撑”这两个超平面的必定会有一些点，而这些“支撑”的点便叫做支持向量。很显然，由于这些支持向量(x,y)刚好在边界上，所以它们满足（前面，函数间隔固定为 1）；而对于所有不是支持向量的点，也就是在“阵地后方”的点，则显然有 y(wTx + b) > 1。事实上，当最优的超平面确定下来之后，这些后方的点就不会对超平面产生任何影响。SVM 这样的特性一个最直接的好处就在于存储和计算上的优越性-只需要存储和计算少量的支持向量点即可完成对新数据的分类判断。例如，如果使用 100 万个点求出一个最优的超平面，其中是 supporting vector 的有 100 个，那么我只需要记住这 100 个点的信息即可，对于后续分类也只需要利用这 100 个点而不是全部 100 万个点来做计算。当然，通常除了 k 近邻之类的“Memory-based Learning”算法，通常算法也都不会直接把所有的点用来做后续推断中的计算。

4，容错松弛因子 Outlier 上述 SVM 超平面的构造过程中并未考虑数据有噪音（即偏离正常位置很远的数据点）的情况，这些点称之为 outlier。在原来的 SVM 模型里，超平面本身就是只有少数几个 support vector 组成的，outlier 的存在有可能造成很大的影响，如果这些 support vector 里又存在 outlier 的话，其影响就很大了。

上图中用黑圈圈起来的那个蓝点是一个 outlier ，它偏离了自己原本所应该在的那个半空间，如果直接忽略掉它的话，原来的分隔超平面还是挺好的，但是由于这个 outlier 的出现，导致分隔超平面不得不被挤歪了，变成途中黑色虚线所示（这只是一个示意图，并没有严格计算精确坐标），同时 margin 也相应变小了。当然，更严重的情况是，如果这个 outlier 再往右上移动一些距离的话，我们将无法构造出能将数据分开的超平面来。为了处理这种情况，SVM 允许数据点在一定程度上偏离一下超平面。例如上图中，黑色实线所对应的距离，就是该 outlier 偏离的距离，如果把它移动回来，就刚好落在原来的超平面上，而不会使得超平面发生变形了。加入松弛因子后，目标函数变为：

资料库

基于SMO的SVM分类器.docx

相关推荐

安全技术

热门标签

最新资料