编辑推荐：
随机森林聚类方法通过锚图构建和虚拟路径相似性度量优化计算效率与聚类性能，采用分层K-means生成代表性锚点，结合负样本生成和稳定性感知的集成选择策略，在8个数据集上显著提升聚类准确率并减少运行时间。
Jinyu Li|Congyu Wang|Mingjing Du
江苏省教育智能技术重点实验室，江苏师范大学人工智能与计算机科学学院，徐州，221116，中国
摘要
随机森林（RF）聚类利用决策树提取相似性信息以进行聚类，但现有方法通常存在计算成本高以及不考虑决策树贡献程度的问题。为了解决这些限制，我们提出了一种基于锚图（RFAG）的随机森林聚类方法。该方法包括两个阶段：训练和聚类。在训练阶段，生成具有代表性的锚点以构建锚图，从而降低计算成本。然后在由锚点和生成的负样本组成的伪标记数据集上训练二分类随机森林模型。在聚类阶段，通过基于虚拟路径的度量从训练好的决策树中提取锚点之间的相似性。一种考虑稳定性的集成选择策略用于选择贡献较大的决策树来划分锚点，并通过锚图将聚类结果映射到数据点上。在8个真实世界数据集上的实验表明，与7种基线方法相比，RFAG显著减少了计算时间，同时保持了或提高了聚类性能。
引言
随机森林（RF）[1]是一种由多个决策树组成的集成学习模型，因其鲁棒性和在模式识别和机器学习中的有效性而广受认可。这种优势源于在训练单个决策树时引入的随机性，这些决策树随后被聚合成一个强大的最终模型。尽管RF在回归和分类任务中表现良好，但其在聚类应用中的潜力仍相对未被充分探索。
作为一种无监督学习方法，RF聚类不直接使用类别标签信息。一种常见的方法是通过对锚点进行边际随机采样来生成负样本，从而将聚类任务转化为二分类问题。RF聚类利用其决策树集成提取样本之间的相似性信息，将这些信息转换为相似性矩阵，并最终通过共识聚类算法产生聚类结果。然而，现有的RF聚类方法仍面临一些挑战。首先，RF聚类中的相似性信息是通过追踪每个数据点在所有决策树中的路径来获得的，这需要遍历每个数据点的整个树结构，从而显著增加了计算时间和内存消耗。此外，这些方法使用所有决策树，忽略了单个决策树对最终聚类结果的贡献。
为了解决这些问题，本文提出了一种基于锚图的新的随机森林聚类方法，称为RFAG。该方法分为两个主要阶段：训练阶段和聚类阶段。具体来说，在训练阶段，首先使用基于平衡K-means的层次K-means方法生成具有代表性的锚点。这些锚点的数量远少于原始数据点，有助于降低后续相似性计算的计算复杂性[2]。随后，实现了一种无参数的邻居分配策略来基于锚点构建锚图。通过对锚点进行边际随机采样生成负样本，并与锚点一起用于训练RF。在聚类阶段，训练好的决策树作为基础聚类器来提取锚点之间的相似性信息，这些相似性信息被转换为相似性矩阵并进行聚类。接下来，根据数据集的稳定性设计了两种聚类集成选择策略，用于选择特定的决策树，然后将它们组合起来构建新的RF。最后，新形成的RF对锚点进行聚类。锚图与这些聚类结果相结合，建立了将数据点链接到锚点再链接到簇的层次关联。
本文的贡献总结如下：
•我们开发了一种基于锚点的随机森林训练方法，该方法从具有代表性的锚点和生成的负样本构建伪标记数据集，实现了高效的二分类器训练，并显著降低了计算成本。
•我们提出了一种基于虚拟路径的锚点相似性度量方法，该方法比传统的叶子节点共现方法更能捕捉它们之间的细微关系，提高了相似性矩阵的质量并增强了聚类性能。
•我们引入了一种考虑稳定性的集成选择方法，该方法根据数据集的稳定性和不稳定性设计了两种策略，以克服低贡献决策树对聚类质量的负面影响。
本文的其余部分组织如下：第2节讨论相关工作，第3节介绍方法论，第4节展示实验评估，第5节对本文进行总结。
部分摘录
随机森林聚类
RF聚类提取样本之间的相似性信息并将其应用于聚类算法。与传统基于距离的聚类方法相比，这种方法利用决策树的结构特征而不是直接计算距离。具体来说，该方法使用RF中每个决策树的划分信息来捕捉样本之间的相似性。
这一优雅的概念最初由[3]提出。在这种方法中，当两个样本最终
方法论
所提出的方法分为两个主要阶段：训练阶段和聚类阶段，如图1所示。
简而言之，RFAG方法遵循一个紧密集成的过程，每个模块都自然地建立在之前的模块之上，以确保在大规模数据集上的高效聚类。
该过程从锚点选择（第3.1.1节）开始，通过BKHK生成具有代表性的锚点。这些锚点保留了原始数据的全局结构特征，同时
准备工作
我们在8个不同的数据集上进行了实验来评估RFAG的性能。所有实验都在配备Intel i9-12900H处理器（14核，20线程，2.50GHz，32GB RAM）的Lenovo Y9000P上进行，操作系统为Windows 11。RFAG方法和7种比较方法使用MATLAB R2022b和Python实现。
结论
在本文中，我们提出了一种新的随机森林聚类方法RFAG，该方法结合了基于锚点的采样和聚类集成选择，以解决传统聚类框架中的效率和准确性挑战。在不同数据集上的实验结果表明，与现有的随机森林聚类方法相比，RFAG在聚类准确性方面取得了统计学上的显著改进，并减少了运行时间。RFAG的优势源于三个主要创新：
CRediT作者贡献声明
Jinyu Li：撰写——原始草稿，可视化，软件，概念化。Congyu Wang：撰写——原始草稿，资源，概念化。Mingjing Du：撰写——审稿与编辑，监督，资金获取。
利益冲突声明
作者声明他们没有已知的可能影响本文工作的竞争性财务利益或个人关系。
致谢
本工作得到了中国江苏省青兰计划、国家自然科学基金（编号：62006104）和江苏师范大学研究生研究实践创新计划（编号：2024XKT2583）的支持。
