48
$\begingroup$

What is the right approach and clustering algorithm for geolocation clustering?

I'm using the following code to cluster geolocation coordinates:

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

Is it right to use K-means for geolocation clustering, as it uses Euclidean distance, and not Haversine formula as a distance function?

$\endgroup$
  • $\begingroup$ Yoou can also take a look at this similar question: datascience.stackexchange.com/questions/10063/… $\endgroup$ – VividD May 11 '17 at 11:41
  • $\begingroup$ I think the feasibility of k-means would depend on where your data are. If your data is spreaded all over the world, it won't work, as the distance is not euclidean, as other users have already told. But if your data is more local, k-means would be good enough, as the geometry is locally euclidean. $\endgroup$ – Juan Ignacio Gil May 31 '18 at 8:34
7
$\begingroup$

K-means should be right in this case. Since k-means tries to group based solely on euclidean distance between objects you will get back clusters of locations that are close to each other.

To find the optimal number of clusters you can try making an 'elbow' plot of the within group sum of square distance. This may be helpful (http://nbviewer.ipython.org/github/nborwankar/LearnDataScience/blob/master/notebooks/D3.%20K-Means%20Clustering%20Analysis.ipynb)

$\endgroup$
  • 3
    $\begingroup$ How are points close to each other on the wrap-around point handled? $\endgroup$ – casperOne Jul 18 '14 at 17:00
  • 1
    $\begingroup$ You need to find an algorithm that takes a pre-computed distance matrix or allows you to supply a distance-function that it can call when it needs to compute distances. Otherwise it wont work. $\endgroup$ – Spacedman Jul 28 '14 at 13:45
  • $\begingroup$ The elbow plot may not help you at all because there might be no elbow. Also make sure to try several runs of k-means with the same cluster number because you might get different results. $\endgroup$ – Grasshopper May 12 '17 at 10:05
48
$\begingroup$

K-means is not the most appropriate algorithm here.

The reason is that k-means is designed to minimize variance. This is, of course, appearling from a statistical and signal procssing point of view, but your data is not "linear".

Since your data is in latitude, longitude format, you should use an algorithm that can handle arbitrary distance functions, in particular geodetic distance functions. Hierarchical clustering, PAM, CLARA, and DBSCAN are popular examples of this.

https://www.youtube.com/watch?v=QsGOoWdqaT8 recommends OPTICS clustering.

The problems of k-means are easy to see when you consider points close to the +-180 degrees wrap-around. Even if you hacked k-means to use Haversine distance, in the update step when it recomputes the mean the result will be badly screwed. Worst case is, k-means will never converge!

$\endgroup$
  • $\begingroup$ Can you suggest a more appropriate clustering method for geo-location data? $\endgroup$ – Alex Spurling Oct 25 '16 at 21:50
  • $\begingroup$ Did you notice the third paragraph? $\endgroup$ – Anony-Mousse Oct 25 '16 at 21:54
6
$\begingroup$

GPS coordinates can be directly converted to a geohash. Geohash divides the Earth into "buckets" of different size based on the number of digits (short Geohash codes create big areas and longer codes for smaller areas). Geohash is an adjustable precision clustering method.

$\endgroup$
  • $\begingroup$ This seems to suffer from the same 180 degree wrap-around problem that K-Means does per the Wikipedia article linked in the answer. $\endgroup$ – Norman H Jun 1 '18 at 4:07
  • $\begingroup$ Yep! Plus codes are much better plus.codes $\endgroup$ – Brian Spiering Jun 2 '18 at 18:28
  • $\begingroup$ One benefit to this solution is that as long as you calculate the geohash once, repeated comparison operations will go much more quickly. $\endgroup$ – Norman H Jun 7 '18 at 14:15
  • $\begingroup$ Geohash will have issues with bucket-edge cases - two very close points will be put in different buckets based on the arbitrary edges of each bucket. $\endgroup$ – Dan G Jun 12 at 21:08
5
$\begingroup$

I am probably very late with my answer, but if you are still dealing with geo clustering, you may find this study interesting. It deals with comparison of two fairly different approaches to classifying geographic data: K-means clustering and latent class growth modeling.

One of the images from the study:

enter image description here

The authors concluded that the end results were overall similar, and that there were some aspects where LCGM overperfpormed K-means.

$\endgroup$
5
$\begingroup$

You can use HDBSCAN for this. The python package has support for haversine distance which will properly compute distances between lat/lon points.

As the docs mention, you will need to convert your points to radians first for this to work. The following psuedocode should do the trick:

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)
$\endgroup$
0
$\begingroup$

The k-means algorithm to cluster the locations is a bad idea. Your locations can be spread across the world and the number of clusters cant be predicted by you, not only that if you put the cluster as 1 then the locations will be grouped to 1 single cluster. I am using Hierarchical clustering for the same.

$\endgroup$
0
$\begingroup$

Java Apache commons-math does this pretty easily.

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) 
$\endgroup$
-1
$\begingroup$

Go with Kmeans clustering as HBScan will take forever. I tried it for one of the project and ended but using Kmeans with desired results.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.