Nächste-Nachbar basierte Methoden in der nichtlinearen Zeitreihenanalyse
Nearest-neighbor based methods for nonlinear time-series analysis
by Christian Merkwirth
Date of Examination:2000-11-02
Date of issue:2001-09-11
Advisor:Prof. Dr. Ulrich Parlitz
Referee:Prof. Dr. Ulrich Parlitz
Referee:Prof. Dr. Dirk Ronneberger
Persistent Address:
http://dx.doi.org/10.53846/goediss-2870
Files in this item
Name:merkwirth.pdf
Size:1.43Mb
Format:PDF
Description:Dissertation
The following license files are associated with this item:
Abstract
English
The subject of this thesis is the application of nearest-neighbor based methods within the field of nonlinear time-series analysis. A main area of application there is the modeling and prediction of nonlinear dynamical systems, where usually scalar time series are embedded into reconstruction spaces via time-delay reconstruction. These methods are presented together with techniques to validate the derived models. As a central result of this thesis, a fast algorithm for exact and approximate nearest neighbor searching is presented that can be used in combination with any metric. Empirical benchmarks show that the algorithm´s performance depends mainly on the fractal dimension of the data set, which is usually smaller than the reconstruction dimension of the vector space in which the data points are embedded. This feature makes the algorithm highly suitable for a new reconstruction technique for spatio-temporal time series that uses high dimensional reconstruction spaces.
Keywords: nonlinear dynamics; spatio-temporal dynamics; prediction; modeling; nonlinear time-series analysis; nearest-neighbor algorithm
Other Languages
Das Thema dieser Arbeit ist die Anwendung der Nächste-Nachbar-Suche in Verfahren der nichtlinearen Zeitreihenanalyse. Ein Haupteinsatzgebiet der Nächste-Nachbar-Suche in der nichtlinearen Zeitreihenanalyse ist die Modellierung und Vorhersage nichtlinearer dynamischer Systeme. Dazu werden meist skalare Zeitreihen dieser Systeme durch die Technik der Zeitverzögerungsrekonstruktion in einen mehrdimensionalen Zustandsraum eingebettet. Diese Verfahren werden in der Arbeit zusammen mit einer Methode zur Validierung der so gewonnenen Modelle vorgestellt. Als ein zentrales Ergebnis dieser Arbeit wird dann ein effizienter Algorithmus zur Nächsten-Nachbar-Suche, der sogenannte ATRIA (Advanced Triangle Inequality Algorithm), vorgestellt. Dieser zeichnet sich sowohl durch flexible Wahl der zur Distanzberechnung verwendeten Metrik als auch durch die Möglichkeit aus, die Laufzeit des Algorithmus durch eine abgeschwächte Variante der Suche, bei der sogenannte approximative Nächste-Nachbarn bestimmt werden, weiter zu verringern. Weiter werden verschiedene Methoden der Bestimmung des Spektrums der fraktalen Dimensionen eines dynamischen Systems vorgestellt und verglichen. In diesem Zusammenhang werden numerische Untersuchungen zur Ermittlung des Zusammenhangs zwischen Laufzeit des ATRIA und der fraktalen Dimension des Datensatzes, in dem die Nachbarsuche stattfindet, präsentiert. Danach wird ein Verfahren zur lokalen Modellierung raum-zeitlicher dynamischer Systeme vorgestellt. Dieses Verfahren, bei dem Nächste-Nachbarn in einem vergleichsweise hochdimensionalen Raum bestimmt werden müssen, profitiert deutlich von der Verwendung eines Algorithmus, dessen Laufzeit wie die des vorgestellten ATRIA nur unkritisch von der formalen Dimension des Datensatzes abhängt
Schlagwörter: nichtlineare Dynamik; raum-zeitliche Dynamik; Vorhersage; Modellierung; nichtlineare Zeitreihenanalyse; Nächster-Nachbar-Algorithmus