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!

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 k zestawu n linii dla k = n / 2 ] . 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/