梳理 | 异常检测

in 机器学习 Views: 8,236 s with 1 comment

异常是什么？

当我们提到异常检测（Anomaly Detection）的时候，首先需要明确的，就是异常是什么？

在大多数的异常检测场景里，异常指与大部分其他对象不同的对象。

需要注意的是，出现异常并不代表这个异常就一定是个坏样本、或者说是错误的，而只是单单指，这个出现异常的样本和通常我们所见到的样本有些不一样，仅此而已。比如在入侵检测的场景里，出现异常并不代表出现了入侵事件、攻击事件，但是当很多个异常事件被串起来之后，我们可以认为，我们发现了一个入侵事件。

异常的成因

异常的成因通常有以下3个方面：

异常的类型

异常（离群点）的类型可以分为3类：

通常，异常对象被称为离群点（outlier），因为在数据的散布图中，它们远离其他数据点。
异常检测也称偏差检测（deviation detection），因为异常对象的属性值明显偏离期望的或常见的属性值。
异常检测有时还会被称为例外挖掘（exception mining），因为异常在某种意义上是例外的。

在这篇文章里，我们主要使用术语 异常 或 离群点。

异常检测的应用

异常检测作为一个存在时间较长的算法，在最初的时候主要用于改进常见的数据对象分析技术，通常用于数据预处理的部分，如相对少的离群点可能扭曲一组值的均值和标准差，或者改变聚类算法产生的簇的集合。
后来异常检测逐渐由关注异常的应用驱动，发展得更加宏大。

异常检测的方法

标签问题

基于模型的方法

这里主要讲统计学上的方法，即为数据创建一个模型，并且根据对象拟合模型的情况来评估它们。
大部分用于离群点检测的统计学方法都基于构建一个概率分布模型，并考虑对象有多大可能符合该模型，Andrew NG在“Machine Learning”这门课中介绍的关于Anomaly Detection的方法就是基于统计学的方法。

离群点的概率定义：离群点是一个在数据的概率分布模型中具有低概率的对象。

一元高斯分布

高斯分布（正态分布）是统计学最常使用的分布之一，因为其优美的数据表达和自然界中无处不在的身影，甚至被人称为最能让人感受到上帝存在的数学公式。
正态分布由记号$N(\mu,\sigma^2)$表示，其中 $\mu$ 和 $\sigma$ 分别为均值和标准差。如果一个随机变量$X$服从这个分布，我们写作$X$ ~ $N(\mu,\sigma^2)$.下图是正态分布的概率密度函数。
normal_curve.png

如果我们将其写成数学表达式的话，就是下面这个样子
密度函数：$$f(x;\mu,\sigma)=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}}$$
标准正态分布的密度函数（$\mu=0 and \sigma=1$）：$$f(x;\mu,\sigma)=\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}$$

也就是说，对于标准正态分布$N(0,1)$而言，只有0.0027的概率会分布在$\pm3$的范围里。
那么如果某个值距离分布的均值 $\mu$ 超过了 $3\sigma$，那么这个值就可以被简单的标记为一个异常点（outlier）。

使用一元高斯模型的异常检测中，我们认为样本的每个特征都服从独立的高斯分布，为这些特征单独拟合参数：
$$\mu_j=\frac{1}{m}\sum_{i=1}^m x_j^{(i)}$$
$$\sigma_j^2=\frac{1}{m}\sum_i^m (x_j^{(i)}-\mu_j)^2$$
对于样本x，因为我们已经假设特征之间是独立的，则可以计算出样本概率：
$$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)= \prod_{j=1}^n p(x_j;\mu_j,\sigma_j^2)$$
其中$p(x_n;\mu_n,\sigma_n^2)$是通过每个特征维度单独计算出来的概率（也就是说样本在这一个维度上，是异常的概率有多大。）
当$p(x)<\epsilon$时，我们认为该样本是异常的。

让我们用图来理解一下上面的公式。假如我们有两个特征，他们分别服从不同的正态分布（如右图），那么我们将训练集打在图上，就会是左图的样子，一层一层的同心圆，离圆心越远，样本是正常的可能性越小。
20150629142832728.png

但是，因为在一元正态分布中我们假设样本的每个特征都服从独立的高斯分布，这其实是一个强假设。比如说对于下图而言，我们可以看到，A点是正常样本的概率应该远大于B点，但对于当前这个高斯模型而言，AB两点的概率是一样的（落在一个同心圆上）
屏幕快照 2018-03-24 下午4.31.36.png

因此，为了发现不同特征之间的关联，我们引入多元正态分布来解决这个问题。

多元高斯分布

与上面介绍的假设每一维数据都是相互独立的高斯分布模型不同的是，多元高斯分布整体考虑所有特征以及其相关性。
对于多元高斯分布而言，同样有两个参数，均值$\mu$和协方差矩阵$\sum$，公式如下
$$\mu = \frac{1}{m}\sum_{i=1}^m x^{(i)}$$
$$\sum = \frac{1}{m}\sum_{i=1}^m (x^{(i)}-\mu)^T$$

当我们输入一个新样本$x$的时候，计算
$$p(x)=\frac{1}{(2\pi)^{\frac{n}{2}}|\sum|^{\frac{1}{2}}}e^{-\frac{(x-\mu)^T}{2\sum(x-\mu)}}$$

当$p(x)<\epsilon$时，我们认为该样本是异常的。

实际上，就和数学书上的无数例子一样，一元高斯分布是多元高斯分布的特殊形式，多元高斯分布中的$\sum$和一元高斯分布中的$\sigma$关系如下：

$$ \sum = \left[ \begin{matrix} \sigma^2 & 0 & \cdots & 0 \\ 0 & \sigma^2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \sigma^2 \\ \end{matrix} \right] $$

如果让我们用热力图来展示的话，噔噔噔~

混合模型方法

前面的两种方法都是假定数据是由正态分布产生的，但是当实际数据很复杂时，这种假定就显得过于简单了。在这种情况下，我们假定数据是被混合参数分布产生的，如图所示，其中有两个大簇$C_1$和$C_2$。
屏幕快照 2018-03-25 下午11.30.38.png

对于这样一个数据集，假定它由一个正态分布产生，估计的均值就会落在两个簇的中间，而不是任何一个簇的内部，效果当然很不好。
为了克服这一困难，我们可以假定正常的数据对象被多个正态分布产生，也就是混合模型（mixture models），它使用若干统计分布对数据建模，每一个分布对应于一个簇，而每个分布的参数提供对应簇的描述。
除此之外，在异常检测中，还通常将数据用两个分布的混合模型建模，一个分布为普通数据，而另一个为离群点。
聚类和异常检测的目标都是估计分布的参数，以最大化数据的总似然（概率）。聚类时，使用EM算法估计每个概率分布的参数，异常检测同样可以使用EM算法来估计参数。

在这里，我们给出一种更简单的方法——

初始时，将所有对象放入普通对象集，而异常对象集为空。
然后，用一个迭代过程将对象从普通集转移到异常集，只要该转移能提高数据的总似然。

假定数据集D包含来自两个概率分布的对象：M是正常对象的分布，A是异常对象的分布。数据的总概率分布可以记作
$$D(x)=(1-\lambda)M(x)+\lambda A(x)$$
其中，x是一个对象；$\lambda$是0-1之间的数，给出离群点的期望比例。
分布M由数据估计，而分布A通常取均匀分布。
设$M_t$和$A_t$分别为时刻t正常和异常对象的集合。初始$t=0，M_0=D$，而$A_0$为空。在任意时刻t，整个数据集的似然和对数似然分别由以下两式给出：
$$L_t(D)=\prod_{x_i\in D} P_D(x_i)=\left((1-\lambda)^{|M_t|}\prod_{x_i \in M_t}P_{M_t}(x_i) \right) \left(\lambda^{|A_t|}\prod_{x_i\in A_t}P_{A_t}(x_i) \right)$$
$$LL_t(D)=|M_t|log(1-\lambda)+\sum_{x_i\in M_t}logP_{M_t}(x_i)+|A_t|log\lambda+\sum_{x_i\in A_t}logP_{A_t}(x_i)$$
其中$P_D、P_M、P_{A_t}$分别是$D、M_t、A_t$的概率分布函数。
这个式子可以由下面这混合模型的一般定义推出。
$$p(\chi|\theta)=\prod_{i=1}^m p(x_i|\theta)=\prod_{i=1}^m \sum_{j=1}^k w_j p_j(x_i|\theta_j)$$
为此，有必要做一些简化假定——对于以下两种情况概率为0：

算法的伪代码如下图所示：
屏幕快照 2018-03-25 下午9.25.11.png

因为正常对象的数量比异常对象的数量大得多，因此，当一个对象移动到异常集后，正常对象的分布变化不大。在这种情况下，每个正常对象对正常对象的总似然的贡献保持相对不变。此外，如果假定异常服从均匀分布，则移动到异常集的每个对象对异常的似然贡献一个固定的量。这样，当一个对象移动到异常集时，数据总似然的改变粗略地等于该对象在均匀分布下的概率减去该对象在正常数据点的分布下的概率。从而，异常集由这样一些对象组成，这些对象在均匀分布下的概率明显比在正常对象分布下的概率高。

优缺点

对于一元高斯分布和多元高斯分布而言：

对于整个离群点检测的统计学方法而言：
这类方法建立在标准的统计学技术之上，当存在充分的数据和所用的检验类型的知识时，这些检验可能非常有效。对于单个属性，存在各种统计集群点检测。对于多元数据，可用的选择少一些，并且对于高维数据，这些检验可能性能很差。

基于邻近度的离群点检测

尽管基于邻近度的异常检测的思想存在若干变形，但其基本概念非常简单——

如果一个对象远离大部分点，那么它就是异常的。

度量一个对象是否远离大部分点的一种最简单方法就是K最近邻算法。
下面我们用这张图简单入门一下——
20150521201557111.jpg

根据上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。
也就是说，现在，我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。

我们常说，物以类聚，人以群分，判别一个人是一个什么样品质特征的人，常常可以从他or她身边的朋友入手，所谓观其友，而识其人。我们不是要判别上图中那个绿色的圆是属于哪一类数据么，那么我们就从它的邻居下手。但一次性看多少个邻居呢？从上图中，你还能看到：

于此我们看到，当无法判定当前待分类点是从属于已知分类中的哪一类时，我们可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为(或分配)到权重更大的那一类。这就是K近邻算法的核心思想。

优缺点：

基于密度的离群点检测

基于上面说到的这个缺点，让我们来看看基于密度的离群点检测。
从基于密度的观点来说，离群点是在低密度区域中的对象，因此一个对象的离群点得分是该对象周围密度的逆。
密度通常用邻近度定义，一种常用的定义密度的方法是：定义密度为到k个最近邻的平均距离的倒数，如果该距离小，则密度高，反之亦然。如下式所示：
$$density(x,k)=\left(\frac{\sum_{y \in N(x,k)}distance(x,y)}{|N(x,k)|}\right)^{-1}$$
其中，$N(x,k)$是包含x的k最近邻的集合，$|N(x,k)|$是该集合的大小，而$y$是一个最近邻。

还有一种密度定义是使用DBSCAN聚类算法使用的密度定义，见【梳理】聚类分析这篇文。

优缺点：

基于聚类的技术

聚类分析发现强相关的对象组，而异常检测发现不与其他对象强相关的对象。两者高度相关，只是服务于不同的目的罢了。因此毫无疑问，聚类可以用于异常检测。

优缺点：

异常检测的挑战

References

[1] PANG-NINGTAN, MICHAELSTEINBACH, VIPINKUMAR. 数据挖掘导论:完整版[M]. 人民邮电出版社, 2011.
[2] JiaweiHan, MichelineKamber, JianPei,等. 数据挖掘概念与技术[M]. 机械工业出版社, 2012.
[3] D.W's Notes.机器学习算法-K最近邻从原理到实现
[4] Andrew Ng. Machine Learning. Coursera, 2014.

「一键投喂 软糖/蛋糕/布丁/牛奶/冰阔乐！」

薇拉航线

(๑＞ڡ＜)☆谢谢老板~

使用微信扫描二维码完成支付

本文由 左左薇拉 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: May 11, 2020 at 10:40 am

←下一篇 →上一篇 ↓去底部 ↑回顶部
Comments are closed.
  1. Sunxiaokong

    请教下，数学公式是用什么软件编写/渲染的？

    回复