异常检测
是无监督学习的一种方法。已知一系列正常样本{$x^{(1)},x^{(2)},\cdots,x^{(m)}$}，其中$x^{(i)}\in \mathbb{R^n}$，即每个样本拥有n个特征。对比判断引入的一个新样本$x_{test}$是否存在某种异常。
应用场景有：
- 用户检测：不寻常的客户
- 生产检测：是否为次品
- 集群控制：集群计算机是否存在异常个体
通过分布密度估计
定义如果$x_{test}$落在的区域的概率$p(x_{test})$小于某个阈值$\epsilon$，则认定为异常样本，否则认定为正常样本。这其实是很数学直观的一个定义手段。
高斯分布
高斯分布即为$X\sim N(\mu.\sigma^2)$，$\mu$为样本分布的均值，$\sigma$为样本分布的标准差，不同的$\mu$与$\sigma$值会使得分布函数的图像不同。
参数估计
$\mu$的估计公式是样本的均值
$$\mu=\frac{1}{m}\sum_{i=1}^mx^{(i)}$$
$\sigma^2$的估计公式是平方差公式
$$\sigma^2=\frac{1}{m}\sum_{i=1}^m(x^{(i)}-\mu)^2$$
注：如果使用极大似然法估计，得到的$\sigma^2$的估计公式中的坟墓为m-1，但机器学习中常用m。
算法
选择能够指示异常样本的特征$x_i$
拟合每个特征对应的参数$\mu_1,\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$
对于给定新的样本$x_{test}$，计算$p(x_{test})$。如果$p(x_{test})<\epsilon$，则认定为异常样本。
$p(x_{test})=\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_j^2})$
例子
给定一个特征维度为二的数据集，样本分布如图所示：
已知$x_1\sim N(\mu_1.\sigma_1^2),x_2\sim N(\mu_2.\sigma_2^2)$，其中$\mu_1=5,\sigma_1=2,\mu_2=3,\sigma_2=1$，故$x_1,x_2$的分布函数图像如下：
设定$\epsilon=0.02$，计算得出$p(x_{test}^{(1)})=0.0426\geq\epsilon,p(x_{test}^{(2)})=0.0021<\epsilon$。
特征选择
异常检测需要的特征需要接近高斯分布，如果不是高斯分布，可以采取多种手段变为高斯分布。常用的方法有取对数、指数等。
$x_1$<–$log(x_1)$
$x_2$<–$log(x_2+1)$
$x_3$<–$\sqrt{x_3}$
$x_4$<–${x_4}^{\frac{1}{3}}$
同时我们希望选择的特征能够使得$p(x_+)>>p(x-)$，即正样本的概率远大于负样本的概率，而常见情况是正负样本概率相同，所以解决方法是从单个特征出发，不断扩展新的特征来满足条件$p(x_+)>>p(x-)$。
注意：将符合高斯分布的特征组合（加减乘除）后仍为高斯分布。
例子：监测数据中心机群
选择哪些极有可能或极不可能造成异常的特征。如：
- $x_1$=计算机的内存使用量
- $x_2$=磁盘每秒访问次数
- $x_3$=CPU加载量
- $x_4$=网络负载
而$x_5=\frac{x_3}{x_4}$与$x_6=\frac{(x_3)^2}{x_4}$j均服从正态分布。
多元正态分布
多元正态分布主要解决在相同同心圆内异常等级不同的样本点。例如下图分布：
正常样本的$x_1$与$x_2$特征虽然都是正态分布，但组合起来却不是圆形，难以使用之前的各特征概率相乘的方法，所以要用到多元正态分布。
多元正态分布的理念是：对于一个样本点$x\in \mathbb{R}^n$，不单独对$p(x_1),p(x_2),…，etc.$单独建模，而是用$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|^{1/2}}exp(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu))$$
例子
接下来以二元正态分布为例，取不同的$\mu$和$\Sigma$，看下概率密度函数的模样。
$\mu$代表各特征分布的均值，$\Sigma$的对角元元素代表了分布的方差。
$\mu=[0,,0]^T$代表均值为0，发现对焦圆越大，分布方差越大。
$\Sigma$正对角元的大小影响图的椭圆形态
$\Sigma$的斜对角元非零代表这两个特征具有相关性
$\mu$的取值影响分布中心离原点的偏离程度
算法
预测公式为式(3)，所以只需要拟合两个参数$\mu,\Sigma$，则模型训练完毕。
给定训练集{$x^{(1)},x^{(2)},…,x^{(m)}$}，算法如下：
- 拟合模型$p(x;\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$$
- 对于新的样本点$x$，计算
$$p(x;\mu,\Sigma)=\frac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}}exp(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu))$$
如果$p(x)<\epsilon$，则为异常样本。
正态分布与多元正态分布的区别
正态分布是多元正态分布的特例，其中$\Sigma$的对角元为$\sigma_i^2$。即
$$
\Sigma=\left[
\begin{matrix}
\sigma_1^2&0&0&0\
0&\sigma_2^2&0&0\
0&0&\ddots&0\
0&0&…&\sigma_n^2
\end{matrix}
\right]
$$
| 原始高斯模型 | 多元高斯模型 | |
|---|---|---|
| 手工选择特征 | 自动选择特征 | |
| 计算速度快，样本量大时有优势 | 计算复杂度高 | |
| 训练集很小时也可完成训练 | 训练样本必须大于特征数 |
当使用多元高斯分布时，求解出$\Sigma$矩阵是奇异(不可逆)矩阵，原因往往是m不满足m>n的条件，即有冗余特征。
开发和评估异常检测的应用
半监督学习：数据集标注不完全，通过这些数据进行学习和应用。
例子：
- 10000个正常的飞机引擎(y=0)
- 20个次品引擎(y=1)
划分数据集
- Training Set： 6000个好引擎
- CV： 2000个好引擎，10个坏引擎
- Test： 2000个好引擎，10个坏引擎
另外的选择
- Training Set： 6000个好引擎
- CV： 4000个好引擎，10个坏引擎
- Test： 4000个好引擎，10个坏引擎
从样本分布可以看出，正负样本比例失调，accuracy不正常，所以不能用accuracy作为评判学习优劣的标准，可能的评估手段有：
- True positive, False positive, False negative, True negative
- Precision/Recall
- $F_1-score$
在交叉验证集上，对于测试样本$x$，预测
$$\begin{equation}
y=\left{
\begin{aligned}
1 & &if \ p(x)<\epsilon(anomaly) \
0 & &if \ p(x)\geq\epsilon(normal)
\end{aligned}
\right.
\end{equation}$$
通过交叉验证集选择使误差最小的$epsilon$，以此最大化$F_1-score$ 。
异常检测 vs 监督学习
训练对比
| 异常检测 | 监督学习 |
|---|---|
| 面对的情形是少量的正样本，大量的负样本。 | 适用的情形是同时需要大量的正负样本。 |
| 部分正样本具有突发性，不具有稳定的特征，所以在训练过程中Guass函数只需拟合负样本就好。 | 足够多的正样本让学习算法能够知道正样本的特征，待预测的正样本也具有和已知正样本类似的特征。 |
应用对比
| 异常检测 | 监督学习 |
|---|---|
| * 欺诈识别 * 生产制造（飞机引擎） * 机器监督（集群中心的计算机异常检测） |
* 钓鱼邮件分类 * 天气预报 * 癌症识别 |