快速且稳健的异常值检测方法：基于颗粒球中心隔离与区域一致性策略

《Pattern Recognition》：Fast and robust outlier detection: A granular-ball center isolation and region consistency approach

异常检测方法，k-NN算法，GBCI全局孤立度，GBCRC区域一致性，鲁棒性

　　

王荣祥|万继红|李晓萍|谭帅帅

广东工业大学计算机科学与工程学院，广州，510006，中国

摘要

异常值检测是数据挖掘中的关键任务，旨在识别偏离正常分布的异常对象。基于k最近邻的检测方法是广泛使用的技术之一。然而，随着数据规模的增加，为每个对象查找k最近邻的过程变得极其耗时。此外，如果对象的邻居包含噪声，可能会干扰其与邻居之间的关系计算，从而影响检测性能。为了解决这些问题，本文提出了一种基于颗粒球（GB）中心隔离和区域一致性的快速且鲁棒的异常值检测方法，称为FROD。具体来说，生成GB是第一步。通过生成不同粒度的GB来覆盖数据集。然后，通过计算GB中心隔离度（GBCI），评估不同GB中心相对于其他GB中心的隔离程度。从全局角度来看，GBCI间接反映了每个GB中心在整体数据分布中的位置和隔离情况。进一步地，通过计算对象的GB中心区域一致性（GBCRC），可以测量对象与其所属GB中心邻域之间的接近程度。从局部角度来看，GBCRC反映了对象与其所属GB中心邻域内数据分布的相关性。最后，通过结合GBCI和GBCRC，可以得到每个对象的异常值因子，并设计相应的检测算法。实验结果表明，FROD在检测效率和准确性方面表现优异，并且在噪声环境中表现出良好的鲁棒性。

引言

异常值检测作为数据挖掘中独特而重要的研究任务，旨在识别与大多数数据显著不同的异常值[1]。在大多数数据挖掘任务中，异常值通常被视为噪声并被丢弃[2]。然而，在某些应用中，来自少数类的异常值往往比正常数据点更有价值。例如，在金融领域的欺诈检测[3]、网络安全领域的入侵检测[4]、制造领域的故障诊断[5]以及医疗数据中的异常检测[6]等。

基于距离[7]和基于密度[8]的异常值检测方法是目前最常用的异常值检测技术。这些方法通常依赖于k最近邻（k-NNs）的概念[9]。基于距离的方法通过计算每个对象与其k-NNs之间的距离关系来评估该对象是否为异常值。基于密度的方法评估对象邻域内的区域一致性，并通常将低密度区域中的对象视为异常值[10]。尽管基于k-NNs的异常值检测方法在许多应用中表现良好[11]，但它们仍然面临以下挑战：（1）这些方法通常需要为每个对象查找k-NNs。随着数据集规模的增加，这一过程变得非常耗时，导致基于最近邻的异常值检测方法效率低下。（2）当对象的k-NNs包含噪声时，这些噪声可能会干扰距离或密度计算，从而导致正常点被错误分类为异常值或真实异常值被忽略，从而降低模型的准确性。

为了解决上述基于k-NNs的异常值检测方法所面临的挑战，本文引入了颗粒球（GB）计算[12]，并提出了一种基于GB中心隔离（GBCI）和区域一致性（GBCRC）的快速且鲁棒的异常值检测方法，称为FROD。该方法首先生成不同粒度的GB来覆盖整个数据集。随后，利用GBCI和GBCRC来表征对象的分布特征，以有效识别异常值。本文的贡献如下：

(i)

该方法创新性地定义了一个全局指标GBCI和一个局部指标GBCRC，协同表征数据分布以进行异常值检测。与传统的全局指标不同，GBCI通过计算其中心与其他GB中心之间的平均距离来量化每个GB的全局隔离度，为GB内的对象提供初步的全球异常值程度评估。另一方面，GBCRC使用其中心的k-NNs构建GB的核心区域，并通过计算该对象与核心区域内对象的距离来评估对象的局部结构一致性，而不是使用对象自身的k-NNs进行计算。通过整合全局和局部信息，该方法实现了异常值的准确识别。

(ii)

在计算GBCRC时，使用对象GB中心的k-NNs而不是对象自身的k-NNs来评估区域一致性。由于GB的数量远小于数据集对象的数量，这种方法显著减少了k-NN搜索时间，提高了检测效率。此外，GB中心是通过加权平均计算的，以减轻噪声的影响，确保其k-NNs几乎无噪声。与依赖于对象自身k-NNs且容易受到噪声干扰的传统局部指标不同，这种设计避免了噪声对GBCRC计算的影响，提高了异常值检测的准确性和稳定性。

(iii)

通过将FROD与20个数据集上的几种基于k-NNs和非k-NNs的检测方法进行比较，FROD不仅表现出优异的检测准确性，还具有较高的检测效率。此外，FROD还表现出一定的抗噪声能力。

本文的结构如下：第2节介绍了相关工作。第3节详细介绍了本文提出的方法。第4节进行了对比实验并分析了结果。第5节给出了总结和展望。

相关研究

异常值检测方法主要可以分为基于统计的[13]、基于k最近邻（k-NNs）的[14]、基于模糊粗糙集的[15]和基于深度学习的[16]方法。近年来，基于深度学习的方法在复杂的高维数据中表现出色。这一成功在很大程度上归功于它们强大的表示学习能力，能够从原始数据中自动提取层次化和区分性特征[18]

提出的方法

为了解决现有基于k最近邻（k-NNs）检测方法所面临的挑战，本节提出了一种快速且鲁棒的异常值检测方法（FROD）。

实验

本节通过对比实验系统评估了FROD的有效性（即检测准确性和检测效率），在二十个数据集上与九种检测方法进行了比较。对于准确性评估，使用了ROC曲线、AUC值、箱线图和统计测试等方法。检测效率的评估是通过比较不同算法在同一数据集上的检测时间来进行的。此外，还进行了噪声实验

结论与未来工作

为了解决传统基于k最近邻方法的效率低下和噪声敏感性问题，本文提出了一种基于颗粒球中心隔离和区域一致性的快速且鲁棒的异常值检测（FROD）方法。实验结果表明，FROD在20个数据集上表现优异，有效减轻了噪声干扰，同时实现了高检测准确性和更快的处理速度。然而，FROD的稳定性有所下降

CRediT作者贡献声明

王荣祥：撰写 – 审稿与编辑，撰写 – 原稿，可视化，验证，软件，方法论，调查，形式分析，概念化。万继红：撰写 – 审稿与编辑，监督，资源获取。李晓萍：撰写 – 审稿与编辑，监督，资金获取。谭帅帅：撰写 – 审稿与编辑，监督。

利益冲突声明

作者声明他们没有已知的可能会影响本文所述工作的竞争性财务利益或个人关系。

致谢

本工作得到了国家自然科学基金（项目编号：62406079和62273089）、CPSF博士后奖学金计划（项目编号：GZC20230571）以及国家重点研发计划（项目编号：2022YFB3305500）的支持。