k-Shape

Die Verbreitung und Allgegenwart zeitlicher Daten in vielen Disziplinen hat ein erhebliches Interesse an der Analyse und dem Mining von Zeitreihen geweckt. Clustering ist eine der beliebtesten Datenanalysemethoden, nicht nur wegen ihrer explorativen Stärke, sondern auch als Vorverarbeitungsschritt oder Unterroutine für andere Techniken. In diesem Papier stellen wir k-Shape vor, einen neuartigen Algorithmus zum Clustering von Zeitreihen. k-Shape basiert auf einem skalierbaren iterativen Verfeinerungsverfahren, das homogene und gut getrennte Cluster schafft. Als Abstandsmaß verwendet k-Shape eine normierte Version des Kreuzkorrelationsmaßes, um die Formen der Zeitreihen beim Vergleich zu berücksichtigen. Basierend auf den Eigenschaften dieses Abstandsmaßes entwickeln wir eine Methode zur Berechnung der Cluster-Zentroiden, die in jeder Iteration verwendet werden, um die Zuordnung der Zeitreihen zu den Clustern zu aktualisieren. Um die Robustheit von k-Shape zu demonstrieren, führen wir eine umfangreiche experimentelle Evaluierung unseres Ansatzes gegenüber partitionierenden, hierarchischen und spektralen Clustering-Methoden durch, mit Kombinationen der wettbewerbsfähigsten Abstandsmaße. k-Shape übertrifft alle skalierbaren Ansätze in Bezug auf die Genauigkeit. Darüber hinaus übertrifft k-Shape auch alle nicht-skalierbaren (und daher unpraktischen) Kombinationen, mit einer Ausnahme, die ähnliche Genauigkeitsergebnisse erzielt. Im Gegensatz zu k-Shape erfordert diese Kombination jedoch die Anpassung ihres Abstandsmaßes und ist zwei Größenordnungen langsamer als k-Shape. Insgesamt erweist sich k-Shape als domänenunabhängiger, hochgenauer und hocheffizienter Clustering-Ansatz für Zeitreihen mit breiten Anwendungen.