Part1-异常检测

问题动机

例：假设你是一个飞机引擎制造商，当在生产线上生成飞机引擎时，需要进行质量控制测试，而作为这个测试的一部分，测量了飞机引擎的一些特征变量如：\(x_1\):引擎运转时产生的热量；\(x_2\):振动强度。于是就有了一个数据集：\(\{x^{(1)},x^{(2)},\cdots,x^{(m)} \}\)

如果画图，可能如下：

这样，异常检测问题可以定义如下：

假设有一个新的飞机引擎\(x_{test}\)被生产出来，而所谓的异常检测问题就是我们希望知道这个新的飞机引擎是否有某种异常。

如果更正式的定义异常检测问题，则：

数据集：\(\{x^{(1)},x^{(2)},\cdots,x^{(m)} \}\)

则\(x_{test}\)是异常的么？

通常假定这m个样本都是正常的或者说是非异常的，然后我们需要一个算法来确定新的样本数据是否是异常的。

我们要采用的方法就是给定无标签的训练集，对数据建模得到模型：\(p(x)\)，换句话说，我们将对\(x\)的概率分布建模，则对于一个新的样本，如果\(p(x_{test}) < \epsilon\)，则将其标记为异常，如果\(p(x_{test})\ge \epsilon\)，则将其标记为正常

其它异常检测案例：

欺诈检测：

• \(x^{(i)}\)：用户\(i\)的活动特征
• 从数据中构建模型\(p(x)\)
• 通过检查\(p(x)<\epsilon\)判断用户是否异常

高斯分布

假设\(x\in \mathbb R\)，如果\(x\)服从均值\(\mu\)，方差\(\sigma^2\)的高斯分布 ，记作：\(x\)~$ N(, ^2) $

\(p(x;\mu;\sigma^2)=\frac{1}{\sqrt{2\pi}\sigma}\exp(-\frac{(x-\mu)^2}{2\sigma^2})\)

高斯分布例子

参数估计

数据集：\(\{x^{(1)},x^{(2)},\cdots,x^{(m)} \} x^{(i)} \in \mathbb R\)

参数估计问题就是：假设我们猜测这些样本来自一个高斯分布的总体，假设我们猜测每个样本\(x^{(i)}\)服从某个分布，这里猜测服从高斯分布(正态分布)，它由两个参数(\(\mu\)和\(\sigma^2\))决定，但并不知道这两个参数的值是多少，参数估计问题就是给定数据集，希望找到能估算出\(\mu\)和\(\sigma^2\)的值。

估计\(\mu\)的方法：\(\mu = \frac{1}{m}\sum_{i=1}^m x^{(i)}\)

估计\(\sigma^2\)的方法：\(\sigma^2 = \frac{1}{m}\sum_{i=1}^m(x^{(i)}-\mu)^2\)

异常检测算法

训练集：\(\{x^{(1)},\cdots,x^{(m)} \}\)

每个样本：\(x \in \mathbb R\)

\(\begin{split} 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_n^2) \\ &=\prod_{j=1}^np(x_j;\mu_j,\sigma^2_j) \end{split}\)

整理：

1. 选择认为在异常检测中有用的特征

2. 拟合参数\(\mu1,\cdots,\mu_n,\sigma_1^2,\cdots,\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\)，计算\(p(x)\)：

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

   如果\(p(x) < \epsilon\)为异常

开发和评估异常检测系统

实数评估的重要性

当我们为某个应用开发一个学习算法时，需要进行一系列的选择(如选择使用什么特征等)，如果有某种方法通过返回一个实数，来评估我们的算法，那么对这些选择作出决定往往会容易得多。

假设我们有一些异常的或正常的带标签的数据(如果正常则是\(y=0\)，否则\(y=1\))

训练集：\(x^{(1)},x^{(2)},\cdots,x^{(m)}\)

交叉验证集：\((x_{cv}^{(1)},y_{cv}^{(1)}),\cdots,(x_{cv}^{m_{cv}},y_{cv}^{(m_{cv})})\)

测试集：\((x_{test}^{(1)},y_{test}^{(1)}),\cdots,(x_{test}^{(m_{test})},y_{test}^{(m_{test})})\)

例：以飞机引擎为例，假设有10000个正常的引擎，20个异常的引擎

划分：

​ 训练集：6000个正常引擎

​ 交叉验证集：2000个正常引擎(y=0)，10个异常的(y=1)

​ 测试集：2000个正常引擎(y=0)，10个异常的(y=1)

算法评估

• 在训练集\(\{x^{(1)},\cdots,x^{(m)}\}\)上拟合模型\(p(x)\)
• 在交叉验证集或测试集上，预测\(\left\{ \begin{split} &1，如果p(x) < \epsilon(异常) \\ &0，如果p(x) \ge \epsilon(正常\end{split} \right.\)
• 可能的评估度量
  • 真阳性，假阳性，假阴性，真阴性
  • 查准率/召回率
  • \(F_1\)值
• 也可以使用交叉验证集来选择参数\(\epsilon\)
  • 选择能使\(F_1\)值最大的\(\epsilon\)

异常检测 VS. 监督学习

异常检测	监督学习
非常少的异常样本，而正常样本很多	非常多的正负样本
经常有许多不同类型的异常，则对于算法来说就很难去从小数量的异常样本中去学习异常是什么，尤其是未来可能出现的异常，看起来可能会与已有的截然不同	有足够的异常样本，或是一个已经能识别异常样本的算法，未来出现的异常可能与训练集中的某个异常样本类似
如：欺诈检测、制造业、数据中心的机器监视	如：垃圾邮件分类、天气预测、肿瘤分类

选择要使用的特征

如图，如果将对应特征画图，得出的直方图，符合高斯分布，则显然可以将其作为特征进行尝试：

如果数据画出来，看上去不像一条钟型曲线，通常可以对数据进行一些不同的特征转换\(如z = \log(x)\)，使得它看上去更接近高斯分布，虽然即使不这样做，算法也能运行，但如果这样转换了，那么算法可能可以运行得更好

异常检测的误差分析

首先完整地训练一个算法，然后在一组交叉验证集上运行算法，然后找出那些预测错的样本，并观察能否找到一些其它特征来帮助学习算法，让那些在交叉验证集中判断出错的样本表现更好。

即在异常检测中，我们希望：

\(p(x)\)在正常样本的情况下比较大；在异常样本的情况下比较小

常见问题：

如果\(p(x)\)是可比较的，当样本正常或异常时，\(p(x)\)都比较大

数据中心计算机监控案例

通常选择那些既不会特别大，也不会特别小的特征

以监控数据中心计算机为例：

\(x_1:\)计算机内存使用

\(x_2\)：可使用硬盘数

\(x_3\)：CPU负载

\(x_4\)：网络流量

假设有一台计算机运行到一个死循环卡住了，导致CPU负载升高但网络流量没有升高，在这种情况下，要检测出异常，可以建立一个新特征\(x_5 = \frac{x_3}{x_4}\)，这样如果有一台计算机CPU负载高而网络流量正常就会让\(x_5\)的值非常大

多变量高斯分布

还是以数据中心计算机监控为例：

如果将这两个特征变量\(x_1\)和\(x_2\)当做高斯分布来建模，如果用高斯分布来拟合，则结果如图中右部分

然后，对于测试集中的一个样本，假设其对应的\(x_1\approx 0.4,x_2 \approx 1.5\)，从图中左部分的数据分布看，这个测试样本应该是异常的，而在异常检测算法来看，对于\(x_1\)和\(x_2\)分别代入图中右部分，会发现其对应的纵坐标都相对并不大也不是太小，所以\(p(x_1)\)，\(p(x_2)\)也会不大不小，因此，这个点看上去并不是属于异常的，所以这时，异常检测算法并不能正确预测。

为了解决上述问题，我们需要使用一种改良的异常检测算法，要用到多元高斯分布

多元高斯分布(多元正态分布)

\(x\in \mathbb R^n\)，不要分别为\(p(x_1),p(x_2),\cdots\)分别建模，而是建立一个整体的\(p(x)\)模型

多元高斯分布的参数是：\(\mu\in \mathbb R^n,\Sigma \in \mathbb R^{n\times n}(协方差矩阵)\) \[ p(x;\mu,\Sigma)=\frac{1}{(2\pi)^{n/2}|\Sigma|^{\frac{1}{2}}} \exp(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)) \\ (|\Sigma|:\Sigma的行列式) \] 例：

使用多元高斯分布进行异常检测

参数：\(\mu,\Sigma\)

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

参数拟合：

给定训练集：\(\{x^{(1)},x^{(2)},\cdots,x^{(m)} \}\)

\(\mu = \frac{1}{m} \sum_{i=1}^mx^{(i)}\)

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

多元高斯分布异常检测

1. 拟合模型，通过上述\(\mu\)和\(\Sigma\)的计算公式
2. 给定一个新的样本\(x\)，计算\(p(x)\)，如果\(p(x) < \epsilon\)，则对应标记为异常

多元高斯分布模型和原始模型的关系

原始模型：\(p(x) = p(x_1;\mu_1,\sigma_1^2)\times p(x_2;\mu_2,\sigma_2^2)\times \cdots \times p(x_n;\mu_n,\sigma_n^2)\)

如图，其轮廓都轴对称的

对比多元高斯模型：\(p(x;\mu,\Sigma)=\frac{1}{(2\pi)^{n/2}|\Sigma|^{\frac{1}{2}}} \exp(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu))\)

而多元高斯模型则对应的轮框可以是非轴对称的，通过数据证明，其实可以发现原始模型实际上就是某种特殊情形下的多元高斯分布

这一特殊情形其实就是当多元高斯模型的\(\Sigma\)在非对角线上都是0时，即\(\Sigma = \left[ \begin{matrix} \sigma_1^2 & 0 & 0& 0 \\ 0 & \sigma_2^2 & 0 & 0 \\ 0 & 0 & \cdots & 0 \\ 0 & 0 & 0& \sigma_n^2 \end{matrix} \right]\)

原始模型和多元高斯模型对比

原始模型	多元高斯模型
\(p(x) = p(x_1;\mu_1,\sigma_1^2)\times p(x_2;\mu_2,\sigma_2^2)\times \cdots \times p(x_n;\mu_n,\sigma_n^2)\)	\(p(x;\mu,\Sigma)=\frac{1}{(2\pi)^{n/2}|\Sigma|^{\frac{1}{2}}} \exp(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu))\)
当有一些特征\(x_1,x_2\)等，想通过异常的组合值来捕捉异常样本，需要创建一个额外的特征	能自动捕捉这种不同特征之间的关系
计算成本低(适应巨大规模的特征)	计算成本高
当训练样本数少时可以使用	样本数量必须大于特征数量(实际应用中，应该m >> n)，否则\(\Sigma\)是不可逆

注：如果\(\Sigma\)是不可逆的，则可能存在以下两种情况：

1. 没有满足 m > n
2. 存在冗余特征(特征相同或特征存在线性相关)