Как сгруппировать объекты в наборе по близости?

Question

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

Далее, я могу повторить «кластеризацию» в соответствии с другими правилами:

• N групп
• M адресов на группу
• максимальное расстояние между любыми адресами в группе

Answer 1

Вы можете попробовать алгоритм кластеризации k-средних .

Answer 2

Вы хотите векторное квантование:

http://en.wikipedia.org/wiki/Vector_quantization

" Он работает путем деления большого набора точек (векторов) на группы, имеющие примерно одинаковое количество ближайших к ним точек. Каждая группа представлена ​​своей точкой центроида, как в k-средних и некоторых других кластеризациях алгоритмы."

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

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

Answer 3

Это немного зависит от масштаба данных, которые вы хотите кластеризовать. Метод грубой силы заключается в расчете расстояния между всеми комбинациями точек в массиве расстояний. Результирующий массив равен N ^ 2, и поскольку расстояние от A до B такое же, как от B до A, вам потребуется только половина из них, поэтому результирующий набор равен N ^ 2/2.

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

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

Answer 4

1. Построить матрицу расстояний между всеми адресами.
2. Начиная со случайного адреса, отсортируйте матрицу по возрастанию расстояния до этого адреса
3. Удаляя адреса из матрицы по мере продвижения, размещайте адреса, ближайшие к начальному адресу, в новую группу, пока не достигнете своих критериев (размер группы или максимальное расстояние).
4. Как только группа заполнится, выберите другой случайный адрес и прибегните к матрице по расстоянию до этого адреса
5. Продолжайте так до тех пор, пока все адреса не будут удалены из матрицы.

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

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

Answer 5

Ограничения «N групп» и «M адресов на группу» являются взаимоисключающими. Одно подразумевает другое.