基于数据驱动的支配树混合属性数据异常检测方法

《Neurocomputing》：Data-driven dominance tree-based anomaly detection for mixed attribute data

　　摘要：在混合数据分布场景中实现精确的异常检测仍是一项极具挑战性的任务。基于图的异常检测是一种有效表示数据分布中结构关系的重要技术，但其性能在很大程度上取决于图结构的质量。本文在图结构优化的指导下，提出了一种针对混合属性数据的基于数据驱动的支配树异常检测方法。在图构建阶段，对初始图进行多轮结构优化，从而构建出包含更丰富信息的高质量支配树。基于该树，进一步设计了一种合理且可解释的基于路径的异常评分方法。首先，利用数据对象的混合属性信息构建初始图；其次，通过数据对象间的支配关联关系进行多轮图结构优化，生成支配树结构；第三，结合支配树的结构信息与节点密度信息来表征对象间的连接强度，以此更准确地反映对象间的相关性；最后，沿着对象到其在支配树中根节点的路径，利用累积连接强度来评估该对象的异常程度。在12个合成数据集和27个真实世界数据集上与13种主流算法进行的实验比较结果表明，所提方法的整体异常检测性能更为优异。在27个真实世界数据集上，其平均AUC值达到0.9303，比最优对比方法高出3.12%；在12个合成数据集上，其平均AUC也达到了0.9981。此外，该方法还适用于分类型、数值型和混合类型数据。相关代码可在https://github.com/YangGS119/DDTAD地址获取。

引言：异常检测是数据挖掘和知识发现领域中的一个重要研究课题，其目标是在给定数据集中识别出那些特征模式与正常对象存在显著差异的对象[1]。通常，异常对象在其特征描述中会包含冗余或干扰性信息，而这些信息可能蕴含具有较高应用价值的知识[2]。目前，异常检测技术已被广泛应用于诸多领域，如监控视频异常检测[3]、金融欺诈检测[4]、网络入侵检测[5][6]、工业故障诊断[7][8][9]以及社交媒体异常分析[10]等。目前已有多种异常检测方法被提出，这些方法大致可分为几类：基于统计的方法、基于距离的方法、基于密度的方法、基于聚类的方法以及基于图的方法。对于基于统计的方法，假设数据遵循特定的参数分布，异常则是偏离该分布的对象[11][12]；基于距离的方法则直接通过对象间的距离来检测异常[13]；基于密度的方法则是通过比较对象间的局部密度来识别异常[14]；基于聚类的方法会将数据划分为不同的簇，将不属于任何簇或处于极小簇中的对象视为异常[15][16]；而基于图的方法则利用图结构来发现异常的模式和对象[17]。在现实应用场景中，对象往往不能被视为数据空间中的独立点，它们之间通常存在复杂的相互依赖关系，因此在异常检测时需要考虑对象间的关联信息。图结构能够有效地表征这类相互依赖关系，而且由于其具备强大的表示关系和结构信息的能力[18]，因此能够很好地解决复杂场景下的异常检测问题。然而，对于基于图的方法而言，其检测性能在很大程度上取决于所构建图的质量。如果初始图构建不佳，检测性能就会下降。对于传统的图方法[19]，通常会直接从原始图模型本身提取对象的结构特征，如节点的外度或内度信息，然后将这些特征与其他数据分布特征相结合，形成用于异常识别的特征空间[18]。这类方法一般会采用基于距离的技术，如k最近邻图、ε-邻域图和B匹配图等[20]，来直接构建图结构。不过，面对具有复杂分布的数据时，基于距离的图结构质量可能会受到限制，因为它们无法真正反映数据中蕴含的结构信息。另一种方法则是利用图结构来衡量节点的重要性，随机游走就是其中的例子之一[17]。为确保随机游走过程收敛到平稳分布，通常会对初始图进行连通性优化，这种优化可以通过添加边[21]或合并多个图来实现[22]。优化之后，图通常能够满足算法的要求，但往往会出现许多对异常检测并无必要的冗余边，这些边可能会干扰重要图结构信息的提取。此外，深度学习方法则利用神经网络强大的图结构表示能力，通过连接节点间的聚合操作，获得表达能力较强的图结构表示[23]。尽管深度学习能够有效地表示图的结构信息，但它存在过平滑的问题，而且其检测结果的可解释性较差[23]。总体而言，图结构为异常检测提供了有效的信息载体，但为异常检测构建高质量的图结构仍是当前各类研究方法面临的一个挑战。为应对上述挑战，本文提出了一种针对混合属性数据的基于数据驱动的支配树异常检测方法。该方法以图结构优化的理念为指导，采用多轮优化流程，逐步提升图结构的质量。首先，利用密度支配关系优化初始图结构，从而生成支配图结构；接着，再利用支配连通相似性进一步优化支配图结构，最终得到支配树结构。这样一来，图结构的质量就能得到有效提升，同时也能增强在复杂数据分布中识别关键结构信息的能力。在此基础上，还将支配树中的结构信息与节点密度分布信息相结合，从而量化节点间的连接强度。支配树对应于某一领域内的客观数据分布，通过计算从节点到其在树中根节点的路径上的累积连接强度，就可以对每个数据对象进行异常评估。本文的创新之处在于，通过数据驱动的方法和多轮图结构优化，构建了一种用于无监督异常检测的新型图结构，这种结构既能准确描述底层数据分布，又能突出异常节点的特征，从而在复杂数据分布场景中实现更精准的异常检测。本文的主要贡献包括：(1)提出了一种支配连通相似性度量方法，该度量为多轮图结构优化和异常检测提供了理论基础，同时也使得数据对象间相关性的表征更加准确；(2)基于支配连通相似性开发了一种多轮图结构优化方法，该方法提升了所构建图的质量，进而能更好地识别复杂数据集中的分布结构信息；(3)设计了一种基于累积连接强度的可解释异常评分方法，该方法依赖于支配树结构，且适用于分类型、数值型和混合属性三种类型的数据。本文的其余部分结构如下：第2节介绍相关研究工作，第3节探讨数据驱动的支配树构建方法，并构建异常检测框架，第4节给出实验比较分析结果，第5节对全文进行总结。

相关研究工作：图结构已被广泛用于表示具有复杂分布信息的数据的结构形式，在药物发现、分布式系统、欺诈检测以及社交网络分析等领域都展现了重要的应用价值。在基于图的异常检测中，数据信息会被转换为图表示形式，图节点代表对象，边则代表对象之间的关联关系，通过所构建的图结构，可以……

所提出的方法：本节将对DDTAD模型的理论进行系统阐述，相关主要符号汇总于表1中。

实验结果与分析：为进一步评估DDTAD方法的性能，本节将DDTAD与13种竞争算法在12个合成数据集和27个真实世界数据集上进行了对比实验，随后还进行了统计检验、消融实验以及模型参数敏感性分析。

讨论与结论：DDTAD通过多轮图结构优化构建支配树，并基于累积连接强度进行异常评分。对比实验结果表明，在12个合成数据集和27个真实世界数据集上，DDTAD的平均AUC值和平均最佳F1值均优于13种主流对比方法，这证明了支配树结构在异常检测中的有效性。同时，DDTAD还能处理分类型、数值型和混合类型数据。

作者贡献说明：杨光帅：写作——审稿与编辑、写作——初稿撰写、可视化、验证、软件开发、方法设计、概念构思；冯珊：写作——审稿与编辑、验证、项目监督、项目管理、资金申请；杨晓玲：项目监督、方法设计、资金申请；袁忠：项目监督、方法设计、资金申请；王小红：验证、概念构思。

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

致谢：本研究得到了国家自然科学基金（62306196）以及四川省自然科学基金（2024NSFSC0443、2024NSFSC0486、2025ZNSFSC0873）的支持。杨光帅毕业于中国成都四川师范大学，获信息与计算科学学士学位，目前在该校攻读硕士学位，研究兴趣包括模糊集合和异常检测。杨光帅|冯珊|杨晓玲|袁忠|王小红，中国成都四川师范大学计算机科学学院，邮编610101。