话接上文 (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,\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.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.