2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему
 
 Объединение точек на плоскости.
Сообщение12.12.2016, 12:14 


12/12/16
2
Добрый день!

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

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Объединение точек на плоскости.
Сообщение12.12.2016, 13:32 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Объединение точек на плоскости.
Сообщение12.12.2016, 13:57 


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

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

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


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

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

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

 Профиль  
                  
 
 Re: Объединение точек на плоскости.
Сообщение12.12.2016, 14:33 
Заслуженный участник
Аватара пользователя


30/01/06
63048
Roh3n в сообщении #1176179 писал(а):
Как вариант, разбить точки на кластеры, исходя из расстояний между ними, а потом перераспределить "смежные" точки между кластерами.

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

Roh3n в сообщении #1176215 писал(а):
А когда таких центров уже 5, задача не выглядит тривиальной. :?

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

 Профиль  
                  
 
 Re: Объединение точек на плоскости.
Сообщение12.12.2016, 15:42 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Объединение точек на плоскости.
Сообщение12.12.2016, 20:09 
Заслуженный участник


15/05/05
3343
USA
Roh3n в сообщении #1176215 писал(а):
В примере с 2-мя кластерами всё достаточно просто...
Даже в этом случае все может быть не очень просто.
Представьте лист бумаги А4. В верхнем левом углу разместите 9 точек со средним расстоянием между ними 1-2 миллиметра. В правом нижнем углу разместите одну точку. При разбиении Вы получите 2 кластера: ЛВ из 9 точек и ПН из 1 точки. "Перераспределение" любой точки из кластера ЛВ в ПН делает кластеризацию бессмысленной.

 Профиль  
                  
 
 Re: Объединение точек на плоскости.
Сообщение12.12.2016, 21:46 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Объединение точек на плоскости.
Сообщение13.12.2016, 15:23 
Заслуженный участник


15/05/05
3343
USA
Pphantom в сообщении #1176389 писал(а):
Есть "умеренно плохой" вариант решения. Можно построить, например, минимальное охватывающее дерево для точек, а затем убрать из него $M-1$ ребер наибольшей длины.
По-моему метод совсем не плохой. На его основе можно построить классификатор с автоматическим выбором количества классов. Целевую функцию можно строить как комбинацию среднего расстояния внутри классов и среднего расстояния между центрами классов. (Алгоритм построения покрывающего дерева описан в книге: Э.Дейкстра. Дисциплина программирования. М. "Мир". 1978. Раздел 22.)

Но главная проблема у ТС - это требование:
Цитата:
1)В каждом сегменте было одинаковое количество точек или же можно было задавать пределы (min,max) кол-ва точек у каждого кластера;
Я не уверен, что для нее есть универсальное и разумное решение.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Toucan, maxal, Karan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group