技术摘要：用于无监督异常检测的随机化主成分分析森林

问题陈述

异常检测是数据挖掘和机器学习中的基本任务，对于入侵检测、故障诊断和欺诈检测等应用至关重要。尽管新颖算法层出不穷，但综合评估表明，K 近邻（KNN）和局部异常因子（LOF）等经典方法往往仍处于最先进水平。这些方法有效应对了正常数据与异常数据之间边界模糊以及噪声存在等挑战，但由于需要进行精确的最近邻搜索，它们面临计算复杂度过高的问题。虽然孤立森林（iForest）等基于树的方法提供了效率，但它们依赖随机特征选择，这可能无法始终有效地捕捉高维数据的潜在结构。因此，需要一种方法在计算效率与鲁棒性之间取得平衡，利用降维技术，同时不牺牲检测全局和局部异常的能力。

方法论

作者提出了一种基于随机化主成分分析（RPCA）森林的新型无监督异常检测方法。该方法将原本设计用于近似 K 近邻（KNN）搜索的 RPCA 森林调整为用于异常检测，通过从森林的内在属性中推导出具体的异常分数。

核心组件

1. RPCA 森林构建：

   • 该方法构建了一个树集成。与随机选择特征的 iForest 不同，RPCA 森林在每个节点利用随机化 PCA（Halko 等人，2011）。
   • 在根节点及后续节点，数据点使用少量主成分（$p$）投影到较低维的子空间中。这在降低维度的同时保留了原始特征空间的信息价值。
   • 分裂准则： 算法不是进行随机切割，而是从以均值为中心的拉普拉斯分布中为每个主成分采样分裂点。数据点根据 $p$ 个分量上的多数投票被分配到左子节点或右子节点。
   • 停止准则： 树的生长持续进行，直到叶节点包含的点数小于或等于预定义的邻域大小（$k$）。

2. 异常分数公式化：
   该方法通过结合两个不同的准则，为查询点 $q$ 定义异常分数（$RPCAForestScore$）：

   • 基于深度的异常性（$P(q)$）： 基于异常值通常在树中较早被隔离（深度较浅）的观察结果。这是通过计算包含 $q$ 的叶节点在整个森林中的归一化逆深度得出的。
   • 基于距离的异常性（$\mu_{dist}(q)$）： 计算为查询点 $q$ 与原始特征空间中同一叶节点内所有其他点之间的平均欧几里得距离。
   • 最终分数： 最终分数是这两个分量的乘积：
     $$RPCAForestScore(q) = P(q) \times \mu_{dist}(q)$$
     这种组合确保了即使异常值因投影而被归入包含正常值的叶节点，其在原始空间中与聚类中心的较大距离也会导致较高的异常分数。

3. 分类：
   使用污染参数（$\alpha$）确定异常阈值，该参数代表预期的异常值百分比。分数超过分数分布的 $(1-\alpha)$ 分位数的点被标记为异常值。

主要贡献

• 新颖的整合： 本文首次将 RPCA 森林专门应用于无监督异常检测，弥合了近似最近邻搜索与异常检测之间的差距。
• 混合评分机制： 提出了一种复合异常分数，利用结构隔离深度（类似于 iForest）和原始特征空间中的局部密度/距离（类似于 KNN/LOF），旨在克服单独使用任一指标的局限性。
• 通过随机化 PCA 实现效率： 通过采用随机化 SVD，该方法实现了高计算效率，特别是对于高维数据，因为其复杂度取决于主成分的数量而非完整的数据维度。
• 鲁棒性： 该方法设计为对超参数调整具有鲁棒性，仅需选择树的数量、主成分数量（$p$）和叶节点大小（$k$）。

实验结果

作者在标准基准存储库的22 个多样化数据集上评估了该方法，将其与包括 KNN、KNNW、LOF、SLOF、ODIN、DAO 和 iForest 在内的经典及最先进方法进行了比较。性能使用接收者操作特征曲线下面积（AUC）进行衡量。

• 性能： RPCA 森林在许多数据集上表现出优越或第二好的性能，并在其他数据集上保持竞争力。它在 iForest（使用随机特征选择）表现挣扎的高维数据集上显示出特别的优势。
• 鲁棒性： 该方法仅使用两个主成分设置（$p=1$ 和 $p=5$）就保持了竞争力，而竞争方法则测试了 100 种不同的超参数配置。这表明所提出的方法对超参数调整的敏感度较低。
• 消融研究： 分离基于深度和基于距离的组件的实验表明，组合分数显著优于基于深度的组件，并且通常与或优于单独的基于距离的组件。
• 效率： 虽然 iForest 仍然是最快的方法，但随着数据集规模的增加，RPCA 森林显示出比基于 KNN 的方法显著更好的可扩展性，保持了适合大数据的高效运行时间。
• 观察到的局限性： 该方法在特定数据集（如 ALOI、InternetAds、Annthyroid、Wilt）上表现较低。作者将此归因于：
  • 高维性导致少数主成分（$p=1, 5$）不足以隔离异常值（InternetAds）。
  • 异常值与正常值非常相似，需要比所选 $p$ 能提供的更多信息（Annthyroid, Wilt）。
  • 具有特定特征提取的数据集中局部与全局异常值的性质（ALOI），其中局部结构方法（LOF）优于全局投影方法。

意义与主张

本文声称，RPCA 森林为无监督异常检测提供了一种鲁棒且计算高效的替代方案。其意义在于能够：

1. 平衡效率与准确性： 它提供了一种“白盒”方法来近似邻域搜索，利用树的内部分结构（通过 PCA 投影），而不是将搜索视为黑盒。
2. 良好的泛化能力： 该方法在广泛的数据集上表现具有竞争力，无需进行详尽的超参数优化，解决了许多新颖方法仅在特定问题实例上表现优异的问题。
3. 检测全局和局部异常值： 理论上，该方法旨在检测全局异常值（通过树中的早期隔离）和局部异常值（通过深层节点中的距离度量），尽管作者承认在聚类异常方面存在局限性。

作者总结道，虽然该方法并非适用于所有异常类型（特别是聚类异常）的通用解决方案，但它代表了通用异常检测的强力选择，在基于树方法的计算速度和基于距离方法的准确性之间提供了有利的权衡。