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

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

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.