Is it possible to do time-series clustering based on curve shape?

I have sales data for a series of outlets, and want to categorise them based on the shape of their curves over time. The data looks roughly like this (but obviously isn't random, and has some missing data):

n.quarters <- 100
n.stores <- 20
if (exists("test.data")){
rm(test.data)
}
for (i in 1:n.stores){
interval <- runif(1, 1, 200)
new.df <- data.frame(
var0 = interval + c(0, cumsum(runif(49, -5, 5))),
date = seq.Date(as.Date("1990-03-30"), by="3 month", length.out=n.quarters),
store = rep(paste("Store", i, sep=""), n.quarters))
if (exists("test.data")){
test.data <- rbind(test.data, new.df)
} else {
test.data <- new.df
}
}
test.data$store <- factor(test.data$store)


I would like to know how I can cluster based on the shape of the curves in R. I had considered the following approach:

1. Create a new column by linearly transforming each store's var0 to a value between 0.0 and 1.0 for the entire time series.
2. Cluster these transformed curves using the kml package in R.

I have two questions:

1. Is this a reasonable exploratory approach?
2. How can I transform my data into the longitudinal data format that kml will understand? Any R snippets would be much appreciated!
-
you might get a few ideas from an earlier question on clustering individual longitudinal data trajectories stats.stackexchange.com/questions/2777/… – Jeromy Anglim Oct 5 '10 at 7:52
@Jeromy Anglin Thanks for the link. Did you have any luck with kml? – fmark Oct 5 '10 at 12:24
I've had a quick look, but for the moment I'm using a customised cluster analysis based on selected features of the individual time series (e.g., mean, initial, final, variability, presence of abrupt changes, etc.). – Jeromy Anglim Oct 6 '10 at 2:59
Is this a duplicate? stats.stackexchange.com/questions/3238/… – Rob Hyndman Oct 7 '10 at 1:32
@Rob This question doesn't seem to assume irregular time intervals, but indeed they are close one each other (I didn't remind of the other question at the time of my writings). – chl Oct 7 '10 at 6:11
show 1 more comment

Several directions for analyzing longitudinal data were discussed in the link provided by @Jeromy, so I would suggest you to read them carefully, especially those on functional data analysis. Try googling for "Functional Clustering of Longitudinal Data", or the PACE Matlab toolbox which is specifically concerned with model-based clustering of irregularly sampled trajectories (Peng and Müller, Distance-based clustering of sparsely observed stochastic processes, with applications to online auctions, Annals of Applied Statistics 2008 2: 1056). I can imagine that there may be a good statistical framework for financial time series, but I don't know about that.

The kml package basically relies on k-means, working (by default) on euclidean distances between the $t$ measurements observed on $n$ individuals. What is called a trajectory is just the series of observed values for individual $i$, $y_i=(y_{i1},y_{i2},\dots,y_{it})$, and $d(y_i,y_j)=\sqrt{t^{-1}\sum_{k=1}^t(y_{ik}-y_{jk})^2}$. Missing data are handled through a slight modification of the preceding distance measure (Gower adjustment) associated to a nearest neighbor-like imputation scheme (for computing Calinski criterion). As I don't represent myself what you real data would look like, I cannot say if it will work. At least, it work with longitudinal growth curves, "polynomial" shape, but I doubt it will allow you to detect very specific patterns (like local minima/maxima at specific time-points with time-points differing between clusters, by a translation for example). If you are interested in clustering possibly misaligned curves, then you definitively have to look at other solutions; Functional clustering and alignment, from Sangalli et al., and references therein may provide a good starting point.

Below, I show you some code that may help to experiment with it (my seed is generally set at 101, if you want to reproduce the results). Basically, for using kml you just have to construct a clusterizLongData object (an id number for the first column, and the $t$ measurements in the next columns).

library(lattice)
xyplot(var0 ~ date, data=test.data, groups=store, type=c("l","g"))

tw <- reshape(test.data, timevar="date", idvar="store", direction="wide")
parallel(tw[,-1], horizontal.axis=F,
scales=list(x=list(rot=45,
at=seq(1,ncol(tw)-1,by=2),
labels=substr(names(tw[,-1])[seq(1,ncol(tw)-1,by=2)],6,100),
cex=.5)))

library(kml)
names(tw) <- c("id", paste("t", 1:(ncol(tw)-1)))
tw.cld <- as.cld(tw)
cld.res <- kml(tw.cld,nbRedrawing=5)
plot(tw.cld)


The next two figures are the raw simulated data and the five-cluster solution (according to Calinski criterion, also used in the fpc package). I don't show the scaled version.

-
Thanks for your very detailed answer chi. I've got kml running on my data, but as you suggested it is clustering mostly based on magnitude rather than curve shape, so I'm trying a few pre-processing steps to see if I can improve matters. The work by Sangalli et al. looks very promising for what I want to do - I cannot find an implementation of their approach however. I probably do not have time to create my own implementation of their work for this project, hwoever. Are you aware of any FOSS implementations? – fmark Oct 7 '10 at 6:45
@fmark No OSS implementation to my knowledge (the work is quite recent, though); they use k-means and k-medoids which are both available in R. To my opinion, the most critical parts are to generate template curves and implement the warping function. For that, you could find additional infos by looking at morphometry/procruste analysis, or lookup the code of the Matlab PACE toolbox (but this should be full of EM or things like that). My best recommendation would be: Ask the author for any free of charge implementation of their algorithm. – chl Oct 7 '10 at 6:53
I'll report back if I get an affirmative :) Their paper k-mean alignment for curve clustering has some more implementation details that also might be useful to someone wanting to do this themselves. – fmark Oct 7 '10 at 7:10

You could look at the work of Eamonn Keogh (UC Riverside) on time series clustering. His website has a lot of resources. I think he provides Matlab code samples, so you'd have to translate this to R.

-
 Thanks for the link! – chl♦ Oct 7 '10 at 17:48

An alternative approach was published by a stats.se regular in Wang, Xiaozhe, Kate Smith, and Rob Hyndman.

‘Characteristic-Based Clustering for Time Series Data’. Data Mining and Knowledge Discovery 13, no. 3 (2006): 335–364.

They write:

This paper proposes a method for clustering of time series based on their structural characteristics. Unlike other alternatives, this method does not cluster point values using a distance metric, rather it clusters based on global features extracted from the time series. The feature measures are obtained from each individual series and can be fed into arbitrary clustering algorithms, including an unsupervised neural network algorithm, self-organizing map, or hierarchal clustering algorithm. Global measures describing the time series are obtained by applying statistical operations that best capture the underlying characteristics: trend, seasonality, periodicity, serial correlation, skewness, kurtosis, chaos, nonlinearity, and self-similarity. Since the method clusters using extracted global measures, it reduces the dimensionality of the time series and is much less sensitive to missing or noisy data. We further provide a search mechanism to find the best selection from the feature set that should be used as the clustering inputs.

R code is available on Rob's blog.

-