Mengelompokkan koordinat lokasi geografis (lat, pasangan panjang)

Apa pendekatan yang tepat dan algoritma pengelompokan untuk pengelompokan geolokasi?

Saya menggunakan kode berikut untuk mengelompokkan koordinat geolokasi:

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()

Apakah benar menggunakan K-means untuk pengelompokan geolokasi, karena menggunakan jarak Euclidean, dan bukan rumus Haversine sebagai fungsi jarak?

K-means harus benar dalam kasus ini. Karena k-means mencoba mengelompokkan hanya berdasarkan jarak euclidean antara objek, Anda akan mendapatkan kembali kelompok lokasi yang dekat satu sama lain.

Untuk menemukan jumlah cluster yang optimal, Anda dapat mencoba membuat plot 'siku' dari jumlah grup dalam jarak kuadrat. Ini mungkin membantu ( http://nbviewer.ipython.org/github/nborwankar/LearnDataScience/blob/master/notebooks/D3.%20K-Means%20Clustering%20Analysis.ipynb )

K-means bukan algoritma yang paling tepat di sini.

Alasannya adalah k-means dirancang untuk meminimalkan varians . Ini tentu saja muncul dari sudut pandang statistik dan sinyal, tetapi data Anda tidak "linier".

Karena data Anda berada dalam format lintang, bujur, Anda harus menggunakan algoritma yang dapat menangani fungsi jarak arbitrer , khususnya fungsi jarak geodetik. Hierarchical clustering, PAM, CLARA, dan DBSCAN adalah contoh populer dari ini.

https://www.youtube.com/watch?v=QsGOoWdqaT8 merekomendasikan pengelompokan OPTICS.

Masalah k-means mudah dilihat ketika Anda mempertimbangkan poin dekat dengan + -180 derajat. Bahkan jika Anda meretas k-means untuk menggunakan jarak Haversine, pada langkah pembaruan ketika menghitung ulang berarti hasilnya akan kacau. Kasus terburuknya adalah, k-means tidak akan pernah bertemu!

Koordinat GPS dapat langsung dikonversi ke geohash . Geohash membagi Bumi menjadi "ember" dengan ukuran berbeda berdasarkan jumlah digit (kode Geohash pendek membuat area besar dan kode lebih panjang untuk area lebih kecil). Geohash adalah metode pengelompokan presisi yang dapat disesuaikan.

Saya mungkin sangat terlambat dengan jawaban saya, tetapi jika Anda masih berurusan dengan geo clustering, Anda mungkin menemukan studi ini menarik. Ini berkaitan dengan perbandingan dua pendekatan yang cukup berbeda untuk mengklasifikasikan data geografis: K-means clustering dan pemodelan pertumbuhan kelas laten.

Salah satu gambar dari penelitian:

Para penulis menyimpulkan bahwa hasil akhirnya secara keseluruhan serupa, dan bahwa ada beberapa aspek di mana LCGM overperfpormed K-means.

Anda dapat menggunakan HDBSCAN untuk ini. Paket python memiliki dukungan untuk jarak haversine yang akan menghitung jarak antara titik lat / lon dengan benar.

Seperti yang disebutkan oleh dokumen , Anda harus mengubah poin Anda menjadi radian terlebih dahulu agar ini berfungsi. Psuedocode berikut harus melakukan trik:

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)

Algoritma k-means untuk mengelompokkan lokasi adalah ide yang buruk. Lokasi Anda dapat tersebar di seluruh dunia dan jumlah cluster tidak dapat diprediksi oleh Anda, tidak hanya itu jika Anda menempatkan cluster sebagai 1 maka lokasi akan dikelompokkan ke 1 cluster tunggal. Saya menggunakan pengelompokan hierarki untuk hal yang sama.

Java Apache commons-math melakukan ini dengan mudah.

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) 

Pergilah dengan Kmeans clustering karena HBScan akan berlangsung selamanya. Saya mencobanya untuk salah satu proyek dan berakhir tetapi menggunakan Kmeans dengan hasil yang diinginkan.