What clustering algorithm is appropriate for clustering paths?

Question

I have a dataset with vectors in 2-dimensional space that form separate sequences (paths). Full data is presented below: , while a random sample of 5 paths looks like below (please note that incontinuity in paths are natural for the data and doesn't mean missing values):

I would like to find similar paths, where similar would mean (in order from the most to the less prominent):

1. they end up in a similar region
2. they are similar in direct length (i.e. length from start to end on x axis)
3. they are similar in complexity (i.e. number of vectors)
4. they starts in a similar region

What clustering algorithms are natural choice for such a setup? What are things worth to be aware while clustering paths? How can I deal with the fact, that different paths has different number of vectors? How can I represent a data to take that into account?

Answer 1

Like Ricardo mentioned in his comment on your question, the main step here is finding a distance metric between paths. Then you can experiment with different clustering algorithms and see what works.

What comes to mind is dynamic time warping (DTW). DTW gives you a way to find a measure of "distance" (it is actually not strictly a distance metric, but it is close) between two time series. One very useful thing is that it can be used to compare two time series that are of different lengths.

There are many good blog posts on DTW, so I won't try to give yet another explanation of it. There are also many python implementations of it. And a lot of work has gone into making the algorithm very fast. DTW is a strange algorithm--in some ways very simplistic, but typically works well. Once you modify the algorithm to deal with paths, you can construct the distance matrix and use that for clustering. One common clustering algorithm that is used in conjunction with DTW is spectral clustering, since the distance matrix can be used directly (instead of the matrix of data points, which we don't have here).

Answer 2

Your questions indicates that you may want to rather extract features than use DTW. Nevertheless, you will have to carefully construct a dissimilarity matrix, as start point, end point vs. complexity need to be treated and weighted differently.

Once you have a decent and tested measure of dissimilarity, you have a wide variety of algorithms to choose from: HAC, Affinity Propagation, Spectral, DBSCAN, OPTICS, ...

But you cannot expect them to "just" work on whatever data you have. You need to prepare the data and choose the dissimilarity.