SVDD：支持向量数据描述

背景

支持向量数据描述（Support Vector Data Description，SVDD）是一种单值分类算法，能够实现目标样本和非目标样本的区分，通常应用于异常检测、入侵检测等领域。

SVDD 算法的具体描述可以参考文献：

@article{tax2004support,
  title={Support vector data description},
  author={Tax, David MJ and Duin, Robert PW},
  journal={Machine learning},
  volume={54},
  number={1},
  pages={45--66},
  year={2004},
  publisher={Springer}
}

Python 实现参考: https://github.com/iqiukp/SVDD.

SVDD 原理

假设有一组正类训练数据 $x\in R^{n\times d}$ ，其中 $n$ 是样本个数， $d$ 是特征维度。首先通过非线性变换函数 $\Phi: x\rightarrow F$ 将数据从原始空间映射到特征空间，然后在特征空间中寻找一个体积最小的超球体。为了构造这样一个最小体积超球体，SVDD要解决以下优化问题：

$\min _{\mathbf{a}, R, \xi} R^{2}+C \sum_{i=1}^{n} \xi_{i} \\ \text { s.t. } \quad\left\|\Phi\left(\mathbf{x}_{i}\right)-\mathbf{a}\right\|^{2} \leq R^{2}+\xi_{i}, \xi_{i} \geq 0, \forall i=1,2, \cdots, n$

式中， $R$ 是超球体半径， $\mathbf{a}$ 是超球体的球心， $\xi_{i}$ 是松弛因子， $C$ 是一个权衡超球体体积和误分率的惩罚参数。

结合拉格朗日乘子法，原问题的对偶问题为：

$\min _{\alpha_{i}} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)-\sum_{i=1}^{n} \alpha_{i} K\left(\mathbf{x}_{i}, \mathbf{x}_{i}\right) \\ \text { s.t. } \quad 0 \leq \alpha_{i} \leq C, \quad \sum_{i=1}^{n} \alpha_{i}=1$

其中 $\alpha_{i}$ 是样本 $\mathbf{x}_i$ 对应的拉格朗日系数。求解该对偶问题后，可以获取所有样本对应的拉格朗日系数。

在所有训练样本中，把拉格朗日系数满足 $0 <\alpha_i <C$ 的样本称为支持向量，假设训练数据集中属于支持向量的样本集合为 $\mathbf{SV}$ ,那么超球体的球心和半径的计算公式分别为：

$\mathbf{a}=\sum_{i=1}^{n} \alpha_{i} \Phi\left(\mathbf{x}_{i}\right) \\ R=\sqrt{K\left(\mathbf{x}_{v}, \mathbf{x}_{v}\right)-2 \sum_{i=1}^{n} \alpha_{i} K\left(\mathbf{x}_{v}, \mathbf{x}_{i}\right)+\sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)}$

其中 $\mathbf{v}\in \mathbf{SV}$ ， $K(\mathbf{x}_i, \mathbf{x}_j)$ 是核函数，等于特征空间样本的内积 $K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)=\left\langle\Phi\left(\mathbf{x}_{i}\right), \Phi\left(\mathbf{x}_{j}\right)\right\rangle$ 。

对于测试样本 $\mathbf{x}_{test}$ ，其到超球体球心的距离为

$d=\sqrt{K\left(\mathbf{x}_{\text {test }}, \mathbf{x}_{\text {test }}\right)-2 \sum_{i=1}^{n} \alpha_{i} K\left(\mathbf{x}_{\text {test }}, \mathbf{x}_{i}\right)+\sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)}$

若 $d\leq R$ ，说明测试样本在超球体上或者内部，属于正常样本；反之则属于异常样本。

此外，可以在正类训练集中加入少数的负类样本来防止过拟合情况。假设训练集中正样本和负样本的标签分别为 $y_i=+1$ 和 $y_i=-1$ ，则原优化问题的对偶问题变为

$\min _{\alpha_{i}} \sum_{i=1}^{n} \sum_{j=1}^{n} y_{i} y_{j} \alpha_{i} \alpha_{j} K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)-\sum_{i=1}^{n} y_{i} \alpha_{i} K\left(\mathbf{x}_{i}, \mathbf{x}_{i}\right) \\ \text { s.t. } \quad \sum_{i=1}^{n} y_{i} \alpha_{i}=1 \\ 0 \leq \alpha_{i} \leq C_{1}, y_{i}=+1 \\ 0 \leq \alpha_{i} \leq C_{2}, y_{i}=-1$

超球体的球心和半径的计算公式分别为

$\mathbf{a}=\sum_{i=1}^{n} y_{i} \alpha_{i} \Phi\left(\mathbf{x}_{i}\right) \\ R=\sqrt{K\left(\mathbf{x}_{v}, \mathbf{x}_{v}\right)-2 \sum_{i=1}^{n} y_{i} \alpha_{i} K\left(\mathbf{x}_{v}, \mathbf{x}_{i}\right)+\sum_{i=1}^{n} \sum_{j=1}^{n} y_{i} y_{j} \alpha_{i} \alpha_{j} K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)}$

测试样本 $\mathbf{x}_{test}$ 到超球体球心的距离为

$d=\sqrt{K\left(\mathbf{x}_{\text {test }}, \mathbf{x}_{\text {test }}\right)-2 \sum_{i=1}^{n} y_{i} \alpha_{i} K\left(\mathbf{x}_{\text {test }}, \mathbf{x}_{i}\right)+\sum_{i=1}^{n} \sum_{j=1}^{n} y_{i} y_{j} \alpha_{i} \alpha_{j} K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)}$