Алгоритм к-средних имеет мощность меньше N2 и в реал-тайм в принципе применяется. А Вы на чем решаете задачу? Если у Вас много процессоров, до для реал-тайм можно использовать нейронные сети. Я когда-то для геологов решал задачи подобные, использовал ядерные функции, но это - тяжелые методы, для реал-тайм - не пойдут.
Я проверил специально по литературе только что, и думаю, что метод k-средних (k-means) - это то, что Вам нужно.
Удачи.
: У меня имеется несколько тысяч точек на двумерной плоскости (обычная метрическая плоскость, конкретно - географическая карта). Распределение сильно неравномерное, точки плотно кучкуются, это видно глазом. Мне нужно не вываливать пользователю все точки, а представить этот набор в виде кластеров на карте с какой-то характерной длиной усреднения R. Т.е., скажем, если две точки ближе друг к другу, чем R, то они входят в один кластер. Условие это не строгое, т.е. мне подойдет любой алгоритм, который просто даст на выходе визуально приемлемую группировку.
:
: Сейчас я просто бью плоскость грубой координатной сеткой с шагом R и кластером считаю все, что попало в одну ячейку. Это очень дешево в плане скорости, но и очень сердито в плане качества (скажем, явно выраженный кластер запросто может попасть на границу ячеек). Но проблема в том, что любой более навороченный алгоритм (из тех, что я нашел) сразу требует порядка N2 сравнений, а это для расчетов в реальном времени многовато. Карта может масштабироваться, условия выборки точек могут меняться, так что посчитать кластеры по 'долгому' алгоритму и закэшировать я не могу: ну, точнее, это будет сложно.
:
: Может быть, существуют какие-то более дешевые решения, чем N2?
:
: отредактировано 10.10.2006 17:31
отредактировано 11.10.2006 01:32 |
» Общий форум