如果您有相似度矩阵，请尝试使用光谱方法进行聚类。以拉普拉斯特征图为例。这个想法是从拉普拉斯矩阵（从相似性矩阵计算）计算特征向量，然后得出尊重相似性的特征向量（每个元素一个）。然后，您可以使用例如 k-means 聚类算法对这些特征向量进行聚类。

从实际的角度来看，如果您的矩阵又大又密，频谱方法很快就会变得计算密集型和内存占用。

我使用光谱方法进行图像聚类和最终分类。结果相当不错。困难的部分是得到一个好的相似矩阵。

两个想法立刻浮现在脑海：

更简单的是层次聚类http://en.wikipedia.org/wiki/Hierarchical_clustering，它只需要点之间的距离。

另一个要复杂得多。有一些技术可以在给定点之间的距离的情况下提供距离保持嵌入到欧几里得空间中。一旦到了那里，就会应用许多聚类技术。当我记得（或成功谷歌）其中几种技术的名称时，我将编辑答案。