什么是异常检测?

异常检测(Anomaly Detection)是机器学习里面的一个常见应用,顾名思义,异常检测就是从数据集中检测出异常样本,以下面这个例子开始进入异常检测:

飞机制造商在飞机引擎从生产线上流出时,会考虑进行异常检测,以防止不合格引擎对整机造成的巨大影响,而为了进行异常检测,通常就需要采集一些特征,比如会采集如下特征:

$$x_1 = 引擎运转时产生的热量$$ $$x_2 = 引擎的振荡频率$$

对于一系列的数据集(特征向量集合):$\{x^{(1)},x^{(2)},\cdots,x^{(m)}\}$, 这些数据都是正常样本,我们将其绘制到二维平面上:

飞机引擎数据集

对于新的测试样本$x_{test}$,假如其落到了如下绿色位置,显然,就会被认为是正常样本:

飞机引擎正常样本

而落到了偏离正常样本以外,就会被认为是异常样本:

飞机引擎异常样本

当我们拥有一个数据集$\{x^{(1)},x^{(2)},\cdots,x^{(m)}\}$, 如何判断某测试样本$x_{test}$是否是异常?
通常,我们会根据已知数据集进行建立模型$p(x)$,该模型隔离了正、异常样本,然后如下断言:

$$\begin{equation} x_{test}=\begin{cases} 异常, \mbox{if $p(x_{test})< \epsilon$} \\ 不为异常, \mbox{otherwise} \end{cases}\end{equation}$$

高斯分布(正态分布)与参数估计

高斯分布(正态分布)

从前文内容不难看出,异常检测的关键步骤就在于建立一个能够区别出正、异常样本的模型$p(x)$,而在机器学习中,通常会利用高斯分布(Gaussian distribution)来推导出异常检测算法,下面粗略过一下高斯分布。

我们称$X \sim N(\mu,\delta^2)$为:$X$服从均值为$\mu$,方差为$\delta^2$的高斯分布,也称正态分布,下图展示了一维高斯分布($ p(x;\mu,\delta^2)=\frac{1}{\sqrt{2\pi}\delta}e^{-\frac{(x-\mu)^2}{2}} $):

一维高斯分布

在高斯分布中,参数μ样本均值)决定了分布函数的对称轴,参数σ决定了 分布函数的宽度。服从正态分布的随机变量的概率规律为取与μ邻近的值的概率大,而取离μ越远的值的概率越小;σ越小,分布越集中在μ附近,σ越大,分布越分散:

特殊的一维高斯分布

参数估计(Parameter Estimation)

在推导出最终的异常检测算法前,还有必要了解一下参数估计问题,下面看一下什么是参数估计问题:

假定我们有数据集$\{x^{(1)},x^{(2)},\cdots,x^{(m)}\}$,并且其特征取值分布如下:

参数估计例

观察这样一个分布,我们发现向X轴两边发展,分布渐渐稀疏,故而我猜测这些样本是呈高斯分布 ,即:

$$x^{(i)} \sim N(\mu,\delta^2)$$

并且我估计该分布的两个参数为:

$$\mu=\frac{1}{m}\sum\limits_{i=1}^mx^{(i)}$$ $$\delta^2=\frac{1}{m}\sum\limits_{i=1}^m(x^{(i)}-\mu)^2$$

异常检测算法

有了高斯分布和参数估计的基础,下面概括异常检测算法:

  1. 选择能够标识异常样本的特征$x_i$,并以此构成样本集$\{x^{(1)},x^{(2)},\cdots,x^{(m)}\}$
  2. 假设特征服从高斯分布,对各个特征进行参数估计:
$$\mu_j=\frac{1}{m}\sum\limits_{i=1}^mx_j^{(i)}$$ $$\delta_j^2=\frac{1}{m}\sum\limits_{i=1}^m(x_j^{(i)}-\mu_j)^2$$
  1. 对于一个新的样本$x$,我们这样建立模型$p(x)$
$$p(x)=\prod\limits_{j=1}^np(x_j;\mu_j,\delta_j^2)=\prod\limits_{j=1}^n\frac{1}{\sqrt{2\pi}\delta_j}exp(-\frac{(x_j-\mu_j)^2}{2\delta_j^2})$$

如果$ p(x)<\epsilon $,则样本$x$为异常。

具体看到下面这个例子,该例子中,有两个特征:$x_1$$x_2$,假设他们都服从高斯分布,并且我们通过参数估计获得了$\mu$$\delta$

x1,x2分布

则模型$p(x)$的曲线如下图所示,在当中,$\epsilon$表述了一个截断高度,高度以上为正常样本,高度以下为异常样本,截断曲线(下图紫色线条)投影到$X_1-X_2$平面正好就是划分正、异常样本的分界线:

px曲线

分界线

如何评估异常检测

与有监督学习方法类似,评估异常检测算法的过程如下:

  1. 6:2:2的比例划分数据集为训练集、交叉验证集,测试集,其中,训练集中全为正常样本,亦即,训练集全是无标签数据,而异常样本近似等比例的分布到交叉验证集和测试集中。
  2. 通过训练集构建模型$p(x)$
  3. 对交叉验证集和测试集合的样本$x$进行预测:
$$\begin{equation}y=\begin{cases} 1 & \mbox{if $p(x) < \epsilon$ (anomaly)} \\ 0 & \mbox{if $p(x) \gt \epsilon$ (normal)}\end{cases}\end{equation}$$
  1. 由于异常样本的数量远远小于正常样本的数量,由前文的知识知道,所以该预测是非常偏斜(skewed)的,所以不适用类似“最小均方差”等评估预测准确率的方法来评估算法性能,而应当用概率评估矩阵来进行评估,由前面章节的内容知,概率评估矩阵需要顺序计算以下三部分指标:

    • True Positive, False Positive,False Negative,True Negative
    • Precision/Recall
    • $F_1-score$
  2. 最后,通过交叉验证集来进行参数$\epsilon$调节,优化算法。

异常检测 vs 有监督学习

通常,在如下两种情况下,我们应当选择异常检测算法而不是有监督学习:

  1. 问题是0-1分类问题(正常/异常)
  2. 当异常的数目相较于正常的数目足够少时(0-1二类分布极不平衡)

选取合适的特征标定异常

优化特征分布

我们经常会面临这样一种情况,某个特征并不一定会呈高斯分布,所以,我们可以先通过指数或者对数操作对特征进行预处理,使其分布更接近高斯分布,如下图所示:

优化特征分布

启发性地创建新特征

看到下面这个例子,为了监测机房中的服务器异常状况,我们选定了如下特征:

$$x_1 = 内存使用率$$ $$x_2 = 每秒磁盘访问次数$$ $$x_3 = CPU负载$$ $$x_4 = 网络流量$$

正常情况下,机房中的服务器一般CPU负载和网络流量都比较高,并且,现在我们面临一种新的异常:程序执行时进入了某个死循环,此时CPU的负载很高,而网络流量很低(业务全部卡死在服务器,而没有和客户端通信),要去识别这样一种情况,我们考虑创建如下特征:

$$x_5 = \frac{CPU负载}{网络流量}$$

在上述异常发生时,该特征将会变得异常的大,有助于标识出异常发生。

多元高斯分布(Multivariate Gaussian Distribution)

引子

我们看到下面这样一个网络机房的例子,如下图所示,绿色的样本是一个异常样本(这从道理上也是说得通的,该样本的内存使用率很高,而CPU负载很低,显然不和清理),我们也希望,也感觉正常样本能被如下的蓝色圆圈圈住:

理想圈定

但是,单独考虑两个特征的分布,$p(x_1;\mu_1,\delta_1^2)$$p(x_2;\mu_2\delta_2^2)$ 都会很高,因而,二者的乘积$p(x)$也会很高(很难小于$\mu$),所以绿色标识的样本不会被标识为异常样本:

单独考虑分布

事实上,我们想要的蓝色圈定(想要的$p(x)$)也并没有发生,而是得出了如下圈定情况:

非理想圈定

多元高斯分布

为了解决上述一种情况,我们不再单独考虑各特征的高斯分布,而是直接求取特征向量$x$的多元高斯分布$p(x)$

$$p(x;\mu,\Sigma)=\frac{1}{(2\pi)^{\frac{2}{n}}|\Sigma|^\frac{1}{2}}exp(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu))$$

其中,$\mu$表示均值向量,$\Sigma$表示协方差矩阵

其分布图像如下所示:

多元高斯分布

  • 改变协方差主对角线数值大小可以进行不同方向的宽度拉伸,如下图所示:

改变协方差主对角线

  • 改变协方差次对角线的数值可以旋转分布图像,如下图所示

改变协方差次对角线

改变协方差次对角线--负向

  • 改变均值向量可以对分布图像进行位移:

改变均值向量

参数估计

同样,在多元高斯分布中,我们需要对参数进行估计:

$$\mu=\frac{1}{m}\sum\limits_{i=1}^mx^{(i)}$$ $$\Sigma=\frac{1}{m}\sum\limits_{i=1}^m(x^{(i)}-\mu)(x^{(i)}-\mu)^T$$

多元高斯分布模型与原模型的差异

实际上,原模型只是多元高斯分布模型的一个约束,它将多元高斯分布的等高线约束到了如下所示同轴分布(概率密度的等高线是沿着轴向的):

同轴分布

亦即,原模型无法产生如下所示带角度的高斯分布:

带角度的高斯分布

其次,对于上文提到的网络机房遇到新的异常情况,原模型需要手动构建特征组合,而多元高斯分布则能自动捕获到特征的相关性,避免了人为介入的开销。但原模型并不能因此被打入冷宫,其计算更加迅速,而多元高斯分布模型不仅计算开销大,而且在其算式中,还需要考虑协方差矩阵$\Sigma$是否可逆。

注意,要使得$\Sigma$可逆,需要保证(1)样本数大于特征数($m>n$),(2)不存在冗余特征。