python - 单链接聚类

Question

我正在寻找一种使用 OpenCV 进行单链接聚类的方法。我的场景:

• 数百(可能数千)个特征向量(向量维度最多可达约 800 个特征)。
• 簇数未知(可能远低于向量数)。
• 固定相似度阈值 E - 如果两个向量之间的 l1 范数小于 E，则向量应该在同一簇中。
• 我不需要集群来保持紧凑。也就是说，我不需要集群中的所有向量都在彼此的 E 范围内。这可能会导致长“链”而不是集群，但我同意这一点。

我尝试使用 K-means，但因为我不知道聚类的数量，所以这里并不适用。我可以进行迭代 K 均值并寻找最佳 K，但这听起来效率很低。是否有更合适的在 OpenCV 中实现的聚类算法我可以在这里使用？

理想情况下，我需要类似于 SLINK algorithm 的东西，因为这是我目前正在尝试实现的论文中引用的内容。我的选择是直接实现 SLINK(有点困难，因为需要调试和测试)或寻找执行类似操作的现有算法。

有什么建议吗？

Answer 1

我建议根据您的相似性阈值构建图表并找到 connected components .构建图后，查找连通分量将相当容易且高效。如果喜欢NetworkX已经有连通分量function .