Dynamisches Time Warping Clustering

Was wäre der Ansatz, um mithilfe von Dynamic Time Warping (DTW) ein Clustering von Zeitreihen durchzuführen?

Ich habe über DTW gelesen, um Ähnlichkeiten zwischen zwei Zeitreihen zu finden, während sie zeitlich verschoben werden könnten. Kann ich diese Methode als Ähnlichkeitsmaß für Clustering-Algorithmen wie k-means verwenden?

Sie nicht k-Mittel für Zeitreihen verwenden.

DTW wird nicht durch den Mittelwert minimiert; k-means konvergiert möglicherweise nicht, und selbst wenn es konvergiert, liefert es kein sehr gutes Ergebnis. Der Mittelwert ist ein Schätzer der kleinsten Quadrate für die Koordinaten. Es minimiert die Varianz, nicht die willkürlichen Abstände, und k-means ist zur Minimierung der Varianz, nicht der willkürlichen Abstände ausgelegt .

Angenommen, Sie haben zwei Zeitreihen. Zwei Sinuswellen mit der gleichen Frequenz und einer ziemlich langen Abtastperiode; aber sie sind um . Da die DTW die Zeitverzerrung ausführt, können sie bis auf Anfang und Ende so ausgerichtet werden, dass sie perfekt übereinstimmen. DTW wird diesen beiden Serien einen relativ kleinen Abstand zuweisen. Wenn Sie jedoch den Mittelwert der beiden Reihen berechnen , ist dies eine flache 0 - sie heben sich auf. Der Mittelwert führt keine dynamischen Zeitverzerrungen durch und verliert den gesamten Wert, den die DTW erhalten hat. Bei solchen Daten kann es sein, dass k-means nicht konvergiert und die Ergebnisse bedeutungslos sind. K-Mittel sollten wirklich nur mit der Varianz (= quadrierte euklidische) oder einigen Fällen verwendet werden , die (wie Cosinus äquivalent sind, auf L2 - Daten normalisiert, wobei Kosinusähnlichkeit ist$\pi$dasselbe wie Quadrat (euklidischer Abstand)$2 -$

Berechnen Sie stattdessen eine Distanzmatrix mit DTW und führen Sie dann hierarchische Clustering-Vorgänge wie Single-Link aus. Im Gegensatz zu k-means kann die Reihe auch unterschiedlich lang sein.

Ja, Sie können den DTW- Ansatz zur Klassifizierung und Gruppierung von Zeitreihen verwenden . Ich habe die folgenden Ressourcen zusammengestellt , die sich genau auf dieses Thema konzentrieren (ich habe kürzlich eine ähnliche Frage beantwortet, aber nicht auf dieser Site, daher kopiere ich den Inhalt hier, damit es für jedermann bequem ist):

• UCR-Zeitreihenklassifizierung / Clustering : Hauptseite , Softwareseite und entsprechendes Papier
• Zeitreihenklassifizierung und Clustering mit Python : ein Blogbeitrag
• Capital Bikeshare: Zeitreihen-Clustering : ein weiterer Blog-Beitrag
• Zeitreihenklassifizierung und Clustering : ipython notebook
• Dynamic Time Warping mit rpy und Python : ein weiterer Blogbeitrag
• Mining-Zeitreihen mit Billionen von Punkten: Dynamic Time Warping at Scale : ein weiterer Blog-Beitrag
• Zeitreihenanalyse und Mining in R (um R zum Mix hinzuzufügen): ein weiterer Blog-Beitrag
• Und schließlich zwei Tools, die DTW implementieren / unterstützen, um das Ganze abzurunden : R-Paket und Python-Modul

Petitjean et al. Haben ein neues Verfahren zur DTW-Mittelwertbildung (DBA) vorgeschlagen . zu durchschnittlichen Zeitreihen. In einer anderen Arbeit haben sie empirisch und theoretisch bewiesen, wie man Zeitreihen mit k-Mitteln gruppieren kann. Eine Implementierung wird von den Autoren auf GitHub bereitgestellt ( Link zum Code ).

1 F. Petitjean, G. Forestier, G. I. Webb, AE Nicholson, Y. Chen und E. Keogh, "Dynamische Zeitverzerrungs-Mittelung von Zeitreihen ermöglicht eine schnellere und genauere Klassifizierung", 2014 IEEE International Conference on Data Mining, Shenzhen, 2014 .

2 F. Petitjean, P. Gançarski, Zusammenfassung einer Reihe von Zeitreihen durch Mittelwertbildung: Von der Steiner-Sequenz zur kompakten multiplen Ausrichtung, Theoretical Computer Science, Band 414, Ausgabe 1, 2012

Dynamic Time Warp vergleicht die realisierten Datenpunkte, die möglicherweise funktionieren oder nicht. Ein genauerer Ansatz besteht darin, die Verteilung der Zeitreihen anhand einer Metrik zu vergleichen, die als Teleskopentfernung bezeichnet wird .

Das Coole an dieser Metrik ist, dass die empirische Berechnung durch Anpassen einer Reihe von Binärklassifikatoren wie SVM erfolgt.

Eine kurze Erklärung finden Sie hier .

Bei Clustering-Zeitreihen wurde gezeigt, dass sie die DTW übertreffen. siehe Tabelle 1 im Originalpapier [1].

[1] Ryabko, D. & Mary, J. (2013). Eine auf Binärklassifikationen basierende Metrik zwischen Zeitreihenverteilungen und deren Verwendung bei statistischen und Lernproblemen. The Journal of Machine Learning Research, 14 (1), 2837-2856.

Ja. Ein naiver und möglicherweise langsamer Ansatz könnte sein,

1. Erstellen Sie alle Clusterkombinationen. k steht für die Anzahl der Cluster und n für die Anzahl der Serien. Die Anzahl der zurückgegebenen Artikel sollte betragen n! / k! / (n-k)!. Dies wären so etwas wie potenzielle Zentren.
2. Berechnen Sie für jede Serie die Entfernungen über DTW für jedes Zentrum in jeder Clustergruppe und weisen Sie es dem Minimum zu.
3. Berechnen Sie für jede Clustergruppe die Gesamtentfernung innerhalb der einzelnen Cluster.
4. Wählen Sie das Minimum.

Ich habe das für ein kleines Projekt benutzt. Hier ist mein Repository über Zeitreihen-Clustering und meine andere Antwort dazu.