Я хочу сделать предварительную кластеризацию для набора ок.500 000 баллов.
Я еще не начал, но я подумал, что буду делать:
- сохранить все точки в индексе localSOLR
- определить "естественные кластерные позиции "согласно некоторой административной информации (например, для больших городов)
- , а затем рассчитать кластер для каждого города:
- для каждого города
- для каждого уровня масштабирования
- запросить индекс, чтобы получить точки, содержащиеся в радиусе вокруг города (длина радиуса зависит от уровня масштабирования)
Это должно быть достаточно эффективным, потому что есть только 100 крупных городов и запросы SOLR очень быстрые.Но немного больше размышлений показало, что это неправильно:
- могут быть скопления точек, которые находятся "ближе" друг к другу, чем к городу: у них должен быть свой кластер
- при некоторых уровнях масштабирования некоторые точки не будут находиться на приемлемом расстоянии от любого города, и поэтому они не будут учитываться
- , некоторые города находятся рядом друг с другом, и поэтому некоторые точки будут учитываться дважды (добавляются к обоимкластеры)
Существуют и другие подходы:
- изучить каждую точку и определить, к какому кластеру она относится;это устраняет проблемы 2 и 3 выше, но не 1, а также крайне неэффективно
- сделать (прямоугольную) сетку (для каждого уровня масштабирования);это работает, но приведет к сумасшедшим / произвольным кластерам, которые ничего не «значат»
Я думаю, я ищу универсальный алгоритм геокластеризации (или идея ) и не могу найти ни одного.
Редактировать, чтобы ответить на комментарий от Geert-Jan
Я хотел бы построить "естественные" кластеры, да, и да, я 'Я боюсь, что если я использую произвольную сетку, это не будет отражать реальность данных.Например, если есть много событий, которые происходят вокруг точки, которая находится на пересечении или около пересечения двух прямоугольников, я должен получить только один кластер, но фактически построю два (по одному в каждом прямоугольнике).
Изначально яхотел использовать localSOLR из соображений производительности (и потому что я это знаю, и у меня больше опыта в индексировании большого количества данных в SOLR, чем в обычную базу данных);но поскольку мы говорим о предварительной кластеризации, может быть, производительность не так важна (хотя для визуализации результата нового эксперимента по кластеризации не потребуются дни).Мой первый подход запроса множества точек в соответствии с предопределенным набором «больших точек» в любом случае явно ошибочен, первая причина, которую я упомянул, является самой сильной: кластеры должны отражать реальность данных, а не какое-то другое бюрократическое определение (они будутконечно, частично совпадают, но данные должны стоять на первом месте).
Существует отличный кластер для живой кластеризации, который был добавлен к основному API Карт Google: Marker Clusterer .Интересно, пытался ли кто-нибудь запустить его «в автономном режиме»: запустить его в течение необходимого количества времени, а затем сохранить результаты?
Или существует кластер, который проверяет каждую точку, точку за точкой ивыводит кластеры с включенными в них координатами и количеством точек, и что делает это в разумные сроки?