8
$\begingroup$

I am collecting a group of multivariate time sequences. For example, there are 2000 time series. Each time series is of 12 dimensions.

Are there any systematic models/algorithms that can cluster multivariate time series? For instance, I would like to identify some time series that are very different with others.

Moreover, for the online monitoring, I may run this algorithm in an on-time fashion. For instance, every 10 minutes, I run this kind of algorithm against the time series covering 10 minutes. Are there any efficient algorithms with respect to this?

$\endgroup$
5
$\begingroup$

The R package pdc offers clustering for multivariate time series. Permutation Distribution Clustering is a complexity-based dissimilarity measure for time series. If you can assume that differences in time series are due to differences w.r.t. complexity and, specifically not due to differences in means, variances, or the moments in general, this may be a valid approach. The algorithmic time complexity of calculating the pdc representation of a multivariate time series is in O(DTN) with D being the number of dimensions, T being the length of the time series and N being the number of time series. This is probably as efficient as it gets since a single sweep over each dimension of each time series is enough to obtain the compressed complexity representation. This representation can be used to calculate dissimilarity between two time series at low cost (depending on the chosen representational complexity which can either be pre-specified or derived from the data).

Here is a simple worked example with a hierarchical clustering of multivariate white-noise time series (the plot illustrates only the first dimension of each time series):

require("pdc")

num.ts <- 20 # number of time series
num.dim <- 12 # number of dimensions
len.ts <- 600*10 # number of time series

# generate Gaussian white noise
data <- array(dim = c(len.ts, num.ts, num.dim),data = rnorm(num.ts*num.dim*len.ts))

# obtain clustering with embedding dimension of 5
pdc <- pdclust(X = data, m=5,t=1)

# plot hierarchical clustering
plot(pdc)

Hierarchical clustering of multivariate white noise

The command pdcDist(data) generates a dissimilarity matrix:

Since the data are all white noise, there is no apparent structure in the dissimilarity matrix.

         1        2        3        4        5        6        7
2 4.832894                                                      
3 4.810718 4.790286                                             
4 4.812738 4.796530 4.809482                                    
5 4.798458 4.772756 4.751079 4.786206                           
6 4.812076 4.793027 4.798996 4.758193 4.751691                  
7 4.786515 4.771505 4.754735 4.837236 4.775775 4.794706         
8 4.808709 4.832403 4.722993 4.781267 4.784397 4.776600 4.787757

For more information refer to:

Brandmaier, A. M. (2015). pdc: An R package for complexity-based clustering of time series. Journal of Statistical Software, 67. doi:10.18637/jss.v067.i05 (Full text)

$\endgroup$
  • 1
    $\begingroup$ +1 @Brandmaier thank you for the response and for an excellent package. $\endgroup$ – forecaster Jul 27 '16 at 23:58
2
$\begingroup$

Check RTEFC ("Real Time Exponential Filter Clustering") or RTMAC ("Real Time Moving Average Clustering), which are efficient, simple real-time variants of K-means, suited for real time use when prototype clustering is appropriate. They cluster sequences of vectors. See https://gregstanleyandassociates.com/whitepapers/BDAC/Clustering/clustering.htm and the associated material on representing multivariate time series as one larger vector at each time step (the representation for "BDAC"), with a sliding time window. Pictorially,

These were developed to simultaneously accomplish both filtering of noise and clustering in real time to recognize and track different conditions. RTMAC limits memory growth by retaining the most recent observations close to a given cluster. RTEFC only retains the centroids from one time step to the next, which is enough for many applications. Pictorially, RTEFC looks like:

$\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.