Ein Maschinensensor zeichnet denselben Vorgang heute schneller auf als gestern, eine Sprachaufnahme enthält unterschiedlich lange Pausen oder zwei Bewegungen laufen nicht exakt synchron. Genau für solche Fälle hilft Dynamic Time Warping (DTW), weil der Algorithmus nicht nur Werte, sondern auch deren zeitliche Abfolge vergleicht. Ich zeige, wie die Methode arbeitet, wann sie gegenüber dem euklidischen Abstand überlegen ist und worauf es bei der Nutzung in Datenanalyse und Datenbanken ankommt.
Die wichtigsten Fakten zur flexiblen Zeitreihenanalyse
- DTW gleicht unterschiedliche Geschwindigkeiten und Zeitabstände zwischen zwei Folgen aus.
- Die Berechnung nutzt eine Kostenmatrix und sucht darin den günstigsten Ausrichtungspfad.
- Ohne Einschränkungen liegt der Rechenaufwand bei O(n · m) für zwei Zeitreihen mit n und m Messwerten.
- Eine Sakoe-Chiba-Bandbegrenzung kann die Suche deutlich beschleunigen und unrealistische Zuordnungen verhindern.
- Vor der Berechnung sind Skalierung, Sampling, Ausreißer und Vergleichsfenster zu klären.
Warum ein normaler Abstand bei Zeitreihen oft nicht reicht
Der euklidische Abstand vergleicht normalerweise den ersten Wert der einen Reihe mit dem ersten Wert der anderen, danach den zweiten mit dem zweiten und so weiter. Das funktioniert gut, wenn beide Signale gleich lang und synchron sind. Sobald ein Ereignis aber in einer Reihe früher, später, schneller oder langsamer auftritt, wird der Vergleich unnötig streng.
Ein einfaches Beispiel ist ein Vibrationssignal. Zwei identische Maschinen können denselben Lastwechsel ausführen, doch eine erreicht den kritischen Punkt nach 2,4 Sekunden, die andere erst nach 3,1 Sekunden. Ein direkter Punkt-für-Punkt-Vergleich meldet womöglich eine große Differenz, obwohl das Muster inhaltlich nahezu gleich ist.
Die DTW-Methode darf deshalb die Zeitachse lokal dehnen oder stauchen. Ein Messwert der ersten Reihe kann dabei mehreren benachbarten Werten der zweiten Reihe zugeordnet werden. Die Reihenfolge bleibt erhalten, aber die zeitliche Ausrichtung wird flexibel.
| Verfahren | Stärke | Typische Schwäche |
|---|---|---|
| Euklidischer Abstand | Schnell und leicht verständlich | Empfindlich gegenüber Verschiebungen und unterschiedlichen Geschwindigkeiten |
| Korrelation | Erkennt ähnliche Verläufe unabhängig von manchen Skalierungen | Liefert keine flexible Punktzuordnung entlang der Zeitachse |
| DTW | Vergleicht ähnliche Muster trotz zeitlicher Verzerrung | Höherer Rechenaufwand und Gefahr einer Überanpassung |
Meine Erfahrung bei solchen Vergleichen ist, dass die vermeintlich beste Methode selten allein durch ihre mathematische Eleganz gewinnt. Entscheidend ist, ob die zeitliche Verzögerung tatsächlich bedeutungslos ist. Wenn der genaue Zeitpunkt eines Ereignisses fachlich wichtig ist, kann die Flexibilität von DTW sogar ein Problem statt eines Vorteils sein.
So berechnet der Algorithmus den günstigsten Ausrichtungspfad
Für zwei Zeitreihen X und Y wird zunächst eine Matrix angelegt. Jede Zelle beschreibt, wie groß der lokale Abstand zwischen einem Wert aus X und einem Wert aus Y ist. Bei eindimensionalen Messwerten ist das häufig der absolute Abstand oder das Quadrat der Differenz.
Danach wird die Matrix schrittweise gefüllt. Für die Zelle an Position (i, j) gilt vereinfacht:
D(i,j) = d(xi,yj) + min(D(i-1,j), D(i,j-1), D(i-1,j-1))
D(i,j) ist die bisher günstigste Gesamtdistanz, während d(xi,yj) den lokalen Unterschied der beiden Werte bezeichnet. Der Algorithmus kann dabei einen Schritt nach unten, nach rechts oder diagonal gehen. Ausgehend von der ersten Zelle führt der optimale Pfad bis zur letzten Zelle.
Dieser Pfad ist monoton und darf nicht in der Zeit zurückspringen. Er kann aber einen Wert wiederholt verwenden. Genau dadurch lassen sich beispielsweise längere Pausen, langsame Bewegungen oder gedehnte Signalabschnitte abbilden. Die endgültige DTW-Distanz ist die Summe der lokalen Kosten entlang dieses Pfades.
Ein kleines Beispiel aus der Praxis
Angenommen, ein Referenzsignal enthält die Folge [0, 2, 5, 2, 0]. Ein zweites Signal lautet [0, 1, 3, 5, 3, 1, 0]. Beide zeigen denselben Ausschlag, doch das zweite Signal entwickelt sich langsamer und enthält mehr Zwischenwerte.
Ein direkter Vergleich müsste Werte gleicher Position gegenüberstellen. DTW kann dagegen den Anstieg der ersten Reihe mit mehreren aufeinanderfolgenden Punkten der zweiten Reihe verbinden. Die Reihen sehen dadurch nicht nur zahlenmäßig, sondern auch als zeitlich gestrecktes Ereignis ähnlich aus.
Was die Distanz nicht automatisch bedeutet
Eine niedrige DTW-Distanz heißt nicht, dass zwei Zeitreihen in jedem fachlichen Sinn gleich sind. Sie bedeutet zunächst nur, dass sich ein plausibler Ausrichtungspfad mit geringen lokalen Abständen finden lässt. Deshalb sollte ein Schwellenwert immer anhand bekannter Beispiele, Fehlalarmen und echten Treffern bestimmt werden.
Besonders wichtig ist die Skalierung. Ein Signal mit großen Messwerten dominiert sonst die Kostenmatrix gegenüber einem Signal mit kleinen Einheiten. Je nach Fragestellung helfen z-Standardisierung, Min-Max-Skalierung oder eine fachlich definierte Gewichtung.
Wo DTW in der Datenanalyse echten Nutzen bringt
Die Methode spielt ihre Stärke aus, wenn ein charakteristisches Muster in unterschiedlichem Tempo auftreten kann. Das betrifft weit mehr als Spracherkennung. Auch Sensordaten, Bewegungsprofile und industrielle Abläufe enthalten häufig dieselbe Form mit variabler Dauer.
- Spracherkennung: Ein gesprochenes Wort kann je nach Person, Betonung und Sprechtempo unterschiedlich lang sein. DTW richtet die Sprachmuster zeitlich flexibler aus.
- Maschinenüberwachung: Anfahrvorgänge oder Lastwechsel lassen sich mit historischen Referenzen vergleichen, selbst wenn die Maschine nicht jedes Mal gleich schnell reagiert.
- Bewegungsanalyse: Gesten, Schritte oder Sportbewegungen können trotz unterschiedlicher Ausführungsgeschwindigkeit als ähnliche Muster erkannt werden.
- Medizinische Signale: Herzschlag- oder Atemmuster können sich in ihrer Dauer unterscheiden. Die fachliche Interpretation muss hier allerdings immer die Bedeutung von Verzögerungen berücksichtigen.
- Energie- und Lastprofile: Tagesverläufe lassen sich vergleichen, wenn Verbrauchsspitzen an ähnlichen, aber leicht verschobenen Zeitpunkten auftreten.
Für Klassifikationsaufgaben wird oft eine Zeitreihe als Referenz oder Prototyp verwendet. Neue Reihen werden mit mehreren bekannten Beispielen verglichen und anhand der geringsten Distanz einer Klasse zugeordnet. Das ist transparent und für kleinere Datensätze attraktiv, kann bei vielen langen Reihen aber schnell teuer werden.
Mehrdimensionale Messdaten richtig behandeln
Bei einem Bewegungssensor bestehen die Daten oft aus drei Achsen. Eine Möglichkeit ist, jede Achse separat zu vergleichen und die Distanzen anschließend zu gewichten. Alternativ wird die lokale Distanz direkt als Vektor- oder Matrixabstand berechnet.
Ich würde die Achsen nicht blind gleich gewichten. Eine Beschleunigungsachse kann wesentlich aussagekräftiger sein als eine wenig informative Nebenmessung. Schon eine einfache fachliche Gewichtung verhindert, dass Rauschen den gesamten Ähnlichkeitswert bestimmt.
Wie sich der Rechenaufwand in Datenbanken begrenzen lässt
Für zwei Reihen mit jeweils 1.000 Messwerten entstehen bereits bis zu 1.000.000 Matrixzellen. Bei vielen Vergleichspaaren wächst der Aufwand entsprechend stark. Die klassische Berechnung benötigt für zwei Reihen der Länge n und m im Allgemeinen O(n · m) Zeit.
Der Speicherbedarf lässt sich reduzieren, wenn nur die Distanz und nicht der vollständige Pfad benötigt wird. Dann reichen meist zwei Matrixzeilen, sodass der Speicherbedarf ungefähr auf O(min(n,m)) sinkt. Für eine spätere Interpretation oder Visualisierung des Pfads muss die Ausrichtung dagegen gespeichert oder rekonstruiert werden.
Das Suchfenster sinnvoll wählen
Eine Sakoe-Chiba-Bandbegrenzung erlaubt nur Pfade innerhalb eines festgelegten Abstands zur Diagonalen. Bei einem Fenster von 50 darf ein Punkt also höchstens 50 Positionen von der direkten zeitlichen Zuordnung abweichen. Das reduziert die Zahl der geprüften Zellen und verhindert extreme Verzerrungen.
Ein Fenster von etwa 10 Prozent der Reihenlänge kann ein sinnvoller erster Test sein, ist aber keine allgemeingültige Regel. Bei stark schwankenden Prozessgeschwindigkeiten muss es größer sein, bei gut synchronisierten Messungen kleiner. Ich prüfe mehrere Fenstergrößen und vergleiche nicht nur die Laufzeit, sondern auch Trefferquote und Fehlalarme.
Von der Datenbankabfrage zur Kandidatensuche
In einer Zeitreihendatenbank sollte DTW selten auf jede gespeicherte Reihe angewendet werden. Besser ist eine mehrstufige Suche. Zuerst filtern Metadaten wie Maschine, Zeitraum, Betriebszustand oder Sensortyp die Kandidaten. Danach können einfache Merkmale wie Länge, Mittelwert, Varianz oder Minima und Maxima weitere Reihen ausschließen.
Erst im letzten Schritt wird die teure DTW-Distanz berechnet. Für große Bestände helfen zusätzlich untere Schranken, die schnell beweisen, dass eine Reihe nicht ähnlich genug sein kann. Näherungsverfahren wie FastDTW reduzieren den Aufwand weiter, liefern aber nicht in jedem Fall den exakt optimalen Pfad.
Die Speicherung in einer spezialisierten Zeitreihendatenbank löst das Problem nicht automatisch. Solche Systeme sind gut für Zeitstempel, Aggregationen und Bereichsabfragen geeignet, doch die flexible Pfadsuche benötigt häufig eine Analysekomponente, eine Erweiterung oder eine vorbereitete Kandidatenstruktur.
Welche Vorverarbeitung über gute oder schlechte Ergebnisse entscheidet
DTW ist tolerant gegenüber unterschiedlichen Geschwindigkeiten, aber nicht gegenüber beliebigen Datenproblemen. Unregelmäßige Zeitstempel, fehlende Messwerte und wechselnde Einheiten sollten vor der Berechnung behandelt werden. Sonst vergleicht der Algorithmus womöglich technische Artefakte statt der eigentlichen Muster.
- Messfenster festlegen: Vergleiche nur Abschnitte, die fachlich dasselbe Ereignis enthalten.
- Sampling prüfen: Bei stark unterschiedlichen Abtastraten ist eine gemeinsame Zeitbasis oder Interpolation oft sinnvoll.
- Skalierung wählen: Standardisiere Werte, wenn die absolute Höhe nicht Teil der Ähnlichkeit sein soll.
- Ausreißer behandeln: Einzelne extreme Werte können den optimalen Pfad unverhältnismäßig stark beeinflussen.
- Lokale Distanz definieren: Absolute Differenz, quadratische Differenz oder eine gewichtete Vektordistanz führen zu unterschiedlichen Ergebnissen.
- Grenzwert validieren: Teste die Distanz an bekannten ähnlichen und unähnlichen Beispielen.
Glättung kann helfen, Rauschen zu reduzieren, darf aber keine wichtigen Spitzen entfernen. Gerade bei Fehlerdiagnosen ist ein kurzer Ausschlag manchmal das entscheidende Signal. Deshalb würde ich Filterparameter immer an realen Fehlerfällen testen und nicht nur an optisch ruhigen Normaldaten.
Lesen Sie auch: Data Warehouse Tools - Was wirklich zählt (2024)
Typische Fehlentscheidungen
Der häufigste Fehler ist eine zu große zeitliche Freiheit. Ohne Bandbegrenzung kann DTW zufällige Abschnitte so stark verformen, dass auch fachlich völlig verschiedene Reihen ähnlich wirken. Dieses Verhalten wird oft als Überanpassung des Warping-Pfads sichtbar.
Ein zweites Problem entsteht, wenn Reihen lediglich anhand ihrer DTW-Distanz sortiert werden, ohne den Pfad zu betrachten. Ein niedriger Wert kann durch eine kurze, zufällige Übereinstimmung entstehen. Bei kritischen Anwendungen sollte deshalb zusätzlich geprüft werden, welche Abschnitte tatsächlich einander zugeordnet wurden.
Auch eine fehlende Normalisierung wird regelmäßig unterschätzt. Zwei gleich geformte Signale mit unterschiedlicher Amplitude können eine große Distanz erhalten, obwohl die Form für die Anwendung entscheidend ist. Umgekehrt kann eine aggressive Normalisierung echte Größenunterschiede verdecken.
DTW, Soft-DTW und Alternativen im direkten Vergleich
Die klassische Methode liefert einen konkreten optimalen Pfad und eine Distanz. Für Anwendungen mit großen Datenmengen oder lernenden Modellen kommen jedoch Varianten und Alternativen infrage. Die Wahl sollte sich danach richten, ob Interpretierbarkeit, Geschwindigkeit oder Differenzierbarkeit am wichtigsten ist.
| Methode | Geeignet für | Wichtige Einschränkung |
|---|---|---|
| Klassische DTW | Ähnlichkeitssuche und Mustervergleich | Quadratischer Aufwand ohne Begrenzung |
| DTW mit Sakoe-Chiba-Band | Schnellere Suche mit realistischer Zeitverschiebung | Ergebnis hängt von der Fensterbreite ab |
| Soft-DTW | Optimierung und maschinelles Lernen | Erzeugt eine geglättete, nicht exakt klassische Distanz |
| Fréchet-Distanz | Geometrische Kurven und Bewegungsbahnen | Weniger passend für manche verrauschten Messreihen |
| Time Warp Edit Distance | Zeitreihen mit Lücken, Einfügungen oder Löschungen | Mehr Parameter und aufwendigere Interpretation |
Für eine erste Analyse würde ich meist mit klassischer DTW und einer moderaten Bandbegrenzung beginnen. Erst wenn Laufzeit, Training oder fehlende Werte ein konkretes Problem darstellen, lohnt sich der Wechsel zu einer Variante. So bleibt nachvollziehbar, welche Eigenschaft die Verbesserung tatsächlich bringt.
Die wichtigste Entscheidung liegt vor der Distanzberechnung
DTW ist besonders stark, wenn zwei Zeitreihen dasselbe Ereignis mit unterschiedlichem Tempo zeigen. Es ersetzt aber keine saubere Definition dessen, was überhaupt als ähnlich gelten soll. Wer Messfenster, Skalierung, Warping-Fenster und Validierungsdaten sorgfältig festlegt, erhält deutlich verlässlichere Ergebnisse als mit einer unbeschränkten Standardberechnung.
Für kleine Datenmengen genügt oft eine direkte Berechnung. Bei großen Zeitreihenbeständen sollte die Suche dagegen über Metadaten, einfache Merkmale, untere Schranken und begrenzte Pfade vorgefiltert werden. So bleibt die Methode nicht nur mathematisch interessant, sondern wird zu einem praktisch einsetzbaren Werkzeug für Mustererkennung in Datenanalyse und Datenbanken.
