Muszę skupić (powiedzmy podany jako parametr k),słowa (że ja przechowywać w tablicy tablicowej) zgodnie z ich podobieństwem cosinusowym. Zapisałem wszystkie moje słowa jako wierzchołki na liście w kompletnym, zważonym, i nieukierunkowany wykres (korzystający z listy przyległości) i umieszczający wartości podobieństwa cosinus na krawędziach. Jak rozumiem, muszę używać MST (algorytm Kruskalsa) do procesu grupowania. Jednak ponieważ mój wykres jest kompletnym wykresem, a MST używany do połączonych wykresów, jestem trochę zdezorientowany, jak używać go na pełnym wykresie? Czy robię źle, używając pełnego wykresu? Oto moje słowo:
[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]
Muszę je zgrupować według MST, aby jeśli k (liczba klastrów) wynosiła 2, to będzie tak (2 klastry według ich podobieństw):
boyfriend,college,father,girlfriend,man,nurse,person,professor,son,woman,young
criminals,directors,fiction,film,lovely,movie,producers,science,stunning,thrilling,zombies
Każda podpowiedź lub pomoc jest mile widziana. Z góry dziękuję.
Odpowiedzi:
1 dla odpowiedzi № 1Standardowe jest stosowanie minimalnych drzew opinających na kompletnych wykresach.
Często złożoność środowiska wykonawczego jest podana osobno dla tej sprawy. Możesz sprawdzić, czy Prim jest szybszy niż Kruskal na pełnym wykresie.
Jest także grupowanie z minimalnym drzewem opinającymznany jako klastrowanie pojedynczego łącza, a szybki algorytm SLINK jest ściśle powiązany z algorytmem MST Prim. Jednak format wyjściowy jest bardziej odpowiedni dla klastrowania.