关于《Robust outlier detection based on the changing rate of directed density ratio》的阅读笔记

中文题目：基于有向密度比变化率的鲁棒离群检测
摘要：离群点检测任务旨在挖掘偏离正态分布的异常对象。传统的无监督离群点检测方法可以检测出大部分全局离群点，但只能在数据分布相对单一的情况下表现良好(动机1)。基于$k$-近邻的方法虽然能够拟合更复杂的数据分布，但也存在难以检测局部离群点或性能易受数据流形影响的问题(动机2)。同时，大多数基于$k$-近邻的方法的离群检测性能受参数$k$的影响较大(动机3)。这篇论文提出了一种基于有向密度比变化率的鲁棒离群检测方法。结合核密度估计和包含$k$-近邻和反向$k$-近邻的扩展近邻集来计算样本的局部密度。然后根据该密度比以及该样本与近邻样本之间的向量定义该样本的有向密度比。在不同的局部密度和数据流形下，有向密度比可以更好地估计局部信息。然后，通过增大邻居的大小，计算样本的有向密度比的变化，最终将其累加作为离群得分。在12个模拟不同数据分布的合成数据集和22个公开数据集上进行实验。实验结果表明，与几种主流(state-of-the-art)方法相比，所提方法在不同数据分布下均能取得更好的离群点检测性能。此外，在实验结果中参数$k$发生变化时，所提方法表现出较好的鲁棒性。

**关键词：**离群检测；核密度估计；扩展近邻集；有向密度比

---

目录

• • 关于《Robust outlier detection based on the changing rate of directed density ratio》的阅读笔记
  • @[TOC](目录)
• 1. 引言
• 2. 相关工作
• • 2.1. 距离法
  • 2.2. 密度法
• 3. 所提方法
• • 3.1. 局部核密度估计
  • 3.2. 有向密度比
  • 3.4. 复杂度分析
• 4. 实验分析
• • 4.1.数据集
  • 4.2. 对比方法
  • 4.3. 评估度量
  • 4.4. 合成数据集的实验结果与讨论
  • 4.5. 公开数据集的实验结果与讨论
  • 4.6. 实验结果和执行时间的讨论
• 5. 结论
• 参考文献

1. 引言

  根据Atkinson和Hawkins（1981）的定义，离群值指的是那些明显偏离正常模式的对象，以至于让人怀疑它们是由一个不同的机制产生的。一方面，由于离群点可能是由不同的机制产生，所以它们比正常样本更重要、更有趣。另一方面，离群点的存在会影响聚类等数据统计分析的结果。因此，离群检测是数据挖掘中一个基本而重要的任务。因此，离群检测是数据挖掘中一个基本而重要的任务。离群点检测在现实世界的各个领域有着广泛的应用，如检测银行账户交易中的欺诈行为、协助医生进行医疗诊断、无线传感器网络和物联网的故障检测等等。

  根据数据是否被标记，离群点检测方法可分为三类：有监督方法、半监督方法和无监督方法。有监督方法通过从标记数据中学习来构建分类模型并检测离群值。这种方法需要标记样本作为训练集，这通常很难获得或需要在现实任务中花费大量时间。半监督方法使用部分样本标签来建立模型和检测异常值。这些方法面临的挑战是如何在有限的信息下建立有效的异常点检测模型。无监督方法不需要标记样本，而是通过学习数据的底层分布机制来检测偏离正态分布的异常值。与监督和半监督方法相比，无监督离群点检测方法的研究更具挑战性。同时，由于没有标签的离群点检测任务在现实世界中广泛存在，无监督离群点检测方法的研究也更有意义。目前，离群点检测的研究主要集中在无监督领域。

  最早的无监督离群点检测多基于统计，如3𝜎准则，它假设样本在每个维度上都符合高斯分布，而偏离均值 3 个标准差的对象被视为异常值。基于直方图的离群值评分(Histogram Based Outlier Score, HBOS)(Goldstein & Dengel, 2012) 对数据的各个维度做直方图进行密度估计，并进行汇总来检测异常点。基于copula的离群点检测(COPula-based Outlier Detection, COPOD)(Li et al.，2020)通过copula函数估计分布的尾部概率来检测离群点。基于孤立思想的方法，如孤立森林 (isolation Forest, Forest) (Liu et al.， 2008)通过测量样本被孤立的难度来检测异常值。基于重构思想的方法，如主成分分析(Principal
Component Analysis, PCA ) (Shyu et al.， 2003)首先对数据进行投影和重构，通过每个样本的重构误差估计离群程度。基于聚类的方法，如基于聚类的局部离群因子(Cluster-Based Local Outlier Factor, CBLOF) (He et al.，2003)，通过聚类过程检测出异常点，将不属于任何簇的对象确定为异常点。上面的大多数方法不需要超参数，或者受超参数的影响较小，并且在单个正常模式中表现良好。然而，当正态样本形成多个分布模式或存在局部异常值时，这些方法的检测性能受到限制。

  另一种无监督的离群点检测方法是基于$k$-近邻的思想，通过寻找特征空间中最近的邻居来获取每个样本的局部信息，并在此基础上度量样本的离群点程度。由于这些方法测量的是样本周围的局部信息，因此受样本整体分布变化的影响较小，能够适应更复杂的数据分布。它们中的大多数都有一个标准的超参数，即最近邻的大小$k$，如经典的kNN (k-Nearest Neighbors, kNN) (Ramaswamy et al.，2000)和LOF(Local Outlier Factor, LOF)(Breunig et al.，2000)方法。参数$k$通常是手动指定的，通常很难为不同的任务和不同的数据集设置适当的值。不幸的是，大多数方法都带有参数“邻居的大小$k$"对$k$的选择很敏感，不同的$k$值和不同的数据集之间的方法性能差异很大。最近，一种基于重力的方法(Xie et al.，2020)被提出，通过矢量和变化率来减少参数$k$对检测性能的影响。但是这类方法也存在着当数据形成不同流形和不同密度分布时会降低检测精度的问题，这将在第2节中详细介绍。

  针对上述问题，本文提出了一种基于有向密度比变化率的鲁棒异常点检测方法。鲁棒性体现在两个方面:能够适应多样化和复杂的数据分布，即当数据分布形成不同的模式和流形或存在局部异常值时，能够有效地检测异常值；该方法对参数设置不敏感，即无论实际中将𝑘参数设置为哪个值，该方法都能取得令人满意的结果。该方法的主要贡献如下:
(1)提出了有向密度比的定义。 首先，基于核密度估计和包含𝑘-最近邻和反向𝑘-最近邻的扩展邻居集计算样本的局部核密度。 密度比定义为样本的每个邻居的密度与其自身的比值。 在此基础上，我们将密度比乘以从样本到对应邻居的向量作为有向密度比。 通过结合密度、距离和方向信息，有向密度比可以有效地反映不同分布样本的局部和全局异常值。
(2)提出了一种基于有向密度比变化率的异常检测器。 通过增加最近邻居的大小，计算不同邻居大小下的有向密度比之和，然后计算和的变化。 累积不同大小的邻居的变化值，直到𝑘达到设定的参数。 通过测量变化值来估计异常值程度，可以减轻参数对异常值检测性能的影响。 有向密度比变化的累积值作为样本的最终离群值。

---

2. 相关工作

  根据本文提出的方法的特点，本节将介绍基于𝑘-近邻的无监督离群点检测方法。这些方法大致可以分为基于距离的方法和基于密度的方法，并将依次介绍它们的优缺点。

2.1. 距离法

  kNN (Ramaswamy et al.，2000)离群点检测方法是在假定异常样本通常离最近邻较远的情况下，通过计算每个样本与其最近邻之间的距离来获得离群点分数。在具体实现上，kNN方法有两种不同的实现。LargestkNN直接将样本到𝑘-近邻的距离作为离群值，而averagekNN计算样本到𝑘邻居距离的平均值作为离群值。均值漂移异常值检测(Mean-shift Outlier Detection，MOD) (Yang et al., 2021)计算样本的𝑘-最近邻的平均样本，并用平均样本替换原始样本，对数据集进行均值偏移处理。经过多次迭代，得到均值漂移后的数据集，通过计算均值漂移前后样本的漂移距离来确定离群程度。MOD可以看作是kNN的扩展。当MOD迭代次数为1时，它退化为averagekNN。基于局部策略的离群检测（Local Gravitation-based Outlier Detection, LGOD）(Xie et al., 2020）基于样本间引力的概念，计算相邻样本的引力之和，进一步计算引力和的变化来判断异常值的程度。 在实现上，LGOD通过距离的“向量和”与“范数和”的乘积来计算“引力”，因此也可以认为是一种基于距离的方法。基于距离的方法简单直观，但会受到局部密度问题的影响，即当正态样本形成不同密度的簇时，密集正态簇附近的局部离群点到正态样本的距离可能等于或小于稀疏正态簇中正常样本之间的距离，这将导致该方法无法检测到密集正态簇附近的局部离群点。

2.2. 密度法

  LOF (Breunig et al.， 2000)利用基于密度的模型解决了上述问题。它通过局部可达距离计算样本的局部密度，并计算每个样本与相邻样本的密度比，得出离群点评分。该方法假设离群点密度低于相邻样本的密度，而正态样本的密度与相邻样本的密度相等。基于连接的离群因子 (Connectivity-based Outlier Factor, COF）Tang et al.， 2002)基于LOF的框架，进一步考虑了数据分布的一些特殊情况。局部密度因子（Local Density Factor，LDF）（Latecki et al., 2007）在LOF的基础上引入了核密度估计，通过有效结合局部可达距离和核密度优化了局部密度的计算方法。INFLO (INFLuenced Outlierness)
(Jin et al.， 2006)扩展了最近邻样本集的选择，使用𝑘-近邻和反向𝑘-近邻计算密度，进一步优化了局部密度的计算方法。相对密度离群得分(Relative Density-based Outlier Score,RDOS)
(Tang & He, 2017)结合了LDF和INFLO的理念，并引入了共享𝑘-近邻的概念。将最近邻集扩展为𝑘-近邻、反向𝑘-近邻和共享𝑘-近邻的和。通过核密度估计计算最终的局部密度，并在扩展的最近邻集中计算密度比。该思想在一定程度上缓解了LOF在一些复杂数据分布情况下性能不佳的问题。CELOF (Chen et al.， 2021)也是LOF的一种改进方法，引入信息熵构造了一种新的指标权重计算方法，设计了一种新的可达距离因子判别方法提取原始数据信息。基于密度的方法可以在大多数分布情况下有效地检测出各种异常点，但在正态分布形状特殊的情况下就会失效。例如，二维数据集中的数据表现为一维流形的嵌入。这种情况下，1维流形外的样本密度与流形内的样本密度非常接近，基于密度的方法将无法检测出异常值。这种流形嵌入也存在于许多现实世界的数据集中。

  正如引言中提到的，这些方法也有一个共同的问题，那就是对𝑘值的选择比较敏感。根据𝑘的不同取值，最终的检测性能会有很大的不同。LGOD (Xie et al.， 2020)通过定义重力的变化来估计离群程度，减少了𝑘值对检测结果的影响。然而，由于LGOD在实现中也通过距离计算重力，因此上述局部密度问题也存在。当数据分布密度和形状多样化时，局部离群点检测困难，且在某些数据集上难以获得满意的结果。

  综上所述，目前的无监督离群点检测方法各自存在一些问题。本文提出了一种基于有向密度比变化率的鲁棒离群点检测方法，解决了数据分布不均匀和对参数𝑘敏感的问题。

---

3. 所提方法

  提出的基于有向密度比变化率的离群检测（Directed density ratio Changing
Rate-based Outlier Detection，DCROD）方法主要包括三个部分：(1) 计算样本的局部核密度；(2)定向密度比的定义；(3)基于有向密度比变化率的异常点检测器。

3.1. 局部核密度估计

  考虑到密度估计的鲁棒性和连续性，本文将核密度估计与扩展最近邻相结合来计算样本点的局部密度。对于给定数据集 𝑿 = { 𝒙 1 , 𝒙 2 , 𝒙 3 , … , 𝒙 𝑛 } 𝑿 = \{𝒙_1, 𝒙_2, 𝒙_3,\dots, 𝒙_𝑛\} X={x1​,x2​,x3​,…,xn​}，其中$\mathbf{x}\in {\mathbf{R}}^{\mathbf{d}}$, $i=1,2,\dots ,n,$ $d$表示数据的维度，单个样本的核密度估计由下式给出:
$$\rho (\mathbf{x})=\frac{1}{n}\sum _{j=1}^n\frac{1}{h({\mathbf{x}}_j{)}^d}K(\frac{\mathbf{x}-{\mathbf{x}}_j}{h({\mathbf{x}}_j)})\text{\hspace{1em}(1)}$$
其中，$K()$是核函数，$h({\mathbf{x}}_j)$是${\mathbf{x}}_j$的内核函数的带宽。在我们的方法中，我们使用高斯核函数作为核函数，其定义如下:
$$K_{Gaussian}(\mathbf{x})=\frac{1}{(2\pi {)}^d}\text{exp}(-\frac{\Vert \mathbf{x}{\Vert }^2}{2})\text{\hspace{1em}(2)}$$
其中‖𝒙‖表示𝒙的范数。在实验中，对于核函数$h({\mathbf{x}}_j)$的带宽，我们计算所有样本与其邻居之间的距离的平均值作为带宽$h$。

  为了更好地测量样本的局部密度，我们通过样本的𝑘-近邻和反向𝑘-近邻来计算密度，而不是整个数据集。${\mathbf{x}}_i$的𝑘-近邻用$kNN({\mathbf{x}}_i)$表示。${\mathbf{x}}_i$的反向𝑘-近邻为那些包含${\mathbf{x}}_i$的𝑘-近邻样本${\mathbf{x}}_j$，记为$RkNN({\mathbf{x}}_i)$。这样，我们得到了${\mathbf{x}}_i$扩展后的最近邻集$EkNN({\mathbf{x}}_i)=kNN({\mathbf{x}}_i)\cup RkNN({\mathbf{x}}_i)$。利用扩展的最近邻集和代入等式(2)到等式(1)，在${\mathbf{x}}_i$处的局部密度可以得到:
$$\rho \left({\mathbf{x}}_i\right)=\frac{1}{k}\sum _{{\mathbf{x}}_j\in EkNN\left({\mathbf{x}}_i\right)}\frac{1}{(2\pi {)}^d{h}^d}\exp \left(-\frac{{\Vert {\mathbf{x}}_i-{\mathbf{x}}_j\Vert }^2}{2h^2}\right)\text{\hspace{1em}(3)}$$
其中$||{\mathbf{x}}_i-{\mathbf{x}}_j||$是${\mathbf{x}}_i$和${\mathbf{x}}_j$之间的欧式距离。

3.2. 有向密度比

  为了有效度量样本的离群程度，我们提出了样本有向密度比的概念，它结合密度、距离和方向来反映一个样本与其相邻样本之间的关系。样品的定向密度比为:
$$\overrightarrow{DRD}(i,k)=\sum _{j=1}^k\frac{\rho \left({\mathbf{x}}_j\right)}{\rho \left({\mathbf{x}}_i\right)}\overrightarrow{d\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)},{\mathbf{x}}_j\in EkNN\left(x_i\right)\text{\hspace{1em}(4)}$$
其中，式中$\rho ({\mathbf{x}}_i)$为式(3)计算的样本局部密度，$\overrightarrow{d\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)}$表示在特征空间中${\mathbf{x}}_i$到${\mathbf{x}}_j$向量，即$({\mathbf{x}}_j-{\mathbf{x}}_i)$，和$EkNN({\mathbf{x}}_i)$是3.1节中定义的扩展近邻集。

  式(4)结合了密度、距离和方向的信息。$\frac{\rho \left({\mathbf{x}}_j\right)}{\rho \left({\mathbf{x}}_i\right)}$为样本${\mathbf{x}}_j$与${\mathbf{x}}_i$的密度比，表示${\mathbf{x}}_j$对${\mathbf{x}}_i$的影响程度。$\rho ({\mathbf{x}}_j)$越大，$\rho ({\mathbf{x}}_i)$越小，说明$\rho ({\mathbf{x}}_j)$对$\rho ({\mathbf{x}}_i)$的影响越大。$\overrightarrow{d\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)}$包含了方向和距离信息。首先是距离信息。${\mathbf{x}}_i$离最近邻居越远，它越有可能是一个异常值。二是方向信息。对于一个正态分布的样本，其邻居的分布会比较有规律，也就是说$\overrightarrow{d\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)}$的方向会不一致。在这种情况下，改变$\overrightarrow{DRD}(i,k)$相对较小。然而，异常模式的样本其邻居的分布会更加不规则，即$\overrightarrow{d\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)}$很可能指向相似的方向。在这种情况下，$\overrightarrow{d\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)}$会改变很多。图1提供了有向密度比的直观表示。

图1. 有向密度比的定义   根据上述分析，有向密度比$\overline{DRD}(i, k)$代表了样本与其邻居之间的关系，而$\overline{DRD}(i, k)$的变化在一定程度上反映了样本的离群程度。因此，文中提出了一种基于有向密度比变化率的离群点检测器。 ## 3.3. 基于有向密度比的异常检测器

  我们用有向密度比变化率来衡量样本的离群程度，其定义公式如下:
$$\Delta DRD(i,k)=|\Vert \overrightarrow{DRD}(i,k+1)\Vert -\Vert \overrightarrow{DRD}(i,k)\Vert |\text{\hspace{1em}(5)}$$
其中$\Vert \overrightarrow{DRD}(i,k)\Vert$表示有向密度比的范数。$\Delta DRD(i,k)$反应了当$k$的尺寸增加时，有向密度比的变化度。根据3.2节的分析，$\Delta DRD(i,k)$变化越大，样本${\mathbf{x}}_i$是异常值的可能性越高。因此，我们通过对不同$k$值下的$\Delta DRD(i,k)$求和来计算最终样本的离群程度，如下式所示:
$$DCR=\sum _{k=1}^{K-1}\Delta (i,k)\text{\hspace{1em}(6)}$$
其中𝐾是人为定义的超参数。𝐷𝐶𝑅反映了$\Vert \overrightarrow{DRD}(i,k)\Vert$变化的积累。𝐷𝐶𝑅越大，说明样本越不正常。图2以合成的2d数据集为例，给出了本文方法的DCROD示意图。

图2. 所提出的方法示意图

  图2a显示了合成数据集在特征空间中的分布。正常样本(内点)形成类似于涡流分布的流形，而离群点在剩余空间中随机分布。通过公式(3)计算样本的局部密度后，得到具有密度表示的数据分布如图2b，密度较高的样本将以较大的点表示。然后计算样本的有向密度比;图2c显示了一些样本的有向密度比，包括离群点和内点。最后计算邻域大小𝑘增加时的有向密度比(𝐷𝐶𝑅)变化率，并绘制以𝐷𝐶𝑅分数表示的数据分布，如图2(d)所示。可以看出，基本上离群点会有较大的𝐷𝐶𝑅得分。算法的整体伪代码如算法1所示。

  计算离群值后，离群值大于阈值𝜃的对象将被判定为离群值。考虑到我们方法的优势之一是鲁棒性，我们使用中位数和中位数绝对偏差(𝑀𝐴𝐷)来计算阈值𝜃，而不是使用平均值和标准差，这是由于中位数对异常值的鲁棒性比平均值更强(Leys et al., 2013)。中位数是排在中间的对象值，阈值𝜃计算如下:
$$\{\begin{array}{l}\theta =\mathrm{median}(S)+a\cdot MAD\\ MAD=b\cdot \mathrm{median}(|S-\mathrm{median}(S)|)\end{array}\text{\hspace{1em}(7)}$$
式中𝑆为异常值分数，即我们方法中的𝐷𝐶𝑅分数;𝑎由用户决定，通常设置为2.5;Leys et al.(2013)建议𝑏为1.4826。

3.4. 复杂度分析

  本节将分析该方法的时间复杂度。DCR的时间复杂度取决于以下几个部分:
(1)使用kd树计算𝑘-NN图的时间为𝑂(𝑁∗𝑙𝑜𝑔𝑁),其中𝑁是实例的数据集;
(2)计算$\rho ({\mathbf{x}}_i)$的时间为𝑂(𝑁);
(3)计算离群点分数𝐷𝐶𝑅的时间为𝑂(𝑁∗𝐾)。
因此，DCROD的总时间复杂度为𝑂(𝑁∗𝑙𝑜𝑔𝑁)+𝑂(𝑁)+𝑂(𝑁∗𝐾)=𝑂(𝑁∗𝑙𝑜𝑔𝑁)，与以𝑘-NN为基础的其他方法一样，因为在我们的方法中，没有比寻找邻居的过程更复杂的计算。与不基于𝑘-近邻的方法相比，它们具有较低的时间复杂度，但所解决的问题与本文提出的方法不同。

4. 实验分析

4.1.数据集

  首先，为了更好地分析所提方法在不同数据分布下的离群点检测性能，使用了12个反映不同分布的2d合成数据集。数据集的样本数如表2所示，具体分布如图3所示。

图3. 合成数据集的分布

  此外，我们还使用了22个公开的真实离群点检测数据集进行实验，如表3所示。数据集的样本量范围在80到60632之间，离群点的百分比范围在数据维度在7~1555之间。在我们的实验中，数据经过最小最大归一化处理，其中每个特征被归一化为[0,1]。最小-最大归一化在实际应用中经常使用(Goldstein & Uchida, 2016)，本文中的评估也是如此。

4.2. 对比方法

  所提方法旨在检测不同数据分布下的全局和局部离群点，并解决大多数基于𝑘-近邻的方法对参数𝑘的选择很敏感的问题。因此，我们首先考虑基于𝑘-近邻的方法作为比较方法，包括LOF、COF、RDOS、KNN、LGOD和MOD+等等。此外，为了研究该方法与不是基于𝑘-近邻的性能比较，我们也选择其他方法，如IForest、HBOS和COPOD等等。表4描述了比较方法的细节。一些比较方法的实现可以在github上找到(Zhao et al，2019)。我们方法的实现可以在我们的github上找到。

  对于参数设置，对于所有基于𝑘-NN的方法，我们在𝑘上以2的步长从4到100计算所有结果。对于其他参数，我们使用文献中采用的默认参数。具体来说，IForest的基础估计器数量为100，CBLOF簇的数量
为10，MOD+的迭代次数为3，HBOS的bin数设置为4 ~ 100，步骤为2，得到所有结果。

4.3. 评估度量

  虽然对于异常值检测没有一个公认的评价指标，但常用的评价指标有两种: 曲线下的面积(Receiver Operator Characteristic，ROC )，以及精确率召回率(Precision-Recall，PR )曲线计算的F1得分。Davis和Goadrich讨论了PR和ROC曲线之间的关系，并表明对于给定的数据集，如果一条曲线在ROC空间占主导地位，那么它在PR空间也占主导地位(Davis & Goadrich, 2006)。因此，我们使用ROC曲线来衡量离群点检测的结果。ROC曲线为真阳性率与假阳性率的二维图，在所有可能的值𝑛的选择top-𝑛方法。ROC曲线可以用AUC来概括，即曲线下的面积，取值范围为0 ~ 1。AUC越高，离群点检测器的性能越好。为了验证所有基于𝑘-近邻的方法在不同的𝑘值下的实验结果，我们通过𝑘在步长为2中从4到100的所有AUC结果的平均值来评估所有基于𝑘-近邻的方法的性能。

4.4. 合成数据集的实验结果与讨论

  首先是在合成数据集上的实验结果，如表5所示。平均AUC最高的方法以粗体突出显示。实验结果表明，所提方法DCROD在2d合成数据集上表现良好，在6个数据集上排名第一，在3个数据集上排名第二，最低平均排名为2.00。具体分析每个数据集上的结果，我们可以看到在DS01和DS02存在局部离群点和正常样本形成不同密度簇的情况下，所提方法的平均AUC值DCROD表现良好，分别排在第2和第1位，表现出对局部异常点的准确检测。在DS03和DS04中，平均DCROD的AUC分别为第6位和第3位，低于LOF。实验结果表明，当正常样本构成点阵时，传统的基于密度的方法(如LOF)优于本文方法。这可能是由于正常数据形成点阵时，正常样本到其最近邻居的方向也有限，导致部分正常样本DCR得分较高，并对离群点产生误判。在具有不同流形的正常样本的DS05到DS12中，DCROD表现出良好的性能，表明DCROD能够适应二维数据集上的各种数据分布。

  为了分析实验结果，比较所提方法与所有比较方法之间的关系，对结果进行Wilcoxon符号秩检验(Demsar,2006)。该测试方法可以比较两种方法之间的差异，获得差异的方向。当𝑝-value小于𝛼(𝛼通常设置为0.05)时，两种算法表现相同的零假设被拒绝。那么可以认为这两种方法之间存在明显的差异，𝑅+和𝑅−之间的关系代表了差异的方向。表6显示了在AUC方面本文提出的方法DCROD和各种比较方法之间的Wilcoxon签名秩检验结果。

  从表中数据可以看出，DCROD与除COF外的其他方法有显著差异，优于COF方法。对于COF, DCROD也有87.06%的置信度优于COF。此外，在后续公开真实数据集上的实验可以看出，DCROD的性能明显优于COF。综上所述，从统计学角度来看，DCROD在这12个合成数据集上表现良好，在一定程度上优于对比方法。

图4. 不同合成数据集上所有参数平均AUC的箱线图

  为了更好地考察本文方法在整体数据集上的异常值检测结果，我们绘制了不同数据集上各参数平均AUC结果的盒图，如图4所示。可以看出，本文方法中值最高，方框最小，说明本文方法在合成数据集上具有准确稳定的离群点检测性能。

  为了分析该方法的检测性能在参数变化时的变化情况，我们绘制了不同参数下所有数据集平均AUC的盒图，如图5所示。具体来说，对于基于𝑘-NN的方法，参数是邻域大小𝑘。对于HBOS，这个参数是箱子的数量。对于具有随机性的方法，即CBLOF和IForest，我们应用了50次，得到了50个结果来绘制箱线图。对于没有任何参数和随机性的COPOD，我们只在箱线图中绘制了唯一的结果。可见所提方法具有最高的平均AUC和较小的方框，说明所提方法在参数变化时能够取得良好且相对稳定的离群点检测性能。

图5. 各合成数据集在不同参数上平均AUC的箱线图

  为了更好地分析所有基于𝑘-近邻的方法在参数𝑘变化时的离群点检测结果的变化情况，我们绘制了所有方法在参数𝑘变化时的AUC结果曲线𝑘变化来观察这些方法对𝑘值的稳定性。如图6和图7所示，所提方法在大多数数据集上都表现出了有竞争力的结果，且曲线波动较小，说明DCROD总体上可以取得稳定的离群点检测性能。

图6. 在不同的𝑘合成数据集上的实验结果

图7. 在不同的𝑘合成数据集上的实验结果。

  具体分析每个数据集的结果，在DS01到DS04具有不同密度的正态聚类和局部离群点的数据集上，所提方法基本能保持顶级的离群点检测精度之一，与其他基于密度的方法相比，在𝑘值较小的情况下能达到更高的离群点检测精度。在具有不同流形的DS05 ~ DS12数据集上，所提方法的性能也优于大多数其他方法。特别是对于DS08这样具有复杂流形的数据集，随着𝑘的增加，所提出的方法DCROD很快就达到了离群点检测的最佳性能，并且随着𝑘的不断增加，性能优于所有其他方法。表明DCROD能够适应更复杂的数据流形。

图8. DS08的实验结果   更具体地说，我们在DS08上绘制每种方法的具体离群点检测结果，如图8所示(𝑘= 40，阈值是真实离群点的比例)。由此可见，基于距离的方法，如KNN、LGOD和MOD，都受到数据分布流形的严重影响，将正常数据的尾部样本误判为离群点，而无法检测包裹在流形内的离群点。基于密度的方法，即LOF、COF和RDOS，不会误判尾部正态样本，但也会误判一部分正态流形中的样本为离群点。其中，LOF受流形影响最严重，而COF和RDOS通过优化密度计算降低了部分影响。该方法DCROD具有最好的离群点检测性能，能够检测出大部分的离群点，且未检测的离群点与正常流形极其接近，难以检测。由此可见，在复杂流形数据的情况下，DCROD具有更好的离群点检测性能。

4.5. 公开数据集的实验结果与讨论

  在公共数据集上的实验结果如表7所示。拥有最高平均AUC的方法以粗体突出显示。实验结果表明，该方法在22个数据集中有6个数据集DCROD排名第一。平均排名为4.32，排名最低，说明该方法的性能比较稳定，不会特别差。与图4和图5相似，我们绘制了两个不同方面的箱线图来展示方法的整体性能和稳定性，如图9和图10所示。

图9. 不同公共数据集上所有参数平均AUC的箱线图

图10. 所有公共数据集在不同参数上平均AUC的箱线图   图9为表7中不同数据集上平均AUC的箱线图，可以估计该方法对不同数据集的鲁棒性。图10为各数据集在不同参数下平均AUC的箱线图。具体来说，对于基于𝑘-NN的方法，参数是邻域大小𝑘。对于HBOS，该参数是容器的数量。对于具有随机性的方法，即CBLOF和IForest，我们应用了50次，得到了50个结果，绘制了箱线图。对于COPOD，它没有任何参数和随机性，我们只画出了一个和唯一的结果。

  由于不同数据集的AUC结果差异较大，图9中不同方法的性能差异不显著。但仍然可以看到，所提出的方法DCROD取得了令人满意的性能。如图10所示，本文方法优于其他所有方法，且差异显著，说明本文方法在参数选择上具有较强的鲁棒性，在不同参数下总体可以获得较好的检测结果。

图11. 不同𝑘在公共数据集上的实验结果

图12. 不同𝑘在公共数据集上的实验结果

图13. 不同𝑘在公共数据集上的实验结果

图14. 不同𝑘在公共数据集上的实验结果

  然后我们绘制基于𝑘-NN的方法在𝑘变化时的AUC变化曲线，观察这些方法相对于𝑘值的稳定性。从图11、图12、图13、图14可以看出，本文方法在大多数数据集上的结果都具有竞争力，且曲线波动较小，这说明DCROD在公开的现实世界离群点检测任务中可以获得稳定且满意的离群点检测性能。

4.6. 实验结果和执行时间的讨论

  评估算法的理论计算复杂度已经在第3.4节中讨论过了。然而，在实际操作中，实际的计算时间可能仍然会有很大的差异。因此，我们评估每个方法在所有公共真实数据集上的执行时间。实验中提到的方法是用Python 3.7实现的，使用的是带有Intel Core i7-6700的PC CPU @ 3.40 GHz和8 GB RAM。对于所有基于𝑘-NN的方法，KD-tree和Ball-tree用于加速搜索最近邻。

  为了更好地分析结果，根据数据大小𝑁:𝑁< 1000,1000 <𝑁< 10 000和𝑁 > 10 000.，将数据集分为三组。每个方法在一组数据集上的执行时间取平均值，结果如表8所示。

  从表8可以看出，对于小数据集(𝑁< 1000)时，所有方法的计算速度都足够快(小于1s)。在实际应用中，检测性能更受关注。对于中位数大小的数据集(1000< 𝑁< 10000)，基于𝑘-NN的方法的执行时间与其他方法类似(约为1s到3s)，除了COF，并且比其他方法慢，因为在这种情况下，搜索最近邻的计算需要更多的时间。DCROD的速度大约是KNN和LOF的3倍，主要是因为DCROD计算变化率也需要一些时间。对于大型数据集(𝑁>10000);在实验中，基于𝑘-NN的方法的执行时间远慢于其他方法，因为搜索最近邻的计算需要更多的时间，而其他方法的执行时间与数据集的大小成线性关系。值得注意的是，在这种情况下，该方法的执行时间与KNN和LOF方法非常接近，因为它主要依赖于搜索最近邻的计算量。

  综上所述，本文方法DCROD的执行时间与基于𝑘-NN的方法相似，尤其是在数据量较大的情况下。虽然其他方法，如HBOS和COPOD，比在合成数据集上的实验证实了DCROD无法解决多模式和局部异常点的问题。

5. 结论

  提出了一种基于有向密度比变化率的鲁棒异常检测方法。通过核密度估计和扩展近邻集计算样本的局部密度，然后将该样本与其近邻样本的密度比乘以相应的向量，得到定义的有向密度比。利用有向密度比有效度量样本在不同局部密度和分布流形下的离群程度。然后，通过增大最近邻的大小，计算样本的有向密度比之和的变化程度，并将其累加得到最终的离群点得分，从而降低参数𝑘对最终检测性能的影响。在12个模拟不同局部密度和分布流形的合成数据集上的实验结果表明，所提离群点检测方法能够有效适应各种分布，整体表现最优。同时，在22个公开的真实数据集上的实验结果表明，所提方法也具有稳定且令人满意的离群点检测能力，在所有数据集上的平均排名最低。此外，我们还分析了参数𝑘对所有𝑘-nearest近邻方法检测结果的影响，以验证所提方法对参数𝑘的鲁棒性。

  事实上，我们的方法仍然存在一些缺陷。虽然DCROD在二维数据集和大多数公开的真实世界数据集上表现良好，但在一些具有特殊分布的多维数据集上可能会失败。此外，DCROD在大数据集上速度不够快。因此，未来可能的研究重点是在具有特殊分布的真实数据集上利用附加信息进行更准确的离群点检测，以及在大数据集上加速所提方法。

---

参考文献

Aggarwal, C. C. (2017). Outlier analysis. Springer International Publishing.
Atkinson, A. C., & Hawkins, D. M. (1981). Identification of outliers. Biometrics, 37, 860.
Bhatti, M. A., Riaz, R., Rizvi, S. S., Shokat, S., Riaz, F., & Kwon, S. J. (2020). Outlier detection in indoor localization and internet of things (iot) using machine learning. Journal of Communications and Networks, 22, 236–243.
Boukerche, A., Zheng, L., & Alfandi, O. (2020). Outlier detection: Methods, models, and classification. ACM Computing Surveys, 53, 1–37.
Breunig, M. M., Kriegel, H. P., Ng, R. T., & Sander, J. (2000). LOF: identifying density-based local outliers. ACM SIGMOD Record, 29, 93–104.
Chen, L., Wang, W., & Yang, Y. (2021). CELOF: Effective and fast memory efficient local outlier detection in high-dimensional data streams. Applied Soft Computing, 102, Article 107079.
Davis, J., & Goadrich, M. 2006. The relationship between Precision-Recall and ROC curves. In Proceedings of the 23rd international conference on Machine learning (ICML 2006) (pp. 233–240).
Demsar, J. (2006). Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research, 7.
Domingues, R., Filippone, M., Michiardi, P., & Zouaoui, J. (2018). A comparative evaluation of outlier detection algorithms: Experiments and analyses. Pattern Recognition, 74, 406–421.
Goldstein, M., & Dengel, A. (2012). Histogram-based outlier score (HBOS): A fast unsupervised anomaly detection algorithm. In KI-2012: Poster and demo track.
Goldstein, M., & Uchida, S. (2016). A comparative evaluation of unsupervised anomaly detection algorithms for multivariate data. PLOS ONE, 11(4).
He, Z., Xu, X., & Deng, S. (2003). Discovering cluster-based local outliers. Pattern Recognition Letters, 24, 1641–1650.
Jin, W., Tung, A. K., Han, J., & Wang, W. (2006). Ranking outliers using symmetric neighborhood relationship. In PAKDD 2006: Advances in knowledge discovery and data mining (pp. 577–593).
Latecki, L. J., Lazarevic, A., & Pokrajac, D. (2007). Outlier detection with kernel density functions. Machine Learning and Data Mining in Pattern Recognition, 61–75.
Leys, C., Ley, C., Klein, O., Bernard, P., & Licata, L. (2013). Detecting outliers: Do not use standard deviation around the mean, use absolute deviation around the
median. Journal of Experimental Social Psychology, 49(4).
Li, Z., Zhao, Y., Botta, N., Ionescu, C., & Hu, X. (2020). COPOD: Copula-based outlier detection. In 20th IEEE international conference on data mining (pp. 1118–1123).
Liu, F. T., Ting, K. M., & Zhou, Z. H. (2008). Isolation forest. In 8th IEEE international conference on data mining (pp. 413–422).
Ramaswamy, S., Rastogi, R., & Shim, K. (2000). Efficient algorithms for mining outliers from large data sets. ACM SIGMOD Record, 29, 427–438.
Safaei, M., Asadi, S., Driss, M., Boulila, W., Alsaeedi, A., Chizari, H., Abdullah, R., & Safaei, M. (2020). A systematic literature review on outlier detection in wireless sensor networks. Symmetry, 12, 328.
Shyu, M. L., Chen, S. C., Sarinnapakorn, K., & Chang, L. (2003). A novel anomaly detection scheme based on principal component classifier. In 3rd IEEE international conference on data mining.
Tang, J., Chen, Z., Fu, A. W. C., & Cheung, D. W. (2002). Enhancing effectiveness of outlier detections for low density patterns. In PAKDD 2002: Advances in knowledge discovery and data mining (pp. 535–548).
Tang, B., & He, H. (2017). A local density-based approach for outlier detection. Neurocomputing, 241, 171–180.
Xie, J., Xiong, Z., Dai, Q., Wang, X., & Zhang, Y. (2020). A local-gravitation-based method for the detection of outliers and boundary points. Knowledge-Based Systems, 192, Article 105331.
Yang, J., Rahardja, S., & Fränti, P. (2021). Mean-shift outlier detection and filtering. Pattern Recognition, 115, Article 107874.
Zhao, Y., Nasrullah, Z., & Li, Z. (2019). PyOD: A python toolbox for scalable outlier detection. Journal of Machine Learning Research, 20.