2
$\begingroup$

I am clustering time series data. Each entry is an univariate time series. Aim is to mine relevant features to classify the series. I looked up here, and other general references for this purpose. Most of the features used encode information about the entire time series.

But in my case, based on the exploratory analysis, almost all time series are evolving with time, i.e. the means, spectral powers are all changing with time.(ex: The simple average is decreasing for half the entries over time, and increasing for the rest) How do I take these evolving features into account?

The above-mentioned reference has one possible solution, using an ARIMA model. Is there a simpler way to do this, without involving model-fitting? Moreover, what about features like the spectral distribution, etc? One way is to create blocks of the time series, and say compute the mean for each block and use all of these as variables in the clustering. But here the partitioning size is subjective, and there is no single index to account for the resultant trend, making the clustering difficult.

I'm doing the analysis in R, in case the algorithms that can be used are limited by the programming language.

$\endgroup$
2
$\begingroup$

This is a complex challenge with many ways to think about it. Some of the most basic frameworks date back to the multidimensional scaling work of the 60s and 70s in terms of a multimodal data cube. For instance, Pieter Kroonenberg discusses three mode data with the modes identified as 1) units of analysis (e.g., cross sections of people, machines, objects, whatever), 2) features or descriptors, and 3) temporality or time. To your point and depending on the context, within that basic and idealized data cube things can be evolving quite dynamically. These issues become the input into quantitative and strategic decision-making.

To make the distinctions between modes clearer, here are some of the ways they can vary:

1) The presence or absence of units in a model as a function of sampling can and will lead to issues related to selection bias. Heckman won a Nobel Prize for his work on this topic. In addition, objects under dynamic analysis can be balanced or unbalanced wrt sample size, N. Nearly all theoretical models assume balanced or fixed N, e.g., the models proposed in Wooldridge's Econometric Analysis of Cross Section and Panel Data, among many others. This is largely due to the fact that there simply aren't many good solutions or workarounds for models with unbalanced cross sections.

2) Features can evolve as data is updated or new factors and descriptors are discovered and introduced while old ones are discarded. This used to be a huge problem with old mainframe-type applications when stored data had fixed layouts with little or no room for the introduction of new features. For instance, the FBI's Uniform Crime Reporting data hasn't changed its layout since the 1960s. To account for changed and/or updated numbers in reporting, they have a complicated system of flags indicating where, what and how previous entries have been changed. The introduction of client-server and relational database mgmt systems (RDBMS) in the 90s ameliorated these issues somewhat with more flexible transaction accounting but by no means solved them. Today's unstructured text and image data has added greatly to the computational and combinatorial complexity of these issues. Another important issue has to do with handling missing values.

3) Classic univariate time series models such as Box-Jenkins, ARIMA, and so on, assume a fixed set of information across T, time. With dynamic panel data, this can be a problematic, even unrealistic assumption. Data can have mixed frequencies, e.g., daily, weekly, monthly, quarterly, etc., where the predictors are in one temporal unit and the target is in another. Ghysels has a class of models he calls MIDAS (MIxed DAta Sampling) which attempts to compensate for these issues. Other challenges include right censoring (survival beyond the time frame of the study), suggesting survival modeling to predict the likelihood or timing of future failure, death or exit. In Cook and Campbell terms this can mean attrition but in panel data this can also involve limited or fixed tenure memberships requiring the introduction of new panel members that are matched to units whose tenure is expiring. There can be left censoring where units are born or introduced after a study is initialized. Consideration needs to be given to things such as elasticities, lead-lag structures, seasonality, autocorrelation, trends, drift, cointegration, unit roots, and so on. Many ARIMA-type practitioners advocate detrending, deseasonalizing and/or whitening the data to produce HAC (heteroscedastic, autocorrelated consistent) errors with the goal of minimizing the impact of these data challenges as well as the potential for spurious, trend-based association. However, this approach is not universally recommended or without controversy as, many times, the cure can be worse than the disease.

From an analytic point of view however, it is very difficult to understand the dynamics of data with everything moving at once. One common workaround is to fix two of the modes, allowing the third to vary. This provides a more unified framework, greatly simplifying the process of understanding and insight.

Your question is focused on the temporal or longitudinal dynamics of change. Given that, you might want to fix the units and features of the analysis to those available across the entire span or time frame for the analysis, producing balanced N with a fixed set of features. Consideration should be given to how missing values, if any, are to be handled. To your concern about "creating blocks of the time series," there is no all-purpose, "swiss army knife" answer to this question. The decision should be based on domain-specific knowledge and insight as to how the data should be discretized or "chunked" into meaningful time slices.

Having gotten this far, there remains the question of the longitudinal clustering model or method to be employed. Classic clustering algorithms such as k-means and k-nearest neighbor are not dynamic, i.e., they assume a static cross section of data, and therefore aren't appropriate tools for your purpose. Nor is ARIMA appropriate since it is not a clustering algorithm. That said, there are a multitude of possible methods to choose from. Aggarwal and Reddy's (eds.) book, Data Clustering, has a chapter devoted to discussion and suggestions of many possible models.

Broadly speaking and depending on the volume and type of information under analysis, my suggestions would include variants of supervised, finite mixture, latent class or hidden markov chain models (HMMs). Latent class mixture models date back to the 80s. There are probably R modules for this but, not being an R user, I can't recommend any. I am only aware of PolCA, a free, latent class R module that is intended for use only with features that are entirely categorical or nominally scaled (i.e., it is not for mixtures of scale types). For a reasonable price, Statistical Innovations' Latent Gold package offers one of the best software solutions for this class of models.

There are now some excellent books on HMMs available including MacDonald's Hidden Markov and Other Models for Discrete-Valued Time Series. In addition, Steve Scott was one of the early Bayesian proponents of this method and his website has many papers describing his approaches (https://sites.google.com/site/stevethebayesian/). If you have massive numbers of categorical features, David Dunson's Bayesian tensor model(s) might be useful.

All of the approaches mentioned so far are moment-based, i.e., the analysis is based on the statistical properties of the empirical distribution of the data. An alternative, non-moment based, complexity and information-theoretic approach is Andreas Brandmaier's permutation distribution clustering, which uses a distance metric for determining similarities between pairs of time series. He has developed an R module for this purpose (https://cran.r-project.org/web/packages/pdc/pdc.pdf). Personally, I much prefer Brandmaier's approach to other, similar methods such as Keogh's iSax.

You may want to fix the time period mode, creating a single cross section within which to drive insight into how the features impact the clustering. At this level of analysis, classic clustering algorithms such as k-means or knn are appropriate. A good, moment-based, global approach to clustering time series (the units) like these is explained in a paper by Hyndman, et al., Dimension Reduction for Clustering Time Series Using Global Characteristics, (http://www.robjhyndman.com/papers/wang2.pdf). Along with estimating the moments as Hyndman recommends, there are many other "global" metrics possible with information like this. These include estimating AICs (proxy for data complexity), coefficients of variation for the continuous metrics, output from tests such as augmented Dickey-Fuller for evidence of unit roots, drift, trends, etc., Durbin-Watson statistics for autocorrelation, percentage growth metrics, slopes (first derivatives), and so on. By creating ensembles of metrics across a large number of time series, clustering becomes better informed.

$\endgroup$
1
$\begingroup$

One good place to start is Eamonn Keogh pubs. Pay attention to this paper found there:

Thanawin Rakthanmanon, Eamonn Keogh, Stefano Lonardi, and Scott Evans (2011). Time Series Epenthesis: Clustering Time Series Streams Requires Ignoring Some Data. ICDM 2011

I would look at it first because it points out a pitfall in Time Series Clustering you should keep in mind.

This next paper may be what you are looking for:

Liudmila Ulanova, Nurjahan Begum, Mohammad Shokoohi-Yekta and Eamonn Keogh (2016). Clustering in the Face of Fast Changing Streams. SDM (2016)

A web search on "Time Series Clustering" will yield many resources. It is a rich and evolving field with lots of techniques, and much code and datasets.

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