异常检测(Anomaly detection)

假设我们有数据集{ $x^{(1)},x^{(2)},……,x^{(m)}$ },其中每个样本都有两个特征值 $(x_1,x_2)$ ，将其画在平面坐标系中得到如下结果。假设数据集是正常的，那么我们所得到的模型能根据新数据 $x_{test}$ 的位置告诉我们其属于原数据的可能性 $p(x)$ ，如果 $p(x)>\xi$ ，则我们认为该数据正常，否则数据异常。

高斯分布

高斯分布，也称正态分布。如果 $x$ 符合高斯分布 $x~N(\mu,\sigma^2)$ ，则其概率密度函数为：
$p(x,\mu,\sigma^2)= \frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(x-\mu)^2}{2\sigma^2})$
其中 $\mu,\sigma^2$ 可以利用已知数据集{ $x^{(1)},x^{(2)},……,x^{(m)}$ }进行估算:
$\mu = \frac{1}{m}\sum_{i=1}^{m}x^{(i)} \qquad \sigma^2= \frac{1}{m}\sum_{i=1}^{m}(x^{(i)} -\mu)^2$
高斯分布样例：

异常检测算法

本节利用高斯分布进行异常检测算法的推导。
首先，对于给定数据集{ $x^{(1)},x^{(2)},……,x^{(m)}$ }，针对每个特征计算 $\mu,\sigma^2$ ：
$\mu_j = \frac{1}{m}\sum_{i=1}^{m}x_j^{(i)} \qquad \sigma_j^2= \frac{1}{m}\sum_{i=1}^{m}(x_j^{(i)} -\mu_j)^2$
在得到 $\mu_j,\sigma_j^2$ 的估计值之后，一旦给定一个新的样本实例 $xtest$ ，根据模型即可计算 $p(x)$ ：
$p(x)=\prod_{j=1}^{n}p(xtest_j;\mu_j,\sigma_j^2)=\prod_{j=1}^{n} \frac{1}{\sqrt{2\pi}\sigma_j} exp(-\frac{(xtest_j-\mu_j)^2}{2\sigma_j^2})$
计算结果后，若 $p(x)>\xi$ ，则样本正常，否则异常。

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

到目前为止，我们都把异常检测看做一个非监督学习算法，这种方法意味着我们无法根据结果 y来告诉我们检测是否正确。当我们开发一个异常检测系统时，如果我们从带标记（异常y=1或正常y=0）的数据着手，既可以从其中选择一部分正常数据用于构建训练集，然后用剩下的正常数据和异常数据混合的数据构成交叉检验集和测试集。
假设我们有10000个正常数据x，20个异常数据z，则可以这样分配：

训练集：{ $x^{(1)},x^{(2)},……,x^{(6000)}$ }
交叉验证集：{ $x^{(1)},x^{(2)},……,x^{(2000)},z^{(1)},z^{(2)},……,z^{(10)}$ }
测试集：{ $x^{(1)},x^{(2)},……,x^{(2000)},z^{(1)},z^{(2)},……,z^{(10)}$ }

系统的推导和评估如下：

使用训练集拟合模型 $p(x)$ ，即是把6000个样本都用高斯函数来拟合；
对于交叉验证集，尝试使用不同 $\xi$ 值作为阈值，并对数据进行预测，根据以下指标选择最合适的 $\xi$
- 计算True positive、false positive、false negative、true negative的比例
- 计算出算法的精确率和召回率
- 计算出F1-score，来总结和反映精确率和召回率
选出 $\xi$ 后，针对测试集进行预测，计算异常检验系统的F1值，进行评价

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

异常检测	监督学习
非常少量的正向类（异常数据y=1）,大量的负向类（正常数据y=0），甚至只有负向类	同时有大量的正向类和负向类
异常数据有很多不同种类，很难根据非常少的异常数据来训练算法	有足够多的正向类数据，可以用来训练算法
未来遇到的异常数据可能和已掌握的异常完全不同	未来可能出现的正样本与当前训练集中的正样本类似
欺诈行为检测；生产（例如飞机引擎）；检测数据中心的计算机运行状况	邮件过滤器；天气预报；肿瘤分类

特征的选择

对于异常检测算法，特征的选择是极其重要的。
首先数据特征最好符合高斯分布，如果不符合，最好通过转化使其符合高斯分布，比如 $log(x),log(x+c),\sqrt{x},x^{\frac{1}{3}}$ 等，如下图所示。然后将转化后的结果作为特征。

有时不管样本异常与否， $p(x)$ 值都比较大，如下左图所示，此时算法会认为该数据为正常。通过分析被算法错误判断的数据，看是否能得到新的特征x2来帮助算法更好的进行异常检测。通过特征x2，使得数据能够像下右图一样显示出来，发现异常数据处于外层，从而更容易将异常样本从正常的样本中区分出来。

我们还可以通过将一些相关的特征进行组合，来获得一些新的更好的特征（异常数据的该特征值异常地大或小），例如，在检测数据中心的计算机状况的例子中，我们有四个特征：x1：内存使用量； x2：磁盘的容量；x3：CPU的负载程度；x4：网络流量，我们可以用CPU负载与网络通信量的比例作为一个新的特征x5，如果该值异常地大，便有可能意味着该服务器是陷入了一些问题中，算法便可以捕捉到这一异常值。

多元高斯分布及其应用

假设有两个相关的特征，而且特征的值域范围很大，如下图所示。此时异常检测检测的范围是红色圆圈，即中间的概率最大，而图中的绿色点明显为异常值，其原因在于一般的高斯分布尝试去同时抓住两个特征的偏差，因此有一个比较大的判定边界。而蓝色椭圆为多元高斯分布所判定的边界。在多元高斯分布模型中，我们构建特征的协方差矩阵，用所有的特征一起来计算 $p(x)$ 。

首先我们先计算所有特征的平均值及协方差矩阵：
$\mu = \frac{1}{m}\sum_{i=1}^{m}x^{(i)} \qquad \Sigma = \frac{1}{m}\sum_{i=1}^m(x^{(i)}-\mu)(x^{(i)}-\mu)^T=\frac{1}{m}(X-\mu)^T(X-\mu)$
其中 $\mu_{(m,1)}$ 是一个向量，表示每个特征的均值， $X_{(m,n)}$ 表示整个数据集。
然后计算多元高斯分布的 $p(x)$ :
$p(x)= \frac{1}{(2\pi)^{\frac{\pi}{2}}|\Sigma|^{\frac{1}{2}}} exp (-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu))$

上图为五个不同的高斯模型，从左向右依次为不同的协方差矩阵对模型带来的影响：

一般的原始高斯分布模型
通过协方差矩阵，x1有较小的偏差，x2不变
通过协方差矩阵，x2有较大的偏差，x1不变
通过协方差矩阵增加了两者的正相关性
通过协方差矩阵增加了两者的负相关性

很明显，原本的高斯模型是多元高斯模型的一个特殊情况，原高斯模型的协方差矩阵为一个对角单位矩阵（如上图第一），他们之间的对比如下：

原高斯模型	多元高斯模型
不能捕捉特征之间的相关性，需要手动创建新特征，如x1/x2	可以自动捕捉特征之间的相关性
计算成本低可以进行大规模运算	成本高，能适应的n值范围小
即使有一个较小的有一定相关性的训练集，也能顺利运行	必须m>n，不然协方差矩阵不可逆的，通常需要m>10n；另外特征冗余（比如存在两个相同特征，或者两特征间存在线性关系）也会导致矩阵不可逆

【吴恩达机器学习】第9周 异常检测(Anomaly detection)&推荐系统

文章目录