万寿路网站建设,企业网上申报入口,如何制作网页电子新年贺卡步骤,百度网站评分话接上文(SVM的简单推导)#xff0c;这篇文章我们来看单类SVM#xff1a;SVDD。可能大家会觉得很奇怪#xff0c;我们为什么需要单分类呢#xff1f;有篇博客举了一个很有意思的例子。花果山上的老猴子#xff0c;一生阅猴无数#xff0c;但是从来没有见过其它的物种。有…话接上文(SVM的简单推导)这篇文章我们来看单类SVMSVDD。可能大家会觉得很奇怪我们为什么需要单分类呢有篇博客举了一个很有意思的例子。花果山上的老猴子一生阅猴无数但是从来没有见过其它的物种。有一天猪八戒来到花果山找它们的大王老猴子一声令下把这个东西给我绑起来这里老猴子很清楚的知道这个外来物种不是同类但是它究竟是什么不得而知。老猴子见过很多猴它知道猴子的特征而外来生物明显不符合这个特征所以它就不是猴子。这就是一个单分类的简单例子。而美猴王看到这个场景后哈哈一笑把这呆子抬过来对比二分类显著的区别就是二分类不但能得出来这个东西不是猴子他还能告诉你这个东西叫“呆子”(当然我们的美猴王见多识广肯定不止是二分类那么简单了)今天要介绍的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,\xi\geq 0.$$我们的目标是最小球的半径$R$和松弛变量的值于是目标函数是$$\begin{align}\min_{a,\xi_i}\ \ R^2C\sum_{i1}^m\xi_i\\{\rm s.t.}\ \ (x^{(i)}-a)^T(x^{(i)}-a)\leq R^2\xi_i, \\\xi_i\geq 0,i1,2,\cdots,m.\end{align}$$其中$C0$是惩罚参数由人工设置。对偶问题使用拉格朗日乘子法得到拉格朗日函数$$\begin{align}L(R,a,\alpha,\xi,\gamma) R^2C\sum_{i1}^m\xi_i\\ -\sum_{i1}^m\alpha_i\left(R^2\xi_i({x^{(i)}}^Tx^{(i)}-2a^Tx^{(i)}a^2)\right)-\sum_{i1}^m \gamma_i\xi_i.\end{align}$$其中$\alpha_i\ge 0,\gamma_i\ge 0$是拉格朗日乘子。令拉格朗日函数对$R,a,\xi_i$的偏导为0得到$$\begin{align}\sum_{i1}^m \alpha_i1,\\a\sum_{i1}^m \alpha_ix^{(i)},\\C-\alpha_i-\gamma_i0\end{align}$$我们可以将$\alpha_i$看作样本$x^{(i)}$的权重。上式表明所有样本的权重之和为1而球心$a$是所有样本的加权和。将上式带入到拉格朗日函数中得到原问题的对偶问题$$\begin{align}\max_\alpha\ \ L(\alpha)\sum_{i1}^m\alpha_i{x^{(i)}}^Tx^{(i)}-\sum_{i1}^m\sum_{j1}^m \alpha_i\alpha_j{x^{(i)}}^Tx^{(j)}\\{\rm s.t.}\ \ 0\le\alpha_i\le C,\\ \sum_{i1}^m\alpha_i1,i1,2,\cdots,m.\end{align}$$当通过求解对偶问题得到$\alpha_i$后可以通过$a\sum_{i1}^m \alpha_ix^{(i)}$计算球心$a$。至于半径$R$则可以通过计算球与支持向量($\alpha_i C$)之间的距离得到。当$\alpha_iC$时意味着样本$x^{(i)}$位于球的外面。判断新样本是否为异常点对于一个新的样本点$z$如果它满足下式那么我们认为它是一个异常点。$$(z-a)^T(z-a) R^2.$$展开上式得$$z^Tz-2\sum_{i1}^m \alpha_iz^Tx^{(i)}\sum_{i1}^m\sum_{j1}^m\alpha_i\alpha_j{x^{(i)}}^Tx^{(j)}R^2.$$引入核函数正常情况下数据并不会呈现球状分布因此有必要使用核函数的方法提高模型的表达能力。只需将$\cal K(x^{(i)},x^{(j)})$替换${x^{(i)}}^Tx^{(j)}$即可。于是对偶问题的目标函数变为$$L(\alpha)\sum_i \alpha_i\cal K(x^{(i)},x^{(i)})-\sum_i\sum_j \alpha_i\alpha_j\cal K(x^{(i)},x^{(j)}).$$判别函数变为$${\cal K}(z,z)-2\sum_i \alpha_i {\cal K}(z,x^{(i)})\sum_i\sum_j \alpha_i\alpha_j {\cal K}(x^{(i)},x^{(j)})- R^2.$$下面考虑核函数的影响。多项式核多项式核函数的表达式如下$${\cal K}\left({x^{(i)}}^Tx^{(j)}\right)\left({x^{(i)}}^Tx^{(j)}1\right)^d.$$如下图所示多项式核实际上不太适合SVDD。特别是当d取值非常大的时候。高斯核高斯核函数的表达式如下$${\cal K}\left({x^{(i)}}^Tx^{(j)}\right)\exp\left(\frac{-\left(x^{(i)}-x^{(j)}\right)^2}{s^2}\right).$$如下图相比于多项式核函数高斯核函数的结果就合理多了。可以看到模型的复杂程度随着$s$的增大而减小。在python中使用可通过下面的代码在python中使用单类SVMfrom 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.
