Как группировать точки широты/долготы, которые "близки" друг к другу?

У меня есть база данных о точках широты/долготы пользователей, и я пытаюсь группировать "близкие" точки вместе. "Закрыть" относительно, но пока это кажется ~ 500 футов.

Сначала казалось, что я могу просто группировать по строкам, которые имеют одну и ту же широту/долготу для первых трех знаков после запятой (примерно 300 х 300 ящиков, понимая, что они изменяются при удалении от экватора).

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

Я также размышлял над ситуацией, когда точка A и точка C "близки" к точке B (но не друг к другу) - должны ли они группироваться вместе? Если да, то что происходит, когда точка D "близка" к точке C (и никаким другим точкам) - также должна быть сгруппирована. Разумеется, мне нужно определить желаемое поведение, но как бы реализовать это?

Может ли кто-нибудь указать мне в правильном направлении, как это можно сделать и какие различные методы/подходы могут быть использованы?

Я немного чувствую, что мне не хватает чего-то очевидного.

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

Ответ 1

Существует несколько способов определения расстояния между двумя точками, но для построения точек на двумерном графике вы, вероятно, хотите Евклидово расстояние. Если (x1, y1) представляет вашу первую точку, а (x2, y2) представляет вашу вторую, расстояние

d = sqrt( (x2-x1)^2 + (y2-y1)^2 )

Что касается группировки, вы можете использовать какое-то двухмерное значение, чтобы определить, как "близкие" вещи друг к другу. Например, если у вас есть три точки, (x1, y1), (x2, y2), (x3, y3), вы можете найти центр этих трех точек простым усреднением:

x(mean) = (x1+x2+x3)/3
y(mean) = (y1+y2+y3)/3

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

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

Ответ 2

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

Например, расширение земной поверхности к PostgreSQL работает путем преобразования лат/длинных пар в (x, y, z) декартовых координат, моделируя Землю как однородную сферу. PostgreSQL имеет сложную систему индексирования, которая позволяет этим координатам или ячейкам вокруг них индексироваться в R-деревья, но вы можете ударить что-то вместе, что по-прежнему полезно без этого.

Если вы берете (x, y, z) тройку и округляете, т.е. умножаете на некоторый коэффициент и усекаете на целое число, тогда у вас есть три целых числа, которые вы можете объединить, чтобы создать "имя поля", которое идентифицирует поле в вашей "сетке", в которой находится точка.

Если вы хотите найти все точки в пределах X км некоторой целевой точки, вы генерируете все "имена полей" вокруг этой точки (после того, как вы преобразуете свою целевую точку в (x, y, z) тройку, как хорошо, это легко) и устранить все ящики, которые не пересекаются с земной поверхностью (трюк, но использование формулы x^2+y^2+z^2=R^2 в каждом углу скажет вам), что вы получите список боксов, поэтому просто найдите все точки, соответствующие одному из этих полей, что также вернет вам дополнительные очки. Итак, на заключительном этапе вам нужно рассчитать фактическое расстояние до вашей целевой точки и устранить некоторые (опять же, это можно ускорить, работая в декартовых координатах и преобразуя ваш целевой радиус радиуса большого круга в секущее расстояние).

Скромная работа сводится к тому, что вам не нужно искать слишком много ящиков, но в то же время не приносите слишком много лишних очков. Я счел полезным индексировать каждую точку на нескольких разных сетках (например, разрешения 1Km, 5Km, 25Km, 125Km и т.д.). В идеале вы хотите искать только одну ячейку, помните, что она расширяется до 27, как только ваш целевой радиус превышает размер вашей сетки.

Я использовал этот метод для создания пространственного индекса с использованием Lucene, а не для выполнения вычислений в базах данных SQL. Он действительно работает, хотя есть некоторые попытки его настроить, и индексы требуют времени, чтобы генерировать и довольно большие. Использование R-дерева для хранения всех координат является гораздо более приятным подходом, но требует больше пользовательского кодирования. Этот метод в основном требует быстрого поиска хеш-таблицы (так что, вероятно, будет хорошо работать со всеми базами данных NoSQL, которые являются ярость в эти дни и должна также использоваться в базе данных SQL).

Ответ 3

Может быть, излишний, но мне кажется проблема кластеризации: distance measure определит, как рассчитывается подобие двух элементов. Если вам нужно менее наивное решение, попробуйте Data Mining: Практические инструменты и методы машинного обучения и используйте Weka или Orange

Ответ 4

Если вы рассматриваете широту и долготу, в реальном времени необходимо учитывать несколько факторов: препятствия, такие как реки и озера, и объекты, такие как мосты и туннели. Вы не можете группировать их просто; если вы используете простой алгоритм, так как k означает, что вы не сможете их сгруппировать. Я думаю, вам следует использовать методы пространственной кластеризации как метод разделения CLARANS.

Ответ 5

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

Если у вас есть соседние густонаселенные решетки, вы всегда можете опустить круг в центре каждой сетки и оптимизировать для окружности vs (количество точек в круге * некоторый настраиваемый вес). Не идеально, но легко. Более эффективные группировки - это гораздо более сложные проблемы оптимизации.