Кластеризация Lat/Longs в базе данных

Ответ 1

Я бы, вероятно, использовал модифицированную * версию k-mean clustering с использованием декартовых (например, WGS-84 ECF) координат для ваших точек, Он легко реализуется и сходится быстро и адаптируется к вашим данным независимо от того, как он выглядит. Кроме того, вы можете выбрать k в соответствии с требованиями к пропускной способности, и каждый кластер будет иметь одинаковое количество связанных точек (mod k).

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

* "Модификация" заключалась бы в том, чтобы отрегулировать длину вычисленных центроидных векторов, чтобы они были на поверхности земли. В противном случае у вас будет куча точек с отрицательной высотой (при обращении к LLH).

Ответ 2

Если вы кластеры в географическом местоположении, и я не могу представить, что это что-то еще:-), вы можете сохранить "идентификатор кластера" в базе данных вместе с координатами lat/long.

То, что я имею в виду, состоит в том, чтобы разделить карту мира на (например) матрицу 100x100 (10 000 кластеров), и каждая координата присваивается одному из этих кластеров.

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

Размер ваших квадратов (и, следовательно, их количество) будет определяться тем, насколько точной вам нужна кластеризация. Очевидно, что если у вас есть только матрица 2x2, вы можете получить некоторую кластеризацию координат, которые находятся далеко друг от друга.

Yo всегда будет иметь граничные случаи, такие как две точки, близкие друг к другу, но в разных кластерах (один самый северный в своем кластере, другой самый южный в нем), но вы можете настроить размер кластера OR обрабатывать результаты на стороне клиента.

Ответ 3

Я сделал аналогичную вещь для географического приложения, где я хотел, чтобы я мог легко сбрасывать точки множеств. Мой код geohashing выглядит следующим образом:

def compute_chunk(latitude, longitude)
  (floor_lon(longitude) * 0x1000) | floor_lat(latitude)
end

def floor_lon(longitude)
  ((longitude + 180) * 10).to_i
end

def floor_lat(latitude)
  ((latitude + 90) * 10).to_i
end

Все стало очень легко оттуда. У меня был некоторый код для захвата всех кусков от заданной точки до заданного радиуса, который переводится в единую memgache multiget (и некоторый код для засыпки, когда он отсутствовал).

Ответ 4

Для movielandmarks.com Я использовал код кластеризации из Майк Первис, один из авторов Начало приложений Google Maps с PHP и AJAX. Он создает деревья кластеров/точек для разных уровней масштабирования с использованием PHP и MySQL, сохраняя их в базе данных, чтобы напоминание было очень быстрым. Некоторые из них могут быть полезны для вас, даже если вы используете другую базу данных.

Ответ 5

Почему бы не тестировать несколько подходов?

• перевести библиотеку weka в .NET CLI с IKVM.NET
• добавьте сборку, полученную из вашего кода и weka.dll(используйте ilmerge) в вашу базу данных

Сделайте несколько тестов. Никакая конкретная кластеризация работает лучше, чем кто-либо другой.

Ответ 6

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