graph - 完整图上的 MST 对它们进行聚类（用于余弦相似度）

Question

我需要根据余弦相似度对单词（我存储在数组列表中）进行聚类（假设作为参数 k 给出）。我将所有单词作为顶点存储在一个完整的、加权的和无向图（使用邻接表）中，并将它们的余弦相似度值放在边上。据我了解，我需要使用 MST（Kruskals 算法）进行聚类过程。

但是，由于我的图是完整图，而 MST 用于连接图，我有点困惑如何在完整图上使用它？或者我使用完整图表做错了？

这是我的单词表：

 [directors, producers, film, movie, black, white, man, woman, person, man, young, woman, science, fiction, thrilling, realistic, lovely, stunning, criminals, zombies, father, son, girlfriend, boyfriend, nurse, soldier, professor, college] 

而且我需要通过 MST 对它们进行聚类，这样如果 k（聚类数）为 2，它将是这样的（根据它们的相似性划分为 2 个聚类）：

boyfriend,college,father,girlfriend,man,nurse,person,professor,son,woman,young
criminals,directors,fiction,film,lovely,movie,producers,science,stunning,thrilling,zombies

标签： graphnlpcluster-analysisminimum-spanning-tree

Answer 1

在完整图上使用最小生成树是标准的。

您经常会发现针对这种情况单独给出的运行时复杂度。您可能想在完整图表上检查 Prim 是否比 Kruskal 快。

最小生成树聚类也称为单链路聚类，快速SLINK算法与Prim的MST算法密切相关。但输出格式更适合聚类。