异常检测

2019-05-27 本文已影响0人此间不留白

问题引入

假设给定一组训练数据： $\{x_1,x_2,……x_m \}$ 表示飞机发动机的参数，需要检测飞机发动机状态是否正常，可以通过构建一个关于变量 $x$ 的概率模型 $p(x)$ 来验证测试数据是否满足 $p(x) < \epsilon$ ,若成立，则是异常数据。异常检测的应用非常普遍，如检测网站用户行为是否构成欺诈，数据中心监控等等。

算法原理

高斯分布

概述
高斯分布，又称正态分布，一个变量用 $X$ 服从高斯分布，可以用如下式子表示：
$X ～N(\mu,\sigma)$ , $\mu$ 表示均值。而 $\sigma$ 表示其标准差，高斯分布的计算公式如下所示：

$p(x;\mu,\sigma) = \frac{1}{\sqrt{2\pi \sigma}}exp(-\frac{(x-\mu)^2}{2\sigma^2})$
其图像如下所示：

参数估计
假设给定一组数据集 $X$ 服从高斯分布，对高斯分布中的参数 $\mu$ 和 $\sigma$ 进行估计，有如下公式：

$\mu = \frac{1}{m}\sum_{i=1}^{m}x_i$ ， $\sigma^2 = \frac{1}{m}\sum_{i=1}^{m}(x_i-\mu)^2$

有了以上参数，可以得到关于数据集 $X$ 的高斯分布公式和图像。以上参数估计的公式其实就是对 $\mu$ 和 $\sigma^2$ 的极大似然估计。

注意：在数学表达中， $\sigma^2$ 的估计常写作 $\frac{1}{m-1}\sum_{i=1}^{m}(x_i-\mu)^2$ ，但是机器学习中，这两者区别并不大，因为机器学习中涉及到的数据集包含着极大量的样本。

算法原理
异常检测算法可以用以下步骤来完成

选择样本的特征变量 $x_i$
根据选定的样本，利用以下下公式拟合高斯分布参数：
$\mu_j = \frac{1}{m}\sum_{i=1}^{m}x_j^{(i)}$

$\sigma^2_j = \frac{1}{m}\sum_{i=1}^{m}(x_j^{(i)}-\mu)^2$

给定特征变量 $x$ ,利用以下公式计算概率 $p(x)$ :

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

判断 $p(x) < \epsilon$ ,则说明是异常样本。

注意： $x_j^{(i)}$ 表示第 $i$ 个样本的第 $j$ 个特征。而 $m$ 表示样本数量， $n$ 表示一个样本的特征变量个数。

异常检测算法的评估

对于给定的数据集，利用异常检测算法评估数据的步骤通常如下所示：

给定数据集 $\{x_1,x_2,x_3……x_m\}$ ，拟合函数 $p(x)$
利用交叉验证集或者测试集，预测 $y$ 的输出，如下所示：
$y = \begin{cases} 0 \ \ \ \ if \ \ \ p(x) \ge \ \ \epsilon\\ 1 \ \ \ \ if \ \ \ p(x) < \epsilon \end{cases}$

监督学习与异常检测

通过以上分析，异常检测与监督学习算法具有很高的相似性，在算法实际应用中，异常检测与监督学习的应用主要区别如下所示:

异常检测	监督学习
正样本数量很少，负样本比例较高	正样本和负样本数量接近
异常样本的种类较多，很难利用正样本训练算法	足够多的正样本训练算法
异常样本的特征相差较大	正样本的特征和训练集中的某一类样本非常相似

多变量高斯分布

概述

对于多维变量 $x \in R^n$ ，不需要为每一个变量 $x$ 建立模型 $p(x_1),p(x_2)……$ ，而是建立一个整体的模型 $p(x)$
其参数 $\mu \in R^n$ ，协方差矩阵 $A \in R^{n*n}$ ,其公式如下所示：

$p(x;\mu,A) = \frac{1}{(2 \pi)^{\frac{n}{2}}|A|^{\frac{1}{2}}}exp(-\frac{1}{2}{(x-\mu)}^TA^{-1}(x- \mu))$

其中 $|A|$ 表示矩阵 $A$ 的行列式.一个典型的二维变量的高斯分布图像如下所示：

使用多元高斯分布

以上，给出了多元高斯分布的计算公式，对于 $m$ 个训练样本 $\{x^{(1)},,x^{(2)}……x^{(m)} \}$ ，其高斯分布的使用如下步骤所示：

如下所示，使用训练集拟合参数

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

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

给定新样本，通过以下公式计算 $p(x)$
$p(x;\mu,A) = \frac{1}{(2 \pi)^{\frac{n}{2}}|A|^{\frac{1}{2}}}exp(-\frac{1}{2}{(x-\mu)}^TA^{-1}(x- \mu))$
判断 $p(x) \ge \epsilon \$ 数据正常，否则，数据异常

原始模型与多元高斯模型

多元变量的原始高斯模型可以用以下公式表示：
$p(x) = p(x_1;\mu_1,\sigma_1^2)×p(x_2;\mu_2,\sigma_2^2)×……×p(x_n;\mu_n,\sigma_n^2)$

当协方差矩阵 $A$ 只有主对角线存在元素时,原始模型与高斯模型相等价。

原始模型和多元高斯模型的使用主要有以下原则:

原始模型	多元高斯模型
通过异常值的组合手动创建新的特征捕捉异常，如新变量可以由 $x_3 = \frac{x_2}{x_1}得到$	自动捕捉异常值
计算成本更低，适合计算大规模数据 $n > 10000$	计算成本较高
训练样本 $m$ 的值较小	一般来说 $m>n$ （工程上要求 $m \ge 10*n$ ）,且协方差矩阵 $A$ 不可逆