

第8章 异常值分析

你是独一无二的，如果感到空虚，是因为有些东西流失了。 ——玛莎格雷厄姆

8.1 引言

异常值是与其余大部分数据非常不同的数据点。 霍金斯正式定义了异常值的概念，如下：

异常值是一种与其他观察值有很大差异的观察结果，以至于人们会怀疑它是由不同的机制产生的。

异常值可以被看作是与群集相辅相成的概念。 尽管聚类试图确定类似的数据点组，但异常值是与其余数据不同的单个数据点。 数据挖掘和统计学文献中异常值*outliers*也被称为*abnormalities*,discordants, deviants, 或者*anomalies*。 在许多数据挖掘场景中，异常值有大量应用：

1. *数据清理：*异常值通常代表数据中的噪音。 这种噪音可能是由于数据收集过程中的错误造成的。 因此，异常值检测方法可用于消除这种噪声。
2. *信用卡欺诈：*信用卡活动的不寻常模式往往可能是欺诈的结果。 由于这些模式比正常模式要少得多，因此可以将其检测为异常值。
3. *网络入侵检测：*许多网络上的流量可被视为多维记录流。 异常值通常被定义为该流中的不寻常记录或潜在趋势的不寻常变化。

大多数异常检测方法都是创建一个正常模式的模型。 这种模型的例子包括聚类，基于距离的量化或降维。 异常值被定义为不适合这个正常模型的数据点。 数据点的“异常值”由一个数值来量化，称为异常值。 因此，大多数异常值检测算法产生的输出可以是以下两种类型之一：

1. *实值异常值评分：*这样的评分量化了数据点被视为异常值的趋势。 分数值越高，给定数据点是异常值的可能性越大（或者在某些情况下更小）。 一些算法甚至可以输出量化给定数据点是异常值的可能性的概率值。
2. *二进制标签：*输出二进制值指示数据点是否是异常值。 这种类型的输出比第一个输出包含的信息更少，因为阈值可以施加在异常值分数上以将它们转换为二进制标签，反之不成立。 因此，异常值分数比二元标签更普遍。 不过，大多数应用程序都需要二进制分数作为最终结果，因为它提供了一个明确的决定。

异常值得分的生成需要构建正常模式的模型。 在某些情况下，模型可能被设计为基于正常模式的非常严格的模型来生成特定类型的异常值。 这种异常值的例子是极端值，它们仅适用于某些特定类型的应用。 下面总结一些异常值分析的关键模型。 这些将在后面的章节中更详细地讨论。

1. *极端值：*如果数据点位于概率分布的两端之一，则它是极端值。 极值也可以通过使用多变量概率分布而不是单变量分布来等效地定义多维数据。 这些是非常特殊的异常值类型，但由于它们将分数转换为标签的效用，因此可用于常规异常值分析。
2. *聚类模型：*聚类被认为是异常分析的补充问题。 前一个问题寻找在一个组中发生的数据点，而后一个问题寻找与组隔离的数据点。 实际上，许多聚类模型将异常值确定为算法的副产品。 也可以优化聚类模型以专门检测异常值。
3. *基于距离的模型：*在这些情况下，分析数据点的k最近邻分布以确定它是否是异常值。 直观地说，如果数据点的k-最近邻距离比其他数据点的距离大得多，则数据点是异常值。 基于距离的模型可以被认为是聚类模型的更细粒度和以实例为中心的版本。
4. 基于密度的模型：在这些模型中，数据点的局部密度用于定义其离群值分数。 基于密度的模型与基于距离的模型密切相关，因为在给定数据点处的局部密度只有到其最近邻居的距离很大时才是低密度的。
5. *概率模型：*聚类的概率算法在第6章。因为异常值分析可以被认为是聚类的补充问题，所以使用概率模型进行异常值分析也是很自然的。 这些步骤几乎与聚类算法的步骤类似，只是EM算法用于聚类，并且概率拟合值用于量化数据点（而不是距离值）的异常值分数。
6. *信息理论模型：*这些模型与其他模型共享一个有趣的关系。 大多数其他方法修复了正常模式的模型，然后根据与模型的偏差量化异常值。 另一方面，信息论方法约束了正常模型允许的最大偏差，然后检查构建具有或不具有特定数据点的模型的空间需求差异。 如果差异很大，则将该点报告为异常值。

在下面的章节中，将详细讨论这些不同类型的模型，还将介绍来自这些类别算法的代表性算法。

应该指出的是，本章将异常值分析定义为一个无监督问题，其中以前的异常和正常数据点的例子不可用。 受监督的情景是分类问题的特例，其中以前的异常情况的例子是可用的，。 这种情况将在第11章详细讨论。

本章安排如下。 第8.2节讨论了极值分析的方法。 概率方法在第8.3节中介绍。 这些可以看作是EM聚类方法的修改，它利用聚类和异常值分析问题之间的连接来检测异常值。这个问题在8.4节中有更多的正式讨论。 基于距离的离群值检测模型在第8.5节中进行了讨论。 基于密度的模型在第8.6节讨论。信息理论模型在第8.7中有介绍。 关于聚类有效性的问题在第8.8节中讨论。总结在8.9节中给出。

8.2 极值分析

极值分析是一种非常特殊的异常值分析，其中数据的郊区数据点被报告为异常值。 这些异常值对应于概率分布的统计尾数。 对于一维分布，统计尾数更自然地被定义，尽管可以为多维情况定义类似的概念。

要理解极端值是非常特殊的异常值，这是很重要的。 换句话说，所有极端值都是异常值，但相反可能并非如此。 传统的异常值的定义基于霍金斯对生成概率的定义。 例如，考虑对应于{1，3，3，3，50，97，97，97，100}的1维数据集。 这里，值1和100可以被认为是极端值。 值50是数据集的平均值，因此不是极端值。 但是，它是数据集中最孤立的一个点，因此应该从生成角度来看被视为一个异常点。

类似的论点适用于多元数据的情况，其中极值位于分布的多变量尾数区域。 形式化定义多变量尾数的概念更具挑战性，尽管基本概念类似于单变量尾数的概念。 考虑图8.1所示的例子。 这里，数据点A可以被认为是极端值，也是异常值。 但是，数据点B也是孤立的，因此应该被视为异常值。 但是，它不能被视为多元极值。

异常值检测算法，可用于将多个离群值分数统一为单个值，并生成二进制标签作为输出。 例如，考虑一种气象应用，其中在独立分析它们的温度和压力变量的基础上产生空间区域的异常值得分。 这些证据需要统一到空间区域的单个异常值分数或二元标签中。 多变量极值分析在这些情况下非常有用。 在下面的讨论中，将讨论单变量和多变量极值分析的方法。

8.2.1 单变量极值分析

单变量极值分析与统计尾数置信度测试的概念密切相关。 通常，统计尾部置信度测试假定1维数据是通过特定分布描述的。 根据这些分布假设，这些方法试图确定预期比数据点更为极端的对象的比例。 该量化提供了关于特定数据点是否为极值的置信水平。

如何定义分布的“尾数”？对于不对称的分布，讨论可能不具有相同概率的上尾和下尾通常是有意义的。上尾被定义为大于特定阈值的所有极值，并且下尾被定义为低于特定阈值的所有极值。考虑密度分布${{f}_{X}}\left( x \right)$。通常，对于某些用户定义的阈值$θ$，尾部可以被定义为${{f}_{X}}\left( x \right)\le \theta <span><span class="MathJax_Preview">的分布的两个极端区域。图8.2a和b分别显示了对称和非对称分布的下尾部和上尾部的例子。从图8.2b可以看出，不对称分布的上尾部和下尾部的面积可能不相同。此外，图8.2b分布内部的一些区域的密度低于密度阈值</span><script type="math/tex">的分布的两个极端区域。图8.2a和b分别显示了对称和非对称分布的下尾部和上尾部的例子。从图8.2b可以看出，不对称分布的上尾部和下尾部的面积可能不相同。此外，图8.2b分布内部的一些区域的密度低于密度阈值$θθ，但不是极端值，因为它们不在分布的尾部。该地区的数据点可能被视为异常值，但不是极端值。图8.2a和b中上部尾部或下部尾部内的区域代表这些极端区域的累积概率。在对称概率分布中，尾部是根据此区域定义的，而不是密度阈值。然而，密度阈值的概念是尾部的定义特征，特别是在非对称单变量或多变量分布的情况下。一些不对称分布，例如指数分布，可能有一端没有尾数。

选择模型分布来量化尾部概率。 最常用的模型是正态分布。 具有平均值$μ$和标准差$σ$的正态分布的密度函数${{f}_{X}}\left( x \right)$定义如下：$<span><span class="MathJax_Preview">{{f}_{X}}\left( x \right)=\frac{1}{\sigma \cdot \sqrt{2\cdot \pi }}\cdot {{e}^{\frac{-{{\left( x-\mu \right)}^{2}}}{2\cdot {{\sigma }^{2}}}}}\tag{8.1}</span><script type="math/tex">{{f}_{X}}\left( x \right)=\frac{1}{\sigma \cdot \sqrt{2\cdot \pi }}\cdot {{e}^{\frac{-{{\left( x-\mu \right)}^{2}}}{2\cdot {{\sigma }^{2}}}}}\tag{8.1}$ 标准正态分布是其中均值为$θ$，标准偏差$σ$为1的分布。在一些应用场景中，分布的平均值$μ$和标准偏差$σ$可以通过先前的领域知识来知道。 或者，当大量数据样本可用时，可以非常精确地估计平均值和标准偏差。 这些可以用来计算随机变量的Z值。 观测值${{x}_{i}}$的Z值${{z}_{i}}$可以计算如下：$<span><span class="MathJax_Preview">{{z}_{i}}={\left( {{x}_{i}}-\mu \right)}/{\sigma }\;\tag{8.2}</span><script type="math/tex">{{z}_{i}}={\left( {{x}_{i}}-\mu \right)}/{\sigma }\;\tag{8.2}$ ${{z}_{i}}$的大的正值对应于右尾，而小的负值对应于左尾。 正态分布可以用Z值直接表示，因为它对应于均值为0，标准差为1的标准正态随机变量。 公式${8.3}$可以直接用Z值表示，使用的标准正态分布如下：$<span><span class="MathJax_Preview">{{f}_{X}}\left( {{z}_{i}} \right)=\frac{1}{\sigma \cdot \sqrt{2\cdot \pi }}\cdot {{e}^{\frac{-{{z}_{i}}^{2}}{2}}}\tag{8.3}</span><script type="math/tex">{{f}_{X}}\left( {{z}_{i}} \right)=\frac{1}{\sigma \cdot \sqrt{2\cdot \pi }}\cdot {{e}^{\frac{-{{z}_{i}}^{2}}{2}}}\tag{8.3}$ 这意味着可以使用累积正态分布来确定大于${{z}_{i}}$的尾部区域。 根据经验，如果Z值的绝对值大于3，则相应的数据点被视为极值。 在此阈值下，正态分布尾数内的累积面积可以小于0.01％。

当较小数量的$n$个数据样本可用于估计平均值$μ$和标准偏差$σ$时，可以对上述方法进行小的修改。 ${{z}_{i}}$的值如前所述计算，并且具有$n$个自由度的学生$t$分布被用于量化尾部中的累积分布而不是正态分布。 请注意，当$n$很大时，$t$分布收敛于正态分布。

8.2.2 多变量极值分析

严格地说，尾数是为单变量分布定义的。 然而，正如单变量尾数被定义为概率密度小于特定阈值的极端区域，也可以为多变量分布定义类似的概念。 该概念比单变量情况更复杂，并且定义为具有单峰的单峰概率分布。 如前一种情况一样，使用多元高斯模型，并且以数据驱动的方式估计相应的参数。 多变量极值分析的隐式建模假设是，所有数据点都位于具有单峰值的概率分布（即单高斯聚类）中，并且在任何方向上远离 聚类中心的数据点应被视为极值。

设$\bar{\mu }$是$d$维数据集的$d$维平均向量，$Σ$是其$d×d$协方差矩阵。 因此，协方差矩阵的$（i，j）$项等于维度$i$和$j$之间的协方差。 这些表示多元高斯分布的估计参数。 那么，二维数据点$\bar{X }$的概率分布$f\left( {\bar{X}} \right)$可以定义如下：$<span><span class="MathJax_Preview">f\left( {\bar{X}} \right)=\frac{1}{\sqrt{\left| \Sigma \right|}\cdot {{\left( 2\cdot \pi \right)}^{\left( {d}/{2}\; \right)}}}\cdot {{e}^{-\frac{1}{2}\cdot \left( \bar{X}-\bar{\mu } \right){{\Sigma }^{-1}}{{\left( \bar{X}-\bar{\mu } \right)}^{T}}}}\tag{8.4}</span><script type="math/tex">f\left( {\bar{X}} \right)=\frac{1}{\sqrt{\left| \Sigma \right|}\cdot {{\left( 2\cdot \pi \right)}^{\left( {d}/{2}\; \right)}}}\cdot {{e}^{-\frac{1}{2}\cdot \left( \bar{X}-\bar{\mu } \right){{\Sigma }^{-1}}{{\left( \bar{X}-\bar{\mu } \right)}^{T}}}}\tag{8.4}$ $|Σ|$的值表示协方差矩阵的行列式。 指数中的项是数据点$\bar{X }$与均值$\bar{\mu}$之间马氏距离平方的一半。换句话说，如果$Maha\left( \bar{X},\bar{\mu },\Sigma \right)$表示$\bar{X }$和$\bar{\mu }$之间的马氏距离，这个距离和协方差矩阵$Σ$有关，则正态分布的概率密度函数如下：$<span><span class="MathJax_Preview">f\left( {\bar{X}} \right)=\frac{1}{\sqrt{\left| \Sigma \right|}\cdot {{\left( 2\cdot \pi \right)}^{\left( {d}/{2}\; \right)}}}\cdot {{e}^{-\frac{1}{2}\cdot Maha{{\left( \bar{X},\bar{\mu },\Sigma \right)}^{2}}}}\tag{8.5}</span><script type="math/tex">f\left( {\bar{X}} \right)=\frac{1}{\sqrt{\left| \Sigma \right|}\cdot {{\left( 2\cdot \pi \right)}^{\left( {d}/{2}\; \right)}}}\cdot {{e}^{-\frac{1}{2}\cdot Maha{{\left( \bar{X},\bar{\mu },\Sigma \right)}^{2}}}}\tag{8.5}$ 为了使概率密度降至特定阈值以下，马氏距离需要大于特定阈值。 因此，到均值的马氏距离可以用作极值分数。 相关极值由到均值的马氏距离大于特定阈值的数据多维区域定义。 该区域如图8.3b所示。 因此，数据点的极值分数可以报告为该数据点与平均值之间的马式距离。 较大的值意味着更加极端的行为。 在某些情况下，可能需要更直观的概率测量。 相应地，数据点$\bar{X }$的极值概率由到均值$\bar{\mu }$的马氏距离大于$\bar{X }$多维区域的累积概率定义。 如何估计这种累积概率？

正如在第三章3所讨论的，马氏距离与欧几里得距离相似，只是它将数据沿着不相关的方向标准化。 例如，如果要将数据的轴系旋转到主方向（如图8.3所示），那么在这个新轴系中的变换坐标将不具有相互作用关系（即对角线协方差矩阵）。 在将每个变换的坐标值沿其方向除以标准差之后，马氏距离就等于在这样变换后的（轴旋转的）数据集中的欧几里德距离。 这种方法提供了一个简洁的方式来模拟马氏距离的概率分布，它还提供了多变量尾数累积概率的具体估计。

由于标准偏差的缩放，马氏距离沿主要相关方向的每个独立分量可以被模拟为一个均值为0和方差为1的一维标准正态分布。$d$个相互独立的标准正态分布的变量的平方和服从自由度为$d$的$χ2$分布。 因此，$d$自由度d的$χ2$分布区域的累积概率（其值大于$Maha\left( \bar{X},\bar{\mu },\Sigma \right)$）可以被称为$\bar{X }$的极值概率。概率越小意味着是极值的可能性越大。

直观地说，这种方法将数据沿各种不相关的方向建模为统计独立的正态分布，并对其进行标准化，以便在异常值得分中为每个这样的方向提供同等重要性。 在图8.3a中，根据数据中的自然相关性，数据点B比数据点A更可能是多变量极值。 另一方面，数据点B基于欧几里得距离而不是基于马氏距离，因而更接近数据的质心（比数据点A）。 这表明马氏距离在利用数据的基本统计分布来更有效地推断数据点的异常值方面的实用性。

8.2.3 基于深度的方法

基于深度的方法的一般原则是一组数据点的凸包表示该组的最佳帕雷托极值。 基于深度的算法以迭代方式进行，其中在第k次迭代期间，数据集的凸包的角落处的所有点被移除。 迭代$k$的索引还提供异常值分数，其中较小的值表示数据点异常值更大的趋势。 重复这些步骤直到数据集为空。 通过报告所有具有至多$r$深度的数据点作为异常值，可将异常值分数转换为二元标签。

r的值可能需要通过单变量极值分析来确定。 图8.4说明了基于深度的方法的步骤。

图8.5给出了基于深度的方法的示意图。这个过程可以看作类似于剥离洋葱的不同层（如图8.5b所示），其中最外层定义了异常值。基于深度的方法试图达到与前一节多元方法相同的目标，但它通常在质量和计算效率方面往往不太有效。从定性的角度来看，基于深度的方法不会针对统计数据分布的特征进行标准化，就像基于马氏距离的多变量方法那样。所有在凸包角落处的数据点都是平等对待的。这显然是不可取的，许多数据点的分数由于关系而无法区分。此外，凸包角落处的数据点部分通常会随着维数的增加而增加。对于非常高的维度，大多数数据点位于最外凸包的角落可能并不少见。因此，不可能区分不同数据点的异常值。凸包方法的计算复杂度随着维数的增加而显着增加。与这种方法相关的定性和计算问题的组合使其成为基于马氏距离的多元方法的一个很好的替代方案。

8.3 概率模型

概率模型基于对8.2.2节多变量极值分析方法的推广。 基于马氏距离的多变量极值分析方法可以看作只有单模的混合高斯混合模型。 通过将该模型推广到多模态，可以确定一般的异常值，而不是多元极值。 这个想法与第6章6.5节中讨论的EM聚类算法密切相关。在一个直观的层面上，在概率意义上不属于任何聚类的数据点可能被报告为异常值。 为了方便，这里仅提供了一个简短的概要，若要更详细地了解EM算法，请参阅第6章6.5节。

基于混合的生成模型的基本原理是假定数据是从具有概率分布$G_1$ ... $G_k$的$k$个分布的混合产生的，其基于以下过程：

1. 选择具有先验概率$α_i$的混合分量，其中$i∈{1 ... k} <span><span class="MathJax_Preview">假设选择了第</span><script type="math/tex">假设选择了第$rr个。
2. 从$G_r$中产生一个数据点。

该生成模型将用$M$表示，并且它生成数据$D$中的每个点。数据集$D$用于估计模型的参数。 尽管使用高斯表示混合物的每个组成部分是自然的，但如果有需要，也可以使用其他模型。 这种灵活性对于将方法应用于不同的数据类型非常有用。 例如，在分类数据集中，分类概率分布可以用于每个混合分量而不是高斯分布。 在模型的参数被估计之后，异常值被定义为$D$中那些极不可能由该模型产生的数据点。 请注意，正如本章开头所述，这种假设完全反映了霍金斯定义的异常值。

接下来，我们讨论估计模型的各种参数，如估计$α_i$的不同值和不同分布$G_r$的参数。 这个估计过程的目标函数是确保完整的数据$D$对生成模型有最大的可能性。 假设$G_i$的密度函数由${{f}^{i}}\left( \cdot \right)$给出。 由模型生成的数据点${{\bar{X}}_{j}}$的概率（密度函数）由下式给出：$<span><span class="MathJax_Preview">{{f}^{po\operatorname{int}}}\left( {{{\bar{X}}}_{j}}|M \right)=\sum\limits_{i=1}^{k}{{{\alpha }_{i}}\cdot {{f}^{i}}\left( {{{\bar{X}}}_{j}} \right)}\tag{8.6}</span><script type="math/tex">{{f}^{po\operatorname{int}}}\left( {{{\bar{X}}}_{j}}|M \right)=\sum\limits_{i=1}^{k}{{{\alpha }_{i}}\cdot {{f}^{i}}\left( {{{\bar{X}}}_{j}} \right)}\tag{8.6}$

请注意，密度值$<span><span class="MathJax_Preview">{{f}^{po\operatorname{int}}}\left( {{{\bar{X}}}_{j}}|M \right)</span><script type="math/tex">{{f}^{po\operatorname{int}}}\left( {{{\bar{X}}}_{j}}|M \right)$提供了数据点的异常值分数。 异常的数据点自然会具有较低的值。 图8.6给出了函数值与异常值之间的关系示意图。 数据点$A$和$B$通常对混合模型具有非常低的拟合度，并且将被视为异常值，因为数据点$A$和$B$不属于任何混合组分。 数据点$C$将对混合模型具有较高的拟合度，因此不会被视为异常值。 模型$M$的参数使用最大似然准则来估计，这将在下面讨论。

对于包含$n$个数据点（用$\bar{X_1 }$ ... $\bar{X_n }$表示）的数据集$D$，由模型$M$生成的数据集的概率密度是各种点特定概率密度的乘积：$<span><span class="MathJax_Preview">{{f}^{data}}\left( D|M \right)=\prod\limits_{i=1}^{n}{{{f}^{po\operatorname{int}}}\left( {{{\bar{X}}}_{j}}|M \right)}\tag{8.7}</span><script type="math/tex">{{f}^{data}}\left( D|M \right)=\prod\limits_{i=1}^{n}{{{f}^{po\operatorname{int}}}\left( {{{\bar{X}}}_{j}}|M \right)}\tag{8.7}$

数据集$D$相对于$M$的对数似然函数$L（D | M）$是上述表达式的对数，可以（更方便地）表示为不同数据点上的值之和：$<span><span class="MathJax_Preview">L\left( D|M \right)=\log \left( \prod\limits_{i=1}^{n}{{{f}^{po\operatorname{int}}}\left( {{{\bar{X}}}_{j}}|M \right)} \right)=\sum\limits_{j=1}^{n}{\log \left( \sum\limits_{i=1}^{k}{{{\alpha }_{i}}\cdot {{f}^{i}}\left( {{{\bar{X}}}_{j}} \right)} \right)}</span><script type="math/tex">L\left( D|M \right)=\log \left( \prod\limits_{i=1}^{n}{{{f}^{po\operatorname{int}}}\left( {{{\bar{X}}}_{j}}|M \right)} \right)=\sum\limits_{j=1}^{n}{\log \left( \sum\limits_{i=1}^{k}{{{\alpha }_{i}}\cdot {{f}^{i}}\left( {{{\bar{X}}}_{j}} \right)} \right)}$ $\tag{8.8}$

这个对数似然函数需要进行优化以确定模型参数。 目标函数是使数据点的生成模型最大化。 为此，我们将用到第6章6.5节讨论的EM算法。

在确定了模型的参数之后，${{f}^{po\operatorname{int}}}\left( {{{\bar{X}}}_{j}}|M \right)$（或其对数）的值可以被看作为异常值分数。 这种混合模型的主要优点是混合分量可以包含关于每个分量形状的领域知识。 例如，如果已知特定聚类中的数据点以某种方式相关，则可通过固定协方差矩阵的适当参数并学习其余参数将这一点包含到混合模型中。 另一方面，当可用数据有限时，混合模型可能会过拟合数据。 这会导致真正异常的数据点被错过。

8.4 异常检测的聚类

上一节的概率算法引出了聚类和异常值检测之间的关系。 聚类都是关于发现数据点的“群体”，而异常点分析则是关于发现远离这些群体的数据点。 因此，聚类和异常检测具有众所周知的互补关系。 一个简单的观点是，每个数据点都是群集的成员或异常值。 聚类算法通常具有“异常处理”选项，可以移除群集外的数据点。 然而，将异常值检测作为聚类方法的副产品并不适合，因为聚类算法未针对异常值检测进行优化。 集群边界区域上的数据点也可能被认为是弱异常值，但在大多数特定应用情况下很少有用。

聚类模型也有一些优点。 异常值往往处在他们自己的小群集中。 这是因为生成过程中的异常可能会重复几次。 因此，可能会创建一小组相关的异常值。 图8.7举例说明了一小组孤立的异常值。 正如后面将要讨论的那样，聚类方法通常对这样的场景是强大的，因为这样的组通常不具有形成它们自己的聚类所需的临界数量。

定义数据点异常值分数的简单方法是首先对数据集进行聚类，然后使用数据点到最近的聚类质心的原始距离作为异常值分数。 然而，我们还可以可以做得更好，当类簇被扩大或在数据集上具有变化的密度时。 正如第3章所讨论的，本地数据分布通常会扭曲距离，因此，使用原始距离不是最佳的。 广义原则用于多变量极值分析，其中用全局马氏距离定义异常值分数。 在这种情况下，局部马氏距离可以用于描述到最接近的类簇质心的距离。

考虑一个数据集，其中使用聚类算法发现了$k$个聚类。 假设$d$维空间中的第$r$个类有$d$维平均向量为$\bar{μ_r}$和$d×d$协方差矩阵$Σ_r$。 这个矩阵的第$（i，j）$项是该类中维度$i$和$j$之间的协方差。 然后，数据点$\bar{X}$和聚类质心$\bar{μ_r}$之间的马氏距离$Maha\left( \bar{X},\bar{\mu_r },\Sigma_r \right)$定义如下：$<span><span class="MathJax_Preview">Maha\left( \bar{X},{{{\bar{\mu }}}_{r}},{{\Sigma }_{r}} \right)=\sqrt{\left( \bar{X}-{{{\bar{\mu }}}_{r}} \right)\Sigma _{r}^{-1}{{\left( \bar{X}-{{{\bar{\mu }}}_{r}} \right)}^{T}}}\tag{8.9}</span><script type="math/tex">Maha\left( \bar{X},{{{\bar{\mu }}}_{r}},{{\Sigma }_{r}} \right)=\sqrt{\left( \bar{X}-{{{\bar{\mu }}}_{r}} \right)\Sigma _{r}^{-1}{{\left( \bar{X}-{{{\bar{\mu }}}_{r}} \right)}^{T}}}\tag{8.9}$

这个距离被称为异常值分数。 异常值分数越大表明异常值的可能性越大。 在异常值分数确定之后，可以使用单变量极值分析将分数转换为二进制标签。

使用马氏距离的合理性与8.2节讨论的多变量距离的极值分析的情况类似，。 唯一的区别是局部的特定类簇的马氏距离与确定一般异常值更为相关，而全局马氏距离与确定特定类型异常值（如极值）更相关。 局部马氏距离的使用也与EM算法的似然标准有着有趣的联系，其中（平方）马氏距离出现在每个高斯混合的指数项中。 因此，数据点的对数马氏距离与不同混合分量均值（聚类均值）之和用于确定EM算法中的异常值分数。 这种分数可以被视为硬聚类算法确定的分数的软版本。

聚类方法基于全局分析。 因此，在大多数情况下，小的、密切相关的数据点组不会形成自己的群集。 例如，图8.7中的四个孤立点通常不会被视为一个集群。 大多数聚类算法要求将一组数据点视为一个聚类的最小临界数量。 结果，这些点会有很高的异常值。 这意味着聚类方法能够有意义地检测这些小而密切相关的数据点组并将其报告为异常值。 一些基于密度的方法并非如此，它们单纯地基于局部分析。

聚类算法的主要问题是它们有时无法正确区分环境噪声数据点和真正孤立异常的数据点。 显然，后者比前者强大得多。 这两种类型的点不会驻留在聚类中。 因此，到最近的聚类质心的距离往往不能很好地代表其本地分布（或具体的特定的分布）。 在这些情况下，基于距离的方法更加有效。

8.5 基于聚类的异常值检测

由于异常值被定义为远离数据中“拥挤区域”（或簇）的数据点，因此定义异常值的一个自然而具体的方式如下所示：

对象$O$的基于距离的异常值分数是它到第k个最近邻居的距离。

上述使用$k$-近邻距离的定义是最常见的定义。 有时使用这种定义的其他变体，例如到最近邻的平均距离。 $k$的值是用户定义的参数。 选择大于1的$k$值有助于识别孤立组的孤立点。 例如，在图8.7中，只要$k$固定为大于3的任何值，那么紧密相关点的小组内的所有数据点将具有较高的异常值分数。 请注意，计算异常值分数的目标数据点本身不包含在其最近邻居中。 这样做是为了避免1邻近方法总是产生0的异常值得分的场景。

基于距离的方法通常使用比聚类方法更精细的分析粒度，因此可以区分环境噪声和真正孤立的异常。 这是因为环境噪声通常比真正孤立的异常具有更低的k近邻距离。 这种区分在聚类方法中丢失，其中距最近的聚类质心的距离不能准确反映底层数据点的具体的、特定的分离情况。

这种更好粒度的代价是更高的计算复杂度。 考虑一个包含$n$个数据点的数据集$D$. 当使用顺序扫描时，对于每个数据点，确定$k$-近邻距离需要$O（n）$时间。 因此，确定所有数据点的异常值可能需要$O（n^2）$时间。 对于非常大的数据集，这显然不是一个可行的选择。 因此，使用各种方法来加速计算：

1. *索引结构：*索引结构可以用来有效地确定第k个最近邻距离。 但是，如果数据是高维的，这种选择不可行。 在这种情况下，指数结构的有效性往往会降低。
2. *修剪技巧：*在大多数应用中，不需要所有数据点的异常值。 它可能会提供返回前$r$个异常值的二元标签及其分数。 剩余数据点的异常值分数无关紧要。 在这种情况下，当其最近邻距离值的当前上限估计值低于迄今为止发现的第$r$个最佳异常值分数时，可以终止异常值候选者的$k$-近邻顺序扫描。 这是因为这样的候选人保证不在最高的$r$个异常值之内。 这种方法被称为“提前终止技巧”，本节稍后会详细介绍。

在某些情况下，还可以将修剪方法与索引结构相结合。

8.5.1 修剪法

修剪法仅用于需要返回前$r$个异常值并且其余数据点的异常值分数无关紧要的情况。 因此，修剪法只能用于算法的二元决策版本。 修剪法的基本思想是通过快速排除那些即使采用近似计算也是非异常值的数据点来减少$k$-近邻距离计算所需的时间。

8.5.1.1 抽样方法

第一步是从数据$D$中选择一个大小为$s<<n$的样本$S$，并计算样本$S$中的数据点与数据库$D$中的数据点之间的所有成对距离。总共有$n*s$个这样的对。这个过程需要$O（n*s）<<O（n^2）$的距离计算量。因此，对于$S$中的每个采样点，$k$-近邻距离是已知的。确定样本$S$中前$r$个异常值，其中r是需要返回的异常值的数量。第$r$个异常值的得分是整个数据集$D$上的第$r$个异常值分数的下限$L$。对于$D-S$中的数据点，只有$k$-近邻距离的上限${{V}^{k}}\left( {\bar{X}} \right)$是已知的。这个上界等于$D-S$中每个点与样本$S⊂D$的k-近邻距离。然而，如果这个上界${{V}^{k}}\left( {\bar{X}} \right)$不大于已经确定的下界$L$，则可以将这样的数据点$X∈D-S排$除在前$r$个异常值的进一步考虑之外。通常情况下，只要基础数据集聚类良好，这将导致从$D-S$中立即移除大量异常值候选者。这是因为，只要样本$S$中包含至少一个来自每个聚类的点，并且$S$中至少有$r$个点位于某些稀疏区域，则聚类中的大多数数据点将被删除。这通常可以通过适当选取真实数据集的抽样大小来实现。在从$D-S$中移除这些数据点之后，剩余的点集合是$R⊆D-S$。可以将$k$-近邻方法应用于更小的候选者集合$R$。将$R\cup S$中前$r$个异常值返回作为最终输出。根据已经实现的修剪水平，这可以导致计算时间的显着减少，尤其是当$|R∪S| <<| D |$时。

8.5.1.2 早期终止技巧与嵌套循环

上一节中讨论的方法可以通过加快计算$R$中每个数据点的$k$-近邻距离的第二阶段来进一步改进。该想法是一旦确定X不可能位于最高r异常值之内，则$\bar{X}\in R$中数据点的$k$-近邻距离的计算可以直接终止。 在这种情况下，对数据库$D$进行扫描以计算$\bar{X}$的$k$-近邻邻居可以提早结束。

注意，根据到样本$S$的距离，对每个$\bar{X}∈R$的$k$-近邻距离已经有一个估计（上界）${{V}^{k}}\left( {\bar{X}} \right)$。此外，$S$中第$r$个$k$-近邻距离的异常值提供了前$r$个异常值所需的“修剪”的下限。该下界由$L$表示。随着数据库$D-S$的扫描和$\bar{X}$到$D-S$各点距离的计算，$\bar{X}$的$k$-近邻距离的估计${{V}^{k}}\left( {\bar{X}} \right)$被进一步收紧（减小）。因为估计${{V}^{k}}\left( {\bar{X}} \right)$总是$\bar{X}$真实的k近邻距离的上限，只要${{V}^{k}}\left( {\bar{X}} \right)$低于已知的前$r$个异常值距离的下限$L$，确定X的k最近邻居的过程就可以终止。这被称为提前终止并显着地节约了计算。然后，可以处理$R$中的下一个数据点。在没有达到提前终止的情况下，数据点$\bar{X}$ 几乎总是在前$r$个（当前）异常值之中。因此，在这种情况下，下限$L$也可以收紧（增加）到新的最佳异常值分数。这在处理来自$R$的下一个数据点以确定其$k$-近邻距离值时，将导致更好的修剪。为了最大化修剪的好处，$R$中的数据点不应以任意顺序处理。相反，它们应该按照k-近邻距离（基于$S$）的初始采样估计${{V}^{k}}\left( \cdot \right)$的顺序进行处理。这确保了$R$中的异常值在早期被发现，并且全局边界L被尽可能快地收紧以进行更好的修剪。此外，在内部循环中，基于${{V}^{k}}\left( {\bar{Y}} \right)$的增加值，$D-S$中的数据点$\bar{Y}$可以按相反的方向排序。这样做可以确保尽可能快地更新$k$-近邻距离，并且提前终止的优势被最大化。嵌套循环方法也可以在没有第一阶段采样的情况下实施，但是这种方法不具有处理的数据点正确排序的优点。从抽样阶段获得的第$r$个最佳异常值分数的起始下限$L$开始，嵌套循环执行如下：

for each $\bar{X} ∈R $ do begin for each $\bar{Y} ∈D−S$ do begin Update current $k$-nearest neighbor distance estimate ${{V}^{k}}\left( {\bar{X}} \right)$ by computing distance of Y to X; if ${{V}^{k}}\left( {\bar{X}} \right) ≤ L$ then terminate inner loop; endfor if ${{V}^{k}}\left( {\bar{X}} \right) >L$ then include $\bar{X}$ in current $r$ best outliers and update $L$ to the new $r$th best outlier score; endfor

请注意，数据点$\bar{X}$的$k$近邻不包含数据点本身。 因此，在嵌套循环结构中必须小心忽略在更新$k$近邻距离时$\bar{X} = \bar{Y}$的情况。

8.5.2 局部距离校正方法

第三章的3.2.1.8节详细讨论了局部数据分布对距离计算的影响。特别是，它表明，当密度和形状与数据局部性明显不同时，直接测量（如欧几里得距离）不反映数据点之间的固有距离。这一原则也被用于8.4节来证明使用局部马氏距离来测量到聚类质心的距离，而不是欧几里德距离。在不同数据密度的背景下认识到这一原理的最早方法之一是*局部异常因子（$LOF$）*方法。正式的理由是基于数据集的生成原理，但这里只提供直观的理解。应该指出，对于多变量极值分析（第8.2.2节），使用马氏距离（而不是欧几里德距离）也是基于数据点符合分布的统计特性的生成原理。主要的不同点是，在那种情况下分析是全局性的，而在这种情况下分析是局部的。读者也被建议重温第3章的3.2.1.8节，讨论数据分布对数据点之间固有距离的影响。

为了在异常值分析的背景下激发局部距离校正的原理，将使用两个示例。其中一个例子说明了不同局部分布密度的影响，而另一个例子说明了不同局部簇形状的影响。这两个方面都可以用不同种类的距离计算的局部归一化来解决。在图8.8a中，显示了两个不同的聚类，其中一个比另一个更稀疏。在这种情况下，数据点A和B都明显是异常值。尽管异常值B很容易被大多数基于距离的算法检测到，但异常值A的检测会出现一个挑战。这是因为稀疏簇中许多数据点的最近邻距离至少与异常值A的最近邻距离一样大。因此，取决于所使用的距离阈值，k近邻算法将错误地报告稀疏簇的部分，或者将完全错过异常值A.简而言之，基于距离算法的异常值排序是不正确的。这是因为聚类A中点的真实距离应根据其本地数据分布以标准化的方式进行计算。这方面与第3章3.2.1.8节关于本地数据分布对距离函数设计的影响的讨论有关，而且对于许多基于距离的数据挖掘问题而言，这一点很重要。这里的关键问题是生成原理，数据点A由其最密集（紧密结合）的聚类产生的可能性要小于属于相对不均匀使用聚类的许多稍微孤立的数据点可能由其聚类产生的可能性。 霍金斯在本章开头提到的异常值的定义是基于生成原理制定的。 应该指出的是，8.3节的概率EM算法在识别这些生成差异方面做得更好。 然而，概率EM方法通常不被实际使用，因为较小的数据集过度拟合问题。 *LOF*方法是第一种认识到将这些生成原理引入非参数距离算法的重要性的方法。

这一点可以通过检查图8.8b中不同局部形状和方向的类簇来进一步强调。在这种情况下，如果使用最近邻距离，基于距离的算法将报告其中一个延长聚类的长轴上的数据点作为最强异常值。这个数据点更可能由其最接近的簇产生，而异常值由“$X$”标记。然而，后者具有更小的最近邻距离。因此，基于距离算法的重要问题是它们没有考虑到底层数据的局部生成行为。在本节中，将讨论两种方法来解决这个问题。其中一个是*LOF*，另一个是用于极值分析的全局马氏方法的直接推广。第一种方法可以针对图8.8a所示的生成变化进行调整，第二种方法可以针对图8.8b中所示的生成变化进行调整。

8.5.2.1 局部异常因子（LOF）

局部异常因子（LOF）方法通过使用数据局部中的平均特定点距离归一化距离来调整聚类密度的局部变化。 人们经常将其理解为基于密度的方法，但实际上，它是一种（标准化的）基于距离的方法，其中归一化因子对应于局部的平均数据密度。 这种规范化是解决图8.8a情况所带来挑战的关键。

对于一个给定的数据点 $\bar{X}$，令${{V}^{k}}\left( {\bar{X}} \right)$为到其$k$近邻的距离，令$L_k（\bar{X}）$为$\bar{X}$的$k$-近邻距离内的一组点。设$L_k（\bar{X}）$ 通常会包含$k$个点，但由于$k$-近邻距离的关系，有时可能包含多于$k$个点。

然后，将对象$\bar{X}$相对于$\bar{Y}$的可达性距离$R_k（\bar{X}，\bar{Y}）$定义为对$（\bar{X}，\bar{Y}）$之间的距离$Dist（\bar{X}，\bar{Y}）$和Y的$k$-近邻距离的最大值。$<span><span class="MathJax_Preview">{{R}_{k}}\left( \bar{X},\bar{Y} \right)=\max \left\{ Dist\left( \bar{X},\bar{Y} \right),{{V}^{k}}\left( {\bar{Y}} \right) \right\}\tag{8.10}</span><script type="math/tex">{{R}_{k}}\left( \bar{X},\bar{Y} \right)=\max \left\{ Dist\left( \bar{X},\bar{Y} \right),{{V}^{k}}\left( {\bar{Y}} \right) \right\}\tag{8.10}$

$\bar{X}$和$\bar{Y}$之间的可达性距离不对称。直观地说，当$\bar{Y}$处于密集区域并且$\bar{X}$与$\bar{Y}$之间的距离很大时，$\bar{X}$相对于它的可达性距离等于真实距离$Dist（\bar{X}，\bar{Y}）$。另一方面，当$\bar{X}$和$\bar{Y}$之间的距离很小时，则可达性距离被$\bar{Y}$的最近邻距离平滑。 $k$值越大，平滑度越高。相应地，相对于不同点的可达性距离也将变得更相似。使用这种平滑的原因是它使中间距离计算更加稳定。当$\bar{X}$和$\bar{Y}$之间的距离很小时，这尤其重要，并且会导致原始距离的统计波动更大。在概念层面上，可以根据原始距离直接定义*LOF*，而不是可达性距离。但是，这样的版本会失去平滑提供的稳定性。

数据点$\bar{X}$相对于其邻域$L_k（\bar{X}）$的平均可达性距离$AR_k（\bar{X}）$被定义为其邻域内所有对象的可达性距离的平均值。$<span><span class="MathJax_Preview">A{{R}_{k}}\left( {\bar{X}} \right)=MEA{{N}_{\bar{Y}\in {{L}_{k}}\left( {\bar{X}} \right)}}{{R}_{k}}\left( \bar{X},\bar{Y} \right)\tag{8.11}</span><script type="math/tex">A{{R}_{k}}\left( {\bar{X}} \right)=MEA{{N}_{\bar{Y}\in {{L}_{k}}\left( {\bar{X}} \right)}}{{R}_{k}}\left( \bar{X},\bar{Y} \right)\tag{8.11}$

这里，MEAN函数简单地表示整个邻域$L_k（\bar{X}）$上的平均值。 局部异常因子$LOF_k（\bar{X}）$则等于$AR_k（\bar{X}）$与$\bar{X}$的$k$邻域中所有点的相应值的平均比率。$<span><span class="MathJax_Preview">LO{{F}_{k}}\left( {\bar{X}} \right)=MEA{{N}_{\bar{Y}\in {{L}_{k}}\left( {\bar{X}} \right)}}\frac{A{{R}_{k}}\left( {\bar{X}} \right)}{A{{R}_{k}}\left( {\bar{Y}} \right)}\tag{8.12}</span><script type="math/tex">LO{{F}_{k}}\left( {\bar{X}} \right)=MEA{{N}_{\bar{Y}\in {{L}_{k}}\left( {\bar{X}} \right)}}\frac{A{{R}_{k}}\left( {\bar{X}} \right)}{A{{R}_{k}}\left( {\bar{Y}} \right)}\tag{8.12}$

在定义中使用距离比可确保本定义中的局部距离行为得到很好的解释。 因此，当类簇中的数据点均匀分布时，类簇中对象的*LOF*值通常接近1。 例如，在图8.8a的情况下，即使两个簇的密度不同，两个簇中数据点的*LOF*值也会非常接近于1。 另一方面，两个外围点的*LOF*值将会更高，因为它们将根据平均邻域可达性距离的比率来计算。 实际上，在$k$的不同值范围内的$LOF_k（\bar{X}）$的最大值被用作异常值得分来确定邻域的最佳大小。

关于*LOF*方法的一个发现是，虽然它在文献中被普遍理解为基于密度的方法，但它可以更简单地理解为具有平滑的基于相对距离的方法。 平滑确实是使距离计算更加稳定的一个补充。 基本的*LOF*方法在许多数据集上都能很好地工作，即使使用原始距离而不是可达性距离，对于前面提到的公式8.11的计算也是如此。

因此，LOF*方法能够很好地适应不同密度的区域，因为在等式8.12中每一项的分母都用了相对标准化。在最初的*LOF*算法演示中（参见书目注释），*LOF*是用密度变量来定义的。密度变量松散地定义为平滑可达距离的平均值的倒数。这当然不是密度的精确定义。传统上，密度是根据指定区域或体积内的数据点数量来定义的。本书提供了与*LOF*完全相同的定义，但通过省略中间密度变量略微表现出来。这是为了简单起见，以及直接根据（标准化）距离定义*LOF。 *LOF*与数据密度的真正联系在于其通过使用相对距离来适应不同数据密度的洞察力。因此，本书将这种方法归类为基于（归一化）距离的方法，而不是基于密度的方法。

8.5.2.2 特定实例的马氏距离

特定实例的马氏距离被设计用于调整特定数据点位置的不同形状的分布，如图8.8b所示。 马氏距离与数据分布的形状直接相关，尽管传统上它在全局意义上被使用。 当然，也可以通过使用数据点邻域的协方差结构来使用局部马氏距离。

这里的问题是当邻域簇的形状不是球形时，数据点的邻域难以用欧几里得距离来定义。例如，使用与数据点的欧氏距离偏向于捕获该点周围的圆形区域，而不是拉长的聚类。为了解决这个问题，使用了一种聚类方法来确定数据点$\bar{X}$的$k$-邻域$L_k（\bar{X}）$。首先，将数据点$\bar{X}$添加到$L_k（\bar{X}）$。然后，将数据点迭代添加到$L_k（\bar{X}）$中，该$L_k（\bar{X}）$与$L_k（\bar{X}）$中的最近点具有最小距离。这种方法可以被看作是单连接层次聚类方法的一个特例，其中单一点与聚类合并。单连接方法众所周知用于创建任意形状的簇。这种方法倾向于“增长”与群集形状相同的邻域。计算邻域$L_k（\bar{X}）$的平均值$μ_k（\bar{X}）$和协方差矩阵$Σ_k（\bar{X}）$。然后，数据点$\bar{X}$的特定于实例的马氏得分$LMahak（\bar{X}）$提供其异常值得分。这个得分被定义为$\bar{X}$的马氏距离与$L_k（\bar{X}）$中数据点的平均值$μ_k（\bar{X}）$之间的距离。$<span><span class="MathJax_Preview">LMah{{a}_{k}}\left( {\bar{X}} \right)=Maha\left( \bar{X},\overline{{{\mu }_{k}}\left( X \right)},{{\Sigma }_{k}}\left( {\bar{X}} \right) \right)\tag{8.13}</span><script type="math/tex">LMah{{a}_{k}}\left( {\bar{X}} \right)=Maha\left( \bar{X},\overline{{{\mu }_{k}}\left( X \right)},{{\Sigma }_{k}}\left( {\bar{X}} \right) \right)\tag{8.13}$

这个计算与全局马氏距离极值分析之间唯一的区别在于，局部邻域$L_k（\bar{X}）$被用作前者的“相关”数据进行比较。虽然8.4节在局部邻域中使用了一个马氏度量，在这种情况下，计算只有微妙的不同。在基于聚类的异常值检测的情况下，预处理方法预先将有限数量的聚类定义为可能邻域的全局。在这种情况下，邻域是以特定于实例的方式构建的。不同的点有不同的邻域，它们可能不完全对应于预定义的簇。这个额外的粒度允许更多的精确分析。在概念层面上，这种方法计算数据点$\bar{X}$是否可以视为与其本地集群有关的极值。与*LOF*方法一样，该方法可应用于不同的$k$值，并且可报告每个数据点的最高异常值分数。

如果将此方法应用于图8.8b的示例，则该方法将正确地确定异常值，因为对于每个数据点使用适当的（局部）协方差矩阵进行局部马氏距离归一化。 因为马氏距离已经在开头执行了这些局部归一化，所以不需要距离归一化来改变数据密度（图8.8a的场景）。 因此，这种方法也可以用于图8.8a的场景。 读者可以参考*LOF*变体的书目注释，这些变体使用不同局部簇形状和凝聚邻域计算的概念。

8.6 基于密度的方法

基于密度的方法与基于密度的聚类差不多有相似的原理。 这个想法是确定底层数据中的稀疏区域，以报告异常值。 相应地，可以使用基于直方图，基于网格或基于密度的核心方法。 直方图可以被看作基于网格的方法的一维特殊情况。 然而，由于这些方法在调整不同数据位置的密度变化方面存在困难，因此这些方法并未受到重视。 随着维度的增加，密度的定义也变得更具挑战性。 然而，由于其自然的概率解释，这些方法在单变量情况下被更频繁地使用。

8.6.1 基于直方图和网格的技术

直方图非常简单，易于构建单变量数据，因此在许多应用领域中使用相当频繁。 在这种情况下，数据被离散化为分箱，并且估计每个分箱的频率。 位于频率非常低的分箱中的数据点被报告为异常值。 如果需要连续的离群分数，那么数据点$\bar{X}$的分箱中的其他数据点的数量被报告为$\bar{X}$的异常值分数。因此，分箱的计数不包括该点本身，以便最小化过度拟合较小的箱体宽度或较少数量的数据点。 换句话说，每个数据点的异常值比分箱数小1。

在多元数据的背景下，自然概括是使用网格结构。 每个维度被分成$p$个等宽范围。 与之前的情况一样，特定网格区域中的点数被报告为异常值。 在任何特定网格区域中具有小于$τ$的密度的数据点被报告为异常值。 $τ$的适当值可以通过使用单变量极值分析来确定。

基于直方图技术的主要挑战是很难确定最佳的直方图宽度。 直方图太宽或太窄将不能很好地模拟频率分布。 这些与使用网格结构进行聚类时遇到的问题类似。 当箱太窄时，落入这些箱的正常数据点将被宣布为异常值。 另一方面，当箱太宽时，异常数据点和高密度区域可能合并成一个箱。 因此，这种异常数据点可能不会被宣布为异常值。

使用直方图技术的第二个问题是它们本质上太局部，并且通常不考虑数据的全局特征。 例如，对于图8.7的情况，除非仔细校准网格结构的分辨率，否则基于多元网格的方法可能无法将孤立的一组数据点分类为异常值。 这是因为网格的密度只取决于其内部的数据点，并且当表示的粒度很高时，孤立的一组点可能会创建一个人为密集的网格单元。 此外，当密度分布与数据局部性显着不同时，基于网格的方法可能难以对密度的局部变化进行归一化。

最后，由于网格结构的稀疏性随着维数的增加而变化，直方图方法在高维方面效果不佳，除非相对于精心选择的低维投影计算异常值分数。 例如，$d$维空间将包含至少$2d$个网格单元，并且因此，期望填充每个单元的数据点的数量随着维度的增加呈指数地减少。 这些基于网格的方法存在的问题是众所周知的，而且在其他数据挖掘应用程序（如聚类）的环境中也经常遇到。

8.6.2 核密度估计

核密度估计方法在构建密度剖面方面与直方图技术相似，但主要差异在于构建了更平滑的密度剖面图。 在核密度估计中，在给定点处生成密度的连续估计。 给定点处的密度值被估计为与数据集中每个点相关的核函数$K_h（•）$的平滑值之和。 每个内核函数都与内核宽度$h$相关联，该内核宽度决定函数创建的平滑级别。 基于维度$d$的$n$个数据点和核函数$K_h（•）$的核估计$f（\bar{X}）$定义如下：$<span><span class="MathJax_Preview">f\left( {\bar{X}} \right)=\frac{1}{n}\cdot \sum\limits_{i=1}^{n}{{{K}_{h}}\left( \bar{X}-{{{\bar{X}}}_{i}} \right)}\tag{8.14}</span><script type="math/tex">f\left( {\bar{X}} \right)=\frac{1}{n}\cdot \sum\limits_{i=1}^{n}{{{K}_{h}}\left( \bar{X}-{{{\bar{X}}}_{i}} \right)}\tag{8.14}$

因此，数据集中的每个离散点$\bar{X_i}$被连续函数$K_h（•）$替代，该连续函数在$\bar{X_i}$处达到峰值并且具有由平滑参数$h$确定的方差。 这种分布的例子是宽度为$h$的高斯内核。

估计误差由内核宽度$h$定义，这是以数据驱动的方式选择的。 已经表明，对于大多数平滑函数$K_h（•）$，当数据点的数量变得无限时，假定宽度$h$被适当地选择，则估计渐近收敛于真密度值。 计算每个数据点的密度，而不包括密度计算中的点本身。 密度的值被报告为异常值。 低密度值表明更大的趋势是异常值。

基于密度的方法与直方图和基于网格的技术相似。 特别是，在局部密度有很大变化的情况下，如图8.7和图8.8中的那些，使用全局核宽度$h$来估计密度可能不会很好地工作。 这是因为基于密度方法的近视特性，其中密度分布的变化没有很好地解释。 尽管如此，基于核密度的方法可以更好地推广到具有局部变化的数据，尤其是在本地选择带宽的情况下。 与基于网格的方法一样，这些技术对于更高的维度不是很有效。 原因在于密度估计方法的准确性随着维度的增加而降低。

8.7 信息论模型

异常值是不能自然融入剩余数据分布的数据点。 因此，如果在数据分布中使用“正常”模式来压缩数据集，那么异常值会增加描述它所需的最小码长。 例如，请考虑以下两个字符串：$<span><span class="MathJax_Preview">ABABABABABABABABABABABABABABABABAB</span><script type="math/tex">ABABABABABABABABABABABABABABABABAB$$<span><span class="MathJax_Preview">ABABACABABABABABABABABABABABABABAB</span><script type="math/tex">ABABACABABABABABABABABABABABABABAB$

第二个字符串与第一个字符串具有相同的长度，并且在仅包含唯一符号C的单个位置上不同。第一个字符串可以简洁地描述为“AB 17次”。但是，第二个字符串具有与 符号C.因此，第二个字符串不能再简洁地描述。 换句话说，字符串中符号C的存在会增加其最小描述长度。 也很容易看到这个符号对应于异常值。 信息理论模型基于这个一般原则，因为它们可以尽可能简洁地衡量描述数据所需的模型大小的增加。

信息论模型可以被视为几乎等同于传统的基于偏差的模型，不同之处在于异常值得分由固定偏差的模型大小定义，而不是固定模型的偏差。在传统模式中，外线总是基于正常模式的“概要”模型进行定义。当数据点偏离概要模型的估计值时，则将该偏差值报告为异常值。显然，汇总模型的大小和偏差水平之间存在贸易溢价。例如，如果使用聚类模型，那么大量聚类质心（模型大小）将导致降低任何数据点（包括异常值）与其最接近质心的最大偏差。因此，在传统模型中，使用相同的聚类来计算不同数据点的偏差值（分数）。计算异常值得分的一种稍微不同的方式是找出最大允许偏差（而不是聚类质心数），并计算达到相同偏差水平所需的聚类质心数，无论有无特定数据点。正是这种增长被报告为同一模型的信息论版本中的异常值得分。这里的想法是，每个点可以通过其最接近的聚类质心来估计，并且聚类质心用作“代码本”，数据以有损的方式被压缩。

信息论模型可以被视为传统模型的补充版本，其中检验了空间偏差交易曲线的不同方面。 实际上，每一个传统的模型都可以通过检验双空间标准的空间偏差交易而不是偏差来转换成信息论的版本。 书目注释还将提供以下每种情况的具体示例：

1. 8.3节的概率模型根据生成模型参数（如混合均值和协方差矩阵）对正常模式进行建模。 模型所需的空间由其复杂性（例如，混合组分的数量）定义，并且偏差对应于概率拟合。 在该模型的信息论版本中，补充方法是检查达到固定水平的过滤所需的模型的大小。
2. 基于聚类或基于密度的汇总模型根据聚类描述，直方图或其他汇总表示描述数据集。 这些表示的粒度（聚类质心数或直方图箱）控制着空间，而使用聚类中心元素（箱）近似数据点的误差定义了偏差。 在传统模型中，模型的大小（箱或簇的数量）是固定的，而在信息理论版本中，最大允许偏差是固定的，并且所需模型大小被报告为异常值分数。
3. 3.频繁模式挖掘模型根据频繁模式的底层代码本描述数据。 代码簿的大小越大（通过使用频率较低的支持模式），数据的描述就越准确。 这些模型特别受欢迎，并且在书目注释中提供了一些指针。

所有这些模型都近似代表总体趋势的单个浓缩组分的数据。一般而言，异常值会根据这些浓缩成分增加描述的长度，以达到相同的近似水平。例如，具有异常值的数据集将需要大量的混合参数，聚类或频繁模式才能达到相同的近似水平。因此，在信息论方法中，这些概要模型的组成部分被粗略地称为“代码簿”。异常值被定义为数据点，这些数据点的去除会导致相同误差的描述长度下降最大。编码的实际构造通常是启发式的，与常规离群值分析中使用的概要模型并无太大差别。在某些情况下，可以估计数据集的描述长度，而无需明确构建代码本或构建摘要模型。一个例子是数据集的熵，或者一个字符串的Kolmogorov复杂度。关于这些方法的例子，读者可以参考书目注释。

虽然信息论模型与传统模型大致相同，但他们以相同的方式探索相同的贸易，但它们在某些情况下确实具有优势。 这些情况下数据的精确概要模型难以明确地构建，并且诸如熵或Kolmogorov复杂度的度量可以用于间接估计数据集的压缩空间需求。 在这种情况下，信息论方法可能有用。 在可以明确构建概要模型的情况下，最好使用传统模型，因为异常值分数直接针对点特定偏差进行优化，而不是对不均匀空间影响的更直接测量。 书目记录提供了上述某些方法的具体例子。

8.8 异常值有效性

如在聚类模型的情况下，需要确定由特定算法确定的异常值的有效性。 尽管聚类和异常值分析之间的关系是相辅相成的，但异常有效性的测量方法不能以相似的补充方式进行设计。 事实上，有效性分析在异常值检测方面比数据聚类困难得多。 其原因将在下一节讨论。

8.8.1 方法上的挑战

就数据聚类而言，异常值分析是一个无监督的问题。 由于缺乏外部标准，无监督的问题很难验证，除非这些标准是综合生成的，或者真实数据集的一些罕见方面被用作代理。 因此，自然地出现问题，就是内部标准是否可以用于异常值验证，就像数据聚类一样。

但是，内部标准很少用于异常值分析。尽管即使在数据聚类的情况下，这些标准也是众所周知的，但这些标准变得非常重要，无法将这些标准用于异常分析。建议读者参考第6章的6.9.1节讨论内部集群有效性的挑战。这些挑战中的大多数都与聚类有效性标准来自聚类算法的目标函数标准的事实有关。因此，一个特定的有效性度量将有利于（或超过）使用类似目标函数准则的聚类算法。由于样本溶液空间较小，这些问题在异常值分析中变得更为重要。一个模型只需要在一些异常数据点上是正确的就可以被认为是一个好的模型。因此，即使在聚类中，内部有效性标准的过度配置在异常值分析中也变得更加棘手。作为一个具体的例子，如果使用k-近邻距离作为内部有效性度量，那么纯粹的基于距离的离群值检测器将总是胜过局部标准化的检测器，如LOF。当然，这与现实环境中的已知经验不一致，其中*LOF*通常提供更有意义的结果。可以通过设计一个有效性度量来减少溢出效应，这种效果度量与被比较的异常值检测模型是不同的。然而，这不是一个令人满意的解决方案，因为重大的不确定性总是依赖于这些措施和异常值检测模型之间隐藏的相互关系的影响。内部措施的主要问题是，即使数据集不同，对各种算法评估的相对偏倚始终存在。在算法基准测试中，内部措施的偏倚选择很容易被滥用。

内部度量几乎不用于异常值分析，尽管它们通常用于聚类评价。 即使在聚类中，尽管内部有效性措施被广泛接受，但使用内部有效性措施仍值得怀疑。 因此，用于异常值分析的大多数有效性度量都基于外部度量，如接收机操作特性曲线。

8.8.2 接收机操作特性

通常使用外部度量来评估离群点检测算法，其中来自合成数据集的已知离群标签或来自真实数据集的罕见类标签被用作基础事实。 将这个基础事实系统地与异常值评分进行比较以产生最终输出。 虽然这种罕见的类别可能并不总是反映数据中的所有自然异常值，但是当通过许多数据集进行评估时，结果通常可合理地代表算法质量。

在异常值检测模型中，阈值通常用于异常值得分以生成二进制标签。 如果阈值被选择得过于严格以使已声明的离群值数量最小化，那么该算法将错过真正的离群点（假阴性）。 另一方面，如果以更轻松的方式选择阈值，这将导致太多的误报。 这导致了假阳性和假阴性之间的贸易关系。 问题在于，使用“正确”的阈值在实际情况下从来不知道。 然而，可以生成整个交易曲线，并且可以在整个交易曲线上比较各种算法。 这种曲线的一个例子是接受者操作特征（ROC）曲线。

对于异常值分数上的任何给定阈值$t$，所声明的异常值集合由$S（t）$表示。 随着$t$的变化，$S（t$）的大小也随之改变。 设$G$代表数据集中异常值的真实集合（地面真值集合）。 真正的阳性率也被称为召回率，被定义为地面真值离群值的百分比，它被报告为阈值$t$处的异常值。$<span><span class="MathJax_Preview">TPR\left( t \right)=\operatorname{Re}call\left( t \right)=100*\frac{\left| S\left( t \right)\cap G \right|}{\left| G \right|}\tag{8.15}</span><script type="math/tex">TPR\left( t \right)=\operatorname{Re}call\left( t \right)=100*\frac{\left| S\left( t \right)\cap G \right|}{\left| G \right|}\tag{8.15}$

表8.1：ROC建设与地面实况离群排名

算法	地面真值异常值的等级
算法A	1, 5, 8, 15, 20
算法B	3, 7, 11, 13, 15
随机算法	17, 36, 45, 59, 66
完美的Oracle	1, 2, 3, 4, 5

假阳性率$FPR（t）$是从地面实况阴性中错误报告的阳性的百分比。 因此，对于具有地面实况正数$G$的数据集$D$，此度量定义如下：$<span><span class="MathJax_Preview">FPR\left( t \right)=100*\frac{\left| S\left( t \right)-G \right|}{\left| D-G \right|}\tag{8.16}</span><script type="math/tex">FPR\left( t \right)=100*\frac{\left| S\left( t \right)-G \right|}{\left| D-G \right|}\tag{8.16}$

通过绘制$X$轴上的$FPR（t）$和$Y$轴上的$TPR（t）$来绘制$t$的变化值，从而定义*ROC*曲线。 请注意，*ROC*曲线的终点总是在（0,0）和（100,100）处，并且随机方法预计会沿连接这些点的对角线显示性能。 在这条对角线上方获得的升力提供了该方法准确性的想法。*ROC*曲线下的面积为特定方法的有效性提供了具体的定量评估。

为了说明从这些不同图形表示中获得的见解，考虑一个具有100个点的数据集的示例，其中5个点是异常值。 两种算法A和B应用于这个数据集，它将从1到100的所有数据点排序，较低的等级表示更大的倾向是异常值。 因此，通过确定5个地面真值离群点的等级，可以生成真正的阳性率和假阳性率值。 在表8.1中，对于不同的算法，已经说明了五个地面真值离群点的一些假设等级。 另外，已经指出了随机算法的地面真值离群值的等级。 随机算法为每个数据点输出一个随机离群分数。 同样，表中也列出了“完美预言”算法的排名，该算法将正确的前5个点排除为异常值。 相应的ROC曲线如图8.9所示。

这些曲线真的告诉我们什么？对于其中一条曲线严格控制另一条曲线的情况，显然前者曲线的算法是优越的。例如，显而易见的是，oracle算法优于所有算法，并且随机算法不如所有其他算法。另一方面，算法A和B在ROC曲线的不同部分显示支配。在这种情况下，很难说一种算法是严格优越的。从表8.1可以清楚地看出，算法A非常高地排列了三个正确的地面真值离群值，但其余两个离群值排名很差。在算法B的情况下，排名最高的离群值的排名不如算法A的情况，尽管所有五个离群值都是以排名阈值较早确定的。相应地，算法A在ROC曲线的较早部分占主导地位，而算法B在后面部分占主导地位。一些从业人员使用ROC曲线下方的面积作为算法整体效能的代表，尽管应该非常小心地使用这种方法，因为ROC曲线的所有部分可能对于不同的应用并不重要。

8.8.3 常见错误

对异常值分析应用进行基准测试的常见错误是ROC曲线下方的区域被重复使用以调整异常值分析算法的参数。 请注意，这种方法隐含地将地面实况标签用于模型构建，因此它不再是无监督的算法。 对于诸如聚类和异常值检测等问题，以任何方式使用外部标签来调整算法是不可接受的。 在异常值分析的特殊情况下，使用这种调整方法可能会大大高估其准确度，因为少数异常点的相对得分对ROC曲线有非常大的影响。

8.9 总结

异常值分析问题是一个重要问题，因为它适用于各种问题领域。 异常值检测中的常见模型包括概率模型，聚类模型，基于距离的模型，基于密度的模型和信息论模型。 其中，距离模型是最流行的，但在计算上更昂贵。 已经提出了许多加速技巧来使这些模型更快。 基于距离的模型的局部变化通常倾向于更有效，因为它们对基础数据的生成方面的敏感性。 信息理论模型与传统模型密切相关，并探讨了空间偏差交易的不同方面 - 与传统模型相比。

异常值验证是一个难题，因为与异常值检测的无监督性质相关的挑战以及小的样本空间问题。 通常使用外部验证标准。 异常值分析算法的有效性通过使用接收器操作特性曲线进行量化，该曲线显示异常值得分上不同阈值的假阳性和假阴性之间的贸易差异。 该曲线下面的区域提供了异常值检测算法的定量评估。

8.10 书目注释

有关异常值分析问题的书籍和调查已经写了很多。这方面的经典着作[89,259]大多是从统计界的角度出发的。这些书中的大多数是在数据库技术被广泛采用之前编写的，因此不是从计算的角度编写的。最近，这个问题已经被计算机科学界广泛研究。这些工作考虑了与数据可能非常大或者维度非常高的情况相对应的异常值检测的实际方面。最近的一本书[5]也从计算机科学界的角度研究了这个领域。还编写了许多调查，从不同的角度，方法或数据类型讨论异常值的概念[61,84,131,378,380]。其中，Chandola等人的调查[131]是最新的，可以说是最全面的。这是一个很好的综述，涵盖了从多个社区角度进行异常值检测的相当广泛的工作。

Z值测试在统计学文献中通常使用，并且有许多扩展，例如t值测试[118]。 尽管该测试对大数据集进行了正态分布假设，但它仍被广泛用作一种很好的启发式算法，即使对于不满足正态分布假设的数据分布也是如此。

[319,436]中提出了多种基于距离的异常值检测方法，[109]中提出了异常值检测的距离校正方法。 [487]中探讨了LOF算法中任意形状簇的确定。 发现任意形状邻域的凝聚算法在实例特定马氏距离的章节中是基于这种方法的。 但是，此方法使用连通性异常因子，而不是特定于实例的Mahalanobis距离。 尽管这些方法是全局的而不是局部的，但是在[468]中提出了使用Mahalanobis距离作为异常值检测模型。 [257]中讨论了一种基于图形的局部异常值检测算法。 ORCLUS算法还显示了如何在存在任意形状的簇时确定异常值[22]。 [320]首先提出了解释距离异常值的方法。

[68,102,160,340,472]讨论了用于异常值检测的各种信息论方法。 许多这些不同的模型都可以以与传统模型相辅相成的方式进行查看。 例如，[102]中的工作在信息论模型的背景下研究概率方法。 [68,472]中的作品使用频繁模式的代码书来进行建模过程。 [470]中探究了频繁模式和压缩之间的关系。 文献[340,305]探讨了熵值和Kolmogorov复杂度等度量方法在异常值分析中的应用。 编码复杂性的概念在基于集合序列的背景下在[129]中进行了探索。

离群分析的评估方法基本上与用于理解精确回忆交易的信息检索技术相同，或者用于ROC曲线分析的分类。 详细的讨论可以在[204]中找到。

8.11 习题

1. 假设一个特定的随机变量具有均值3和标准差2.计算值为-1,3和9的Z值。这些值中的哪一个可以被认为是最极端值？
2. 根据维数特定的标准偏差$σ_1...σ_d$，定义$d$维在统计上彼此独立的数据基于马氏距离的极值测度。
3. 考虑四个二维数据点（0,0），（0,1），（1,0）和（100,100）。 用数学软件如MATLAB绘制它们。 视觉上哪个数据点看起来像极端值？ 马氏指标报告哪个数据点是最强的极值？ 哪些数据点通过基于深度的度量来报告？
4. 实现用于聚类的EM算法，并用它来实现概率异常值分数的计算。
5. 实现马氏$k$均值算法，并用它来计算异常值得分，以到最近群集质心的局部马氏距离来计算。
6. 讨论练习4和5中实现的算法之间的关系。
7. 讨论基于距离模型的聚类模型的优缺点。
8. 实现一个不需要修剪的原始的基于距离的异常值检测算法。
9. $k$-近邻异常值检测中参数$k$的作用是什么？ 什么时候$k$的小值很好地工作，什么时候$k$的较大值工作得很好？
10. 使用第6章的NMF方法设计异常值检测方法。
11. 讨论在（a）均匀分布的数据集中修剪基于距离算法的相对有效性，以及（b）具有适度环境噪声和异常值的高度聚类。
12. 实现用于异常值检测的LOF算法。
13. 考虑一维数据点{1,2,2,2,2,2,6,8,10,12,14}的集合。 对于基于距离的算法，使用k = 2的离群点得分最高的数据点是什么？ 使用LOF算法的离群点得分最高的数据点是什么？ 为什么不一样？
14. 实现特定实例的马氏方法进行异常值检测。
15. 给定一组地面实况标签和异常值分数，实施计算机程序来计算一组数据点的ROC曲线。
16. 使用各种异常值检测算法的目标函数标准来设计相应的内部有效性度量。 讨论这些措施偏向特定算法的偏见。
17. 假设你从数据集构造一个有向k-近邻图。 你如何使用节点的程度来获得异常值？ 这种算法与LOF共享什么特征？