往返 KNN 聚类能否在无预设簇数下发现层次簇？

有向 KNN 连接转化为加权投票

多数图聚类流程会先把 k 近邻（KNN）图变为无向图再聚类。RTKNNC 保留邻居关系的两个方向：某个点选择了哪些点，以及哪些点选择了它。论文把被选中的入向连接视为加权投票，用来决定在递归的正向与反向遍历中哪些局部连接保持可见。

这一遍历是核心机制。从一个种子点出发，方法沿可见连接正向走向被选中的邻居，反向走向选择了当前点的那些点，如此重复直到无法再加入新点。论文称之为一次往返，最终集合称为饱和往返闭包。因此簇来自局部图连通性，而非预设的几何形状，算法也从不被告知簇的数量。

邻域规模 K 取代预设簇数

K 决定传播尺度。较小的值描述非常局部的结构，可能使图碎裂；较大的值让信息在更广的邻域上扩散。对递增的 K 独立运行该方法，会产生一系列簇层，持续存在的群体与合并过程因此直接可见。

在这篇论文中，层次指的是这种跨邻域尺度的组织方式，而非传统的基于连接度的凝聚过程。在变密度团块数据集上，未细化的参考反平方模型从 K=2 时的 595 个微簇降到 K=3 的 277 个、K=4 的 99 个、K=5 的 18 个、K=6 的 6 个、K=7 的 5 个、K=8 的 4 个，此后划分一直保持到 K=16 不变。全部 N=2000 个点各被表示一次，未聚类数为零，因此这些层都是正常划分。

未细化层只合并不分裂

对于参考反平方投票规则，在应用可选的结构细化之前，论文证明了相邻正常划分的只合并性质：随着 K 增大，一个簇可以持续存在或与另一个簇合并，但不会分裂。图 2 在变密度团块上以 K=5,6,7,8 展示了这一点，每个尺度上的簇都完整包含于下一尺度上的唯一簇中，因此转移森林只包含保持与合并事件，没有分裂。

这一性质属于未细化的参考模型，而非每一种投票核或细化后的输出。它也是关于层结构的陈述，而非关于正确性的陈述：只合并森林描述的是簇如何跨尺度对应，这与单个报告的层是否为正常划分是不同的诊断。

簇数稳定不代表类别正确

变密度团块让这一区别变得具体。在 K=7 时簇数已等于五个参考类别，但调整兰德指数（ARI）仅为 0.7805。在从 K=8 开始的受测范围饱和处，仍剩四个分量，ARI 为 0.7817。报告簇数与参考簇数相等，以及稳定的平台期，都未能表明潜在类别被恢复。

ARI 和 NMI 将每个划分与已知参考标签比较，且在簇标识符置换下不变。论文仅用它们做评估；标签列从不进入聚类特征。这正是作者把稳定的四分量平台描述为需要单独修正的稳定合并，而非一个解的原因。

无标签细化只拆分有证据的分量

基于连通性的聚类可能通过稀疏桥或小范围重叠把不同群体连在一起。RTKNNC 增加一个可选细化，仅在连通分量已经形成后应用。它检验该分量是否更适合用两个或三个高斯子群体描述，并且只有当提议的群体足够大、且与可见 KNN 图一致时才接受细分。

论文明确指出，这一阶段并非用高斯混合聚类算法取代往返方法。混合模型只在局部用作内部结构的检验，要求最小 BIC 增益为 10，并设有规模检查、图一致性检查和四分量否决。在 840 次运行的核比较中细化全程关闭，因此该消融把投票分配与结构剪枝隔离开来。

细化提升两个困难基准的 ARI

在变密度基准上，细化把 ARI 从 0.7817 提升到 0.9627，并把报告簇数从四个变为五个。在稀疏桥基准上，ARI 从 0.8083 升到 0.9853，在 K=6 时达到三个簇，在 K=10 时为 0.9865。在三个本已正确的保持性对照上，细化未接受任何分裂，ARI 保持为 1。

这些增益特定于细化所针对的两种连通性失败。变密度情形是四个分量的稳定合并；桥情形是稀疏链连接了稠密核心。保持性对照表明，当分量本已正确时，接受规则不会强行细分。

两种实现在 120 次参考运行中一致

在八个合成数据集和 K=2 到 16 上，独立的 C 与 Python 实现在全部 120 次参考运行中产生相同划分（在簇标识符置换意义下，并包括未聚类掩码）。另有六次 C-Python 比较覆盖了变密度团块在 K=8 和桥在 K=6 时的三种加权核。

独立运行约定对这一致性很重要。每个报告的尺度都以 K0=K 运行，因此图、半径、受欢迎度和可见性都指向同一所述邻域尺度；若以 K0 小于 Kmax 运行，构建时的半径可能在较小的中间层仍绑定于 Kmax。

投票核的影响小于可见连通性

840 次运行的核扫描在相同的每源投票预算下比较了均匀、反距离、反平方和 S 形分配。投票分配常常改变可见性，有时也改变诱导出的划分。在两个困难的参考尺度上，反距离、反平方和 S 形投票都保持了修正后的簇数，得分基本一致，其六个未剪枝的原生划分也通过了逐点 C-Python 一致性检验。

对变密度团块，三种核产生了逐点相同的最终划分，尽管它们的原生平均可见邻居数不同，审计也发现数百条依赖核的有向边。对桥而言，稳定性只是近似的：相对于逐点相同的反平方和 S 形结果，反距离投票改变了四个分配，这一差异被三位小数的 ARI 和 NMI 掩盖。

一次按标签选优的网格比较覆盖了七种外部方法的 10,344 次外部拟合和 90 次 RTKNNC 拟合。启用结构细化的 RTKNNC 在四个基准数据集上 ARI 达到 1，在变密度数据集上 ARI 为 0.9627，而全协方差 GMM 为 0.9639，并在稀疏桥上取得最高 ARI 0.9865，而 GMM 为 0.9831。由于参考标签用于在每个网格内选出最佳候选，论文并未把 ARI 作为无监督部署规则。

无标签主张的适用边界

无标签主张在簇构建上最为有力：簇的数量从不被提供，细化只有在规模与图一致性检查之后才接受细分。相比之下，只合并性质是针对未细化的参考反平方模型、且在各层为正常划分时证明的，并不适用于每一种核或细化后的输出。

证据基础是八个合成数据集、K=2 到 16，外部比较使用六个具有非平凡离散参考的数据集。均匀点云没有非平凡参考划分，瑞士卷标签是对连续流形的一个人为离散化，因此其外部得分只作描述性解读。论文把重复随机实现、更高维数据、替代协方差模型、无标签尺度选择以及更多基于图的基线列为未来工作。

实际优先级来自两个困难案例，而非稳定的平台期。评估 RTKNNC 的读者应首先看一个分量是稳定合并还是稀疏桥连接，因为正是在这些条件下，可选细化把 ARI 从 0.7817 变为 0.9627、从 0.8083 变为 0.9853；而簇数吻合或划分在 K 上保持不变，本身并不表明潜在类别已被恢复。

本文引用的文献