基于最近邻关系的加权异常值检测方法

《Expert Systems with Applications》：Weighted Outlier Detection Method Based on Nearest Neighbor Relation

　　•一种结合局部密度与空间分布的新型异常值检测方法。•通过邻域熵对属性重要性进行自适应加权，从而提升检测精度。•所提出的加权最近邻异常值因子在16个数据集上的九种基准测试中均表现更优。•该方法具有很强的鲁棒性，且对参数k的敏感度较低。

引言
目前大多数异常值检测方法均为无监督学习方法，根据技术实现方式可大致分为三类：基于统计的方法（Bates, Candès, Lei, Romano, & Sesia 2023；Chander & Kumaravelan 2022；Mohseni, Duchaine, & Wong 2024）、基于聚类的方法（Abhaya & Patra 2023；Kiersztyn, Pylak, Horodelski, Kiersztyn, & Urbanovich 2024；Li, Zhu, Liao, Liu, & Zhang 2024），以及基于邻居的方法（Ayd?n 2023；Li等人2025；Zhang, Wang, Dong, & Li 2025b）。基于统计的方法主要关注样本的统计特性，在数据分布已知或可估算的情况下效果较好。但这类方法往往依赖于对数据分布的特定假设，而在现实数据中数据分布可能与假设模型不符，这限制了其应用范围。基于聚类的方法则是通过识别那些与簇中心距离极大的样本来检测异常值（Jain, Murty, & Flynn 1999），这类方法在处理具有复杂分布的数据时表现良好，但其性能很大程度上取决于所选的聚类算法以及对数据结构的假设。相比之下，基于邻居的方法因无需复杂的数学模型，且对数据分布的假设要求较低，因而受到了更多关注，它们能够更好地适应不同类型的数据。基于密度的方法是基于邻居方法的早期重要代表，至今仍是异常值检测领域的研究重点（Yuan等人2023；Zhang, Hou, Jia, & Zhang 2025a；Zhou, Xia, Yu, Cheng, & Li 2024）。这类方法基于这样的假设：异常值通常出现在数据集的低密度区域，而正常样本则周围环绕着较高密度的区域（Yuan等人2023）。其中应用最广泛的基于密度的方法之一是局部异常值因子（LOF）（Breunig, Kriegel, Ng, & Sander 2000），它通过衡量样本与其邻居之间的局部密度差异来检测异常值。尽管LOF在识别局部异常值方面效果不错，但在处理包含多个簇的数据集时却存在不足，常常会将位于簇边缘的内点误判为异常值。为解决这一问题，Influenced Outlierness（INFLO）方法（Jin, Tung, Han, & Wang 2006）引入了反向k最近邻概念，并优化了局部密度计算以提高检测精度。Local Outlier Probabilities（LoOP）方法（Kriegel, Kr?ger, Schubert, & Zimek 2009）则进一步通过将得分转化为概率来细化异常值的量化过程，从而使检测结果更具直观性和可解释性。Natural Outlier Factor（NOF）方法（Huang, Zhu, Yang, & Feng 2016）则通过自然邻居自动确定相关参数，以提高检测效率。Reversed k-Nearest Neighborhood Outlier Detection（RKNMOD）方法（Yang, Feng, & Yuan 2020）则结合了k最近邻和反向k最近邻概念，以此定义邻域空间，并通过相对距离来衡量异常程度。Directed Density Ratio Changing Rate-based Outlier Detection（DCROD）方法（Li等人2022a）则整合了核密度估计与扩展的邻居集合，从而捕捉局部密度变化，进一步提升检测精度。尽管许多基于密度的检测方法最初是为特定类型的数据设计的，但在处理数据中的不确定性及模糊性方面仍存在一定困难。在模糊-粗糙集框架下，Weighted Fuzzy-Rough Density-based Anomaly Detection（WFRDA）方法（Yuan等人2023）通过由模糊相似关系生成的粒状结构来定义模糊-粗糙密度，并通过模糊熵为属性赋值，将这些加权信息纳入异常值评分函数中用于检测，不过该方法并未考虑样本的邻居信息及空间分布情况。为克服这一缺陷，WOD方法引入了反向k最近邻粒化机制，从而有效捕捉样本的空间分布特征。为解决连续数据粒化及邻域半径选择的问题，邻域粗糙集理论（NRST）逐渐成为异常值检测领域的研究热点。Lin等人（Lin 1988）通过用邻域关系替代传统粗糙集中的等价关系，提出了NRST理论，使得连续数据也能进行粒化处理。此后，Hu等人（Hu, Liu, & Yu 2008）进一步发展了该理论，提出了δ-邻域粗糙集模型与k最近邻粗糙集模型，并将其应用于数值数据的粒化问题。Chen等人（Chen, Miao, & Zhang 2010）则将邻域粗糙集模型引入异常值检测领域，结合了相对邻域熵与属性集序列。尽管NRST在处理连续数据方面取得了进展，但邻域半径的选择依然是异常值检测中的一个重大挑战。通常情况下，这一参数需要手动设定，这种主观性会影响到模型的稳定性与适应性。为解决这一问题，Yuan等人（Yuan, Zhang, & Feng 2018）提出了一种自适应方法，通过将属性值的标准差与邻域半径调整参数λ相结合，用于基于邻域熵的异常值检测，不过该方法对参数λ的选择依然十分敏感。为进一步提升模型的适应性，Chen等人（Chen, Yuan, & Feng 2025）提出了一种自适应k最近邻粗糙集模型，该模型以样本的第k距离作为邻域半径，从而使粒化结果更加合理。在这一改进的基础上，人们又开发出了结合近似精度与局部密度的异常值检测方法，有效提升了检测的准确性与鲁棒性。为进一步克服NRST的局限性，研究人员还探索了其他利用邻居信息的异常值检测方法。例如，Korn等人（Korn & Muthukrishnan 2000）提出了反向最近邻（RNN）与反向k最近邻（RkNN）的概念，旨在充分利用样本的邻居信息。自提出以来，RkNN方法受到了广泛关注，并已被成功应用于聚类（Tang & He 2017）、异常值检测（Radovanovi?, Nanopoulos, & Ivanovi? 2014）以及分类（Tang & He 2015）等领域。在RkNN方法的基础上，研究人员又提出了多种改进方案，以满足不同的异常值检测需求。例如，Outlier Detection using Indegree Number（ODIN）算法（Hautamaki, Karkkainen, & Franti 2004）是通过统计样本的反向k最近邻数量来计算其异常值得分，不过其异常值判定仍然依赖于人为设定的阈值。为解决这一问题，Lin等人（Lin, Etter, & DeBarr 2008）提出了一种改进型的RkNN异常值检测方法，通过将没有反向k最近邻的数据点直接归类为异常值，简化了阈值设置流程。此外，Radovanovic等人（Radovanovi? et al. 2014）还提出了AntiHub与AntiHub2两种改进方法。AntiHub方法依旧依赖反向k最近邻的数量来进行异常值检测，而AntiHub2则考虑了数据样本与其邻居之间的反向k最近邻关系，从而能够更精确地描述数据中不同程度的异常情况。这些改进优化了基于邻居的异常值检测技术，也为相关研究指明了新的方向，进一步推动了该领域的进展。此外，样本的邻居信息在异常值检测中也起着至关重要的作用，主要包括邻居密度与邻居结构信息。邻居密度反映了样本在特征空间中的聚集程度，它是衡量样本分布密度的重要指标，对于异常值检测而言具有重要意义。在这一点上，邻居密度有助于识别那些偏离典型数据集模式的异常值。如果一个样本的邻居数量较少，且与其他样本存在显著差异，那么它很可能是异常值。传统方法通常假设异常值存在于低密度区域，主要依靠样本的局部密度来进行识别，因此，位于密集区域与稀疏区域边界处的正常样本很容易被误判为异常值。比如LOF算法（Breunig等人2000）就是通过分析样本的k最近邻来评估其是否为异常值，但该方法并未充分考虑样本的粒度结构或全局分布信息，因此在处理复杂数据分布时效果有限。而反向k最近邻方法则能提供额外的与粒度相关的信息（Tang & He 2017），有助于揭示数据的内在结构。通过将局部密度与反向k最近邻结合，WOD方法能够捕捉到全局的邻居覆盖情况，从而更精准地区分边界样本与真正的异常值，减少误报现象。另外，不同属性对异常值检测的贡献程度也各不相同。那些能够有效区分正常样本与异常值的属性至关重要，因此对属性进行识别与加权处理对于提升检测性能极为重要。然而，现实世界中的数据集往往存在不确定性与复杂性，这增加了异常值检测的难度。为克服这些挑战，可以利用邻域熵来量化数据集的不确定性，从而更准确地捕捉全局分布信息。通过为不同属性赋予适当的权重，加权后的属性能够更真实地反映其对异常值的影响，进而提升检测精度。本文提出的加权异常值检测（WOD）方法，结合了k最近邻粒化与反向k最近邻粒化技术，能够同时捕捉局部密度与全局邻居覆盖情况，从而更精准地区分边界样本与真正的异常值，同时减少误报。此外，为解决不同属性贡献不均衡的问题，WOD方法还利用邻域熵来量化数据不确定性，并为属性赋予权重，从而增强关键属性在异常值识别中的作用。通过整合样本分布、粒度结构与数据不确定性，该方法有效提升了异常值检测的性能。具体而言，该方法首先通过邻居关系来评估样本的局部密度，密度较低的样本更有可能被识别为异常值；接着，通过RkNN关系来捕捉数据中样本的空间分布情况；最后，通过邻域熵来量化数据不确定性，从而为各个特征分配权重。基于这些要素，本文定义了加权邻居异常值因子（WNOF），用以评估样本的异常程度。实验结果表明，所提出的方法在16个数据集上的表现均优于现有算法，不仅具备更高的检测精度，还具有更好的适应性。

本文结构如下：第2节介绍所提方法所需的预备知识；第3节阐述WOD方法；第4节展示对比实验及其分析结果；第5节给出结论并展望未来研究方向。

预备知识
本节介绍所提方法所需的预备知识。设U={x1,x2,…,xn}为一个非空的有限样本全集，其中每个样本xi∈U都由一组属性C={c1,c2,…,cm}来描述。对于C中的每一个属性ct，其值域记为Vct，所有Vct的并集则定义为整个值集V。函数f: U×C→V的作用是为每个样本xi和属性ct分配对应的值，使得对所有xi∈U和ct∈C都有f(xi,ct)∈Vct。给定一种距离度量Δ后，邻域信息系统（NIS）就可以用来表示样本之间的邻域关系。

WOD方法
为更充分地利用邻居信息，本文提出了一种基于最近邻关系的加权异常值检测方法，该方法重点考虑三个方面的因素：样本密度、粒度空间分布以及数据集的不确定性。该方法的目的是提升其在不同数据分布场景下的适应性。本节将介绍邻域信息、全局信息、加权最近邻异常值因子（WNOF）、相应的检测算法（WOD），以及相关的示例说明。

实验部分
在本节中，我们将通过实验来验证WOD方法的有效性，并分析其对参数k的敏感性。实验将采用多种评估指标，在16个数据集上将该方法与13种现有的异常值检测方法进行对比，系统地验证其准确性与有效性。本节还将介绍数据集的准备工作、实验设置、评估指标、结果分析以及参数敏感度分析等内容。

结论
本文提出了一种基于最近邻关系的加权异常值检测（WOD）方法，旨在整合样本分布信息、粒度结构以及数据不确定性信息，从而解决现有异常值检测方法在面对不同数据分布时的适应性难题。具体而言，WOD方法引入了加权最近邻异常值因子（WNOF），该因子结合了局部密度、粒子的空间分布情况以及属性的重要性，从而进一步提升检测性能。

CRediT作者贡献声明
Shan Feng：概念设计、方法论、原始稿撰写、正式分析、监督指导、审稿与编辑、资源协调
Xi Liu：软件工具使用、审稿与编辑、可视化处理、正式分析、方法验证
Xiaoling Yang：研究调查、方法论设计、审稿与编辑、方法验证、监督指导、资源协调

利益冲突声明
作者声明不存在任何可能影响本文研究成果的已知财务利益或个人关系。

Shan Feng | Xi Liu | Xiaoling Yang