Visual Recurrence Analysis Demonstration
Download Visual Recurrence Analysis v4.0
Recurrence Plots
Recurrence Plots (RPs) were first described by J.Eckmann, S.Kamphorst and D.Ruelle in "Recurrence plots of dynamical systems" in 1987. RP is a relatively new graphical device for the qualitative assessment of time series. With RP, one can graphically detect hidden patterns and structural changes in data or see similarities in patterns across the time series under study. RP is also an excellent tool for visualization of high-dimensional dynamics. Say, you have a function y = f(x) and you wish to examine its behavior. So, you plot Y vs. X on a regular graph, -- that's the way to do it. But what if your function is more complex, such as y = f(x, w, z, r) ? There is no way to plot all variables at the same time, -- we think and see in 3 dimensions at most! Here is where recurrence plots come very useful. With RP, you can plot and visualize the system dynamics in any number of dimensions! However, the interpretation of RP is not as straightforward as it is with other, "conventional" types of graphs, and it requires careful analysis.
Before a RP is constructed, a one-dimensional time series (sequence of observations) can be expanded into a higher-dimensional space, in which the dynamic of the underlying generator takes place. This is done using a technique called "delayed coordinate embedding", which recreates a phase space portrait of the dynamical system under study from a single (scalar) time series. As remarkable as it seems, it has been proven mathematically that one can recreate a topologically equivalent picture of the original multi-dimensional system behavior by using the time series of a single observable variable. For example, the stock market is a highly complex system with a large number of participants and factors that influence its dynamics. By using delay coordinate embedding, one can recreate the dynamics of that multi-dimensional system from a single observable variable (say the Dow Jones Industrial Averages index) and (hopefully) to predict it. The idea is that the effect of all the other (unknown) variables is already reflected in the system output, its observable signal.
To expand a one-dimensional signal into an M-dimensional phase space, one substitutes each observation in the original signal X(t) with vector
y(i) = (x(i), x(i + d), x(i + 2d), , x(i + (m-1)d),
where
i is the time index,
m is the embedding dimension
d is the time delay.
As a result, we have a series of vectors:
Y = {y(1), y(2), y(3), , y(N-(m-1)d) ),
where
N is the length of the original series.
The idea of such reconstruction is to capture the original system states at each time we have an observation of that system output. Each unknown state S(t) at time t is approximated by a vector of delayed coordinates
Y(t) = { x(i), x(i - d), x(i - 2d), , x(i - (m-1)d }
Once the dynamical system is reconstructed, RP can be used to show which vectors in the reconstructed space are close and far from each other. Specifically, one calculates the (Euclidean) distances between all pairs of vectors and codes them as colors. Essentially, RP is a color-coded matrix, where each [i][j]th entry is calculated as the distance between vectors Y(i) and Y(j) in the reconstructed series. The distances are then mapped to colors from the preset color map and are displayed as colored pixels in their corresponding places. Recurrence plot is essentially a graphical representation of a correlation integral. The important distinction (and an advantage of the recurrence plots) is that the recurrence plots, unlike the correlation integrals, preserve the temporal dependence in the time series, in addition to the spatial dependence.
To make RP more meaningful, the color mapping should be meaningful, too. For example, "hot" colors (yellow, red, and orange) can be associated with small distances between the vectors, while "cold" colors (blue, black) may be used to show large distances. This way one can visualize and study the motion of the system trajectories and infer some characteristics of the dynamical system that generated the time series. For random signals, the uniform (even) distribution of colors over the entire RP is expected. The more deterministic the signal is, the more structured the recurrence plot will be.
Below is the recurrence plot of the standard human limb lead II electrocardiogram, embedded in the three-dimensional phase space.
Average Mutual Information Function
Mutual information function can be used to determine the "optimal" value of the time delay for the state space reconstruction, as first proposed in an article by Andrew M. Fraser and Harry L. Swinney in "Independent coordinates for strange attractors from mutual information", Phys. Rev. A 33 (1986) pp. 1134-1140. The idea is that a good choice for the time delay T is one that, given the state of the system X(t), provides maximum new information with measurement at X(t+T). Mutual information is the answer to the question, "Given a measurement of X(t), how many bits on the average can be predicted about X(t+T)?" A graph of I(T) starts off very high (given a measurement X(t), we know as many bits as possible about X(t+0)=X(t)). As T is increased, I(T) decreases, then usually rises again. It is suggested that the value of time delay where I(T) reaches its first minimum be used for the state space reconstruction.
To calculate average mutual information, choose Analysis | General Nonlinear Analysis | Mutual Information from the main menu. Once the dialog shows up, set the options as desired and click "Calculate average mutual information" button. The "Detail" option controls the smoothness of the resulting plot. While the shape of that plot may change for different values of "Detail" option, the first minimum of the mutual information function should not change, except, perhaps, for the leftmost position of the "Detail" control.
Below is the mutual information function calculated for the Lorenz attractor (file Lorenz.dat included with VRA). As can be seen from the graph, the mutual information reaches its first minimum at the time delay of 16. That is a value that can be considered "optimal" for the time delayed embedding.
False Nearest Neighbors
The False Nearest Neighbors is a method of choosing the minimum embedding dimension of a one-dimensional time series, suggested by Kennel et al. This method finds the nearest neighbor of every point in a given dimension, then checks to see if these points are still close neighbors in one higher dimension. The percentage of False Nearest Neighbors should drop to zero when the appropriate embedding dimension has been reached. While the FNN method is intuitive and easy to implement, it is not straightforward to use and interpret. Among some other things, the FNN method requires setting two threshold values to some rather arbitrary values, which are then used to determine the false neighbors. In addition, FNN method is sensitive to the sampling rate of the time series.
In VRA, the FNN method is implemented with some modifications from the original FNN method. It does not have any free parameters to set, it is robust in the presence of noise, and is not sensitive to sampling rate. The algorithm is set as follows:
For each vector X = (x1, x2, x3, ...xn) in the time series find its nearest neighbor Y = (y1, y2, y3, ..., yn) in an n-dimensional space. Iterate both points and compute R = | xn+1 - yn+1 |. This distance R is essentially a distance between the images of vectors X and Y. One may also think of yn+1 as a predictor for xn+1, so R is then the prediction error. The idea is that when the attractor is completely unfolded in n dimensions, the distance R between the (n+1)st components of vectors X and Y will be small. To detect if the nearest neighbor just found is false, we compare R (the prediction error) with the errors that would have been made by a trivial predictor. If the error made by the trivial predictor is less than R, we register the nearest neighbor as "false". The trivial predictor simply uses xn as a predictor xn+1. So, more formally,
If | xn+1 - yn+1 | = | xn+1 xn |,
the nearest neighbor is labeled as "false".
Below is the result of the FNN calculations for the far-infrared laser in a chaotic state:
Nonparametric Time Series Prediction
Even if you are not interested in time series forecasting as a subject matter, you can think of it as the ultimate test of your analysis of a particular dynamical system. Have your noise reduction techniques resulted in a better predictability of the signal in question? Are your embedding parameters optimal in a sense that the corresponding predictive model minimizes the error?
Nonparametric modeling is useful in situations when we cant make any assumptions about the functional form of the process that generated the observable time series. Instead of assuming a certain model and computing its coefficients, we may derive the model from given data directly.
In VRA, this is done using local polynomial models. That is, instead of fitting one complex model with many coefficients to the entire data set, we can fit many simple models to small portions of the data set. In VRA, these simple models are based on locally weighted polynomials. In effect, we come up with a model that changes its parameters adaptively depending on the geometry of the local neighborhood. One can think of such a model as a regression model that moves in time.
The general methodology is as follows:
To predict point x(n+1), we determine the last known state of the system as represented by vector X = [x(n), x(n-t), x(n-2t), x(n-(d-1)t)], where d is the embedding dimension and t is the time delay. We then search the time series to find k similar states that have occurred in the past, where "similarity" is determined by evaluating the distance between vector X and its neighbor X' in the d-dimensional state space. The idea is that if the observable signal was generated by some deterministic map M(x(n),x(n-t), x(n-2t), x(n-(d-1)t)) = x(n+1), that map can be recovered (reconstructed) from the data by looking at its behavior in the neighborhood of X. We find the approximation of M by fitting a (low order) polynomial which maps k nearest neighbors (similar states) of X onto their next immediate values. Now we can use this map to predict x(n+1). In other words, we make an assumption that M is fairly smooth around X, and so if a state X'= [x'(n), x'(n-t), x'(n-2t), x'(n-(d-1)t)] in the neighborhood of X resulted in the observation x'(n+1) in the past, then the point x(n+1) which we want to predict must be somewhere near x'(n+1).
In VRA, you can construct a model from a range of classes (nearest neighbor, local constant, kernel regression, local linear, and locally weighted linear).
To construct the actual model to generate predictions, we need to choose certain parameters (the model is nonparametric only in a sense of its global functional form), such as embedding dimension, time delay, the order of the polynomial, etc. The screen shot from VRA below shows an example of time series prediction of the Lorenz attractor (data file included with VRA), along with the model parameters.
Recurrence quantification analysis
Recurrence quantification analysis (RQA) is a relatively new analytical tool for the study of nonlinear dynamical systems, developed by Charles Webber and Joseph Zbilut.
To start RQA calculations, load the time series, and choose Analysis | Recurrence Plot Analysis | RQA Measurements from the main menu. The RQA dialog window will be displayed. Set the desired values of input parameters and click on the "Calculate RQA Measurements" button. The RQA outputs will be calculated and displayed. You may want to repeat the calculation for different input parameters.
Recurrence histogram
Recurrence histogram shows the characteristic periodicity in the time series. Here is an example of a recurrence histogram for the Lorenz attractor:
References:
Some remarks on nonlinear data analysis of physiological time series.
1989, In: Measures of Complexity and Chaos, Neal A. Abraham, Alsonso M. Albano, Anthony Passamante and Paul E. Rapp (eds.), pp. 51-62, Plenum Press, NATO ASI Series B: Physics Vol. 208, New York and London
A. Babloyantz
Evidence for slow brain waves: a dynamical approach.
1991, Electroencephalogr. Clin. Neurophysiol., vol. 78, pp. 402-405
M.C. Casdagli
Recurrence plots revisited.
Physica D 108 (199) 12-44
J.P. Eckmann, S. Oliffson Kamphorst and D. Ruelle
Recurrence plots of dynamical systems.
1987, Europhys. Lett., Vol. 4, No. 9, pp. 973-977
Claire G. Gilmore
A new test for chaos.
1993, J. Econ. Behav. Organ., Vol. 22, pp. 209-237
Claire G. Gilmore
A new approach to testing for chaos, with applications in finance and economics.
1993, Int. J. Bifurcation Chaos, Vol. 3, No. 3, 583-587.
Pawel Kaluzny and Remigiusz Tarnecki
Recurrence plots of neuronal spike trains.
1993, Biol. Cybern., vol. 68, pp. 527-534
Keegan AP, Zbilut JP, Merritt SL, Mercer PJ
Use of recurrence plots in the analysis of pupil diameter dynamics in narcoleptics.
(1993) SPIE Proceedings: Chaos in Biology and Medicine, Vol 2036, pp 206-213.
M.C.K. Khoo (ed)
Approaches to Pulmonary Physiology and Medicine.
Plenum Press, New York, 1996., Chapter 8, pp 137-148.
Matthew Koebbe and Gottfried Mayer-Kress
Use of recurrence plots in the analysis of time-series data.
1992, In: Nonlinear Modeling and Forecasting, M. Casdagli and S. Eubank (eds.), pp. 163-188, SFI Studies in the sciences of complexity, Proc. Vol. XII, Addison-Wesley
Gottfried Mayer-Kress and Alfred Huebler
Time evolution of local complexity measures and aperiodic perturbations of nonlinear dynamical systems.
1989, In: Measures of Complexity and Chaos, Neal A. Abraham, Alsonso M. Albano, Anthony Passamante and Paul E. Rapp (eds.), pp. 155-171, Plenum Press, NATO ASI Series B: Physics Vol. 208, New York and London
F. Takens
Detecting strange attractors in turbulence.
1981, In: Dynamical Systems and Turbulence (Warwick 1980), Lecture Notes in Mathematics, No. 898, Springer-Verlag, Berlin
Trulla, L.L, A. Giuliani, J.P. Zbilut, and C.L. Webber, Jr.
Recurrence quantification analysis of the logistic equation with transients.
Phys. Lett. A 223: pp 255-260, 1996.
M. Vihinen
An algorithm for simultaneous comparison of several sequences.
1988, CABIOS, Vol. 4, No. 1, pp. 89-92.
C.L. Webber, Jr. and J.P. Zbilut
The application of chaos theory to rhythmic breathing patterns.
1991, In: Cardiorespiratory and motor coordination, H.-P. Koepchen and T. Huopaniemi (eds.), pp. 239-247, Springer-Verlag, Berlin, Heidelberg, New York
C.L. Webber, Jr.
Rhythmogenesis of deterministic breathing patterns.
1991, In: Rhytms in Physiological Systems, H. Haken and H.P. Koepchen (eds.), pp. 177-191, Springer-Verlag, Springer Series in Synergetics, Berlin, Heidelberg, New York
Webber, C.L., Jr. and J.P. Zbilut.
Assessing deterministic structures in physiological systems using recurrence plot strategies. In: Bioengineering
Charles L Webber and Joseph P. Zbilut
Dynamical assessment of physiological systems and states using recurrence plot strategies.
1994, J. Appl. Physiol., vol. 76, no. 2, pp. 965-973
Webber, C.L., Jr. and J.P. Zbilut.
Recurrent structuring of dynamical and spatial systems.
In: Complexity in the Living: A Modelistic Approach. A.
J.P. Zbilut, M. Koebbe, H. Loeb and G. Mayer-Kress
Use of recurrence plots in the analysis of heart beat intervals.
1991, In: Proceedings IEEE Computers in Cardiology, pp. 263-265, IEEE Computer Society Press, Washington, Brussels, Tokyo
J.P. Zbilut
Power laws, transients, attractors, and entropy: possible implications for cardiovascular dynamics.
1991, In: Rhytms in Physiological Systems, H. Haken and H.P. Koepchen (eds.) pp. 139-151 Springer-Verlag Springer Series in Synergetics Berlin, Heidelberg, New York
Joseph P. Zbilut and Charles L Webber Jr.
Embeddings and delays as derived from quantification of recurrence plots.
1992, Phys. Lett. A, vol. 171, pp. 199-203
Webber, C.L., Jr. and J.P. Zbilut.
The applicability of methods from nonlinear dynamics in assessing physiological states of the respiratory system.
Proc. Eng. Med. Biol. Soc. 12: 1863-1864, 1990.
Webber, C.L., Jr. and J.P Zbilut.
The applicability of chaos theory to rhythmic breathing patterns.
In: Cardiorespiratory and Motor Coordination. H.-P. Koepchen and T. Huopaniemi (eds.). Springer-Verlag, Berlin, Heidelberg, New York, pp 239-247, 1991.
Webber, C.L., Jr.
Rhythmogenesis of deterministic breathing patterns.
In: Rhythms in Physiological Systems. H. Haken and H.P. Koepchen (eds.).
Springer-Verlag, Berlin, Heidelberg, New York, pp 177-191, 1991.
Zbilut, J.P. and C.L. Webber, Jr.
Embeddings and delays as derived from quantification of recurrence plots.
Physics Letters A 171: 199-203, 1992.
Webber, C.L., Jr. and J.P Zbilut.
Dynamical assessment of physiological systems and states using recurrence plot strategies.
J. Appl. Physiol. 76: 965-973, 1994.
Webber, C.L., Jr., Schmidt, M.A., and J.M. Walsh.
Influence of isometric loading on biceps EMG dynamics as assessed by linear and nonlinear tools.
J. Appl. Physiol. 78: 814-822, 1995.
Webber, C.L., Jr. and J.P. Zbilut.
Assessing deterministic structures in physiological systems using recurrence plot strategies.
In: Bioengineering Approaches to Pulmonary Physiology and Medicine. M.C.K. Khoo (ed.). Plenum Press, New York, Chapter 8, pp 137-148, 1996.
Trulla, L.L., A. Giuliani, J.P. Zbilut, and C.L. Webber, Jr.
Recurrence quantification analysis of the logistic equation with transients.
Physics Lett. A. 223: 255-260, 1996.
Zbilut, J.P., A. Giuliani, C.L. Webber, Jr.
Recurrence quantification analysis and principle components in the detection of short complex signals.
Physics Lett. A. 237: 131-135, 1998.
Zbilut, J.P. and C.L. Webber, Jr.
Quantification of heart rate variability using methods derived from nonlinear dynamics.
In: Analysis and Assessment of Cardiovascular Function. G. Drzewiecki and J.K.-J. Li (eds.). Springer Verlag, New York.
Webber, C.L., Jr. and J.P. Zbilut.
Recurrent structuring of dynamical and spatial systems.
In: Complexity in the Living: A Modelistic Approach. Interdisciplinary Science Rev. Oxford Press, A. Colosimo and A. Lesk (eds.). (in press)