摘要：话接上文的简单推导，这篇文章我们来看单类。单分类方法常用于异常检测，或者类别极度不平衡的分类任务中。另一种思路就是，在样本空间中为此类数据划定一个大致的边界。上式表明所有样本的权重之和为，而球心是所有样本的加权和。
话接上文(SVM的简单推导)，这篇文章我们来看单类SVM：SVDD。可能大家会觉得很奇怪，我们为什么需要单分类呢？有篇博客举了一个很有意思的例子。
花果山上的老猴子，一生阅猴无数，但是从来没有见过其它的物种。有一天，猪八戒来到花果山找它们的大王，老猴子一声令下，把这个东西给我绑起来！这里老猴子很清楚的知道这个外来物种不是同类，但是它究竟是什么，不得而知。老猴子见过很多猴，它知道猴子的特征，而外来生物明显不符合这个特征，所以它就不是猴子。
这就是一个单分类的简单例子。
而美猴王看到这个场景后，哈哈一笑，把这呆子抬过来！
对比二分类，显著的区别就是，二分类不但能得出来这个东西不是猴子，他还能告诉你这个东西叫“呆子”（当然我们的美猴王见多识广，肯定不止是二分类那么简单了）
今天要介绍的SVDD的全称是Support vector domain description。首先让我们简单了解一下domain description，也就是单分类问题。
单分类问题不像常见的分类问题，单分类问题的目的并不时将不同类别的数据区分开来，而是对某个类别的数据生成一个描述（description）。这里的description比较抽象，可以理解为是样本空间中的一个区域，当某个样本落在这个区域外，我们就认为该样本不属于这个类别。
单分类方法常用于异常检测，或者类别极度不平衡的分类任务中。
当我们假设数据服从一个概率分布，我们就可以对这个分布中的参数进行估计了。对于一个新样本，如果这个样本在给定类别的概率分布中的概率小于阈值，就会被判定为异常样本。
但是这样的方法存在的问题是，
预先假定的概率分布对模型性能的影响很大。
当特征的维度很大的时候，该方法需要一个很大的数据集。
一些低密度区域的样本点会被误判为异常样本。
另一种思路就是，在样本空间中为此类数据划定一个大致的边界。如何划定这个边界，就是SVDD要研究的问题啦。
目标函数假设我们有$m$个样本点，分别为$x^{(1)},x^{(2)},cdots,x^{(m)}$。
我们假设这些样本点分布在一个球心为$a$，半径为$R$的球中。那么样本$x^{(i)}$满足
$$ (x^{(i)}-a)^T(x^{(i)}-a)leq R^2. $$
引入松弛变量，我们允许部分样本不再这个球中，那么
$$ (x^{(i)}-a)^T(x^{(i)}-a)leq R^2+xi_i,xigeq 0. $$
我们的目标是最小球的半径$R$和松弛变量的值，于是目标函数是
$$ egin{align} min_{a,xi_i} & R^2+Csum_{i=1}^mxi_i { m s.t.} & (x^{(i)}-a)^T(x^{(i)}-a)leq R^2+xi_i, &xi_igeq 0,i=1,2,cdots,m. end{align} $$
其中，$C>0$是惩罚参数，由人工设置。
对偶问题使用拉格朗日乘子法，得到拉格朗日函数
$$ egin{align} L(R,a,alpha,xi,gamma)=& R^2+Csum_{i=1}^mxi_i & -sum_{i=1}^malpha_ileft(R^2+xi_i({x^{(i)}}^Tx^{(i)}-2a^Tx^{(i)}+a^2) ight)-sum_{i=1}^m gamma_ixi_i. end{align} $$
其中，$alpha_ige 0,gamma_ige 0$是拉格朗日乘子。令拉格朗日函数对$R,a,xi_i$的偏导为0，得到
$$ egin{align} &sum_{i=1}^m alpha_i=1, &a=sum_{i=1}^m alpha_ix^{(i)}, &C-alpha_i-gamma_i=0 end{align} $$
我们可以将$alpha_i$看作样本$x^{(i)}$的权重。上式表明所有样本的权重之和为1，而球心$a$是所有样本的加权和。将上式带入到拉格朗日函数中，得到原问题的对偶问题
$$ egin{align} max_alpha &L(alpha)=sum_{i=1}^malpha_i{x^{(i)}}^Tx^{(i)}-sum_{i=1}^msum_{j=1}^m alpha_ialpha_j{x^{(i)}}^Tx^{(j)} { m s.t.} & 0lealpha_ile C, & sum_{i=1}^malpha_i=1,i=1,2,cdots,m. end{align} $$
当通过求解对偶问题得到$alpha_i$后，可以通过$a=sum_{i=1}^m alpha_ix^{(i)}$计算球心$a$。至于半径$R$，则可以通过计算球与支持向量（$alpha_i< C$）之间的距离得到。当$alpha_i=C$时，意味着样本$x^{(i)}$位于球的外面。
判断新样本是否为异常点对于一个新的样本点$z$，如果它满足下式，那么我们认为它是一个异常点。
$$ (z-a)^T(z-a)> R^2. $$
展开上式，得
$$ z^Tz-2sum_{i=1}^m alpha_iz^Tx^{(i)}+sum_{i=1}^msum_{j=1}^malpha_ialpha_j{x^{(i)}}^Tx^{(j)}>R^2. $$
引入核函数正常情况下，数据并不会呈现球状分布，因此有必要使用核函数的方法提高模型的表达能力。
只需将$cal K(x^{(i)},x^{(j)})$替换${x^{(i)}}^Tx^{(j)}$即可。于是对偶问题的目标函数变为
$$ L(alpha)=sum_i alpha_ical K(x^{(i)},x^{(i)})-sum_isum_j alpha_ialpha_jcal K(x^{(i)},x^{(j)}). $$
判别函数变为
$$ {cal K}(z,z)-2sum_i alpha_i {cal K}(z,x^{(i)})+sum_isum_j alpha_ialpha_j {cal K}(x^{(i)},x^{(j)})- R^2. $$
下面考虑核函数的影响。
多项式核
多项式核函数的表达式如下
$$ {cal K}left({x^{(i)}}^Tx^{(j)} ight)=left({x^{(i)}}^Tx^{(j)}+1 ight)^d. $$
如下图所示，多项式核实际上不太适合SVDD。特别是当d取值非常大的时候。
高斯核
高斯核函数的表达式如下
$$ {cal K}left({x^{(i)}}^Tx^{(j)} ight)=expleft(frac{-left(x^{(i)}-x^{(j)} ight)^2}{s^2} ight). $$
如下图，相比于多项式核函数，高斯核函数的结果就合理多了。可以看到模型的复杂程度随着$s$的增大而减小。
在python中使用可通过下面的代码在python中使用单类SVM
from sklearn.svm import OneClassSVM参考文献
Tax D M J, Duin R P W. Support vector domain description[J]. Pattern recognition letters, 1999, 20(11-13): 1191-1199.
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/43793.html
摘要：基于机器学习的异常检测防火墙是信息安全的第一道防线。然而，机器学习应用于入侵检测也存在挑战，其中最大的困难就是标签数据的缺乏。本文管中窥豹式的介绍了机器学习用于异常检测的几个思路。 基于机器学习的web异常检测 Web防火墙是信息安全的第一道防线。随着网络技术的快速更新，新的黑客技术也层出不穷，为传统规则防火墙带来了挑战。传统web入侵检测技术通过维护规则集对入侵访问进行拦截。一方面，...
摘要：很显然，上面目标函数中最重要的常亮是矩阵，既训练样本的，满足先看好的一方面，根据核函数的定义，能够保证是一个正定的矩阵。的目标函数与的分类模型稍有区别。 模型与优化 LIBSVM和LIBLINEAR都提供了多种不同的模型供使用者选择，不同的模型有各自适用的场景。下面分别介绍LIBSVM和LIBLINEAR所提供的各种模型。 LIBSVM 下面是LIBSVM帮助内容提供的介绍，给出了LI...
摘要：支持向量机的目标非常简单，找到一条直线划分两个类别，并让种类别之间保持了一条尽可能宽敞的街道图中平行的虚线，其被称为最大间隔分类。 支持向量机 SVM的目标非常简单，找到一条直线划分两个类别，并让种类别之间保持了一条尽可能宽敞的街道（图中平行的虚线），其被称为最大间隔分类。我们注意到添加更多的样本点在街道外并不会影响到判定边界，因为判定边界是由位于街道边缘的样本点确定的，这些样本点被称...
摘要：本文转自由于作者不明，未能附上其姓名，深表歉意。然而神经网络也有一个致命的弱点，由于模型本身的局限性，非常容易过拟合，尤其是在训练样本量较少的情况下。之所以效果好，主要是得益于非线性核函数的引入。 本文转自：http://orangeprince.info/2014/11/22/libs... 由于作者不明，未能附上其姓名，深表歉意。由于原文网站并不稳定，借此机会进行转载，希望优秀的文...
摘要：全系列目录小白学系列教程一间隔小白学系列教程二向量小白学系列教程三最优超平面介绍这是我写的背后的数学原理系列文章的第一篇。什么是间隔和它是如何帮助选择最优超平面我们的最优超平面的间隔给定一个超平面，我们能够计算出超平面到最近的一个点的距离。 英文原文链接：SVM - Understanding the math - Part 1 - The margin 译者注：本人研一，项目原因需要...
阅读 1348·2023-04-26 02:08
阅读 2930·2021-10-14 09:42
阅读 6272·2021-09-22 15:34
阅读 3126·2019-08-30 13:16
阅读 2578·2019-08-26 13:49
阅读 1251·2019-08-26 11:59
阅读 1121·2019-08-26 10:31
阅读 2035·2019-08-23 17:19
