Time series 'clustering' in R

Question

I have a set of time series data. Each series covers the same period, although the actual dates in each time series may not all 'line up' exactly.

That is to say, if the Time series were to be read into a 2D matrix, it would look something like this:

date     T1   T2   T3 .... TN
1/1/01   100  59   42      N/A
2/1/01   120  29   N/A     42.5
3/1/01   110  N/A  12      36.82
4/1/01   N/A  59   40      61.82
5/1/01    05  99   42      23.68
...
31/12/01  100  59   42     N/A

etc 

I want to write an R script that will segregate the time series {T1, T2, ... TN} into 'families' where a family is defined as a set of series which "tend to move in sympathy" with each other.

For the 'clustering' part, I will need to select/define a kind of distance measure. I am not quite sure how to go about this, since I am dealing with time series, and a pair of series that may move in sympathy over one interval, may not do so in a subsequent interval.

I am sure there are far more experienced/clever people than me on here, so I would be grateful for any suggestions, ideas on what algorithm/heuristic to use for the distance measure and how to use that in clustering the time series.

My guess is that there is NOT an established robust statistic method for doing this, so I would be very interested to see how people approach/solve this problem - thinking like a statistician.

Answer 1

In data streaming and mining of time series databases, a common approach is to transform the series to a symbolic representation, then use a similarity metric, such as Euclidean distance, to cluster the series. The most popular representations are SAX (Keogh & Lin) or the newer iSAX (Shieh & Keogh):

• Symbolic Aggregate approXimation
• iSAX: Indexing and Mining Terabyte Sized Time Series

The pages above also contain references to distance metrics and clustering. Keogh and crew are into reproducible research and pretty receptive to releasing their code. So you could email them and ask. I believe they tend to work in MATLAB/C++ though.

There was a recent effort to produce a Java and R implementation:

• jmotif

I don't know how far along it is -- it's geared towards motif finding, but, depending on how far they've gotten, it should have the necessary bits you need to put something together for your needs (iSAX and distance metrics: since this part is common to clustering and motif finding).

Answer 2

Another way of saying "tend to move in sympathy" is "cointegrated".

There are two standard ways of calculating cointegration: Engle-Granger method and the Johansen procedure. These are covered in "Analysis of Integrated and Cointegrated Time Series with R" (Pfaff 2008) and the related R urca package. I highly recommend the book if you want to pursue these methods in R.

I also recommend that you look at this question on multivariate time series and, in particular, at Ruey Tsay's course at U. Chicago which includes all the necessary R code.

Answer 3

Clustering time series is done fairly commonly by population dynamacists, particularily those that study insects to understand trends in outbreak and collapse. Look for work on Gypsy moth, Spruce budoworm, mountain pine beetle and larch budmoth.

For the actual clustering you can choose whatever distance metric you like, each probably has it's own strengths and weeknesses relative to the kind of data being clustered, Kaufmann and Rousseeuw 1990. Finding groups in data. An introduction to cluster analysis is a good place to start. Remember, the clustering method doesn't 'care' that you're using a time series, it only looks at the values measured at the same point of time. If your two time series are not in enough synch over their lifespan they the won't (and perhaps shouldn't) cluster.

Where you will have problems is determining the number of clusters (families) to use after you've clusterd the time series. There are various ways of selecting a cut-off of informative clusters, but here the literature isn't that good.

Answer 4

See my answer to a similar question here. Long story short, do a fast Fourier transform of the data, discard redundant frequencies if your input data was real valued, separate the real and imaginary parts for each element of the fast Fourier transform, and use the Mclust package in R to do model-based clustering on the real and imaginary parts of each element of each time series. The package automates optimization over number of clusters and their densities.

Answer 5

You could also use the package clustDDist, which performs the leaders method and the hierarchical clustering method with different error measures:

http://r-forge.r-project.org/projects/clustddist/

The squared Euclidean distance favors patterns of distributions that have one steep high peak and therefore measure $$ d_4(x, y) = \frac{(x-y)^2}{y} $$ is sometimes preferred.