Principles of Time Series Clustering

Question

I would like to understand complexity of time series clustering. Clustering is similarity based, so as a basic step we evaluate distance between to points in a multidimensional space. In time series, each point is expanded in time - a function of time. Instead of finding distance between two points we are finding distance between two lines? Then a distance component in one dimension is a difference, but for a line that would be something like sum of square differences (like in regression)?

Let's consider a simple example of classifying human beings. A person has a number of descriptors at a given fixed moment of time (age, occupation, income, residence, marital status, gender, medical conditions, etc.) We could do clustering on these as dimensions. Now, let's introduce a time component as nearly all of these characteristics change in a lifetime.

Usually, we consider a one-dimensional time series. But above is a practical example. Some dimensions will change in time, some will not. They will change differently in different people. For some people some descriptors remain constant, for others - not. There could be also a non-linear higher-order dependencies between the descriptors.

So, how do we deal with these complex problems? Clustering is a very computationally intensive task. But time component makes it a lot more complicated.

We could even generalize this problem for supervised and unsupervised learning. What if one or more descriptors (attributes, features, independent variables) we have are functions of other variables. How do we model such problems then? Which multi-model solutions exist?

Answer 1

Related to the crucial part of your question - the time-series aspect of your data:

Technically, you only need a finite set of points along each curve to get a vector representation of finite length. (as fine-grained as your application requires it). Now the problem should be clear, as it is exactly the same as in the case of the usual clustering of high-dimensional data.

• Pick a distance function for your high-dimensional data points
• Calculate the dissimilarity matrix
• Apply any number of clustering algorithms, such as knn, or k-means

I have never used clustering on curves in practice, but all you need for clustering in general are pairwise distances between your objects.

So there is nothing particularly tricky about it, perhaps only how to pick the right distance function if you have multiple time-series and also some categorical predictors. The computational complexity of clustering (which is btw. typically done in unsupervised manner) is NP hard, but that is not due to the time-series aspect of the data.