Объединение точек на плоскости.

[Roh3n]

Добрый день!

Стоит такая задача.

На плоскости заданы N точек с координатами (x,y). Нужно их распределить на заданное кол-во кластеров (M), так чтобы:

1)В каждом сегменте было одинаковое количество точек или же можно было задавать пределы (min,max) кол-ва точек у каждого кластера;

2)Естественно, кластеры должны образовываться, исходя из минимального расстояния между точками.

По второму условию в интернете достаточно информации (алгоритмы кластеризации), но во всех классических алгоритмах не накладывается ограничение 1). Вот его и никак не могу вписать в решение задачи.

Как вариант, разбить точки на кластеры, исходя из расстояний между ними, а потом перераспределить "смежные" точки между кластерами. Или же вписать проверку на кол-во точек в кластере в самом алгоритме. Но как реализовать эти 2 метода, пока не могу додуматься.

Буду благодарен за идеи и помощь. Спасибо.

[Pphantom]

Задача явно недоформулирована: надо как-то понять, что предполагается делать в ситуации, когда критерии 1 и 2 противоречат друг другу.

[Roh3n]

В этом, наверное, и трудность. Понять, что и как делать в данных условиях.

Попробую объяснить на примере. Есть 1000 точек с координатами (x,y). Надо их разбить на 5 кластеров по 200 шт.

Естественно, можно произвольно разбить точки на 5 множеств, но в условиях задачи нужно ориентироваться на расстояния между точками. И итоговый результат должен быть оптимальным в данных условиях.


В примере с 2-мя кластерами всё достаточно просто. К примеру, алгоритм разбил множество на 600 и 400 точек. Теперь мне нужно перераспределить 100 точек, которые являются ближайшими к кластеру с 400 точками (к центру кластера, например).

А когда таких центров уже 5, задача не выглядит тривиальной.

Когда противоречие - главное первое условие, т.е. задача распределить точки в равных количествах или же (что лучше) с возможность регулировки диапазона этого количества (не 200, а 180-220).

[Munin]

Roh3n в сообщении #1176179 писал(а):

Как вариант, разбить точки на кластеры, исходя из расстояний между ними, а потом перераспределить "смежные" точки между кластерами.

Это выглядит разумным.

Roh3n в сообщении #1176215 писал(а):

А когда таких центров уже 5, задача не выглядит тривиальной. :?

Для точек каждого кластера вычисляете их расстояние до других кластеров. И перераспределяете точки, начиная с наименьших таких расстояний. Здесь возможны разные оптимизации, но они зависят от того, сколько у вас кластеров, точек, как конкретно распределены точки, какие условия на кластеризацию. Увы, без конкретики здесь высасывать что-то из пальца бесполезно: в реальных условиях оно не пригодится.

[Pavia]

Roh3n
Посмотрите как это делается в алгоритмах:
1) K-средних.
2) Карты-Кохенена.
А заодно некоторые идеи можно взять из:
3) Минимальный разрез графа.
4) Алгоритм кластеризации на основе скользящего среднего.
5) Генетические алгоритмы.

[Yuri Gendelman]

Roh3n в сообщении #1176215 писал(а):

В примере с 2-мя кластерами всё достаточно просто...

Даже в этом случае все может быть не очень просто.
Представьте лист бумаги А4. В верхнем левом углу разместите 9 точек со средним расстоянием между ними 1-2 миллиметра. В правом нижнем углу разместите одну точку. При разбиении Вы получите 2 кластера: ЛВ из 9 точек и ПН из 1 точки. "Перераспределение" любой точки из кластера ЛВ в ПН делает кластеризацию бессмысленной.

[Pphantom]

Есть "умеренно плохой" вариант решения. Можно построить, например, минимальное охватывающее дерево для точек, а затем убрать из него $M-1$ ребер наибольшей длины. В результате останется $M$ подграфов. При удачном расположении (фактически означающем, что оба исходных условия можно более-менее соблюсти) в каждом подграфе останется примерно одинаковое количество вершин. Сильное отклонение числа вершин от среднего означает, что в такой постановке задача не решается и нужно вводить какой-то количественный критерий, позволяющий предпочесть одно из условий другому.

[Yuri Gendelman]

Pphantom в сообщении #1176389 писал(а):

Есть "умеренно плохой" вариант решения. Можно построить, например, минимальное охватывающее дерево для точек, а затем убрать из него $M-1$ ребер наибольшей длины.

По-моему метод совсем не плохой. На его основе можно построить классификатор с автоматическим выбором количества классов. Целевую функцию можно строить как комбинацию среднего расстояния внутри классов и среднего расстояния между центрами классов. (Алгоритм построения покрывающего дерева описан в книге: Э.Дейкстра. Дисциплина программирования. М. "Мир". 1978. Раздел 22.)

Но главная проблема у ТС - это требование:

Цитата:

1)В каждом сегменте было одинаковое количество точек или же можно было задавать пределы (min,max) кол-ва точек у каждого кластера;

Я не уверен, что для нее есть универсальное и разумное решение.