Regression Trees for Non Parametric Modeling and Time Series Prediction
Arbres de Régression Modélisation non Paramétrique et Analyse des Séries Temporelles
OPEN ACCESS
We present a non-parametric approach to nonlinear modeling and prediction based on adaptive partitioning of the reconstructed phase space associated with the process. The partitioning method is implementedwith a recursive tree-structured algorithm which successively refines the partition by binary splitting where the splitting threshold is determined by a penalized maximum entropy criterion. An analysis of the statistical behavior of the splitting rule suggests a criterion for determining the depth of the tree. The effectiveness of this method is illustrated through comparisons with classical approaches for nonlinear system analysis on the basis of reconstruction error and computational complexity. An importantrelation between our tree-structured model for the process and generalized non-linear thresholded AR model (ART) is established. We illustrate our method for cases where classical linear prediction is known to be rather ineffective : chaotic signals (measured at the output of a Chua-type electronic circuit), and second order ART signal.
Résumé
Nous présentons une approche non linéaire non paramétrique pour la modélisation et la prédiction de signaux, basée sur une méthode de partition récursive de l'espace des phases reconstruit, associé au système sur lequel le signal est prélevé. La partition de l'espace des phases est obtenue par un algorithme récursif de partition binaire . Les seuils de partition sont déterminés à l'aide d'un critère de maximum d'entropie. Une courte analyse statistique du comportement de ces seuils permet de définir un critère simple d'arrêt de la partition récursive. L'intérêt de cette méthode est illustré par la comparaison avec des méthodes classiques dans le cadre de l'analyse de systèmes non linéaires, ainsi que du point de vue du coût de calcul . Nous présentons un lien important entre cette méthode reposant sur une partition hiérarchique (en arbre) et les modèles non linéaires auto-régressifs à seuils (ART). Dans ce contexte, la méthode présentée est appliquée dans des cas pour lesquels les méthodes linéaires échouent en général :les signaux de chaos (séries expérimentales mesurées sur des circuits électroniques de type Chua), ainsi que sur des séries numériques ART d'ordre deux.
Modeling, Non linear, Non parametric, Statistics, Dynamical Systems, Regression Trees, Phase Space, Prediction .
Mots clés
Modélisation, Non linéaire, Non paramétrique, Statistique, Systèmes dynamiques, Arbres de régression, Espace des phases, Prédiction.
[1] M.B. PRIESTLEY, Nonlinear and Nonstationary Time Series Analysis, Academic Press, 1988.
[2] H. TONG, Non Linear Time Series :a Dynamical System Approach, Oxford Science Publication, Oxford University Press, NY, 1990 .
[3] D. GUÉGAN, Séries Chronologiques Non Linéaires à Temps Discret, Economica, 1994.
[4] H.D.I.ABARBANEL, R.BROWN, J.J.SIDOROWICH, L.S. TSIMING, "The Analysis of Observed Chaotic Data in Physical Systems",Review of Modern Physics,vol.65, no. 4, 1993, pp. 1331-1392.
[5] M. CASDAGLI, S. EUBANK, J.D. FARMER, J. GIBSON, "State Space ReconstructioninPresence of Noise",Physica D, vol.51, 1991, pp. 52-98.
[6] J.P . ECKMANN, S. OLIFFSON KAMPHORST, D. RUELLE, S. CILIBERTO, "Lyapunov Exponents from Time Series", Physical Review A, vol. 34, no. 6, 1986, pp. 4971-4979.
[7] A.M. FRASER, "Information and Entropy in Strange Attractors", IEEE Transactions on Information Theory, vol. 35, no. 2, 1989, pp. 245-262.
[8] R. SHAW, "Strange Attractors, Chaotic Behaviour, and Information Flow", Z . Naturforschung,vol.36a, 1981, pp. 80-112.
[9] J.P. ECKMANN, D. RUELLE, "Ergodic Theory of Chaos and Strange Attractors", Review of Modern Physics, vol. 57, no. 3, 1985, pp. 617-656.
[10] O. MICHEL, P . FLANDRIN, "Application of Methods Based on Higher Order Statistics for Chaotic Signal Analysis", Signal Processing, vol. 53, no.2, 1996,
[11] H. WHITNEY, "Differentiable Manifolds",Annals of Mathematics, vol.37, no. 3, 1936, pp. 645-680.
[12] N. H. PACKARD, J.P. CRUTCHFIELD, J.D. FARMER, R. SHAW, "Geometry from a Time Series", Physical Review Letters, vol. 45, no. 9, 1980, pp. 712-716.
[13] F. TAKENS, "Detecting Strange Attractors in Turbulence",Lecture Notes in Mathematics, vol. 898, 1981, pp. 366-381.
[14] D. GUÉGAN, "Detecting Non Linearity : A Review",Statistiqueet Analyse des Données vol. 15, no. 2, 1990, pp. 1-17.
[15] D. RUELLE, Chaotic Evolution and Strange Attractors, Cambridge University Press, 1989.
[16] P. GRASSBERGER, I. PROCACCIA, "Characterization of Strange Attractors", Physical Review Letters, vol. 50, no. 5, 1983, pp. 346-349.
[17] P . FLANDRIN,O. MICHEL,P. RUIZ, "Chaos et Analyse Non Linéairedu Signal", rapport interne, Laboratoire de Physique ENS-Lyon, 1993.
[18] O. MICHEL, P FLANDRIN, "Higher Order Statistics for Chaotic Signal Analysis", Computer Techniques and Algorithms in Digital Signal Processing, Control and Dynamic Systems, Advances in Theory and Applications, C.L. Leondes, Academic Press, vol. 75, 1996, pp. 105-154.
[19] A.M. FRASER, H.L. SWINNEY, "Independent Coordinates for Strange Attractors from Mutual Information", Physical Review A, vol . 33, no. 2, 1986, pp. 1134-1140.
[20] A.M. FRASER, "Reconstructing Attractors from Scalar Time Series : a Comparison of Singular System and Redundancy Criteria", Physica D, vol. 34, 1989, pp. 391-404.
[21] A. PASSAMANTE, M.E. FARREL, "Characte izing Attractors Using Local Intrinsic DimensionviaHigher Order Statistics",Physical Review A, vol. 43, no. 10, 1991, pp. 5268-5274.
[22] M.B. KENNEL, R. BROWN, H.D.I. ABARBANEL, "Determining Embedding Dimension for Phase-Space Reconstruction Using a Geometrical Construction",Physical Review A, vol.45, no. 6, 1992, pp. 3403-3411.
[23] D.T.KAPLAN,L. GLASS, "Direct Test for Determinism in a Time Series", Physical Review Letters, vol. 68, no. 4, 1992, pp. 427-430.
[24] P. COMON, "Independent Component Analysis", Proceedings of thelotemational Signal Processing Workshop on Higher Order Statistics, Chamrousse (France), 1991, pp. 11-120.
[25] W.H. PRESS, B.P. FLANNERY, S.A. TEUKOLSKY, W.T. VETTERLING, Numerical Recipes in C : the Art of Scientific Computing, Cambridge University Press, 1988.
[26] R. BARLOW, Statistics. A Guide to the Use of Statistical Methods in the Physical Sciences, Wiley, 1989.
[27] O. MICHEL,"Regression Trees for Phase Space Analysis and Prediction of Non-Linear Time Series", rapport OTANno. 21B93F, Paris, 1995.
[28] O. MICHEL, A.O. HERO, "Tree-Structured Non-Linear Signal Modeling and Prediction", ICASSP'95 Proceedings, Detroit, Michigan, 1995.
[29] A.M. MOOD, F.A. GRAYBILL, D.C. BOES, Introduction to the Theory of Statistics, Me Graw Hill International Editions, Statistics Series, 3rd ed ., 1974.
[30] M. CASDAGLI, "Nonlinear Prediction of Chaotic Time Series", Physica D, vol. 35, 1989, pp. 335-356.
[31] B. FINKENSTÄDT, P.KUHBIER, "Forecasting Nonlinear Economic Time Series : A Simple Test To Accompany the Nearest Neighbor Approach", Empirical Economics, vol. 20, 1995, pp. 243-263.
[32] O. MICHEL, A.O. HERO, A.-E. BADEL, P. FLANDRIN, "Tree based Modeling, Prediction and Analysis of Chaotic Time-Series", Proceedings ofIEEE Workshop on Non Linear Signal and Image Processing, vol.1,Halkidiki, Greece, 1995, pp. 117-120.
[33] J.D. FARMER, J.J. SIDOROWICH, "Exploiting Chaos to Predict the Future and Reduce Noise",Evolution, Learning and Cognition, Ed. Lee, Y.C. (World Scientific), 1988, pp. 277-330.
[34] A.-E. BADEL, O. MICHEL, A.O. HERO, "Arbres de Régression Pour l'Analysede Séries Chaotiques", GRETSI'95 Proceedings, vol. 1,Juan-lesPins, France, 1995, pp. 169-172.
[35] W. LIEBERT, K. PAWELZIK, H.G.SCHUSTER, "Optimal Embeddings of Chaotic Attractors from Topological Considerations", Europhysics Letters, vol. 14, no. 6, 1991, pp. 521-526.
[36] T.P. WELDON, An Inductorless Double-Scroll Chaotic Circuit", American Journal of Physics, vol. 58, no. 10, 1990, pp. 936-941.