基于KNN图谱谱分析的特征值空间异常值检测

《Neurocomputing》：Outlier detection in eigenvalue spaces based on spectral analysis of KNN graphs

　　贾莉|王晨旭|冯斯·J·费尔贝克
中国陕西省西安市西安交通大学软件工程学院，邮编710049

摘要
异常值检测是数据挖掘中的重要方法，它在各个领域都有广泛的应用。谱聚类因其能够有效应对高维空间中的维度灾难问题而备受关注。尽管谱聚类已被用于异常值检测，但现有方法通常依赖特征向量，缺乏同时处理局部和全局异常值的统一机制。本文提出了一种基于谱分析的异常值检测（SAOD）框架。首先，我们为每个样本构建最近邻图，并计算这些图中拉普拉斯矩阵的特征值。研究结果表明，异常值的特征值分布与正常值存在差异。基于这一观察，我们利用多元高斯核密度估计来实证分析给定数据集的特征值分布。随后，我们引入了一种新的异常值因子，该因子基于样本特征值的概率来评估其异常程度。通过合成数据集和真实数据集的实验结果表明，我们的基于谱分析的异常值检测方法优于现有的先进方法。相关实验代码可在以下地址获取：https://github.com/laetella/SAOD。

引言
现实世界的数据中往往同时存在噪声和异常值——那些与大多数数据有显著差异的样本，通常由不同于正常数据的机制产生[1]。检测这类异常值旨在找出数据集中的特殊模式，这一技术被广泛应用于多个领域[2]，包括数据挖掘[3]、机器学习[4]、网络安全[5]以及医学诊断[6][7]。例如在医学诊断中，常规模式被视为正常状态，而异常值则可能指示病理状况。作为许多机器学习任务（如分类和信号处理）中的关键数据处理技术，异常值检测能够在去除异常样本后，使用更干净的数据集进行模型训练。不过需要指出的是，异常值去除在本文所述范围之外也有重要意义。

一般来说，异常值检测方法主要分为四类[8]：基于分布的方法[9]、基于距离的方法[10]、基于密度的方法[11]以及基于聚类的方法[12]。基于分布的方法将不符合特定分布的样本视为异常值，但由于现实世界中的数据分布往往未知、非唯一或非标准，这类方法的适用性往往有限。为了解决这一问题，基于距离的方法将远离大多数样本的样本视为异常值[10]。基于密度的方法，如局部异常因子（LOF）[13]及其变体简化LOF[14]，通过评估点的局部异常程度，在不同密度分布下都能表现良好。为至少部分克服对模型参数敏感的缺点，人们提出了基于聚类的解决方案。这类方法首先对样本进行聚类，然后再找出不属于任何聚类的点[15]。此外，基于深度学习的异常值检测也因能在潜在空间中学习有效的表示而受到关注[16][17][18]。随着数据收集能力的提升，着眼于从不同来源查找异常值的多视角异常值检测也逐渐流行起来[19][20]。

为减少单一检测结果可能存在的偏差，人们致力于开发基于集成方法的技术，如基于集成的异常值检测（EBOD）[21]、可扩展无监督异常值检测（SUOD）[22]以及基于经验累积分布的异常值检测（ECOD）[23]。集成机器学习[21][24]通过整合多种成熟的检测算法来提升整体性能，其重点不在于开发新的检测器，而在于优化集成结构。因此，集成方法通常是通过与其他集成模型比较来评估的。在本研究中，我们提出了一种新的异常值检测方法，并通过充分实验验证了其可行性，因此未涉及集成机器学习的研究。未来，各类集成机器学习方法以及其他同类算法都可以从我们提出的方法中受益。

在机器学习任务中，一个亟待解决的问题是“维度灾难”，随着特征维数的增加，它会影响各种异常值检测算法在计算效率和内存使用方面的性能[25]。为了解决这一问题，基于空间变换的方法试图将原始数据映射到低维空间，从而更容易识别异常值。这类算法通常寻找一种能够将异常值与普通数据点有效分离的变换矩阵。其中，基于谱聚类的异常值检测利用拉普拉斯矩阵的特征向量来捕捉数据的关键结构信息。

近期的理论研究表明，基于谱分析的异常值检测方法取得了令人满意的结果[26]。以往的方法往往依赖于最近邻图中第二小特征值对应的概率[26]。相比之下，我们的研究旨在充分利用整个特征值谱中的信息。为此，我们使用高斯核密度估计来分析特征值分布。与以往方法不同，我们的算法首先计算最近邻图的亲和矩阵及其对应的未归一化拉普拉斯矩阵。为降低其他因素的影响，我们采用固定的核带宽而非自适应带宽。由于异常值通常比正常值具有更高的方差，其拉普拉斯矩阵的特征值对应的出现概率往往更低。因此，拉普拉斯矩阵的特征值分布可作为异常值检测的判别特征。为进一步验证特征值在异常值检测中的作用，我们分析了特征值分布的影响，并利用多元高斯KDE来评估样本的异常程度。在某些情况下，我们可能需要明确判断一个点是否为异常值，此时可以为异常值得分设定阈值。

本研究的贡献主要有三点。首先，我们提出了一种基于谱分析的异常值检测（SAOD）框架，该框架利用最近邻图的特征值分布。其次，我们运用多元高斯KDE来估计特征值空间中特征值的概率，并基于概率密度定义了一种新的异常值因子。最后，我们通过使用合成数据集和真实数据集，将我们的算法与十余种先进的异常值检测方法进行比较，全面评估了其性能。

本文的其余结构如下：第2节回顾相关研究；第3节详细介绍我们的基于谱分析的异常值检测算法；第4节阐述实验结果，补充材料中还提供了更多支持数据；最后，第5节总结本研究并指出未来工作的方向。

片段摘录
基于密度的异常值检测
基于密度的异常值检测通过比较数据点所在局部邻域的密度来评估其异常程度。这一类别中的经典方法是局部异常因子（LOF），由Markus提出[13]，该方法通过比较数据点的局部密度与其邻居的密度来评估其异常程度。在此概念基础上，FindCBLOF算法被提出，它利用基于聚类的局部异常因子（CBLOF）来识别异常值；该算法首先对数据集进行聚类。

基于谱分析的异常值检测
本节介绍所提出的方法。我们首先阐述该方法的理论依据和框架概述，随后详细讲解谱分析及其在异常值检测策略中的应用。

实验
本节描述了一系列实验，用于评估SAOD的性能。实验代码可在github上获取。我们使用18个不同的数据集，将SAOD与十余种基准算法进行了比较。我们的算法和KDEOS方法是根据原始论文[30]用Python实现的，其他方法则来自PyOD Python包[52]。所有实验都在一台配备Intel? Core? 3.2 GHz i5-3470处理器和8GB内存的计算机上完成。

结论
异常值检测的目的是找出数据集中的特殊模式。然而，在复杂的现实场景中，现有方法往往难以准确识别真正的异常值。为了解决这一问题，本文提出了一种新的异常值检测框架SAOD，该框架利用谱分析和特征值的高斯核密度估计。最近邻图的特征值分布与高斯KDE的结合，使得该方法在多种合成数据集和真实数据集上均表现出良好的性能。

CRediT作者贡献声明
贾莉：撰写——初稿、验证、方法论、形式分析、概念设计。王晨旭：撰写——审阅与编辑、指导、方法论、资金获取、概念设计。冯斯·J·费尔贝克：撰写——审阅与编辑、指导。

利益冲突声明
作者声明没有已知的财务利益或个人关系可能影响本文所述的工作。

致谢
本文的研究得到了国家自然科学基金（编号62272379、T2341003）、陕西省自然科学基础研究计划（2024JC-YBQN-0815、2025JC-JCQN-081）以及西安交通大学人工智能研究基金（2025YXYC004）的部分支持。我们衷心感谢王晓春在概念设计和方法论方面给予的帮助。贾莉是中国西安交通大学和荷兰莱顿大学的联合博士，她的研究兴趣在于机器学习，尤其专注于异常值检测。她的研究致力于开发新型算法，以识别复杂和高维数据中的异常现象。