Graphische Zeitverzerrung (GTW) ist ein Framework zur gemeinsamen Ausrichtung mehrerer Paare von Zeitreihen oder Sequenzen. Im Gegensatz zur dynamischen Zeitverzerrung (DTW), die jedes Paar unabhängig ausrichtet, indem sie nur die Distanz zwischen den beiden Sequenzen eines gegebenen Paares minimiert, berücksichtigt GTW sowohl die Ausrichtungsgenauigkeit jedes Sequenzpaares als auch die Ähnlichkeit zwischen den Paaren. Diese gemeinsame Optimierung ermöglicht es GTW, eine bessere Ausrichtungsleistung zu erzielen, wenn Ähnlichkeit zwischen den Paaren erwartet wird, und verallgemeinert DTW als Sonderfall.
Das Framework ist auf beliebige Daten anwendbar, die mit voneinander abhängigen Zeitreihen oder Sequenzen strukturiert sind. Zu den Anwendungen gehören die Analyse der Signalausbreitung in Zeitraffer-Bioimaging-Daten, die Signaturidentifikation, die Tiefenberechnung bei binokularem Stereo-Sehen sowie die Profilausrichtung in der Flüssigchromatographie-Massenspektrometrie (LC-MS) in der Proteomik-Datenanalyse. In diesen Kontexten weisen benachbarte oder verwandte Sequenzen oft ähnliche Verzerrungsmuster auf, die GTW nutzt, um die Ausrichtungsqualität zu verbessern.
Formulierung
GTW formuliert das Problem der gemeinsamen Ausrichtung als Minimierung über eine Menge von Verzerrungspfaden. Gegeben seien \(N\) Paare von Zeitreihen \((x_n, y_n)\) für \(n = 1, 2, ..., N\), wobei jedes Paar einen entsprechenden Verzerrungspfad \(P_n\) hat. Einige Paare von Verzerrungspfaden sind bekanntermaßen ähnlich, bezeichnet durch die Menge \(Neib\). Das Ziel ist die Minimierung von:
\[\min_{\{P_n\}} \left( \sum_{n=1}^{N} cost(P_n) + \kappa \sum_{(m,n) \in Neib} dist(P_m, P_n) \right)\]
Hierbei ist \(cost(P_n)\) die Distanz zwischen \(x_n\) und \(y_n\) nach der Ausrichtung mit der Verzerrungsfunktion \(P_n\). Der Term \(dist(P_m, P_n)\) misst die Distanz zwischen zwei Verzerrungspfaden, definiert als die Fläche der Region, die durch \(P_m\) und \(P_n\) begrenzt wird. Der Hyperparameter \(\kappa\) balanciert den Ausrichtungskostenterm und den Distanzterm der Verzerrungsfunktion. Die Ähnlichkeitsstärke kann anwendungsspezifisch sein; für verschiedene verwandte Paare \((m, n)\) können unterschiedliche Parameter \(\kappa_{(m,n)}\) festgelegt werden.
Beziehung zur dynamischen Zeitverzerrung
Die dynamische Zeitverzerrung ist eine klassische Technik zur Ausrichtung zweier Zeitreihen, indem ein optimaler Verzerrungspfad gefunden wird, der die kumulative Distanz minimiert. DTW behandelt jedes Paar unabhängig und löst ein Problem des kürzesten Pfades in einem Gitter. GTW erweitert dies, indem mehrere Verzerrungspfade durch eine Strafe auf ihre paarweisen Distanzen gekoppelt werden. Wenn \(\kappa = 0\), reduziert sich GTW auf unabhängiges DTW für jedes Paar. Wenn \(\kappa > 0\), werden die Verzerrungspfade dazu angeregt, ähnlich zu sein, was vorteilhaft ist, wenn die zugrunde liegenden Sequenzen gemeinsame zeitliche Verzerrungen aufweisen.
Lösung mittels maximalem Fluss
GTW transformiert das DTW-äquivalente Problem des kürzesten Pfades in ein Problem des maximalen Flusses im dualen Graphen. Die Einschränkungen oder Ähnlichkeiten zwischen Verzerrungspfaden werden als zusätzliche Kanten oder Kapazitäten modelliert. Diese duale Graphenformulierung ermöglicht es, die gemeinsame Optimierung mit Standard-Max-Flow-Algorithmen zu lösen. Für große Datensätze werden generische Max-Flow-Algorithmen jedoch zeitaufwendig und speicherintensiv.
Um die Skalierbarkeit zu adressieren, wurde ein effizienter Algorithmus namens Bidirectional pushing with Linear Component Operations (BILCO) speziell für GTW entwickelt. BILCO nutzt die Struktur des dualen Graphen und erreicht eine durchschnittliche 10-fache Verbesserung sowohl bei der Rechenzeit als auch beim Speicherverbrauch im Vergleich zu modernen generischen Max-Flow-Algorithmen in GTW-Anwendungen.
Anwendungen
GTW wurde in mehreren Bereichen angewendet, in denen voneinander abhängige Zeitreihen auftreten:
- Signalausbreitungsanalyse in Zeitraffer-Bioimaging: Benachbarte Pixel zeigen oft ähnliche Ausbreitungsmuster, was GTW zur Verfolgung von Wellenfronten oder zellulären Signalen geeignet macht.
- Signaturidentifikation: Handschriftliche Signaturen können als Sequenzen behandelt werden; die gemeinsame Ausrichtung mehrerer Signaturen verbessert die Erkennung.
- Tiefenberechnung bei binokularem Stereo-Sehen: Disparitätskarten aus linken und rechten Bildern können mit GTW ausgerichtet werden, um die Tiefenschätzung zu verbessern.
- LC-MS-Profilausrichtung in der Proteomik: Chromatographische und massenspektrometrische Profile aus mehreren Proben profitieren von einer gemeinsamen Ausrichtung, um Retentionszeitverschiebungen zu korrigieren.
Diese Anwendungen teilen die Eigenschaft, dass die Sequenzen nicht unabhängig sind, sondern räumliche oder zeitliche Korrelationen aufweisen, die GTW nutzt.