2
$\begingroup$

Context

Consider the following problem where we have two time dependent (yearly) measures:

  • Fertility rate
  • Life expectancy

And a dimension: country. In other words we have over two hundred "bivariate" time series, one for each country.

This data can be plotted in a scatter plot for a single year (LHS) and animating the scatter plot over several years gives the following trajectory path (RHS). See here for the gif animation.

enter image description here

Question

What approaches, preprocessing steps and algorithms can be used in order to cluster the trajectories of each country over time ? For example, a use case would be to find a cluster of countries for which the life expectancy falls abruptly (and against the overall trend) during the mid 90's. This is partly due to the AIDS epidemic in sub-saharan Africa at the time.

I am familiar with various clustering techniques for longitudinal data, but I struggle to understand how to transform this ordered data set into a format which can be fed into an algorithm.

Some sources / ideas \ comments

The following SE posts offer some help

The blocking point in my understanding is that there are ordered sets of points, which means that using clustering algorithms on the unordered data may be miss leading. For example in the picture below

enter image description here

Trajectories are close together when un-ordered, but far when ordered.

$\endgroup$
1
$\begingroup$

I think you are aiming to explore two overlapping problems. Preprocessing time-trajectories and clustering time-trajectories. Functional data analysis (FDA) and in particular the methodology behind Multivariate Functional Principal Components seems like a potential avenue for what you want.

In respect to preprocessing:

Dynamic Time Warping [1] is just one of the multiple and earliest (prior to 1980) ways of exploring the curve alignment problem. Of the top of my head I can think of "pairwise synchronization"[2] approaches, "quantile synchronisation"[3] approaches, "self-modelling warping functions"[4] approaches as well as "square-root velocity functions"[5] approaches. All these approaches try to align data registered over a continuous domain (most often than not, time).

In respect to clustering:

Clustering trajectories has been a task visited by multiple scientific communities. I would not confine my search to Statistics community; for example, Zheng [6] gives an excellent overview of what takes place on the Computer Science side of things. That said and turning back to FDA-based approaches, Jacques & Preda [7] offer a relatively nice overview of the matter. In general, most approaches take the approach "align, get relevant representation (i.e. one that encapsulate the function-like nature of the data and does not treat the data as a simple multivariate sample) and then cluster". There is a smaller community with model-based approaches where alignment and clustering are done concurrently (e.g. [8]). As mentioned it seems the data you are concerned with are multivariate (or more accurately bivariate) so probably approached related to multivariate functional principal components (e.g. [9]) would be helpful to get a relevant representation prior to clustering. (You may also find my answer here on :How to consider different samples in functional data clustering? useful.)

Notice that earlier approaches like the DTW, focused on time-registration and generally regarded the amplitude changes as "not so important". That was a reasonable assumption for their working environment (e.g. Speech processing, later on vehicle trajectories) where difference in phases (i.e. when the amplitude of the function changed) are usually more important that difference in amplitude (i.e. how much the amplitude of function changed). For example, when doing phoneme registration we do not really care how loud the speaker talks or when we doing air-traffc registration we do not care a lot about a plane's cruising altitude. In contrast, biological/medical applications (e.g. how fast does a particular animal reach peak weight, and what that peak weight is) people often care about both.

For something quick out of the box I would suggest looking at the CRAN has a separate view on Functional Data Analysis. There is a specific section of algorithms addressing the task of clustering functional data.

References:

  1. H. Sakoe & S. Chiba. Dynamic programming algorithm optimization for spoken word recognition. (1978) IEEE Transactions on Acoustics, Speech and Signal Processing
  2. R. Tang & H.-G. Mueller. Pairwise curve synchronization for functional data. (2008) Biometrika
  3. Z. Zhang & H.-G. Mueller. Functional density synchronization. (2011) Computational Statistics and Data Analysis
  4. D. Gervini & T. Gasser. Self-modelling warping functions. (2004) Journal of the Royal Statistical Society. Series B
  5. S. Kurtek, A. Srivastava, & W. Wu. Signal estimation under random time-warpings and nonlinear signal alignment. (2011) Advances in Neural Information Processing Systems
  6. Y. Zheng. Trajectory Data Mining: An Overview. (2011) ACM Transactions on Intelligent Systems and Technology
  7. J. Jacques & C. Preda. Functional data clustering: a survey. (2014) Advances in Data Analysis and Classification
  8. E. Fu & N. Heckman. Model-based curve registration via stochastic approximation EM algorithm. (2018) Computational Statistics and Data Analysis (to appear)
  9. C. Happ & S. Greven. Multivariate Functional Principal Component Analysis for Data Observed on Different (Dimensional) Domains. (2018) Journal of the American Statistical Association
$\endgroup$
  • $\begingroup$ Excellent thanks a lot for all these references. Let me know if you find something like a tutorial or worked example $\endgroup$ – Xavier Bourret Sicotte Sep 22 '18 at 21:25
  • $\begingroup$ Cool, I am happy I could help. I think you are a Pythonista right? Quickly checking for Python "curve registration" example, returned a Github repo named: pyFDA, I have not used it and I cannot intelligently comment on the correctness of it but it does contain a registration example you might want to check out. The Square Root Velocity stuff in Python can be found in fdasrsf_python; I have met the dev once in a conference, he seemed on top of what he was doing. Give it a spin! $\endgroup$ – usεr11852 says Reinstate Monic Sep 23 '18 at 9:24
1
$\begingroup$

Well. You already found the answer three times...

Use a trajectory distance function such as DTW. It solves the problem you mention quite well, because it doesn't ignore order.

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