2
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Perhaps just adding the timestamp of each datapoint as an extra dimension can work. $\endgroup$
    – Felix Goldberg
    Jan 15, 2013 at 10:57
  • $\begingroup$ Hi Felix, thanks for your reply. I have a timestamp for each point, but please can you point me in the direction of an algorithm that would then use this 3rd dimension to produce clusters? $\endgroup$
    – Julius
    Jan 15, 2013 at 14:53
  • $\begingroup$ I changed the tag as cluster algebras are absolutely not what you are after. $\endgroup$
    – Benoît Kloeckner
    Feb 26, 2013 at 15:02
  • $\begingroup$ So, this is sort of a venue, where multiple performances are to be given, and you want to measure where and when these takes place, based only on people that walks around and occasionally stop and look at the performance? Except you only get snapshots, and cannot tell people apart from frame to frame? So you need clusters to take place in the time dimension as well. By adding extra data from your model, you might be able to determine how to scale the spatial and time dimensions in a good way; 10 minutes walking, is that same "length" as 10 minutes? $\endgroup$
    – Per Alexandersson
    Feb 26, 2013 at 15:17

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Hi Hagen. The timestamps and 2D location points are not directly correlated, i.e. points will not always be separated by a regular time span as the sampling frequency can change, or data points might be filtered out because they do not meet other initial criteria (for example I might receive an erroneous location point that I exclude as it does not fall within the boundaries of my area of interest (spacially). Your suggestion of breaking down the clustering into spacial, and then time based clustering is interesting, but would it not be easy for data that is chronologically diverse to.... $\endgroup$
    – Julius
    Jan 15, 2013 at 14:57
  • $\begingroup$ ...(cont)...impact the position, size and shape of a cluster, for example if the location data focussed around point A, moved away and then returned near to point A, the two visits to point A might result in a cluster that is skewed in size, centre point and shape by the second visit. The subsequent attempt to split the cluster into two (based on the timestamps of the points in the cluster around point A) would have to recalculate both clusters. This sounds possible, but is it an optimal approach? Thank you for your reply by the way - it's all hugely appreciated. $\endgroup$
    – Julius
    Jan 15, 2013 at 15:00
  • $\begingroup$ I forgot to mention also that as well as the points not always being separated by the same timespan, the person might speed up and slow down (the points might be further/closer between subsequent samplings). $\endgroup$
    – Julius
    Jan 15, 2013 at 15:04

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