15.异常检测

15 异常检测

15.1 异常检测问题的动机

异常检测算法虽然主要用于无监督学习问题，但从某些角度看，它又类似于一些监督学习问题。

举例：当飞机引擎从生产线上流出时需要进行QA(质量控制测试)，数据集包含引擎的一些特征变量，比如运转时产生的热量，或者振动等。当有一个新的飞机引擎从生产线上流出，它具有特征变量 $x_{test}$ 。异常检测问题就是：希望知道这个新的飞机引擎是否有某种异常。如下图：

训练出的模型，需要能够根据 $x_{test}$ 的位置告诉我们其属于一组数据的可能性 $p(x_{test})$。在下图中，蓝色圈内的数据属于该组数据的可能性较高；而越偏远，属于该组数据的可能性就越低。这种方法称为密度估计，表达式如下：

常见的异常检测问题如下：

例1：欺诈检测，通过 $p(x) < \varepsilon$ 检测非正常用户。例如在线采集而来的有关用户的数据，一个特征向量中可能会包含如:用户多久登录一次，访问过的页面，在论坛发布的帖子数量，甚至是打字速度等。根据这些特征构建一个模型，可以用来识别不符合该模式的用户。
例2：检测一个数据中心，特征可能包含:内存使用情况，被访问的磁盘数量，CPU 的负载，网络的通信量等。根据这些特征构建模型，用来判断某些计算机是否可能出错了。

15.2 高斯分布

高斯分布，也称为正态分布。如果变量 $x$ 符合高斯分布 $x∼N(u,\sigma^2)$ 则其概率密度函数如下 :

高斯分布样例如下图（其中 $u$ 决定中心点的位置， $\sigma^2$ 决定曲线的宽度）：

通过已有数据集 $x$ ，可以预测总体的均值 $u$ 和方差 $\sigma^2$(参数估计) ，计算方法如下：

机器学习中对于方差通常除以 m，而统计学中会除以(m − 1)。这两个公式在理论和数学特性上稍有不同，但在实际使用中的区别几乎可以忽略不计。

15.3 异常检测算法

现在我们应用高斯分布开发异常检测算法。对于给定的数据集 $x$ ，针对每一个特征计算均值 $u$ 和方差 $\sigma^2$ 的估计值。然后，当出现一个新的训练实例，可以根据模型计算其对应的 $p(x)$，这个过程也叫做密度估计(Density estimation)，公式如下:

$p(x)=\prod_{j=1}^{n}{p(x_j;u_j,\sigma_j^2)}=\prod_{j=1}^n\frac{1}{\sqrt{2\pi}\sigma_j}exp(-\frac{(x_j-u_j)^2}{2\sigma_j^2})$

（注：每个特征 $x_i$ 都对应不同的高斯分布）

异常检测算法流程如下：

对于一个新的样本$x$，计算$p(x)$，若$p(x)<\varepsilon$，则判断为异常。

例子：下图中的 2D 图形是一个具有两个特征的训练集及其两个特征的分布情况，3D 图形表示密度估计函数，z轴为根据两个特征对$x_{test}$估计出的$p(x)$值。我们选择一个 $\varepsilon=0.02$，将$p(x) = \varepsilon$作为决策边界，当$p(x) > \varepsilon$时预测为正常数据，否则为异常。

15.4 开发和评价一个异常检测系统

异常检测算法是一个无监督学习算法。但事实上，如果我们拥有一些带标记的数据，为了检验算法是否有效。可以在最开始将其看作一个监督学习算法。将已有数据分开，从中选择一部分正常数据作为训练集，剩下的正常数据和异常数据混合构成交叉检验集和测试集。

例如：有 10000 台正常引擎的数据，有 20 台异常引擎的数据。

我们这样分配数据:

6000 台正常引擎的数据作为Training set；
2000 台正常引擎和 10 台异常引擎的数据作为CV set
2000 台正常引擎和 10 台异常引擎的数据作为Test set

但还有一些人把同样一组数据既用作CV集，也用作Test集。这是不好的做法。

算法流程：

1）根据训练集数据，估计特征的平均值和方差并构建$p(x)$函数
2）对CV set，尝试使用不同的 $\varepsilon$ 值作为阈值，并预测数据是否异常，根据 F1 值或者查准率与查全率的比例来选择 $\varepsilon$
3）选出 $\varepsilon$ 后，针对Test集进行预测，计算异常检验系统的F1值，或者查准率与查全率之比

15.5 异常检测与监督学习对比

之前构建的异常检测系统也使用了带标记的数据，与监督学习有些相似。下面对异常检测和监督学习进行对比:

15.6 选择特征

1.特征转换

特征的选择对异常检测算法至关重要。假设特征不符合高斯分布，算法也能够工作，但最好还是将数据转换成高斯分布，例如：使用对数函数 $x = log(x + c)$，其中 c 为非负常数; 或者 $x = x^c$ ，c 为 0-1 之间的一个分数。

如下图，一些异常的数据可能也会有较高的$p(x)$值，因而被算法认为是正常的。可以使用误差分析帮我们分析是否存在问题。也许从问题样本中发现需要增加一些新的特征$x_2$，增加这些新特征后获得的新算法能够帮助我们更好地进行异常检测。

通常可以通过将一些相关的特征进行组合，来获得一些新的更好的特征(异常数据的该特征值异常地大或小)。例如增加两个特征值的比例。

例如，在检测计算机状况的例子中，可以用 CPU负载与网络通信量的比例作为一个新的特征，如果该值异常地大，便有可能意味着该服务器是陷入了一些问题中(死循环中，CPU负载高，网络通信量低)。如下图：

15.7 多元高斯分布

（1）多元高斯分布的定义

假如我们有两个相关的特征，其值域范围比较宽。一般的高斯分布模型可能不能很好地识别异常数据。其原因在于，一般的高斯分布模型尝试的是去分别抓住两个特征的偏差，得到的判定边界范围比较大。
例如下图中是两个相关特征，粉色的线(根据 $\varepsilon$ 的不同其范围可大可小)是原始高斯分布模型获得的判定边界，绿色的 X 点很可能是异常值，但其$p(x_1)$、$p(x_2)$值却仍然在正常范围内。

如果使用多元高斯分布，获得蓝色曲线所示的判定边界，范围更小，判定结果会更准确。

回顾下一般的高斯分布模型，通过分别计算每个特征对应的几率，将其累乘起来，得到 $p(x)$。

$p(x)=\prod_{j=1}^{n}{p(x_j;u_j,\sigma_j^2)}=\prod_{j=1}^n\frac{1}{\sqrt{2\pi}\sigma_j}exp(-\frac{(x_j-u_j)^2}{2\sigma_j^2})$

而多元高斯分布模型将构建特征的协方差矩阵，使用所有的特征一次性计算出 p(x)。首先，计算所有特征的平均值，然后再计算协方差矩阵:

$u=\frac{1}{m}\sum_{i=1}^{m}x^{(i)}$

$\Sigma=\frac{1}{m}\sum_{i=1}^{m}(x^{(i)}-u)(x^{(i)}-u)^T=\frac{1}{m}(X-u)^T(X-u)$

$p(x)=\frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}}exp(-\frac{1}{2}(x-u)^T\Sigma^{-1}(x-u))$其中： $|\Sigma|$是矩阵$\Sigma$的行列式，在 Matlab 中用det(sigma) 计算； $\Sigma^{-1}$ 是逆矩阵。