Разделение множества точек на два оптимальных подмножества

9

Я хочу разделить набор точек на два подмножества одинакового размера так, чтобы сумма квадратов внутри кластера была минимальной. Можно предположить, что точки находятся в двумерном евклидовом пространстве. Я надеюсь на что-то более быстрое, чем обычный алгоритм кластеризации k-средних, учитывая, что k = d = 2. Может кто-нибудь указать мне в направлении хорошего алгоритма для этого?

Точное решение не требуется, если у нас есть хорошее приближение.

Спасибо!

Эндрю Бейкер
источник

Ответы:

10

Если вы настаиваете на точном разбиении, то вам нужно вычислить все сбалансированные разбиения набора точек на плоскости по линии (оптимальное разбиение - это разбиение Вороного, поэтому два набора точек разделены линией). Такие разделы известны какk-множествами. Самый быстрый алгоритм, известный в настоящее время для этой работы вO(n4/3logn) для вычисления этих разделов в двойном [т.е. kУровень набора n линии, для k=n/2]. Когда у вас есть все возможные разделы, вам просто нужно проверить каждый из них. Используя стандартные приемы, это можно сделать за постоянное время для каждого раздела.

(Обновление: доказательство того, что оптимальный раздел реализуется k-установить для k=n/2не совсем тривиально. Я бы оставил это как милое упражнение для заинтересованного читателя. Подсказка: рассмотрите линию, проходящую через два оптимальных центра, и направление, перпендикулярное к нему.)

Если вам нет дела до точного решения, тогда более простым подходом будет использование kозначает кластеризацию. Это приведет кO(ϵ2logn) взвешенные точки в этом случае, с общим весом n, Затем вам просто нужно решить проблему с помощью взвешенного набора точек. Самым простым решением было бы создать набор подходящих местоположений для центров и проверить все пары на взвешенных точках. Конструкция coreset и создание центров-кандидатов описаны в этой статье:

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

Сариэль Хар-Пелед
источник