Dynamic-Time-Warping: So funktioniert Zeitnormierung

Dynamic-Time-Warping kommt zum Einsatz, um verschieden lange Wertfolgen in einem Mustervergleich auf Übereinstimmungen hin zu überprüfen. Hierzu erzeugt der Algorithmus der dynamischen Zeitnormierung Warping-Pfade, an denen sich durch Backtracking und Differenzmaße Übereinstimmungen trotz Zeitverzerrung oder unterschiedlicher Geschwindigkeit erkennen lassen. Zur Anwendung kommt DTW u. a. für die Spracherkennung, zur digitalen Unterschriftenerkennung oder auch zur Analyse von Finanzmärkten.

Was bedeutet Dynamic-Time-Warping?

Dynamic-Time-Warping (DTW), übersetzt: „dynamische Zeitnormierung“ – das klingt im ersten Moment wie eine Technologie aus Star Trek. Tatsächlich handelt es sich jedoch um nichts anderes als einen Algorithmus für den Vergleich von verschiedenen Zeitabläufen oder Wertereihen. Diese werden hierzu vom Algorithmus aufeinander abgebildet und miteinander verglichen. Durch das namensgebende „Warping“ der Sequenzen lassen sich auch bei unterschiedlicher Länge oder Geschwindigkeit Gemeinsamkeiten und übereinstimmende Muster zwischen den Sequenzen erkennen.

Zur Veranschaulichung: Sollen zwei verschiedene Gehsequenzen auf Übereinstimmungen hin untersucht werden, ist der Algorithmus in der Lage, auch bei unterschiedlicher Gehgeschwindigkeit oder zurückgelegter Strecke identische Muster zu erkennen. Beim Vergleich von Unterschriften derselben Person wiederum lassen sich auch bei unterschiedlicher Größe der Schrift Gemeinsamkeiten identifizieren.

Welchen Zweck hat Dynamic-Time-Warping?

Zugegeben, DTW wirkt auf den ersten Blick wie ein abstraktes Konzept ohne erkennbaren praktischen Nutzen. Das Gegenteil ist jedoch der Fall: Dynamic-Time-Warping erfüllt in vielfältigen Anwendungsbereichen eine wichtige Analysefunktion. Das gilt vor allem für die Sequenzanalyse von Video- und Audio-Sequenzen, Grafiken oder statistischen Modellen, Sequenzen also, die sich linear abbilden und vergleichen lassen. Indem DTW Übereinstimmungen erkennt, lassen sich bestimmte Aktionen, Signale oder Funktionen auslösen.

Darüber hinaus können durch Mustermessung und Mustererkennung in Wertereihen ähnliche Systementwicklungen auch über verschiedene Zeiträume hinweg untersucht werden. Aus diesem Grund findet der Dynamic-Time-Warping-Algorithmus auch in zukunftsweisenden Technologien wie Machine Learning, Supervised Learning oder Neural Networks Anwendung, um die Analyse- und Reaktionsfähigkeiten selbstlernender Systeme zu trainieren und Datensätze effizienter auszuwerten.

Wie funktioniert Dynamic-Time-Warping?

Um Muster und Gemeinsamkeiten in verschiedenen Wertereihen zu erkennen, sucht DTW nach optimalen Übereinstimmungen, auch „optimal matches“ genannt. Hierbei helfen die Prinzipien „One-to-Many“ oder „Many-to-One“. Es werden verschiedene Regeln und Bedingungen angewandt:

  • Jeder Wert einer Sequenz muss mit einem oder mehreren Werten der zweiten Sequenz verglichen werden (und umgekehrt).
  • Der erste Wert einer Sequenz muss mit dem ersten Wert der zweiten Sequenz verglichen werden.
  • Der letzte Wert einer Sequenz muss mit dem letzten Wert der zweiten Sequenz verglichen werden.
  • Die Abbildung (Mapping) der Wertereihen der ersten Sequenz auf den Wertereihen der zweiten Sequenz muss monoton zunehmen. Werte am Anfang und Ende der Sequenzen müssen also in Ihren Positionen übereinstimmen, ohne Auslassung oder Überschneidungen.

Eine optimale Übereinstimmung liegt vor, wenn alle Vorgaben und Bedingungen erfüllt sind. Hierbei kommt eine sogenannte Kostenfunktion zum Einsatz, mit der sich ein Differenzmaß zwischen Werten der Sequenzen erstellen lässt. Eine optimale Übereinstimmung hängt von einer möglichst geringen Kostenfunktion ab.

Zudem erstellt der Algorithmus einen Warping-Pfad, der in der Lage ist, auch optimale Übereinstimmungen in Sequenzen mit verschiedenen Längen zu erkennen. Der Warping-Pfad entsteht durch Backtracking, bei dem der Algorithmus einen oder mehrere Werte einer Sequenz auf Punkten der zweiten Sequenz abbildet. Hierdurch lassen sich trotz oder vielmehr durch Zeitverzerrung auch bei unterschiedlich langen Zeitsequenzen Übereinstimmungen finden.

Domain kaufen
Registrieren Sie Ihre perfekte Domain
  • Inklusive Wildcard-SSL-Zertifikat
  • Inklusive Domain Lock
  • Inklusive 2 GB E-Mail-Postfach

Wo kommt Dynamic-Time-Warping zum Einsatz?

Dynamic-Time-Warping kann überall dort zum Einsatz kommen, wo sich Datensätze in linearen Sequenzen abbilden und vergleichen lassen. So wird DTW oftmals als Vor- oder Nachuntersuchung in der Datenanalyse eingesetzt. Dabei kann es sich um Audio-Daten, Video-Daten, alphanumerische Daten oder Big-Data-basierte Datensätze handeln.

Weitere Anwendungsbereiche für DTW sind zum Beispiel:

  • Mustererkennung in Audio-Sequenzen: Ein wichtiger Anwendungsfall für DTW ist die Spracherkennung. Hierbei werden aufgezeichnete und gespeicherte Sprachmuster per DTW im Mustervergleich aufeinander abgebildet. Bei unterschiedlich langen oder schnellen Audio-Sequenzen nutzt DTW die adaptive Zeitnormierung, um einen Warping-Pfad zu erstellen. Hierdurch lassen sich Übereinstimmungen auch in unterschiedlich lang oder schnell ausgesprochenen Vokalen und Konsonanten erkennen.
  • Mustererkennung Video-Sequenzen: Zur Gesten- und Bewegungserkennung werden durch DTW Video-Sequenzen, z. B. von Bewegungsabläufen, aufeinander abgebildet. Es erfolgen ein Vergleich und eine Mustererkennung in Bewegungsabläufen, auch bei verschiedenen zeitlichen Längen oder unterschiedlichen Geschwindigkeiten.
  • Mustererkennung in Finanzdaten: Weitere wichtige Anwendungsbereiche sind Finanzmärkte und Unternehmensfinanzen. Sollen Prognosen zu Finanzzyklen, Umsatzkurven oder Börsentrends erstellt werden, bietet sich der Einsatz von DTW an. Über verschiedene Zeiträume hinweg lassen sich durch DTW ähnliche oder identische Zyklen und Trends in Markt- und Unternehmensdaten aufzeigen und visualisieren. Die Untersuchung basiert sowohl auf Prognosen als auch auf gesammelten Geschäfts- und Finanzdaten.

Welche Tools implementieren Dynamic-Time-Warping?

Der DTW-Algorithmus findet sich in den Bibliotheken verschiedener Open-Source-Software. Dazu zählen:

  • DTW Suite mit Programmierpaketen für Python und R
  • FastDTW bietet eine Java-Implementierung für DTW-Algorithmen.
  • MatchBox implementiert DTW für Audio-Signale.
  • mlpy und pydtw bieten als Python Bibliotheken für Machine Learning auch DTW-Funktionen.
  • Gesture Recognition bietet DTW-Algorithmen zur Echtzeit-Gestenerkennung.

Um DTW möglichst effizient anzuwenden, kommen auch folgende Fast-Computation-Techniken zum Einsatz:

  • PruneDTW
  • SparseDTW
  • FastDTW
  • MultiscaleDTW

Beispiel: Dynamic-Time-Warping als Algorithmus in Python

Zur Veranschaulichung der Komplexität von Dynamic-Time-Warping finden Sie im Folgenden ein Beispiel für einen DTW-Algorithmus im Python-Code:

def dtw(s, t, window):
    n, m = len(s), len(t)
    w = np.max([window, abs(n-m)])
    dtw_matrix = np.zeros((n+1, m+1))
    
    for i in range(n+1):
        for j in range(m+1):
            dtw_matrix[i, j] = np.inf
    dtw_matrix[0, 0] = 0
    
    for i in range(1, n+1):
        for j in range(np.max([1, i-w]), np.min([m, i+w])+1):
            dtw_matrix[i, j] = 0
    
    for i in range(1, n+1):
        for j in range(np.max([1, i-w]), np.min([m, i+w])+1):
            cost = abs(s[i-1] - t[j-1])
            # take last min from a square box
            last_min = np.min([dtw_matrix[i-1, j], dtw_matrix[i, j-1], dtw_matrix[i-1, j-1]])
            dtw_matrix[i, j] = cost + last_min
    return dtw_matrix

Der im Codebeispiel vorgestellten Funktion werden zunächst drei Parameter übergeben: Zuerst werden die beiden Signale, die untersucht werden sollen, in den Parametern namens s und t übergeben. Im Regelfall handelt es sich bei den Signalen um Arrays oder Vektoren. Mit dem Parameter namens window kann spezifiziert werden, mit wie vielen anderen Elementen ein Matching stattfinden kann.

In der Funktion wird dann zunächst eine Matrix erstellt und mit dem Wert unendlich initialisiert. Der zentrale DTW-Schritt passiert in den letzten beiden verschachtelten For-Schleifen: Man addiert zu den bisherigen Kosten, die in der Variable costs gespeichert werden und die sich aus der Distanz der beiden Eingabewerte am jeweiligen Index zueinander ergeben, den Wert, der in der Variable last_min gespeichert ist.

Hierbei handelt es sich um einen Wert, der sich aufgrund des dynamischen Programmierens aus bereits berechneten Werten ergibt. Man wählt das Minimum aus den bereits zuvor berechneten, umliegenden Werten aus und addiert es zu den zuvor errechneten Kosten. Dieser Schritt entscheidet darüber, ob man zwei Elemente direkt matcht, ein Element hinzufügt oder aber ein Element löscht.

Nachdem die Funktion ausgeführt wurde, erhält man eine Distanzmatrix, aus der man den Warping-Pfad ablesen kann.

Alternativen zu Dynamic-Time-Warping

Weitere Möglichkeiten zur Mustererkennung in Sequenzen und Zeitabläufen, die als Alternative zu DTW zum Einsatz kommen, sind:

  • Correlation Optimized Warping (COW)
  • Funktionale Datenanalyse
  • Hidden Markov Model
  • Viterbi-Algorithmus
War dieser Artikel hilfreich?