cluster-analysis - 从最小生成树java聚类

Question

我必须根据它们的余弦相似度比较单词，并从它们中产生 k 个具有意义相似性的簇。基本上我有如下的话：

[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，如下所示：

son criminals 7.622005318852533E-5
directors film 0.00269683524940825
college thrilling 0.004318332211016577
lovely girlfriend 0.011496356899859533
producers science 0.011946913151506599
nurse person 0.01222182619788835
fiction criminals 0.019032592497457333
film producers 0.021182908439749612
college fiction 0.02777607695416014
woman criminals 0.028081533433767823
realistic producers 0.028614429314768274
fiction film 0.031228743740582716
woman stunning 0.034664134514120794
college zombies 0.04113726420938837
criminals black 0.0442203277881683
professor science 0.04546819590424154
zombies soldier 0.04787773897201146
boyfriend stunning 0.04931897200102598
white producers 0.04969833492364299
nurse girlfriend 0.0498423837867863
thrilling nurse 0.05126380652206475
movie science 0.05220609189928112
nurse man 0.05229834114709604
movie young 0.07777548636454826
father nurse 0.13334569901132612

我需要得到类似的结果（比如说 2 个集群）：

boyfriend,college,father,girlfriend,man,nurse,person,professor,son,woman,young

criminals,directors,fiction,film,lovely,movie,producers,science,stunning,thrilling,zombies

在我的分配中它说，“一旦你有了一个加权图，你就可以找到最小生成树并切割图上具有最小权重的 k-1 条边以获得 k 个集群。” 问题是我有点困惑并坚持现在该怎么办？例如，我应该如何获得在每个集群中包含相似单词的结果 2 个集群？ 任何想法或提示表示赞赏。在此先感谢。

标签： cluster-analysisminimum-spanning-tree

Answer 1

使用余弦时，请确保不要混淆符号。

如果您使用余弦相似度，则需要最大生成树（最高相似度）。对于余弦距离，最小值很好。你现在可能有这个错误。

从最小生成树中提取分区的一种方法是删除最长的边（最大距离，删除最大生成树上的最小相似性）。

但是在聚类中还有很多东西可以找到。这种方法本质上是单链路层次聚类。MST 可以可视化为一个树状图，并且可能有十几种方法可以将这个树状图“切割”成簇。