Clustering geo-data for heatmap

Question

I have a list of tweets with their geo locations. They are going to be displayed in a heatmap image transparently placed over Google Map. The trick is to find groups of locations residing next to each other and display them as a single heatmap circle/figure of a certain heat/color, based on cluster size.

Is there some library ready to grouping locations in a map into clusters? Or I better should decide my clusterization params and build a custom algorithm?

Answer 1

I don't know if there is a 'library ready to grouping locations in a map into clusters', maybe it is, maybe it isn't. Anyways, I don't recommend you to build your custom clustering algorithm since there are a lot of libraries already implemented for this.

@recursive sent you a link with a php code for k-means (one clustering algorithm). There is also a huge Java library with other techniques (Java-ML) including k-means too, hierarchical clustering, k-means++ (to select the centroids), etc.

Finally I'd like to tell you that clustering is a non-supervised algorithm, which means that effectively, it will give you a set of clusters with data inside them, but at a first glance you don't know how the algorithm clustered your data. I mean, it may be clustered by locations as you want, but it can be clustered also by another characteristic you don't need so it's all about playing with the parameters of the algorithm and tune your solutions.

I'm interested in the final solution you could find to this problem :) Maybe you can share it in a comment when you end this project!

Answer 2

K means clustering is a technique often used for such problems

The basic idea is this:

Given an initial set of k means m₁,…,m_k, the algorithm proceeds by alternating between two steps:

1. Assignment step: Assign each observation to the cluster with the closest mean

2. Update step: Calculate the new means to be the centroid of the observations in the cluster.

Here is some sample code for php.