arXiv:2505.08489cs.LGcs.DM2025-05被引 1

改进孤立树算法,让新奇数据更容易被识别。

Isolation Forest in Novelty Detection Scenario

  • 利用树结构高层节点更易隔离新奇数据的特性
  • 理论证明新方法使新奇点平均深度显著增加
  • 适合需要可解释性的实时异常检测场景

数据挖掘为从复杂数据中提取有意义结构提供了丰富工具,其中异常检测在流式或实时数据背景下尤为关键。新颖性检测专注于仅用正常数据训练后识别此前未见的模式。尽管一类支持向量机(One-Class SVM)或局部离群因子(LOF)等经典算法广泛应用,但往往缺乏可解释性和可扩展性。本文探讨了最初用于流式异常检测的半空间树(HST)算法,并提出一种新的理论改进,使其专用于新颖性检测任务。该方法基于异常(即新奇点)倾向于出现在树的高层节点、而正常实例较少访问这些节点的假设。通过概率分析、期望深度(EXD)计算和组合推理,我们理论证明了该方法的有效性。与原始孤立森林相比,新方法在期望深度上对新奇点有更显著的隔离效果,验证了半空间树经适当结构调整后可作为可解释且高效的新型检测器。论文为此类适应提供了理论基础与分析支持,为后续应用与实验奠定基础。

原文摘要 · Abstract (English)

Data mining offers a diverse toolbox for extracting meaningful structures from complex datasets, with anomaly detection emerging as a critical subfield particularly in the context of streaming or real-time data. Within anomaly detection, novelty detection focuses on identifying previously unseen patterns after training solely on regular data. While classic algorithms such as One-Class SVM or Local Outlier Factor (LOF) have been widely applied, they often lack interpretability and scalability. In this work, we explore the Half-Space Tree (HST) algorithm, originally proposed for streaming anomaly detection, and propose a novel theoretical modification to adapt it specifically for novelty detection tasks. Our approach is grounded in the idea that anomalies i.e., novelties tend to appear in the higher leaves of the tree, which are less frequently visited by regular instances. We analytically demonstrate the effectiveness of this approach using probabilistic analysis, expected depth (EXD) calculations, and combinatorial reasoning. A comparative analysis of expected depths between our modified HST and the original Isolation Forest highlights that novelty points are significantly more isolated in our approach. This supports the hypothesis that HSTs, with appropriate structural adaptation, can serve as interpretable and efficient novelty detectors. The paper contributes a theoretical foundation and supporting analysis for this adaptation, setting the stage for further application and experimentation.

异常检测孤立树可解释性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。