Question

I am a software developer struggling to understand which clustering method/algorithm would be most appropriate to spatially group 2-dimensional point data (x,y) that is arranged over a time series (an example might be location data as someone moves around a 2D map).

I've read up on techniques such as K-Means, but it doesn't seem like it would respect the ordering of the data at all.

In terms as simplistic as I can explain;

• The sample size is variable.
• I will not know the number of clusters that the algorithm should produce ahead of time. The number of clusters is also not linked to the sample size in any meaningful way.
• I will be able to provide the maximum area/spread that a cluster should cover (in other words; how tightly grouped the points must be to be considered part of the same cluster).
• I will want to ignore outliers to these clusters as the point data may have erroneous values.
• The exact time stamps are not important, but the ordering of the data is critical. For example if the series of points was focussed around a central point 'A', moved away to be focussed around a central point 'B', and then returned to be focussed around a central point near 'A' again, the ordering of the data should dictate that there should be at least 3 clusters produced, rather than the 2 that I believe K-means clustering would produce.

I appreciate you reading this far and thank you for any help you can give me.

I intend to post this same query on mathforum.org, mymathforum.com, mathhelpforum.com and mathoverflow.net (and possibly any other active forums I might find). I hope this is not unacceptable duplication.

Thanks, Julius

Answer 1

Hello Julius.

The proposal of Felix Goldberg will only work, if the data are sampled in such a way, that the time intervals between successive (in time) data are correlated with the spatial data. Essentially short time intervals should imply spatially small movements. In particular the proposal will not work (without further processing) if the data are equidistantly sampled.

You may want to take a look at the so called QT-algorithm (Quality threshold) for clustering (wikipedia describes it). You can apply it without prior specification of the number of clusters but specifying for example the cluster diameter. You could try to cluster the spatial data first. Then you could analyse the various clusters separately with respect to time: points with subsequent time stamps form one cluster, gaps in time signal the passage to a new cluster at the same location.

Of course whether this approach works or not again depends on the sampling structure ... If you have enough data and the clusters you search for are typically big you could force an equidistant sampling by leaving out some samples. If the movement in space is not too erratic you could also try to replace points by interpolated points thus again forcing equidistant time intervals.

Moreover the QT-algorithm has problems with large data sets. Maybe you have to take some kind of stochastic speed up into account.