异常检测（Anomaly Detection）是机器学习算法的一个常见应用。它主要用于非监督学习，但又类似一些监督学习问题。

异常检测常用在对网站异常用户的检测；还有在工程上一些零件，设备异常的检查；还有机房异常机器的监控等等

概念说明

假设有数据集$x^{(1)},x^{(2)},…,x^{(m)}$，当又有一个新的测试样本$x_{test}$；
想要知道这个新样本是否是异常的；
首先对x的分布概率建模p(x) ，用来说明这个例子不是异常的概率；
然后定一个阈值$\epsilon$，当$p(x)<\epsilon$时说明是异常的。

当出现在高概率分布的区域时，说明该例子时正常的；当出现在低概率的区域时，说明是异常的。

高斯分布

高斯分布又被称之为正态分布，曲线呈钟型，两头低，中间高，左右对称因其曲线呈钟形，因此人们又经常称之为钟形曲线

假设x是一个实数随机变量，如果它的概率分布为高斯分布，定义几个变量：
$\mu$=平均值
$\sigma$=标准差
$\sigma^2$=方差
那么x的概率分布可以用公式来表示：
$$x \sim \mathcal{N}(\mu, \sigma^2)$$

其平均值$\mu$决定了其位置，其标准差$σ\sigma$决定了分布的幅度

完整的高斯分布的概率公式为：
$$\large p(x;\mu,\sigma^2) = \dfrac{1}{\sigma\sqrt{(2\pi)}}exp(-\dfrac{1}{2}(\dfrac{x - \mu}{\sigma})^2)$$

当参数平均值$\mu$和标准差$\sigma$变化时：

关于平均值和方差的求解：
$$\mu=\frac{1}{m}\sum_{i=1}^m x^{(i)}, \sigma^2=\frac{1}{m}\sum_{i=1}^m (x^{(i)} - \mu)^2 $$

异常检测算法

在一个异常检测的例子中，有m个训练样本，每个样本的特征值数量有n个，那么某个样本的分布概率模型p(x)就可以用样本的每个特征值的概率分布来计算：
$$p(x) = p(x_1;\mu_1,\sigma_1^2)p(x_2;\mu_2,\sigma^2_2)\cdots p(x_n;\mu_n,\sigma^2_n)$$
上面的式子可以用更简洁的方式来表达
$$p(x) = \displaystyle \prod^n_{j=1} p(x_j;\mu_j,\sigma_j^2)$$

总计一下，异常检测的过程：

  1. 在训练样本中提取觉得可能会导致异常的特征值$x_i$
  2. 计算训练样本的参数$\mu_1,…,\mu_n,\sigma_1^2,…,\sigma_n^2$
    $$\mu_j=\frac{1}{m}\sum_{i=1}^m x_j^{(i)}, \sigma_j^2=\frac{1}{m}\sum_{i=1}^m (x_j^{(i)} - \mu_j)^2 $$
  3. 当有一个新的测试样本$x_{test}$时，计算它的分布概率：
    $$p(x) = \displaystyle \prod^n_{j=1} p(x_j;\mu_j,\sigma_j^2) = \prod\limits^n_{j=1} \dfrac{1}{\sqrt{2\pi}\sigma_j}exp(-\dfrac{(x_j - \mu_j)^2}{2\sigma^2_j})$$
  4. 和阈值ϵ比较，当 p(x)<ϵ 时，则为异常。

评估异常检测算法

如何评估一个异常检测算法，以及如何开发一个关于异常检测的应用：

首先，在获取到的一堆数据中，取一大部分正常的（可能包含少部分异常）的数据用于训练集来训练分布概率公式p(x)。

然后，在交叉验证和测试集中使用包含正常和一定比例异常的数据，来通过查准率和召回率，以及F值公式来评价一个算法。

举个例子

假设有：

  • 10000个正常的样本
  • 20个异常的样本

下面分割一下训练集，交叉验证集和测试集：

  • 训练集：6000个正常的
  • 交叉验证集：2000个正常的+10个异常的
  • 测试集：2000个正常的+10个异常的

在训练集上训练出概率分布函数p(x)
在交叉验证集上，预测y：

$y = \begin{cases} 1 　　 p(x) < \epsilon \\ 0 　　 p(x) \geq \epsilon \end{cases}$

下面通过和真实标签的比较，可以计算出 查准率（Precision）和召回率（Recall），然后通过F值公式来得到一个数值。

我们可以通过改变不同的阈值$\epsilon$从而得到不同的评价系数来选取一个最佳的阈值。
当得到的评价系数不佳时，也可以通过改变特征值的种类和数量来获取理想的评价系数

特征值的选择

在使用异常检测时，对性能影响最大的因素是特征值的选择。

首先要对特征向量使用高斯分布来建模，通常情况下，我们得到的原始数据并没有呈现高斯分布，例如这种：

有几种方法可以实现：

  • log(x)
  • log(x+c)
  • $\sqrt{x}$
  • $x^{\frac{1}{3}}$

通过上述办法，可以将数据转换成高斯分布的形式。

异常检测有点类似监督学习中的二元分类问题。
我们的目标是使得p(x)对于正常的数据来说是大的，而对于异常的数据来说是很小的，而在异常检测中一个常见的问题是最终我们的到的p(x)对于正常和异常的都很大。
在这种情况下需要观察一下交叉验证集中的异常示例，尝试找出能更好区分数据的新特性。

例子

例如，有一个关于机房机器的样本示例，开始收集的样本示例中包含的特征值有关于cpu负载和网络流量的。

cpu负载和网络流量是呈线性关系的，当网络流量变大时，cpu也会相应增大。

现在有一个异常的示例是网络流量不大，cpu确负载很大。假如在只有这两个特征值的情况下运行异常检测算法得出的p(x)，可能就效果不佳。这时可以添加一个特征值，是流量和cpu的比例关系，这样就约束来上述的异常示例，通过这三个特征值得到的异常检测算法可能就会好一点。

异常检测和监督学习的区别

异常检测一般用于：
样本中$y=1$的数量非常少（0-50个），而$y=0$的非常多。这样由于样本数量的过少，达不到良好的训练效果，而在异常检测中确能够表现良好。
还有就是导致$y=1$的情况非常多，且有不可预见性。

监督学习一般用于：
样本中$y=1$和$y=0$的数量都非常多。这样就有足够的样本数量去训练算法。

多元高斯分布（Multivariate Gaussian Distribution）

多元高斯分布是异常检测的一种推广，它可能会检测到更多的异常。

在原始高斯分布中，模型p(x)的搭建是通过分别计算$p(x_1),p(x_2),…,p(x_n)$来完成的，而多元高斯分布则是一步到位，直接计算出模型：
$$p(x;\mu,\Sigma) = \dfrac{1}{(2\pi)^{n/2} |\Sigma|^{1/2}} exp(-1/2(x-\mu)^T\Sigma^{-1}(x-\mu))$$
PS：$\Sigma$是一个协方差矩阵。

通过改变$\mu$和$\Sigma$可以得到不同的多元高斯分布图：

原始高斯分布模型，它的多个特征值之间的关系是轴对齐的（axis-aligned），两个或多个高斯分布之间没有相关性。
而多元高斯分布能够自动捕获x的不同特征之间的相关性。因此它在图像上会现实椭圆或有斜率的椭圆。

在平常的使用中，一般是使用原始高斯分布模型的，因为它的计算成本比较低。
在多元高斯分布中，因为要计算多个特征值之间的相关性，导致计算会慢很多，而且当特征值很多是，协方差矩阵就会很大，计算它的逆矩阵就会花费很多时间。

何时使用多元高斯分布

要保证样本数量m大于特征值数量n，否则协方差矩阵会不可逆；
根据经验法则，当$m>10n$时，多元高斯分布会表现良好。

在原始高斯分布模型中可以手动添加相关性高的特征值之间的关系，可以避免了使用多元高斯分布，减小计算成本。