39
$\begingroup$

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.

$\endgroup$
24
$\begingroup$

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):

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:

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).

$\endgroup$
  • 1
    $\begingroup$ This looks like a good, tractable starting point. thanks for the links. $\endgroup$ – morpheous Oct 2 '10 at 17:17
  • 4
    $\begingroup$ Holy crap, I think that SAX page is the ugliest web page I have ever seen! $\endgroup$ – naught101 Apr 5 '12 at 1:44
18
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I had come accross cointegration a few years back - but it did seem terribly complicated to me (I didn't understand it!). I was hoping there would be a less theoretical (i.e. more practical) solution ... $\endgroup$ – morpheous Oct 1 '10 at 15:08
  • 3
    $\begingroup$ The Engle-Granger method is not especially complicated: you just take the residuals of a regression between the two series and determine if it has a unit root. This is certainly practical: it's used regularly for a broad spectrum of problems. That said, I imagine that any answer to your question will require some statistical knowledge (for instance, you should understand things like stationarity, independence, etc.)... $\endgroup$ – Shane Oct 1 '10 at 15:19
  • $\begingroup$ is there a better way to do this than to test all pair-wise series for co-integration (with the same ideal in mind to cluster series together?) Also wouldn't this suggestion be dependent on the fact that the series themselves are integrated at the onset? $\endgroup$ – Andy W Oct 1 '10 at 16:34
  • $\begingroup$ @Andy: I'm sure that there is a better way, and I look forward to hearing about it. This is a pretty basic approach. $\endgroup$ – Shane Oct 1 '10 at 16:38
  • 1
    $\begingroup$ > i can't suggest anything else, but cointegration is both very fragile ('parametric assumptions' gone wild series) in practice and ill suited for the task at hands: at each step, it amounts to doing hierarchical clustering, at most merging two series unto one (the co-integrated mean). $\endgroup$ – user603 Oct 1 '10 at 21:09
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Chris, regular clustering won't cut it. You either have to acknowledge that a series is highly correlated with it's own past by putting each $y_{1,t}$ as a dimension of it's own (i.e. resulting in N*T dimensions) or you trow all the dimensions together, but then (given the high correlation inside a series) you will always end up with a single cluster. Also most clustering methods are ill-suited/advised for highly correlated variables (there is a more or less bending assumption of spherical clusters). $\endgroup$ – user603 Oct 1 '10 at 21:01
  • 1
    $\begingroup$ @user603 Can you explain "You either have to acknowledge that a series is highly correlated with it's own past by putting each y1,t as a dimension of it's own (i.e. resulting in N*T dimensions)" please? $\endgroup$ – B_Miner Nov 19 '11 at 21:32
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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