基于随机_i_k__i_NN图的批量边删除聚类算法.pdf

局部连通性 among vertices, making the clustering results less sensitive to the deletion or retention of individual edges. This addresses the issue of instability in traditional kNN-based clustering algorithms. RkNNClus算法是基于随机kNN图的批量边删除聚类算法，它提供了一种新的处理邻接图的策略。在传统的k近邻图（kNN图）中，每个顶点的邻居是其最接近的k个点，而RkNN图则引入随机性，通过在kNN图的基础上添加随机因子来构建。这样做旨在提高图中的局部连通性，从而在进行边删除时，聚类结构不会因为少数边的变化而大幅波动。 文章提出了一个批量边删除的判定准则，这个准则基于局部高斯平滑模型。在数据对象的局部高斯平滑下，如果删除某条边不会显著影响数据点的聚类归属，那么这条边被视为可删除的。这种准则有助于找到对聚类结构影响较小的边，以实现更稳定且有效的聚类结果。 RkNNClus算法的优点在于它的简洁性和效率，以及较少的依赖参数。它不需要预先指定类簇的数量，这使得算法更加灵活，能够自适应地发现数据集中的自然聚类结构。实验部分对比了模拟数据和真实数据上的性能，证实了RkNNClus算法的有效性和鲁棒性。 这篇论文提出了一个针对邻接图的批量边删除聚类框架，特别是通过随机kNN图的构建，增强了图的局部连通性，降低了对特定边的依赖，提升了聚类算法的稳定性。RkNNClus算法为聚类问题提供了一个新的视角，对于理解和改进基于图的聚类方法具有重要意义。此外，该算法的高效性和参数少的特点使其在实际应用中具有广泛的应用前景。