Есть набор точек на плоскости, каждая точка описывается координатами x,y:

Код

.       .. .       . . ..               .    .  .             ..     .....           .           ...      .   . .                 ..      . .

Каждое из "облаков" тяготеет к некоторому центру. Надо разбить плоскость на кластеры, т.е. вписать каждое облако, скажем, в окружность внутри которой плотность точек имеет некоторое заданное значение или больше этого занчения. Не обязательно что бы каждая точка плоскости принадлежала какому-либо кластеру. В итого должно получиться, если использовать окружности, набор кластеров в виде списка из: x, y - координаты центра, r - радиус.

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

з.ы. точек с одинаковыми координатами может быть несколько.

>но ощушение такое, что я изобретаю велосипед

Поищи "кластерный анализ", вывалится куча ссылок.

Совсем необязательно получишь окружность, прямоугольник или какую-нибудь другую геометрическую фигуру. Дело в том, что существует несколько методов объединения объектов в кластеры и, соответственно, способов задать метрику для вычисления расстояния между объектами.
To be continued...

я вот тут подумал: можно придумать абстрактный физический процесс, который даст нам ответ (немного коряво сказал)
Представим себе, что между каждыми двумя точками действует сила притяжения, пусть они двигаются по направлению этой силы. Тогда через некоторое время они сосредоточатся в нескольких точках.
Силу нужно выбирать сильно убывающей с расстоянием.
И не надо точно моделировать процесс гравитационного взаимодействия (а то начнется движение по орбитам и прочие неприятности), пусть не вторая производная координаты будет пропорциональна силе, а первая.

а вот еще одна идея (она мне даже больше нравится):
Введем функцию плотности заполнения точки пространства (если там есть объект - значение 1, если нет - 0). Локальных максимумов будет столько же, сколько объектов. Теперь как-нибудь сгладим эту функцию. Если сгладили не сильно, локальные максимумы останутся, но объекты станут немного "размытыми". Если сглаживать все больше, максимумы станут объединяться. Так можно сглаживать, пока нас не устраивает количество кластеров (а оно будет со временем уменьшаться).

продолжение

И еще результат разбиения на кластеры зависит от того, как ты будешь бить данные: на максимальное число кластеров, на заданное число кластеров или оптимальное число в смысле, скажем для определенности, минимума энтропии.

Возьми Matlab, там есть готовый инструментарий, которым пользоваться так же просто как и лопатой. Поиграйся со своими точками, хотя бы прочувствуешь, что такое кластерный анализ и как он работает. Дальше уже можно будет засесть за программирование конкретной задачи.

Хотя в общих словах еще добавлю, что кластерным анализом пользуются так:
1. выбирают метрику в заданном пространстве объектов (метрики существуют всякие-разные)
2. вычисляют все возможные попарные расстояния между объектами
3. выполняют процедуру агломерации (способов агломерации тоже известно несколько). Обычно строят дендрограмму (дерево) для наглядности.
4. оценивают качество кластеризации

И еще мне нравится вот это http://www.clustan.com/

Спасибо большое всем, буду разбираться. Не ожидал, что так поддержите Еще раз спасибо.

А у меня все вроде как проще, но и сложнее (очень медленно ).
Тоже набор точек x, y и задаваемое пользователем число R.
Никак не могу сформулировать, проще вот так, образно: вокруг каждой точки рисуем "в уме" окружности радиуса R и объединяем в группы те точки, чьи окружности пересеклись.

Пока алгоритм такой:
1. сначала столько же групп, сколько точек, в каждой по одной точке;
2. взять очередную группу, проверить "пересекается" ли она с какой-нибудь другой, если да, объеденить их;
3. повторять 2. до последней группы.

Подозреваю, что работает за время n^2 или еще хуже. Все время уходит на функцию, которая проверяет, не пересекаются ли две группы.
Эта ф-я перебирает все пары точек (в которых одна точка из первой группы, другая из второй) до тех пор, пока не встретит двух точек, между которыми расстояние меньше R.

Вопрос такой: есть ли более быстрый алгоритм решения всей задачи, и если нет, то есть ли более быстрый алгоритм для этой функции?
Спасибо.

PS. Похоже, что-то типа алгоритма "ближайшего соседа". Нигде сам алгоритм не нашел. Он, конечно, очевиден, если грубо в лоб решать. А как-то до n*log(n) он оптимизируется??

Это сообщение отредактировал(а) Liner - 24.3.2006, 23:47

Я бы использовал горную кластеризацию. Идея следующая --задается вес -- функция от положений двух точек убывающая с ростом расстояния между точками. Для каждой точки считается качество -- сумма весов по всем отсальным точкам.
Задается параметр отесечения. (т.е. если качество меньше этого параметра то точка не принадлежит кластеру(или сама образует кластер из 1 точки)).
выбираем точку с наибольшим качеством(обозначим ее -- Т1), все точки вокруг качество котрых больше параметра отсечения объединяем в кластер с центром
в Т1. Далее выбираем точку с наибольшим качеством, котроя не попала в первый кластер, формируем кластер воокруг нее и.т.д.
По сути подход maxim1000, в качестве параметра сглаживания взят параметр отсечки





времени будет жрать много. Тоже через специальные нейроети можно сделать