5
$\begingroup$

I am interested in clustering $N$ time series of $T$ 'values' each. These values are distributions (which can be represented by their cumulative distribution functions (cdf), or their probability density functions (pdf), or more convenient forms such as square-root pdfs yielding a simple spheric geometry).

For comparing given distributions, there is an extensive literature on statistical distances (KL, Hellinger, Wasserstein, and so on), but for comparing given time series of distributions, I am not sure whether there is any literature at all?

Such distances should somehow take into account dynamics information besides the distribution proximity at time t. Ideally, I wish I could have a kind of information factorization similar to this result.

I am wondering if such distances already exist and whether this kind of problem has already been formulated in the literature?

-- edit for further precisions and answer to comments:

Thanks for your answer, but dynamic time warping does not suit to my need. This dp technique only captures a rough similarity of shapes by allowing non-linear time distortion. But, it does not amount for the whole information in these time series, e.g. what about the distribution of distortions? Do the distributions of a given time series vary smoothly through time or violently? DTW is not always the solution, for instance, when working with random walks, it does not make sense to use a DTW since there are no time patterns! In this case, the only information is "correlation" and "distribution" (cf. Sklar's theorem in Copula Theory), and the paper cited above.

-- edit 2 Here are the papers that are somehow related to my question:

$\endgroup$
  • $\begingroup$ Have you tried mutual information? $\endgroup$ – Alexandru Daia Jun 12 '15 at 6:05
  • $\begingroup$ For measuring dependency between variables, I prefer using copulae, [though mutual information and copula are very much the same]{ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6077935}! Yet, in my case, dependency is not the only information I care about / in this kind of time series. In fact, I wish I could obtain [a result similar to this one]{arxiv.org/pdf/1506.00976v1.pdf}. $\endgroup$ – mic Jun 12 '15 at 6:33
  • $\begingroup$ Check my answer on DTW clustering of time series. $\endgroup$ – Aleksandr Blekh Jun 12 '15 at 7:59
  • $\begingroup$ Basically, I have a time series of time series. Let's assume that I use at time $t$ a DTW (but I would rather use $\phi = \arccos \langle p,q \rangle$), how to extend it to the whole time series? This is really my point. $\endgroup$ – mic Jun 12 '15 at 8:36
  • $\begingroup$ You're welcome. My advice does not imply that I think that TDW is universal solution. I just thought that papers, referenced in my linked answer, potentially might contain some ideas, useful to your case. I don't have an answer for your "time series of time series" case. As for analyzing distortions, you could consider applying time series anomaly detection and analysis approaches. $\endgroup$ – Aleksandr Blekh Jun 12 '15 at 9:05
4
$\begingroup$

This is similar to the fundamental information theory problem that Shannon explored. In that domain, it is framed this way: given two rvs, X and Y, what information does X convey about Y?

An example would be that I create sequence of numbers/bit/letters from a known PDF (X) and you receive a distorted version of those values for which you also know the PDF (Y). The mutual information is the number of bits that Y communicates about X which can be thought of as a type of correlation.

In the case of time varying PDFs (ie stochastic processes), information theory would just treat the ensemble of rvs as one joint rv and then calculate the mutual information of the joint PDFs. If the PDFs are iid, then significant simplifications are possible. Joint Gaussian PDFs also make things easier.

Another information theory concept that might be useful is the entropy rate of a process. ER is a quantification of the amount of information contained in a process. Depending on your problem, you might be able to compute the ER for each process and then use those values as realizations of a feature that can be grouped with a clustering algorithm.

$\endgroup$
0
$\begingroup$

Why would you need a distance when you have the pdf?

Time series can be assigned to clusters based on their fit to the cluster's pdf. This also means the method works for ragged timeseries, for which distance methods would break down.

$\endgroup$
  • $\begingroup$ By "Time series can be assigned to clusters based on their fit to the cluster's pdf. " you mean the mixture modelling EM-based clustering? I am not sure to understand your point. Basically, pdfs are my object of study, i.e. my dataset consists in $N \times T$ pdfs. Any of these N series can be viewed as a pdf which is evolving "smoothly" through time, and we have T regularly spaced snapshot of it. So, I want to capture its distorition dynamics AND I want to capture how it relates to other pdfs time series both in pdfs similarity and dynamics. $\endgroup$ – mic Jun 17 '15 at 11:41
  • $\begingroup$ @mic think my reading of your post oversimplified the question. Do we have any simplifying assumptions, e.g. could the distribution at time $t$ have a parametric form? $\endgroup$ – conjectures Jun 18 '15 at 14:53
  • $\begingroup$ No. But, approximation is allowed if it can lead to a reasonable solution. $\endgroup$ – mic Jun 18 '15 at 15:40
  • 1
    $\begingroup$ @mic what are your samples? Do you actually have the distributions at all times for each series or do you have a sample(s) from the distribution at time $t$ in series $n$? $\endgroup$ – conjectures Jun 18 '15 at 15:59

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.