How to Conduct Time-Series Clustering Based on Curve Shape

clusteringrtime series

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:

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.
Cluster these transformed curves using the kml package in R.

I have two questions:

Is this a reasonable exploratory approach?
How can I transform my data into the longitudinal data format that kml will understand? Any R snippets would be much appreciated!

Best Answer

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.

alt text

Related Solutions

Solved – Time series clustering

Step 1

Perform a fast Fourier transform on the time series data. This decomposes your time series data into mean and frequency components and allows you to use variables for clustering that do not show heavy autocorrelation like many raw time series.

Step 2

If time series is real-valued, discard the second half of the fast Fourier transform elements because they are redundant.

Step 3

Separate the real and imaginary parts of each fast Fourier transform element.

Step 4

Perform model-based clustering on the real and imaginary parts of each frequency element.

Step 5

Plot the percentiles of the time series by cluster to examine their shape.

Alternately, you could omit the DC components of the fast Fourier transform to avoid your clusters being based on the mean and instead on the series defined by the Fourier transform, which represents the shape of the time series.

You will also want to calculate the amplitudes and phase angles from the fast Fourier transform so that you can explore the distribution of time series spectra within clusters. See this StackOverflow answer on how to do that for real-valued data.

You could also plot the percentiles of time series shape by cluster by computing the Fourier series from the amplitudes and phase angles (the resulting time series estimate will not perfectly match the original time series). You could also plot the percentiles of the raw time series data by cluster. Here is an example of such a plot, which came about from a harmonic analysis of NDVI data I just did today:

1st, 25th, 50th, 75th, and 99th percentiles of period-level NDVI measures by clusters derived from model-based clustering using Mclust package in R

Finally, if your time series is not stationary (i.e., mean and variance shift over time), it may be more appropriate to use a wavelet transform rather than a Fourier transform. You would do so at the cost of information about frequencies while gaining information about location.

Solved – Shape detection for time series data

I wouldn't go too deep into the clustering of the time series based on a complex curve analysis, as you have probably a lot of noise in your data and you will probably get strange (meaningless) clusters.

I think that an easier way will be to discover the major pattern of your data, which will most probably based on trends and seasonality (days of the week, weekends, holidays...). You can find it with plotting some statistics from each day (mean, morning trend, evening trend...) with time (day of the year, day of the week, day of the month...) on the x-axis. This will give you the baseline of your data, and therefore your basic clusters.

For example in R, if you have your date in col 1, and your mean in col 2, you can easily plot your base line of weekdays pattern by:

data[,3] <- as.factor(weekdays(data[,1]))
plot(data[,3],data[,2],main='mean by Day of Week')

The next step can be to identify your outliers and check if you can find a patterns there.

If you prefer to work in a reverse order; running automatic analysis like the ones you suggested or more Time-Series tuned as LB_Keogh or kml, this is OK. But you need to return to the meaningful interpretation of the findings with the logic above.

Best Answer

Related Solutions

Solved – Time series clustering

Solved – Shape detection for time series data

Related Question