Dynamic Time Warping für unregelmäßige Zeitreihen

10

Ich habe in letzter Zeit viel über Dynamic Time Warping (DTW) gelesen. Ich bin sehr überrascht, dass es überhaupt keine Literatur zur Anwendung von DTW auf unregelmäßige Zeitreihen gibt, oder zumindest konnte ich sie nicht finden.

Könnte mir jemand einen Hinweis auf etwas geben, das mit diesem Problem zusammenhängt, oder vielleicht sogar eine Implementierung davon?

Remi D.
quelle
Ich würde mit cran.r-project.org/web/packages/dtw/index.html
kjetil b halvorsen

Antworten:

11

Soweit ich weiß, meinen Sie mit unregelmäßigen Zeitreihen ungleichmäßig verteilte Zeitreihen , die auch als unregelmäßig abgetastete Zeitreihen bezeichnet werden . Da ich auf Zeitreihen im Allgemeinen neugierig bin, habe ich eine kurze Recherche zum Thema Ihres (und jetzt meines) Interesses durchgeführt. Die Ergebnisse folgen.

Trotz der großen Beliebtheit des DTW- Ansatzes (Dynamic Time Warping) bei der Analyse, Clusterbildung und Klassifizierung von Zeitreihen stellen unregelmäßige Zeitreihen einige Herausforderungen für die direkte Anwendung von DTW auf einen solchen Datentyp dar (siehe beispielsweise dieses und dieses Dokument ). Aufgrund meiner relativ kurzen Forschungsanstrengungen ist mir nicht ganz klar, ob es unmöglich ist, DTW direkt anzuwenden, wie einige Untersuchungen etwas anderes vorschlagen (siehe auch dieses Papier / Kapitel ). Für mehr Vollständigkeit möchte ich auch eine IMHO erwähnen, die für das Thema Dissertation über unregelmäßige Zeitreihen ausgezeichnet und relevant ist .

Dennoch scheint dieses Thema hauptsächlich von den folgenden zwei Forschungsströmen abgedeckt zu werden :

  • Vorschläge und Bewertungen alternativer Ansätze zur DTW , z. B. modellbasierte (siehe dieses und dieses Papier );
  • Vorschläge und Bewertungen modifizierter DTW-Ansätze wie cDTW , EDR , ERP , TWED , Hüllkurventransformationen , CDTW ( kontinuierliche DTW - nicht verwechseln mit cDTW - eingeschränkte DTW !) und andere Varianten (siehe z. B. dieses Dokument ). Eine Übersicht über die oben genannten Ansätze und Ergebnisse einiger empirischer Vergleiche finden Sie in diesem Artikel .

Abschließend möchte ich auf das Thema Open-Source-Software eingehen , die für Forschungszwecke oder zur Systemimplementierung zur Verfügung steht , sich auf DTW konzentriert und einige der oben genannten Algorithmen für unregelmäßige Zeitreihen unterstützt. Zu dieser Software gehören ein Python / NumPy- basiertes cDTW-Modulprojekt sowie ein GPU-fokussiertes CUDA-basiertes CUDA-DTW-Projekt . Für REnthusiasten sollte auch ein umfassendes Dynamic Time Warp-Projekt erwähnt werden ( entsprechendes Paket dtwist auf CRAN verfügbar). Auch wenn es derzeit möglicherweise nicht viele DTW-Algorithmen für unregelmäßige Zeitreihen unterstützt (obwohl ich denke, dass es cDTW unterstützt), ist es meiner Meinung nach nur eine Frage der Zeit, bis dieses Projekt eine umfassendere Unterstützung für DTW-Algorithmen bietet, die sich auf solche Typen konzentrieren von Dateien. Ich hoffe, es hat Ihnen genauso viel Spaß gemacht, meine Antwort zu lesen, wie es mir Spaß gemacht hat, das Thema zu recherchieren und diesen Beitrag zu schreiben.

Aleksandr Blekh
quelle
1

Ich habe DTW erfolgreich in 'C' implementiert, um es auf die dynamische Signaturüberprüfung anzuwenden. Ich habe eine Testdatenbank mit chinesischen und niederländischen Signaturen verwendet, um die EER zu überprüfen, und habe sehr beeindruckende Ergebnisse erzielt. Es ist derzeit als Demo auf einem iPad implementiert. Mein Algorithmus wurde aus mehreren veröffentlichten Beschreibungen handcodiert. Ich werde den Code weitergeben, wenn es eine Möglichkeit gibt, ihn zu Ihnen zu bringen. Eine Sache, die ebenfalls zum Erfolg beitrug, war die "Normalisierung" der Eingabedaten. Dies machte es viel einfacher, unterschiedliche Daten mit unterschiedlichen Abtastraten zu vergleichen.

user6009837
quelle
Willkommen auf unserer Webseite! Beachten Sie, dass Ihr Benutzername, Ihr Identikon und ein Link zu Ihrer Benutzerseite automatisch zu jedem Beitrag hinzugefügt werden, sodass Sie Ihre Beiträge nicht signieren müssen.
Silverfish
2
Wir möchten, dass unsere Antworten für zukünftige Leser nützlich sind und nicht nur für das Originalposter persönlich. Daher wäre die Möglichkeit, den Code zu teilen, nützlicher, wenn Sie irgendwo hochladen und hier einen Link teilen könnten. Aber wenn das nicht möglich ist, könnten Sie vielleicht etwas Licht auf "Mein Algorithmus wurde aus mehreren veröffentlichten Beschreibungen handcodiert" werfen - könnten Sie diejenigen zitieren, die Sie verwendet haben, falls jemand anderes in Ihre Fußstapfen treten und sie implementieren möchte?
Silverfish
0

Ich steige gerade erst selbst in die DTW ein und habe die unten genannten Pakete nicht persönlich verwendet, aber ich hoffe, dass das Folgende Ihnen helfen kann.

Das Cran.R-Projekt, insbesondere: • "ts" ist die Grundklasse für regelmäßig beabstandete Zeitreihen mit numerischen Zeitstempeln. • Das "Zoo" -Paket bietet Infrastruktur für regelmäßige und unregelmäßig verteilte Zeitreihen unter Verwendung beliebiger Klassen für die Zeitstempel. Es ist so konzipiert, dass es mit "ts" so konsistent wie möglich ist. • Zoo: S3-Infrastruktur für reguläre und unregelmäßige Zeitreihen (Zs geordnete Beobachtungen)

Verweise: http://cran.r-project.org/web/views/TimeSeries.html und http://cran.r-project.org/web/packages/zoo/index.html

Schöne Grüße.

TonyMorland
quelle
1
Meine Frage betraf die Anpassung der DTW als Methode an den Kontext unregelmäßiger Zeitreihen. Pakete wie Zoo bieten keine Lösung für dieses Problem.
Remi D
0

TSdist hat eine Funktion, die den Abstand durch dtw bestimmt. Es akzeptiert unregelmäßige Zoo-Zeitreihen

tiagovrtr
quelle
1
"Akzeptiert" bedeutet nicht, dass es sie behandelt. Sie sollten immer den Quellcode einer Funktion überprüfen.
Remi D