Кластеризация координат географического местоположения (широта, длинные пары)

51

Каков правильный подход и алгоритм кластеризации для геолокации?

Я использую следующий код для кластеризации координат геолокации:

import numpy as np
import matplotlib.pyplot as plt
from scipy.cluster.vq import kmeans2, whiten

coordinates= np.array([
           [lat, long],
           [lat, long],
            ...
           [lat, long]
           ])
x, y = kmeans2(whiten(coordinates), 3, iter = 20)  
plt.scatter(coordinates[:,0], coordinates[:,1], c=y);
plt.show()

Правильно ли использовать K-средства для кластеризации геолокации, так как он использует евклидово расстояние, а не формулу Хаверсайна в качестве функции расстояния?

ROK
источник
Вы также можете взглянуть на этот похожий вопрос: datascience.stackexchange.com/questions/10063/…
VividD
Я думаю, что выполнимость k-средних зависит от того, где находятся ваши данные. Если ваши данные распространяются по всему миру, они не будут работать, так как расстояние не является евклидовым, как уже сказали другие пользователи. Но если ваши данные более локальны, то k-means будет достаточно хорошим, так как геометрия локально евклидова.
Хуан Игнасио Хиль

Ответы:

7

K-средства должны быть правильными в этом случае. Так как k-means пытается группировать, основываясь исключительно на евклидовом расстоянии между объектами, вы получите группы местоположений, которые расположены близко друг к другу.

Чтобы найти оптимальное количество кластеров, вы можете попробовать составить «коленчатый» график внутригрупповой суммы квадратного расстояния. Это может быть полезно ( http://nbviewer.ipython.org/github/nborwankar/LearnDataScience/blob/master/notebooks/D3.%20K-Means%20Clustering%20Analysis.ipynb )

mike1886
источник
3
Как обрабатываются точки, расположенные близко друг к другу в точке обтекания?
casperOne
1
Вам нужно найти алгоритм, который использует предварительно вычисленную матрицу расстояний или позволяет вам предоставить функцию расстояния, которую он может вызывать, когда ему нужно вычислить расстояния. В противном случае это не сработает.
Космонавт
Заговор локтя может вам совсем не помочь, потому что локтя может не быть. Также обязательно попробуйте несколько прогонов k-средних с одним и тем же номером кластера, потому что вы можете получить разные результаты.
Кузнечик
Это плохая идея, поскольку все точки будут сгруппированы, что редко является хорошей идеей при картировании.
Ричард
52

К-значит здесь не самый подходящий алгоритм.

Причина в том, что k-means предназначен для минимизации дисперсии . Это, конечно, выглядит с точки зрения статистики и обработки сигналов, но ваши данные не являются «линейными».

Поскольку ваши данные представлены в формате широты и долготы, вы должны использовать алгоритм, который может обрабатывать произвольные функции расстояния, в частности, функции геодезического расстояния. Иерархическая кластеризация, PAM, CLARA и DBSCAN являются популярными примерами этого.

https://www.youtube.com/watch?v=QsGOoWdqaT8 рекомендует кластеризацию OPTICS.

Проблемы k-средних легко увидеть, когда вы рассматриваете точки, близкие к + -180 градусам. Даже если вы взломали k-means, чтобы использовать расстояние Haversine, на этапе обновления, когда он пересчитывает среднее значение, результат будет плохо испорчен. В худшем случае, k-means никогда не сойдет!

Anony-Мус
источник
Можете ли вы предложить более подходящий метод кластеризации для данных о географическом местоположении?
Алекс Сперлинг
Вы заметили третий абзац?
Anony-Mousse
7

Координаты GPS могут быть непосредственно преобразованы в геохэш . Geohash делит Землю на «ведра» разного размера в зависимости от количества цифр (короткие коды Geohash создают большие области и более длинные коды для небольших областей). Geohash - это метод кластеризации с регулируемой точностью.

Брайан Спиеринг
источник
Похоже, что это страдает от той же самой проблемы 180 градусов, которую K-Means делает в статье Википедии, приведенной в ответе.
Норман Х
Ага! Плюс коды намного лучше, чем плюсы.
Брайан Спиеринг,
Одним из преимуществ этого решения является то, что пока вы вычисляете геохэш один раз, повторные операции сравнения будут выполняться намного быстрее.
Норман Х
У Geohash будут проблемы с краями сегмента - две очень близкие точки будут помещены в разные сегменты на основе произвольных краев каждого сегмента.
Дан Дж
5

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

Одно из изображений из исследования:

введите описание изображения здесь

Авторы пришли к выводу, что конечные результаты были в целом схожими, и что были некоторые аспекты, в которых LCGM превышал K-средних.

VividD
источник
5

Вы можете использовать HDBSCAN для этого. В пакете python есть поддержка расстояния haversine, которое будет правильно вычислять расстояния между точками широты и долготы.

Как уже упоминалось в документах , вам нужно сначала конвертировать ваши очки в радианы, чтобы это работало. Следующий psuedocode должен сделать свое дело:

points = np.array([[lat1, lon1], [lat2, lon2], ...])
rads = np.radians(points)
clusterer = hdbscan.HDBSCAN(min_cluster_size=N, metric='haversine')
cluster_labels = clusterer.fit_predict(points)
Matt
источник
0

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

Ругвед Махамуне
источник
-1

Пойдите с кластеризацией Kmeans, поскольку HBScan будет длиться вечно. Я попробовал это для одного проекта и закончил, но используя Kmeans с желаемыми результатами.

Вивек Хетан
источник