Press "Enter" to skip to content

单类SVM:SVDD

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

话接上文( SVM的简单推导 ),这篇文章我们来看单类SVM:。可能大家会觉得很奇怪,我们为什幺需要单分类呢? 有篇博客 举了一个很有意思的例子。

 

花果山上的老猴子,一生阅猴无数,但是从来没有见过其它的物种。有一天,猪八戒来到花果山找它们的大王,老猴子一声令下,把这个东西给我绑起来!

 

这里老猴子很清楚的知道这个外来物种不是同类,但是它究竟是什幺,不得而知。老猴子见过很多猴,它知道猴子的特征,而外来生物明显不符合这个特征,所以它就不是猴子。

 

这就是一个单分类的简单例子。

 

而美猴王看到这个场景后,哈哈一笑,把这呆子抬过来!

 

对比二分类,显着的区别就是,二分类不但能得出来这个东西不是猴子,他还能告诉你这个东西叫“呆子”(当然我们的美猴王见多识广,肯定不止是二分类那幺简单了)

 

今天要介绍的SVDD的全称是Support vector domain description。首先让我们简单了解一下domain description,也就是单分类问题。

 

单分类问题

 

不像常见的分类问题,单分类问题的目的并不时将不同类别的数据区分开来,而是对某个类别的数据生成一个描述(description)。这里的description比较抽象,可以理解为是样本空间中的一个区域,当某个样本落在这个区域外,我们就认为该样本不属于这个类别。

 

 

单分类方法常用于异常检测,或者类别极度不平衡的分类任务中。

 

当我们假设数据服从一个概率分布,我们就可以对这个分布中的参数进行估计了。对于一个新样本,如果这个样本在给定类别的概率分布中的概率小于阈值,就会被判定为异常样本。

 

但是这样的方法存在的问题是,

 

 

    1. 预先假定的概率分布对模型性能的影响很大。

 

    1. 当特征的维度很大的时候,该方法需要一个很大的数据集。

 

    1. 一些低密度区域的样本点会被误判为异常样本。

 

 

另一种思路就是,在样本空间中为此类数据划定一个大致的边界。如何划定这个边界,就是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^2+C\sum_{i=1}^m\xi_i\\ {\rm s.t.}\ \ & (x^{(i)}-a)^T(x^{(i)}-a)\leq R^2+\xi_i, \\ &\xi_i\geq 0,i=1,2,\cdots,m. \end{align} $$

 

其中,$C>0$是惩罚参数,由人工设置。

 

对偶问题

 

使用拉格朗日乘子法,得到拉格朗日函数

 

$$ \begin{align} L(R,a,\alpha,\xi,\gamma)=& R^2+C\sum_{i=1}^m\xi_i\\ & -\sum_{i=1}^m\alpha_i\left(R^2+\xi_i({x^{(i)}}^Tx^{(i)}-2a^Tx^{(i)}+a^2)\right)-\sum_{i=1}^m \gamma_i\xi_i. \end{align} $$

 

其中,$\alpha_i\ge 0,\gamma_i\ge 0$是拉格朗日乘子。令拉格朗日函数对$R,a,\xi_i$的偏导为0,得到

 

$$ \begin{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$是所有样本的加权和。将上式带入到拉格朗日函数中,得到原问题的对偶问题

 

$$ \begin{align} \max_\alpha\ \ &L(\alpha)=\sum_{i=1}^m\alpha_i{x^{(i)}}^Tx^{(i)}-\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_j{x^{(i)}}^Tx^{(j)}\\ {\rm s.t.}\ \ & 0\le\alpha_i\le C,\\ & \sum_{i=1}^m\alpha_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-2\sum_{i=1}^m \alpha_iz^Tx^{(i)}+\sum_{i=1}^m\sum_{j=1}^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中使用单类SVM

 

from sklearn. import OneClassSVM

 

参考文献

 

 

    1. Tax D M J, Duin R P W. Support vector domain description[J]. Pattern recognition letters, 1999, 20(11-13): 1191-1199.

 

Be First to Comment

发表评论

邮箱地址不会被公开。 必填项已用*标注