© 2024 SOME RIGHTS RESERVED
The content of this web site is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 2.0 Germany License.
(2016)
Recurrence Quantification Analysis (RQA) ist eine Methode zur Analyse dynamischer Systeme. Hauptaufgabe der RQA ist das Auffinden von Wiederholungen (Reccurences) in einer Zeitreihe. Hierfür wird die Verteilung der vertikalen und diagonalen Linien in einer Ähnlichkeitsmatrix, der sogenannten Reccurence Matrix, bestimmt. Zur Konstruktion der Ähnlichkeitsmatrix werden die paarweisen Ähnlichkeiten zwischen mehrdimensionalen Vektoren berechnet, die aus einer gegebenen Zeitreihe extrahiert wurden. Als Ähnlichkeitsmaß dient z.B. die euklidische Norm. Unterschreitet die Distanz zwischen zwei Vektoren eine definierte Schranke, wird eine 1 in die Matrix eingetragen. Vertikale und diagonale Linien ergeben sich durch aufeinanderfolgende Einsen [1].
Anhand der Recurrence Matrix werden eine Reihe quantitativer Maße bestimmt. Zum Beispiel gibt die Recurrence Rate (RR) den Anteil der Recurrence Points (als ähnlich markierte Matrixelemente) in der Matrix an. Mit Hilfe der ermittelten diagonalen Linien kann ein weiteres Maß, der Determinism (DET), bestimmt werden. Dieser gibt für einen Recurrence Point die Wahrscheinlichkeit an, dass dieser Punkt zu einer diagonalen Linie mit mindestens der Länge j gehört [1].
Die RQA wird in vielen wissenschaftlichen Bereichen eingesetzt. Zum Beispiel wird in [2] die mögliche Anwendung in der Analyse des Herz-Lungen-System mittels der RQA genannt. Diese wird durchgeführt, um Einblicke in die Funktionsweise des Systems zu erhalten. Zusätzlich können Fehlfunktionen identifiziert werden, um lebensbedrohliche Zustände zu diagnostizieren [2].
Der Brute Force Algorithmus zur Konstruktion der Ähnlichkeitsmatrix hat eine quadratische Laufzeit, da dieser alle paarweisen Ähnlichkeiten berechnet und in der Matrix entsprechend kodiert.
Ein Ansatz zur Verbesserung der Performance ist die Parallelisierung des Algorithmus. Das Geoforschungszentrum Potsdam (GFZ) entwickelte eine Implementierung, die eine RQA auch für Zeitreihen mit mehr als 1 Millionen Datenpunkten in akzeptabler Zeit durchführt. Hierfür wurde ein stark parallelisierter Berechnungsprozess verwendet [2]. Die quadratische Laufzeit bleibt bei einem parallelen Ansatz allerdings erhalten. Hierdurch kommt es bei steigender Datenmenge zu einem drastischen Anstieg der Laufzeit.
Ein weiterer Ansatz ist die Reduktion der Anzahl an benötigten Ähnlichkeitsvergleichen mittels einer Indexstruktur. In [3] wurde dieser Ansatz im Kontext der k-Nächsten Nachbarsuche evaluiert und mit dem parallelen Ansatz des GFZ verglichen. Im Ergebnis wurde geschlussfolgert, dass durch Indexierung für bestimmte Datenmengen und Dimensionalitäten eine Verbesserung der Laufzeit erzielt werden kann. Die Dimensionalität der zugrunde liegenden Datenmenge hat den größten negativen Einfluss auf die Laufzeit der verwendeten Indexstruktur. Dies bedeutet: Für hinreichend große Datenmengen mit einer niedrigen Dimensionalität (d < 10) könnte eine echte Verbesserung der Konstruktionszeit gegenüber dem parallelen Ansatzes des GFZ erzielt werden. Für Dimensionalitäten größer als 10 übersteigt der Rechenaufwand den einer parallelisierten Brute Force Variante.
Sowohl der parallele Ansatz als auch die Verwendung einer Indexstruktur liefern immer exakte Ergebnisse. In dieser Diplomarbeit soll ein dritter Ansatz untersucht werden. Mit Hilfe approximativer Verfahren wird der Inhalt der Reccurence Matrix abgeschätzt. Dieser Ansatz hat potentiell einen geringeren Rechenaufwand als die beiden bereits untersuchten Ansätze. Im Gegensatz zu diesen wird aber keine exakte Ergebnismenge garantiert.
In [4] wurde bereits ein approximativer Ansatz für die RQA untersucht. Dieser überspringt den Schritt der Konstruktion der Recurrence Matrix vollständig und bestimmt die Recurrence Rate und den Determinism näherungsweise anhand der zugrundeliegenden Zeitreihe. Die Genauigkeit der Ergebnisse hängt stark von der gewählten Ähnlichkeitsschwelle ab.
Es existieren zwei grundlegende Ansätze, eine Reccurence Matrix zu konstruieren. Diese nutzen zwei unterschiedliche Nachbarschaftsbedingungen: fester Radius und feste Anzahl von nächsten Nachbarn.
fester Radius: Alle Datenobjekte dϵD, welche eine definierte Ähnlichkeitsschranke zu dem Queryobjekt q nicht überschreiten – entspricht einer Bereichssuche.
feste Anzahl von nächsten Nachbarn: Genau die k Elemente, welche dem Queryobjekt q am ähnlichsten sind – entspricht einer k-Nächsten Nachbarsuche.
Um die Reccurence Matrix zu erzeugen wird pro Datenobjekt eine Suche durchgeführt. Die Ergebnismenge bildet eine Zeile bzw. Spalte der Matrix ab. Hierfür werden alle in der Ergebnismenge enthaltenen Datenobjekt mit einer “1“ kodiert, alle anderen werden dementsprechend mit “0“ kodiert.
Die in der Einleitung beschriebene Reccurence Matrix kann auf die Konstruktion mittels einer Bereichssuche zurückgeführt werden. Im Fokus dieser Arbeit steht genau diese Konstruktionsweise. Um Laufzeit zu sparen wird ein approximativer Ansatz zur Durchführung der Suche eingesetzt.
Für die Bereichssuche existieren bereits approximative Ansätze, welche näherungsweise die Nachbarn zu einem Queryobjekt bestimmen [5,6,7,8,9]. Die Ergebnismenge eines approximativen Verfahrens kann zu wenige bzw. zu viele (und somit falsche) Nachbarn enthalten, welche auch als false negative/positives bezeichnet werden. Abhängig vom verwendeten Algorithmus können sowohl false negatives als auch false positives oder nur eines von beiden auftreten. Beim Locality Sensitive Hashing (LSH)[7] können beispielsweise beide Varianten auftreten, wohingegen beim Randomized k-d-trees [8] nur false negatives vorkommen.
Es werden zwei Kategorien der approximativen Bereichssuche untersucht: fehler- und ressourcenbasierte Algorithmen.
Ein fehlerbasierter Algorithmus im Kontext der Bereichssuche liefert beispielsweise zu einem Queryobjekt q alle Nachbarn, welche die Ähnlichkeitsbedingung näherungsweise erfüllen. Hierfür wird ein Fehler ε, 0 definiert, welcher angibt, wie stark die Ähnlichkeit der ermittelten Nachbarn von der geforderten Bedingung abweichen darf. Ist beispielsweise die Ähnlichkeitsbedingung die Distanz d
© 2024 SOME RIGHTS RESERVED
The content of this web site is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 2.0 Germany License.
Please note: The abstracts of the bibliography database may underly other copyrights.
Ihr Browser versucht gerade eine Seite aus dem sogenannten Internet auszudrucken. Das Internet ist ein weltweites Netzwerk von Computern, das den Menschen ganz neue Möglichkeiten der Kommunikation bietet.
Da Politiker im Regelfall von neuen Dingen nichts verstehen, halten wir es für notwendig, sie davor zu schützen. Dies ist im beidseitigen Interesse, da unnötige Angstzustände bei Ihnen verhindert werden, ebenso wie es uns vor profilierungs- und machtsüchtigen Politikern schützt.
Sollten Sie der Meinung sein, dass Sie diese Internetseite dennoch sehen sollten, so können Sie jederzeit durch normalen Gebrauch eines Internetbrowsers darauf zugreifen. Dazu sind aber minimale Computerkenntnisse erforderlich. Sollten Sie diese nicht haben, vergessen Sie einfach dieses Internet und lassen uns in Ruhe.
Die Umgehung dieser Ausdrucksperre ist nach §95a UrhG verboten.
Mehr Informationen unter www.politiker-stopp.de.