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

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

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

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-средства для кластеризации геолокации, так как он использует евклидово расстояние, а не формулу Хаверсайна в качестве функции расстояния?

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

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

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

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

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

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

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

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

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

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

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

Вы можете использовать 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)

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

Java Apache commons-math делает это довольно легко.

https://commons.apache.org/proper/commons-math/javadocs/api-3.1/org/apache/commons/math3/stat/clustering/DBSCANClusterer.html

List<Cluster<T>>    cluster(Collection<T> points) 

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