异常检测

简介

异常检测的基本思想：若发生了小概率事件，就认为出现了异常。

常用的异常检测方法是利用高斯密度函数，计算数据出现的概率，如果发现了概率小于某个阈值的数据，就认为该数据是异常的。

异常检测也是一种模式二分类方法，但两类数据严重不平衡，异常数据要显著少于正常数据。异常检测通常只需要对正常数据进行建模。

异常检测还可以用于数据清洗或剪枝，减少过拟合提升性能。

基于高斯（正态）分布的异常检测

本节的主要内容来自Andrew NG的机器学习课程[1]。

根据异常检测的思想，若$\mathbf x$出现的概率$p(\mathbf x) < \varepsilon$，则认为$\mathbf x$是异常点。因此，异常检测的重要内容是估计概率密度函数。

一元高斯分布

基于一元高斯分布的异常检测的前提条件是假设特征之间相互独立。

通常假设特征分量的数据集$X$满足均值为$\mu$，方差为$\sigma^2$的正态分布， \begin{equation} X\sim\mathcal{N}\left(\mu, \sigma^2\right)， \end{equation} 因此有 \begin{equation} p(x;\mu,\sigma^2)=\frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)， \end{equation} 这需要估计均值$\mu$和方差$\sigma^2$，它们的极大似然估计为 \begin{equation} \begin{aligned} \mu = & {1\over m}\sum_{i=1}^{m}x^{(i)}\\ \sigma^2 = & {1\over m}\sum_{i=1}^{m}\left(x^{(i)}-\mu\right)^2 \end{aligned}。 \label{eq:likehood-mu-sigma} \end{equation}

得到了概率密度函数，就容易利用概率判断异常。

一、异常检测

####异常检测算法

1. 选择能指示异常的特征$\mathbf x_j$；
2. 利用公式\eqref{eq:likehood-mu-sigma}，估计每维特征的均值和方差$\mu_1,\ldots,\mu_n,\sigma_1^2,\ldots,\sigma_n^2$；
3. 计算$\mathbf x$的概率， \begin{equation} p(\mathbf x) = \prod_{j=1}^n p\left(x_j;\mu_j,\sigma_j^2\right)， \end{equation} 通过特征分量概率密度函数乘积计算$\mathbf x$概率密度，需满足特征之间相互独立的假设；
4. 若$p(\mathbf x) < \varepsilon$，则$\mathbf x$为异常点。

异常检测的训练过程就是估计概率密度函数参数$\boldsymbol\mu$和$\boldsymbol\sigma^2$。通常情况，训练过程不需要异常数据。$60\%$的正常数据作为训练集，$20\%$的正常数据和$50\%$的异常数据作为交叉检验集，$20\%$的正常数据和$50\%$的异常数据作为测试集。

通过交叉检验集可确定判定异常的阈值$\varepsilon$，选择参数可利用分类器性能评价指标。

异常检测和监督学习存在不同的特点，应用在不同的场景：

二、特征变换

根据异常检测方法可知，运用异常检测有两个重要的前提条件：

1. 特征满足高斯分布（特征之间的相关性下节考虑）；
2. $p(\mathbf x)$对正常数据很大，但对异常数据很小。

在实际应用中，原始特征可能并不满足这两个前提条件，需要将特征作一定变换或构造新的特征。

图 1: 原始特征通过变换满足高斯分布 [PNG]

上图展示了通过函数$\log x$变换原始特征以满足高斯分布。也可以通过构造新的特征，比如数据中心监控，利用特征$\mbox{CPU load}$和$\mbox{network traffic}$构造新的特征$\frac{\mbox{CPU load}}{\mbox{network traffic}}$¹，使其在发生异常的时数据会变得很大或者很小。

多元高斯分布

实际应用中，特征之间可能存在相关性，需要采用多元高斯分布概率密度函数进行异常检测。

多元高斯分布的概率密度函数定义为

\begin{equation} p(\mathbf x; \boldsymbol\mu, \Sigma)=\frac{1}{(2\pi)^{n\over 2}\lvert\Sigma\rvert^{1\over 2}}\exp\left(-{1\over 2}(\mathbf x - \boldsymbol\mu)^T\Sigma^{-1}(\mathbf x - \boldsymbol\mu)\right)， \label{eq:multi-gaussians-pdf} \end{equation}

其均值向量和协方差矩阵的极大似然估计为

\begin{equation} \begin{aligned} \boldsymbol\mu = & {1\over m}\sum_{i=1}^{m}\mathbf x^{(i)}\\ \Sigma = & {1\over m}\sum_{i=1}^{m}\left(\mathbf x^{(i)}-\boldsymbol\mu\right)\left(\mathbf x^{(i)}-\boldsymbol\mu\right)^T \end{aligned}。 \end{equation}

图 2: 二元高斯分布 [PNG]

上图给出了不同参数的二元高斯密度函数图。图上排的协方差矩阵为对角阵，表示特征之间独立，可用一元高斯分布的方法进行异常检测；图下排的协方差矩阵是非对角阵，表示特征之间存在相关性，需借助多元高斯分布密度函数\eqref{eq:multi-gaussians-pdf}进行异常检测。

基于一元高斯分布和多元高斯分布的异常检测有不同的应用场景：

若$\Sigma$不可逆，原因可能是不满足条件$m>n$，或者存在冗余特征，也就是特征之间有相关性（比如$\mathbf x_1=k\mathbf x_2$或$\mathbf x_1=\mathbf x_2 ＋ \mathbf x_3$等）。

由此可见，特征之间是否具有相关性并非利用多元还是一元高斯分布进行异常检测的唯一条件，在必要的时候需要借助一元高斯分布对具有相关性特征的数据集进行异常检测。

具有相关性的特征数据，经过基于PCA的坐标变换（参考维数约减部分关于PCA的内容）消除相关性，也可以用一元高斯分布的方法处理。

参考文献

1. [1]A. Ng, “Anomaly detection.” Coursera, 2014. [Online]

脚注