【异常检测】数据挖掘领域常用异常检测算法总结以及原理解析（一）

【异常检测】数据挖掘领域常用异常检测算法总结以及原理解析（一）

一、基于统计的方法

基于统计的异常检测方法主要依赖于统计学原理来识别数据中的异常值。这些方法通常假设数据遵循一定的统计分布，如正态分布等。

1. 3sigma

基于正态分布，3sigma准则认为超过3sigma的数据为异常点。

如果数据处于均值加减三倍标准差之间，则认为是正常数据，否则，则认为是异常数据。

2. Z-Score（标准分数）

Z-Score（标准分数）异常检测方法是通过测量数据点与数据集均值的偏差程度来识别异常数据的。这种方法假设数据大致遵循正态分布（也称为高斯分布）。在正态分布中，大多数数据点（约68%）位于均值的一个标准差内，约95%的数据位于两个标准差内，而几乎所有的数据（约99.7%）位于三个标准差内。

识别异常数据

• 在Z-Score方法中，较高或较低的Z-Score值表示数据点与均值相比有显著的偏差。
• 通常，如果一个数据点的Z-Score的绝对值很高（例如，高于2或3），它就被认为是异常的。这意味着该数据点距离平均值相当远。例如，如果我们选择Z-Score的阈值为3，那么任何Z-Score大于3或小于-3的数据点都会被认为是异常的（与3sigma一致）。这基于统计学上的标准，即在正态分布中，距离均值超过3个标准差的数据点是非常罕见的。

应用场景

• 数据分布：Z-Score最适合于接近正态分布的数据。如果数据显著偏离正态分布，这种方法可能不那么有效。
• 异常值的影响：由于Z-Score方法依赖于均值和标准差，异常值本身可能会显著影响这两个参数，从而影响异常检测的结果。在实际应用中，决定什么样的Z-Score阈值用于标识异常通常取决于特定的应用场景和对于异常数据的敏感度。

综上所述，Z-Score方法是一种有效的工具来识别那些在统计上显著偏离大多数数据的数据点，但它的有效性取决于数据的分布和所选的阈值。

3. Grubbs’ Test（格拉布斯检验）

Grubbs’ Test（格拉布斯检验）是一种用于检测数据集中单个异常值的统计检验方法。这种方法假设数据遵循正态分布，并旨在确定数据集中是否存在一个显著偏离其他数据点的观测值。

识别异常数据

• 计算Grubbs’ 统计量：首先计算数据集中每个数据点的Grubbs’ 统计量。
• 临界值：然后，这个统计量与临界值进行比较。临界值通常基于所需的置信水平（如95%、99%）和数据集的大小，可以通过查看Grubbs’Test的临界值表或使用相关统计软件得到。
• 判断异常：如果计算出的Grubbs’ 统计量大于临界值，那么认为数据集中存在异常值。

应用场景

• 数据分布：Grubbs’ Test最适合于正态分布的数据。如果数据偏离正态分布，这种方法可能不准确。
• 单一异常值：Grubbs’Test主要用于检测数据集中的单个异常值。如果存在多个异常值，这种方法可能不适用。
• 数据大小：Grubbs’Test对于小样本数据可能不那么有效，因为小样本容易受到个别值的影响。

总之，Grubbs’ Test是一种用于检测单个异常值的统计方法，它基于数据点与数据集均值的偏差程度。但它的准确性取决于数据的分布和样本大小，且主要适用于单一异常值的检测。在实际应用中，选择合适的置信水平和理解其局限性是非常重要的。

4. 四分位距异常检测（箱线图（Boxplot）异常检测）

四分位距异常数据检测是一种基于统计的方法。这种方法使用四分位数（即数据集分布的四个等分点）来识别异常值。具体而言，它依赖于第一四分位数（Q1）和第三四分位数（Q3），以及基于这两个四分位数计算的四分位间距（IQR）来进行异常数据的识别。

实现步骤
1.计算四分位数：

• 第一四分位数（Q1）：位于数据集下25%处的值。
• 第三四分位数（Q3）：位于数据集上75%处的值。

2.计算四分位间距（IQR）：

• IQR = Q3 - Q1
• IQR是数据分布的中间50%区域的范围。

3.确定异常值阈值：

• 下界（Lower Bound）= Q1 - k * IQR
• 上界（Upper Bound）= Q3 + k * IQR
• 其中k通常取1.5，但根据需要可以调整。

4.识别异常值：

• 任何低于下界或高于上界的数据点被视为异常值。

应用场景
在这种方法中，异常数据通常是指那些与大部分数据显著不同的数值，它们远离数据的主要集中趋势。这些数据点可能是由于数据录入错误、测量误差或真实的变异性产生的。四分位点异常检测方法特别适合于处理偏斜数据集，因为它不依赖于数据的正态分布假设。

总之，这种方法的一个优点是它简单直观，容易计算和理解。但是，它也有局限性，比如对于包含多个异常值的数据集，这些异常值可能会影响四分位数的计算，进而影响异常检测的准确性。此外，k值的选择也会影响异常值的识别，需要根据具体的数据集和应用场景来调整。

二、基于邻近性的方法

基于临近性的异常检测方法是一种利用数据点之间的距离或相似性来识别异常值的算法。这类方法的基本假设是，正常数据点会彼此靠近或形成紧密的簇，而异常数据点则与大多数数据点的距离较远。

1. K-最近邻（K-Nearest Neighbors, KNN）

K-最近邻（K-Nearest Neighbors, KNN）异常检测方法是通过分析数据点与其最近的K个邻居之间的距离来识别异常数据的。这个方法的基本思想是基于临近性原理：正常的数据点通常位于数据集中的高密度区域，彼此之间距离较近，而异常数据点则通常距离这些高密度区域较远。

实现步骤

• 1.计算每个点与其他点的距离：对于数据集中的每个点，计算它与所有其他点之间的距离。
• 2.确定最近的K个邻居：对于每个点，找出距离最近的K个邻居。
• 3.计算异常得分：异常得分可以根据这K个邻居的距离来计算。常见的计算方法包括使用这些距离的平均值、最大值或总和。
• 4.确定异常阈值：设定一个阈值来区分正常数据和异常数据。这个阈值可以是固定的，也可以是基于数据集特性动态确定的。
• 5.标记异常数据：那些异常得分超过阈值的点被标记为异常。

应用场景

在KNN方法中，被认为是异常数据的通常具有以下特征：

• 1.与大多数数据点距离较远：如果一个数据点与其最近的K个邻居的距离明显大于大多数其他数据点与其邻居的距离，则该点可能是异常的。
• 2.处于低密度区域：如果一个数据点周围的点很少，即它位于数据集的低密度区域，则可能被视为异常。
• 3.与模式不吻合：在某些情况下，即使数据点不是孤立的，但如果它与数据集中的主要模式或趋势不一致，也可能被视为异常。

注意事项

• 1.K的选择至关重要：K的大小直接影响着异常检测的灵敏度。K值太小可能会导致过多的误报，而K值太大可能会错过一些细微的异常。
• 2.距离度量的选择：常用的距离度量包括欧几里得距离、曼哈顿距离等，不同的距离度量可能对结果产生影响。
• 3.对噪声敏感：KNN方法可能对噪声和离群值敏感，这可能会影响异常检测的准确性。
• 4.计算成本：对于大型数据集，计算每个点与其他所有点的距离可能非常耗时。

2. 局部异常因子（Local Outlier Factor, LOF）

局部异常因子（Local Outlier Factor, LOF）方法用于识别异常数据，其核心思想是通过比较一个点与其邻近点的局部密度来判断其是否异常。在LOF算法中，数据的异常程度是基于相对密度的概念来定义的。

LOF的工作原理

• 1.计算局部可达密度（Local Reachability Density, LRD）：
  • 对于每个数据点，首先确定其K个最近邻居（K是一个预设的参数）。
  • 计算每个点到这些邻居的可达距离。可达距离是实际距离和邻居点的K距离（第K近的点的距离）中的较大者。
  • LRD是这些可达距离的倒数的平均值，它反映了一个点周围邻居的密度。
• 2.计算局部异常因子（LOF）：
  • 对于每个数据点，计算其邻居的LRD与该点的LRD的比值的平均值，这就是LOF。
  • LOF反映了一个点与其邻居的密度对比。LOF值越大，表示该点与其邻居的密度差异越大。

应用场景

• 高LOF值：当一个点的LOF值显著高于1时，它被认为是异常的。LOF值为1意味着点的密度与其邻居相似，而高于1则意味着该点的密度远低于其邻居。
• 局部异常：LOF特别擅长于检测局部异常，即那些在其局部邻域中密度显著低于邻居的点。
• 敏感于参数：LOF的结果受到邻居数量K的影响。不同的K值可能导致不同的检测结果。因此，选择合适的K值对于正确识别异常至关重要。

LOF算法适用于各种场景，特别是在数据集的分布不均匀，或者异常数据的分布有局部特性时表现良好。例如，在金融领域用于检测欺诈行为，在网络安全中用于识别入侵，或在环境监控中用于检测异常读数。然而，它可能不适用于全局异常检测或者在数据分布非常均匀的场景中。

3. 基于连通性的离群因子（Connectivity-Based Outlier Factor, COF）

Connectivity-Based Outlier Factor (COF) 是一种用于异常检测的算法，其核心思想是基于数据点之间的连通性。这种方法特别适合于处理具有高度相关性或连通性的数据集，如在空间数据分析中常见的情况。

算法原理
COF算法的基本思想是通过考虑数据点之间的连通性来评估每个点的异常程度。与传统的基于距离或密度的异常检测方法不同，COF关注点之间的连通路径。

• 连通性：COF算法计算每个点与其k个最近邻居之间的平均连通性。连通性是通过考虑到达每个邻居所需的路径长度来衡量的。路径长度是通过点之间的连通路径上的点的数量来确定的。
• 异常得分：一个点的COF得分是基于它与其邻居的平均连通性与整体数据集中其他点的平均连通性之间的比较。如果一个点与其他点的平均连通性显著不同，它可能被视为异常。

应用场景

• 1.空间数据分析：在地理信息系统(GIS)和空间数据挖掘中，数据点的空间位置和邻近关系至关重要。COF算法可以有效地识别出在空间上表现不同的异常点。
• 2.社交网络分析：在社交网络中，节点（如个人或组织）之间的关系可以表示为网络。COF算法可以帮助识别在网络中行为异常或位置异常的节点。
• 3.生物信息学：在基因表达数据分析中，COF可以用来识别异常表达的基因或样本，这可能表明了某种疾病状态或生物学上的特异性。
• 4.金融欺诈检测：在金融领域，COF可以帮助识别异常交易模式，这些可能是欺诈行为的迹象。

局限性和注意事项

• 1.参数选择：与其他基于邻近性的算法一样，COF的效果很大程度上依赖于参数的选择，如邻居的数量。
• 2.计算复杂度：计算每个点的连通性可能在大数据集上变得计算密集和时间消耗。
• 3.数据类型适用性：COF算法更适用于那些连通性或关系在数据分析中起关键作用的数据类型。

总的来说，COF提供了一种独特的视角来评估数据点的异常程度，特别是在那些连通性或关系在数据分析中扮演重要角色的应用场景中。然而，与所有异常检测算法一样，理解数据的本质和适当的参数调整对于达到最佳性能至关重要。

4. 随机离群选择（Stochastic Outlier Selection, SOS）

Stochastic Outlier Selection（SOS）是一种基于随机抽样的异常检测算法。核心思想是通过随机抽样的方式，计算数据集中每个样本的离群得分（outlier score）。这些离群得分可以用来标识潜在的离群点或异常值。

算法原理

• 1.随机抽样：首先，从原始数据集中随机抽样生成多个子集。每个子集包含原始数据集的一部分样本。
• 2.距离度量：对于每个子集，计算其中每一对样本之间的距离。通常使用的是欧氏距离或其他合适的距离度量。这一步旨在捕捉子集内样本的相对分布情况。
• 3.离群得分计算： 对于每个样本，计算其到其他样本的平均距离。离群得分越高，表示该样本越可能是离群点。这个过程有助于识别在整个数据集中相对较远的样本。
• 4.阈值设定： 根据计算得到的离群得分设定一个阈值。样本的离群得分超过该阈值的话，就被认为是离群点。

应用场景

• 1.大规模数据集：SOS 算法通过随机子集抽样的方式，可以有效地处理大规模数据集。这使得它在需要快速处理大量数据的场景下表现出色。
• 2.无监督学习：SOS 是一种无监督学习的异常检测方法，不依赖于预先标记的异常样本。因此，适用于那些没有明确标签的情况。
• 3.多维数据：SOS 对于多维数据集也是适用的，因为它可以计算样本之间的距离，捕捉多维数据中样本的相对位置关系。
• 4.离群点分布不均匀：SOS 对于离群点在数据集中分布不均匀的情况也比较鲁棒，因为它使用了随机抽样的策略。
• 5.快速筛选离群点：SOS 的设计使得它能够快速地生成离群点得分，用于迅速筛选出可能的异常点，适用于需要快速反馈的应用场景。

总的来说，Stochastic Outlier Selection 主要适用于大规模、多维、无监督的异常检测场景，特别是在需要高效处理大量数据并且对计算效率有一定要求的情况下表现良好。然而，它可能不适用于所有异常检测问题，具体选择还需要考虑数据特性和问题要求。

5. 核密度估计（Kernel Density Estimation，KDE）

算法原理：核密度估计是一种非参数估计方法。它能够根据独立同分布（i.i.d.）样本计算出整个随机变量的概率密度函数。核密度估计的基本思想是在每一个观察值位置上放一个核函数（通常为正态分布曲线），然后对所有的核函数取平均，形成密度的估计。在估计过程中，核函数的形状以及带宽是两个关键参数。带宽太大，会使得估计结果过于平滑，可能忽视数据结构；带宽太小，则会生成复杂的模型，即过拟合现象。

Kernel Density Estimation (KDE)在异常检测中的应用：在异常检测中，核密度估计被用来估计每个数据点附近的密度。若一个数据点的密度远低于正常数据的密度，则可以将这个数据点判定为异常数据。这种方法的一个优点是，它对输入数据的形状没有先验假设。缺点是计算复杂度较高，特别是当处理大量数据时。

应用场景

• 1.多维数据的异常检测：由于核密度估计方法不依赖于具体的分布假设（如高斯分布等），所以它可以被用于同时考虑多个特征的异常检测，即使这些特征的联合分布是未知或复杂的。
• 2.对于有噪声的复杂环境：由于核密度估计方法能够提供连续的概率密度估计，因此当数据包含复杂的结构或噪声时，它可能比基于简单统计的方法更鲁棒。
• 3.对于不满足常规假设的数据：当数据可能无法满足其他统计异常检测方法的常规假设(如正态分布等）时，核密度估计方法可以提供一个有效的替代方案。

需要注意的是，虽然核密度估计是一种极其强大的工具，但是选择适当的核函数以及调整适当的带宽都是一项极富挑战的任务。可能需要根据数据的特征和需求进行调整。

总结