MST на полном графе для их кластеризации (для косинусного сходства)

Question

Мне нужно кластеризовать (скажем, задано в качестве параметра k), слова (что я хранить в массиве List) в соответствии с их косинусным сходством. Я сохранил все свои слова как вершины в списке в полном, взвешенном и неориентированном графе (который использует список смежности), и поместил их значения косинусного сходства по краям. Как я понимаю, мне нужно использовать MST (алгоритм Крускала) для процесса кластеризации.

Однако, поскольку мой граф является полным графом, а 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

Answer 1

Стандартно использовать минимальные остовные деревья на полных графиках.

Вы часто найдете сложность времени выполнения, данную для этого случая отдельно. Вы можете проверить, быстрее ли Prim, чем Kruskal, на полном графике.

Кластеризация с минимальным остовным деревом также известна как кластеризация по одной линии, а быстрый алгоритм SLINK тесно связан с алгоритмом MST Prim. Но выходной формат больше подходит для кластеризации.