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

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

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

Answer 5

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

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

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