图解机器学习/第十二章 异常检测

异常检测，是指找出给定的输入样本$\lbrace x_i \rbrace_{i=1}^n$中包含的异常值的问题。

局部异常因子

局部异常因子，是指对偏离大部分数据的异常数据进行检测的方法。

从$x$到$x’$的可达距离

$$RD_k(x,x')=max(||x-x^{(k)}||,||x-x'||)$$

$x^{(k)}$表示的是训练样本$\lbrace x_i \rbrace_{i=1}^n$中距离$x$第$k$近的样本。

$x$的局部可达密度可由下式加以定义

$$LRD-k(x) = (\frac{1}{k} \sum_{i=1}^k RD_k(x^{(i)},x))^{-1}$$

$x$的局部可达密度，是从$x^{(i)}$到$x$的可达距离的平均值的倒数。

$x$的局部异常因子

$$LOF_k(x) = \frac{ \frac{1}{k} \sum_{i=1}^k LRD_k(x^{(i)})}{LRD_k(x)}$$

$LOF_k(x)$的值越大，$x$的异常度就越大。$LOF_k(x)$是$x^{(i)}$的局部可达密度的平均值和$x$的局部可达密度的比。当$x^{(i)}$的周围的密度比较高而$x$周围的密度比较低的时候，局部异常因子就比较大，$x$就会被看作是异常值。

局部异常因子，是遵循事先制定的规则(偏离大部分正常值的数据被认为是异常值)，寻找异常值的无监督的异常检测算法。

支持向量机异常检测

支持向量机异常检测器会求出几乎包含所有训练样本$\lbrace x_i \rbrace_{i=1}^n$的超球，并将没有包含在超球内的训练样本看作是异常值。

具体而言，就是通过求解下述的最优化问题来求得超球的球心$c$和半径$R$

$$\mathop{min}_{c,R,\xi}[R^2+C\sum_{i=1}^n\xi_i] \\ 约束条件 ||x_i-c||^2 \le R^2+\xi_i,\xi_i \ge0 对于i=1,\dots,n$$

这样就变成了支持向量机分类器类似的最优化问题。

基于密度比的异常检测

由于无监督学习的异常检测中完全没有与异常值相关的信息，因此要想进行理想的异常检测是很困难的。异常值各式各样，对其进行模型化一般是比较困难的，而正常值则相对比较稳定，因此通过把非正常的数据看作是异常数据的方法，有望实现高精度的异常检测。

已知是正常值的样本$\lbrace x’_{i’} \rbrace_{i’=1}^{n’}$的概率密度$p’(x)$，测试样本$\lbrace x_i \rbrace_{i=1}^n$的概率密度值$\lbrace p’(x_i) \rbrace_{i=1}^n$就可以看作是正常度。当概率密度函数$p’(x)$的值较小的时候需要较高精度的估计，但是因为概率密度很低的时候数据基本上是没有的，所以想要进行高精度的估计往往是比较困难的。

因此，一般通过计算正常样本的概率密度$p’(x)$和测试样本的概率密度$p(x)$的比值

$$w(x) = \frac{p'(x)}{p(x)}$$

这样的密度比$w(x)$，对于正常样本会输出接近1的值，对于异常样本则会输出和1相差较大的值。因为密度比函数对异常值的变化较为明显，因此使用密度比可以很容易地进行异常值的检测。

如果密度比分母很小，则分子值得误差会相应地增加。利用KL散度密度比估计法可以不计算概率密度而直接进行密度比估计。

KL散度密度比估计法的算法流程：

1. 给$\alpha$以适当的初值
2. 直到解$\alpha$达到收敛精度为止，重复以下的参数更新计算
   1. $\alpha \leftarrow \alpha+ \epsilon A^{\intercal}(1./A\alpha)$
   2. $\alpha \leftarrow \alpha + (1-b^{\intercal}\alpha)b/(b^{\intercal}b)$
   3. $\alpha \leftarrow max(0,\alpha)$
   4. $\alpha \leftarrow \alpha/(b^{\intercal}\alpha)$

$\epsilon$为表示梯度上升幅度的正常数。$A$是第$(i’,j)$个元素为$\psi_j(x’_{j’})$的矩阵，1为所有元素为1的向量，“./”表示对各个元素进行除法运算，0为所有元素为0的向量，b为第$j$个元素为$\frac{1}{n}\sum_{i=1}^n \psi_j(x_i)$的向量。另外，向量的max运算表示对各个单独元素进行max运算。步骤2.1为梯度上升，2.2到2.4分别与满足约束条件的各个正交投影矩阵相对应。