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:

Improve this question
$\endgroup$
6
  • $\begingroup$ Have you tried mutual information? $\endgroup$
    – Alexandru Daia
    Jun 12, 2015 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, 2015 at 6:33
  • $\begingroup$ Check my answer on DTW clustering of time series. $\endgroup$
    – Aleksandr Blekh
    Jun 12, 2015 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, 2015 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, 2015 at 9:05

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ if mutual information is a type of correlation, what can be done to make mutual information distinguish between negative correlation events and positive correlation events, given that mutual information is bounded between $(0,\infty)$ whereas correlation spans $(-1,1)$ $\endgroup$
    – develarist
    Aug 28, 2020 at 22:48
  • $\begingroup$ Quick aside: MI is upper bounded by the lowest of the entropies of X or Y. You can't convey more information about an rv than the entropy of the rv itself. So I(X;Y) <= min(H(X), H(Y)). To answer your main question, it is not clear to me how you can distinguish negative and positive correlations through measures like MI. $\endgroup$
    – Bob Baxley
    Aug 30, 2020 at 13:43
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.

Improve this answer
$\endgroup$
4
  • $\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, 2015 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, 2015 at 14:53
  • $\begingroup$ No. But, approximation is allowed if it can lead to a reasonable solution. $\endgroup$
    – mic
    Jun 18, 2015 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, 2015 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.