Podzielić zbiór punktów na dwa optymalne podzbiory

Chcę podzielić zestaw punktów na dwa równe podzbiory, aby zminimalizować sumę kwadratów wewnątrz klastra. Możemy założyć, że punkty znajdują się w dwuwymiarowej przestrzeni euklidesowej. Mam nadzieję na coś szybszego niż ogólny algorytm grupowania k-średnich, biorąc pod uwagę, że k = d = 2. Czy ktoś może wskazać mi dobry algorytm?

Dokładne rozwiązanie nie jest konieczne, jeśli mamy dobre przybliżenie.

Dzięki!

ds.algorithms approximation-algorithms clustering

— Andrew Baker
źródło

Jeśli nalegasz na dokładną partycję, musisz obliczyć wszystkie zrównoważone partycje zestawu punktów w płaszczyźnie za pomocą linii (optymalną partycją jest partycja Voronoi, więc dwa zestawy punktów są oddzielone linią). Takie partycje są znane jako zestawy . Najszybszy znany obecnie algorytm dla tej pracy w do obliczania tych partycji w trybie podwójnym [tj. Poziom zestawu linii dla ] . Po utworzeniu wszystkich możliwych partycji wystarczy sprawdzić każdą z nich. Za pomocą standardowych sztuczek można to zrobić w stałym czasie dla każdej partycji. $k$ $O(n^{4/3} \log n)$ $k$ $n$ $k=n/2$

(Aktualizacja: Udowodnienie, że optymalna partycja jest realizowana przez zestaw , dla , nie jest całkowicie trywialna. Pozostawiłbym to jako słodkie ćwiczenie dla zainteresowanego czytelnika. Wskazówka: Rozważ linię przechodzącą przez dwa optymalne centra i kierunek prostopadły do niego). $k$ $k=n/2$

Jeśli nie dbają o dokładne rozwiązanie, wówczas łatwiej podejście byłoby użyć coreset dla -means klastrów. Spowodowałoby to w tym przypadku punktów o całkowitej masie . Następnie wystarczy rozwiązać problem z zestawem punktów ważonych. Najłatwiejszym rozwiązaniem byłoby wygenerowanie zestawu lokalizacji kandydujących do centrów i wypróbowanie wszystkich par na ważonych punktach. Budowa rdzenia i generowanie centrów kandydujących opisano w tym artykule: $k$ $O( \epsilon^{-2} \log n)$ $n$

http://sarielhp.org/p/03/kcoreset/

— Sariel Har-Peled
źródło