本章主要介绍异常检测（Anomaly detection）问题，这是机器学习算法的一个常见应用。这种算法的有趣之处在于，它虽然主要用于非监督学习问题，但从某些角度看，它又类似于一些监督学习问题。

Problem motivation

主要介绍了什么是异常检测，以及其应用。

Anomaly detection example

下面通过一个例子介绍什么是异常检测。

假如我们测量了飞机引擎的一些特征值，E.g.heat和vibration等等，接着我们将\(m\)个引擎的数据集绘制成图表如下所示。

假设我们现在有一个新的引擎\(x_{test}\)，我们希望检测出这个引擎是否异常，或者说判断这个引擎是否需要进一步测试，这就是所谓的异常检测问题。

Density estimation

给定一组数据集\(\{x^{(1)},x^{(2)}, \cdots, x^{(m)}\}\)，我们可以拟合出概率密度模型\(p(x)\)，对于任意一个输入数据\(x\)，概率密度模型\(p(x)\)能够告诉我们其出现的可能性如何。我们可以其出现的概率与某一个概率值\(\epsilon\)进行对比，假如大于这个概率，我们可以认为其是正常的，反之则是不正常的，这种方法称为密度估计。

\[\begin{cases} p(x) \lt \epsilon &{anomaly} \\ p(x) \ge \epsilon &{normal} \end{cases} \]

Anomaly detection example

异常检测的常见应用：

Gaussian distribution

本节课介绍了高斯分布（Gaussian distribution），也称为正态分布（Normal distribution）。

Gaussian (Normal) distribution

如果\(x \in \R\)服从均值为\(\mu\)，方差为\(\sigma^2\)的高斯分布，记做\(x \sim N(\mu, \sigma^2)\)。则其概率密度函数为：

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

说明：

• \(\sigma\)称为标准差。
• \(\sim\)表示服从于（distributed as）。

离中心点\(\mu\)越近的\(x\)概率越大，反之越远则越小。

Gaussian distribution example

高斯分布样例：

参数\(\mu\)控制着函数最高点（中心点）的位置，\(\sigma\)控制着函数的“胖瘦”，\(\sigma\)越大，函数“越胖”，而由于概率密度函数积分为1，也就意味着函数“越矮”。

Parameter estimation

所谓的参数估计，指的是在已经有数据集\(\{x^{(1)},x^{(2)}, \cdots, x^{(m)}\}\)的情况下，预测出其所属的高斯分布，也就是预测出\(\mu\)和\(\sigma^2\)。估计方法如下：

\[\mu = \frac{1}{m} \sum_{i=1}^m x^{(i)} \\ \sigma^2 = \frac{1}{m} \sum_{i=1}^m (x^{(i)} -\mu)^2 \]

注：在机器学习中方差通常只除以\(m\)而非统计学中的\((m-1)\)，在实际使用中，只要数据集还算大，那么其实两者区别不大。

Algorithm

主要讲解如何将高斯分布应用在异常检测问题中。

Density estimation

对于给定的m个训练集\(\{x^{(1)},x^{(2)}, \cdots, x^{(m)}\}\)，其中每个数据都是n维向量，即\(x \in \R^n\)。我们假设每个特征值都符合高斯分布\(x_j \sim N(\mu_j, \sigma^2_j)\)，那么可以估算概率分布为：

\[\begin{aligned} p(x) &= p(x_1;\mu_1,\sigma_1^2) p(x_2;\mu_2,\sigma_2^2) \cdots p(x_m;\mu_m,\sigma_m^2) \\ &= \prod_{j=1}^m p(x_j;\mu_j,\sigma_j^2) \end{aligned} \]

说明：在统计学中需要各个特征之间相互独立，但是这个算法即使不满足该条件也是可以的。

Anomaly detection algorithm

异常检测算法的计算流程如下：

Anomaly detection example

下面以一个例子走一遍异常检测算法的整个流程。

1.假设我们的数据集如下图的红色点所示，要检测的两个数据为绿色点：

2.根据数据集我们拟合出特征值\(x_1\)和\(x_2\)分别服从以下分布：

3.计算出概率密度函数\(p(x)\)图像如下：

我们令\(\epsilon=0.02\)，计算\(p(x_{text}^{(1)}) = 0.0426 \ge \epsilon\)，因此\(x_{text}^{(1)}\)点正常；而\(p(x_{text}^{(2)}) = 0.0021 \lt \epsilon\)，因此\(x_{text}^{(2)}\)点异常。

Developing and evaluating an anomaly detection system

本节课主要讲解开发一个异常检测系统的一些细节，特别是如何评估一个异常检测系统。

The importance of real-number evaluation

在开发一个学习算法时（比如选择特征值等），如果我们有办法评估我们的学习算法，那么时有利于我们作出选择的。

假设我们拥有一些带标签的数据，\(y=1\)表示正常，\(y=0\)表示异常，那么我们通常会划分数据集如下：

• 训练集：\(x^{(1)},x^{(2)}, \cdots, x^{(m)}\)，都是没有标签的数据（假设都是正常的，即使厘米有少数异常数据也没事）。
• 交叉验证集：\((x_{cv}^{(1)},y_{cv}^{(1)}), (x_{cv}^{(2)},y_{cv}^{(2)}), \cdots , (x_{cv}^{(m_{cv})},y_{cv}^{(m_{cv})})\)。
• 测试集：\((x_{test}^{(1)},y_{test}^{(1)}), (x_{test}^{(2)},y_{test}^{(2)}), \cdots , (x_{test}^{(m_{test})},y_{test}^{(m_{test})})\)。

Aircraft engines motivating example

以之前讲解过的飞机引擎异常检测问题为例，我们拥有以下数据集：

• 10000 good (normal) engines
• 20 flawed engines (anomalous)

那么可以划分数据集如下：

• Training set: 6000 good engines
• CV: 2000 good engines (\(y=1\)), 10 anomalous (\(y=0\))
• Test: 2000 good engines (\(y=1\)), 10 anomalous (\(y=0\))

常见的错误划分方式如下（把交叉验证集的数据和测试集的数据混用）：

• Training set: 6000 good engines
• CV: 4000 good engines (\(y=1\)), 10 anomalous (\(y=0\))
• Test: 4000 good engines (\(y=1\)), 10 anomalous (\(y=0\))

Algorithm evaluation

算法评估方法如下：

1. 使用训练集拟合模型\(p(x)\)。
2. 使用交叉验证集选择参数\(\epsilon\)（可以通过评估指标进行评估）。
3. 使用测试集进行算法评估，异常检测问题类似于之前监督学习中的斜偏类问题，因此我们可以采用的评估参数有：
   • True positive, false positive, false negative, true negative
   • Precision/Recall
   • F1-score

Anomaly detection vs. supervised learning

主要介绍了异常检测和监督学习分别适用于什么场景，以及一些常见的应用。

我们在构建异常检测系统的时候也使用了带标签的数据，与监督学习有些相似。

下面对两者进行对比，有助于我们选择采用监督学习还是异常检测：

Anomaly detection	Supervised learning
Very small number of positive examples (y=1). (0-20 is common).
Large number of negative (y=0) examples.	Large number of positive and negative examples.
Many different “types” of anomalies. Hard for any algorithm to learn from positive examples what the anomalies look like; future anomalies may look nothing like any of the anomalous examples we’ve seen so far.	Enough positive examples for algorithm to get a sense of what positive examples are like, future positive examples likely to be similar to ones in training set.
常见应用：Fraud detection / Manufacturing (e.g. aircraft engines) / Monitoring machines in a data center	常见应用：Email spam classification / Weather prediction (sunny/rainy/etc) / Cancer classification

总结起来就是正样本的数量太少，甚至为0的时候，即有太多么见过的异常类型，那么通常应该使用的就是异常检测算法。

Choosing what features to use

本节课主要讲解如何选择特征。

Non-gaussian features

在把数据输入异常检测算法之间，通常会绘制直方图，看数据的分布是否为高斯分布，如果数据不符合高斯分布，异常检测算法也能够工作，但是将数据转换成高斯分布也许会得到更好的结果。

E.g. 下面种情况通常就会采用对数函数对数据进行转换，将数据转成符合高斯分布的新的特征值。

注：在Pyhton中通常使用np.log1p()函数，也就是\(\log(x+1)\)，可以避免出现负数结果，反向函数是np.exmp1()。

Error analysis for anomaly detection

我们希望对于正常的样本\(x\)会得到较大的\(p(x)\)，对于异常的样本\(x\)会得到较小的\(p(x)\)。然而一个常见的问题就是，对于正常和异常的样本都得到一个较大的\(p(x)\)。

E.g. 下图左图所示绿色异常点，其概率值\(p(x)\)依然较大，就会被异常检测算法错误预测为正常数据。这时我们可以寻找是否有新的特征值，如右图所示新增了特征值\(x_2\)，就会发现在特征值\(x_2\)的这个维度上，绿色异常点的概率值\(p(x)\)是非常小的，异常检测算法能将其正确预测为异常数据。

Monitoring computers in a data center

我们也可以选择在异常发生的情况下非常大或非常小的特征值。

以计算机异常检测为例，有以下特征值：

• \(x_1\) = memory use of computer
• \(x_2\) = number of disk accesses/sec
• \(x_3\) = CPU load
• \(x_4\) = network traffic

假如我们的计算机是作为Web服务器使用，那么正常情况下CPU load和network traffic应该是成正比的，这种时候我们就可以定义一个新的特征值\(x_5 = \frac{CPU \space load}{network \space traffic}\)，假如突然出现了\(x_5\)非常大的情况，那么我们基本上就可以判定计算机出现异常。

Multivariate Gaussian distribution

本节课讲解了多元高斯分布中的二元高斯分布。

Motivating example: Monitoring machines in a data center

以数据中心的机器异常检测为例。

假如我们有两个特征值分别是\(x_1,x_2\)，绿色异常点在左图中的位置如下。如果我们分别对\(x_1,x_2\)求解高斯分布并计算绿色异常点的\(p(x_1),p(x_1)\)，那么结果就是两个概率值都较大，异常检测算会把绿色异常点预测为正常。

分别对\(x_1\)和\(x_2\)求解高斯分布，我们得到的正常范围应该是如左图所示的红色圆形，而我们想要得到的应该是蓝色椭圆形，所以我们需要采用多元高斯分布。

Multivariate Gaussian (Normal) distribution

\(x \in \R^n\)，我们不应该对分别建模\(p(x_1),p(x_2), \cdots\)，而是统一建模为\(p(x)\)。

参数：\(\mu \in \R^n\)，\(\Sigma \in \R^{n \times n}\)（covariance matrix，协方差矩阵）

\[\begin{aligned} p(x) &= \prod_{j=1}^n p(x_j;\mu,\sigma_j^2) \\ &= \prod_{j=1}^n \frac{1}{\sqrt{2 \pi \sigma_j}} \exp(-\frac{(x_j-\mu_j)^2}{2\sigma_j^2}) \\ &= \frac{1}{(2\pi)^{\frac{n}{2}} |\Sigma|^{\frac{1}{2}}} \exp (-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)) \end{aligned} \]

注：\(|\Sigma|\)为\(\Sigma\)的行列式。

Multivariate Gaussian (Normal) examples

下面我们看一下参数\(\mu\)和协方差矩阵\(\Sigma\)是如何影响模型的。

等比例缩小/放大特征1和特征2的范围：

只缩小/放大特征1的范围：

只缩小/放大特征2的范围：

改变正常范围的倾斜角度：

改变倾斜的方向：

改变峰值位置：

Anomaly detection using the multivariate Gaussian distribution

主要讲解如何应用多元高斯分布在异常检测问题，以及多元高斯分布和高斯分布的对比。

Multivariate Gaussian (Normal) distribution

我们前面已经得到了多元高斯分布的表达式为：

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

那么和高斯分布一样，我们接下来要做的就是拟合参数\(\mu\)和\(\Sigma\)：

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

Anomaly detection with the multivariate Gaussian

总结起来，多元高斯分布的异常检测问题步骤如下：

1. 拟合模型\(p(x)\)的参数\(\mu,\Sigma\)；
2. 对于新的样例，计算概率\(p(x)\)和\(\epsilon\)进行对比。

Relationship to original model

原始模型的图形是绝对关于坐标轴对称的，也就是说原始模型实际上就是多元高斯分布的一种特殊情况，当多元高斯分布的\(\Sigma\)除了斜对角线所有元素都为0的时候，就变成了原始模型。

Original model vs. Multivariate Gaussian

Original model	Multivariate Gaussian
\(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)\)	$p(x;\mu,\sigma^2) = \frac{1}{(2\pi)^{\frac{n}{2}}
Manually create features to capture anomalies where \(x_1,x_2\) take unusual combinations of values.	Automatically captures correlations between features.
Computationally cheaper (alternatively, scales better to large )	Computationally more expensive.
OK even if \(m\) (training set size) is small	Must have \(m \gt n\) , or else \(\Sigma\) is non-invertible.

注：

• 更常用的还是原始模型；
• 如果在应用多元高斯分布时发生了\(\Sigma\)不可逆的情况，那么通常可能是没有满足\(m \gt n\)或者出现了冗余特征值。