Bisecting k-means algorytm klastrowania wyjaśnienie

Question

Musiałem napisać dwudzielny algorytm k-średnich, ale nie zrozumiałem algorytmu. Znam algorytm k-średnich.

można wytłumaczyć algorytm, ale nie w academic language

Dzięki.

Answer 1

Pomysł polega na iteracyjnym dzieleniu chmury punktów na 2 części. Innymi słowy, budujesz losowe drzewo binarne, w którym każde dzielenie (węzeł z dwójką dzieci) odpowiada dzieleniu punktów chmury w 2.

Zaczynasz od chmury punktów.

• Oblicz jego ciężkości (środka ciężkości) W

• Wybierz punkt na losowej cL między punktami chmurze

• Construct punkt CR jako punktu symetrycznego Cl w porównaniu do wag (segment cL-> w jest taki sam jak w-> cR)

• Oddziel punkty chmury na dwie części, te najbliższe cR należą do subcloud R, a te najbliższe cL należą do subcloud L

• powtórzyć dla subclouds R i L

Uwagi:

można odrzucić losowe punkty kiedy już je stosować. Jednak zachowaj centroidy wszystkich podkategorii.

Zatrzymaj się, gdy subclouds zawierają dokładnie jeden punkt.

Jeśli chcesz k skupiska, po prostu weź centroidy k tak, aby zawierały wszystkie punkty początkowej chmury. Jeśli chcesz, możesz zrobić dużo bardziej wyszukane rzeczy (minimalizując wariancję chmur, itp.). Załóżmy, że potrzebujesz 4 klastrów (potęga dwóch dla wygody). Wtedy wystarczy przeciąć chmurę na dwie części, a następnie wyciąć każdy podklady na dwóch. Jeśli chcesz 8 klastrów, ponownie wycinaj te subpoławki raz na dwoje. I znowu dla 16 klastrów.

Jeśli chcesz K skupień z K nie potęgą 2 (powiedzmy 24), to spójrz na najbliższą niższą moc dwóch. To 16. Wciąż brakuje ci 8 klastrów. Każdy "klaster poziomu 16" jest środkiem ciężkości "poziomu-16-subkloudu". To, co zrobisz, to wziąć 8-cio poziomowe klastry (na przykład losowo) i zastąpić je dwoma "dziećmi", "klastrami poziomu 32". (Te dwa potomne "klastry poziomu 32" odpowiadają dwóm "subcloudom poziomu 32", które sumują się z rodzicem "16 poziomu subcloud")