摘要

本文提出了一种简单而有效的基于图的凝聚聚类算法，用于高维数据的聚类。我们探讨了图论中的两个基本概念——入度和出度在聚类背景下的不同作用。平均入度反映了样本附近的密度，而平均出度则刻画了样本周围的局部几何结构。基于这些洞察，我们通过平均入度和平均出度的乘积来定义聚类的亲和力测度。这种基于乘积的亲和力测度使得我们的算法对噪声具有鲁棒性。该算法具有三个主要优点：性能优良、实现简便和计算效率高。我们在两个基本的计算机视觉问题上测试了该算法：图像聚类和对象匹配。大量实验表明，该算法在这两个应用中均优于现有的最先进方法。