代码之家 › 专栏 › 技术社区 › Habil Ganbarli

在完整图上进行MST聚类(用于余弦相似性)

minimum-spanning-tree cluster-analysis nlp graph

0

Habil Ganbarli · 技术社区 · 8 年前

我需要聚类(假设给定为参数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

1 回复 | 直到 7 年前

1

Has QUIT--Anony-Mousse 8 年前

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

您通常会单独找到针对这种情况给出的运行时复杂性。在一个完整的图上,您可能想检查Prim是否比Kruskal快。

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