异常是什么？

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

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

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

异常的成因

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

• 数据来源于不同的类
  • 某个数据对象可能不同于其他数据对象（即异常），因为它属于一个不同的类。如进行信用卡欺诈的人属于不同的信用卡用户类，不同于合法使用信用卡的那些人。
• 自然变异
  • 许多数据集可以用一个统计分布建模，如用正态（高斯）分布建模，其中数据对象的概率随对象到分布中心距离的增加而急剧减小。比如一个高个子在一群比较矮的人之中。
• 数据测量和收集误差
  • 数据收集和测量的过程中造成的误差也是导致异常产生的原因。对于这样的异常一般会考虑直接删除，因为它们不提供有意义的信息。

异常的类型

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

• 全局离群点： 指一个数据对象显著偏离数据集中的其余对象。又称点异常
• 情境离群点： 指对于某个特定情境，这个对象显著偏离其他对象。比如对于“温度28°”这个事件，如果对应的是哈尔滨的冬天，就有问题，如果对应四川的夏天，就没问题。情境离群点又称条件离群点。一般来说，在情境离群点的检测中，考虑将数据对象的属性划分成两组：
• 情境属性：数据对象的情境属性定义对象的情境。在温度例子中，情境属性是时间地点。
• 行为属性：定义对象的特征，并用来评估对象关于它所处的情境是否是离群点。在温度例子中，行为属性是温度、湿度和气压。
• 集体离群点： 给定一个数据集，数据对象的一个子集作为整体显著偏离整个数据集。比如在入侵检测时，从一台计算机到另一台计算机的拒绝服务包是正常的，完全不视为离群点，然而，如果多台计算机不断地相互发送拒绝服务包，则它们可能被看做集体离群点。所涉及的计算机可能被怀疑遭受攻击。

通常，异常对象被称为离群点（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][1]

如果我们将其写成数学表达式的话，就是下面这个样子 密度函数：$$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$时，我们认为该样本是异常的。

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

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

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

多元高斯分布

与上面介绍的假设每一维数据都是相互独立 的高斯分布模型不同的是，多元高斯分布整体考虑所有特征以及其相关性。 对于多元高斯分布而言，同样有两个参数，均值$\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] $$ 如果让我们用热力图来展示的话，噔噔噔~

• 一元高斯分布：无论怎么变化$\sigma$，都是同心圆。

• 多元高斯分布：我们不仅考虑了在各特征维度上的异常，还考虑了特征之间的相关性，因此热力图也随之发生了变化。

混合模型方法

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

对于这样一个数据集，假定它由一个正态分布产生，估计的均值就会落在两个簇的中间，而不是任何一个簇的内部，效果当然很不好。 为了克服这一困难，我们可以假定正常的数据对象被多个正态分布产生，也就是混合模型（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：

• A中的对象是正常的
• M中的对象是离群点

算法的伪代码如下图所示：

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

优缺点

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

• 一元高斯分布复杂度低，运算效率高，但定义异常的能力有限
• 多元高斯分布复杂度高（协方差矩阵求逆比较复杂），数据量一大就不行了，但定义异常的能力强大

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

基于邻近度的离群点检测

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

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

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

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

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

• 如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。
• 如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。

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

优缺点：

• 简单易懂，便于解释
• 基于邻近度的方法一般需要$O(m^2)$时间，代价较高
• 对参数选择敏感
• 不能处理具有不同密度区域的数据集，因为这种方法使用全局阈值，不能考虑这种密度的变化

基于密度的离群点检测

基于上面说到的这个缺点，让我们来看看基于密度的离群点检测。 从基于密度的观点来说，离群点是在低密度区域中的对象，因此一个对象的离群点得分是该对象周围密度的逆。 密度通常用邻近度定义，一种常用的定义密度的方法是：定义密度为到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聚类算法使用的密度定义，见【梳理】聚类分析这篇文。

优缺点：

• 给出了离群点程度的定量度量，并且即使数据具有不同密度的区域也能够很好地处理。
• 与基于距离的方法一样，时间复杂度为$O(m^2)$

基于聚类的技术

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

• 一种利用聚类检测离群点的方法是丢弃远离其他簇的小簇。 这种方法可以与任何聚类技术一起使用，但是需要最小簇大小和小簇与其他簇之间距离的阈值。
• 还有一种更系统的方法是，首先聚类所有对象，然后评估对象属于簇的程度。 对于基于原型的聚类，可以用对象到它的簇中心的距离来度量对象属于簇的程度。更一般的，对于基于目标函数的聚类技术，可以使用该目标函数来评估对象属于任意簇的程度。
• 如果删除一个对象导致该目标显著改进，则我们可以将该对象分类为离群点。如对于K均值，删除远离其相关簇中心的对象能够显著地改进该簇的误差的平方和。

优缺点：

• 时空复杂度接近线性，高度有效
• 簇的定义通常是离群点的补，因此可能同时发现簇和离群点。
• 产生离群点集合它们的得分可能非常依赖所用的簇的个数和数据中离群点的存在性
• 聚类算法产生的簇的质量对该算法产生的离群点的质量影响非常大。

异常检测的挑战

• 正常对象和离群点的有效建模
• 针对应用的离群点检测： 不同应用的要求可能很不相同，因此通常异常检测模型的通用性较差。
• 在离群点中处理噪音
• 可理解性： 用户不仅要检测离群点，而且要知道被检测到的点为何是离群点。

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.