dtaidistance
v2.3.10
Bibliothek für Zeitreihenabstände (z. B. Dynamic Time Warping), die in der DTAI-Forschungsgruppe verwendet wird. Die Bibliothek bietet eine reine Python-Implementierung und eine schnelle Implementierung in C. Die C-Implementierung hat nur Cython als Abhängigkeit. Es ist mit Numpy und Pandas kompatibel und so implementiert, dass unnötige Datenkopiervorgänge vermieden werden.
Dokumentation: http://dtaidistance.readthedocs.io
Beispiel:
from dtaidistance import dtw
import numpy as np
s1 = np.array([0.0, 0, 1, 2, 1, 0, 1, 0, 0])
s2 = np.array([0.0, 1, 2, 0, 0, 0, 0, 0, 0])
d = dtw.distance_fast(s1, s2)
Zitieren dieser Arbeit:
Wannes Meert, Kilian Hendrickx, Toon Van Craenendonck, Pieter Robberechts, Hendrik Blockeel und Jesse Davis.
DTAIDistance (Version v2). Zenodo.
http://doi.org/10.5281/zenodo.5901139
Neu in v2 :
ssize_t anstelle von int ermöglicht größere Datenstrukturen auf 64-Bit-Maschinen und ist besser mit Numpy kompatibel.max_dist -Argument der Arbeit von Silva und Batista an PrunedDTW [7] ähnelte. Die Toolbox implementiert jetzt eine Version, die PrunedDTW entspricht, da sie mehr Teilabstände beschneidet. Darüber hinaus wird ein use_pruning Argument hinzugefügt, um max_dist automatisch auf den euklidischen Abstand zu setzen, wie von Silva und Batista vorgeschlagen, um die Berechnung zu beschleunigen (eine neue Methode ub_euclidean ist verfügbar).dtaidistance.dtw_ndim . $ pip install dtaidistance
oder
$ conda install -c conda-forge dtaidistance
Die Pip-Installation erfordert Numpy als Abhängigkeit zum Kompilieren von Numpy-kompatiblem C-Code (mit Cython). Diese Abhängigkeit ist jedoch optional und kann entfernt werden.
Der Quellcode ist unter github.com/wannesm/dtaidistance verfügbar.
Sollten bei der Kompilierung Probleme auftreten (z. B. ist die C-basierte Implementierung oder OpenMP nicht verfügbar), finden Sie in der Dokumentation weitere Optionen.
from dtaidistance import dtw
from dtaidistance import dtw_visualisation as dtwvis
import numpy as np
s1 = np.array([0., 0, 1, 2, 1, 0, 1, 0, 0, 2, 1, 0, 0])
s2 = np.array([0., 1, 2, 3, 1, 0, 0, 0, 2, 1, 0, 0, 0])
path = dtw.warping_path(s1, s2)
dtwvis.plot_warping(s1, s2, path, filename="warp.png")
Nur das Distanzmaß basiert auf zwei Zahlenfolgen:
from dtaidistance import dtw
s1 = [0, 0, 1, 2, 1, 0, 1, 0, 0]
s2 = [0, 1, 2, 0, 0, 0, 0, 0, 0]
distance = dtw.distance(s1, s2)
print(distance)
Die schnellste Version (30-300-mal) verwendet c direkt, erfordert jedoch ein Array als Eingabe (mit dem Typ double) und bereinigt (optional) auch Berechnungen, indem max_dist auf die euklidische Obergrenze gesetzt wird:
from dtaidistance import dtw
import array
s1 = array.array('d',[0, 0, 1, 2, 1, 0, 1, 0, 0])
s2 = array.array('d',[0, 1, 2, 0, 0, 0, 0, 0, 0])
d = dtw.distance_fast(s1, s2, use_pruning=True)
Oder Sie können ein Numpy-Array verwenden (mit dtype double oder float):
from dtaidistance import dtw
import numpy as np
s1 = np.array([0, 0, 1, 2, 1, 0, 1, 0, 0], dtype=np.double)
s2 = np.array([0.0, 1, 2, 0, 0, 0, 0, 0, 0])
d = dtw.distance_fast(s1, s2, use_pruning=True)
Informationen zu den verfügbaren Argumenten finden Sie im __doc__ :
print(dtw.distance.__doc__)
Es sind eine Reihe von Optionen vorgesehen, um einige Pfade, die der dynamische Programmieralgorithmus untersucht, frühzeitig zu stoppen oder die Berechnung des Entfernungsmaßes zu optimieren:
window : Abweichungen von den beiden Diagonalen sind nur bis zu diesem Betrag zulässig.max_dist : Stoppen, wenn das zurückgegebene Entfernungsmaß größer als dieser Wert ist.max_step : Schritte größer als dieser Wert sind nicht zulässig.max_length_diff : Gibt Unendlich zurück, wenn der Längenunterschied zwischen zwei Serien größer ist.penalty : Strafe, die hinzugefügt wird, wenn Komprimierung oder Expansion angewendet wird (zusätzlich zur Distanz).psi : Psi-Relaxierung, um den Anfang und/oder das Ende von Sequenzen zu ignorieren (für zyklische Sequenzen) [2].use_pruning : Bereinigt Berechnungen basierend auf der euklidischen Obergrenze. Wenn Sie möchten, dass die vollständige Matrix neben der Entfernung auch alle möglichen Warping-Pfade anzeigt:
from dtaidistance import dtw
s1 = [0, 0, 1, 2, 1, 0, 1, 0, 0]
s2 = [0, 1, 2, 0, 0, 0, 0, 0, 0]
distance, paths = dtw.warping_paths(s1, s2)
print(distance)
print(paths)
Die Matrix mit allen Warping-Pfaden kann wie folgt visualisiert werden:
from dtaidistance import dtw
from dtaidistance import dtw_visualisation as dtwvis
import random
import numpy as np
x = np.arange(0, 20, .5)
s1 = np.sin(x)
s2 = np.sin(x - 1)
random.seed(1)
for idx in range(len(s2)):
if random.random() < 0.05:
s2[idx] += (random.random() - 0.5) / 2
d, paths = dtw.warping_paths(s1, s2, window=25, psi=2)
best_path = dtw.best_path(paths)
dtwvis.plot_warpingpaths(s1, s2, paths, best_path)
Beachten Sie den psi Parameter, der die Übereinstimmung am Anfang und am Ende lockert. In diesem Beispiel ergibt sich eine perfekte Übereinstimmung, obwohl die Sinuswellen leicht verschoben sind.
Um die DTW-Abstandsmaße zwischen allen Sequenzen in einer Liste von Sequenzen zu berechnen, verwenden Sie die Methode dtw.distance_matrix . Sie können Variablen so einstellen, dass sie mehr oder weniger C-Code ( use_c und use_nogil ) und eine parallele oder serielle Ausführung ( parallel ) verwenden.
Die Methode distance_matrix erwartet eine Liste von Listen/Arrays:
from dtaidistance import dtw
import numpy as np
series = [
np.array([0, 0, 1, 2, 1, 0, 1, 0, 0], dtype=np.double),
np.array([0.0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0]),
np.array([0.0, 0, 1, 2, 1, 0, 0, 0])]
ds = dtw.distance_matrix_fast(series)
oder eine Matrix (falls alle Reihen die gleiche Länge haben):
from dtaidistance import dtw
import numpy as np
series = np.matrix([
[0.0, 0, 1, 2, 1, 0, 1, 0, 0],
[0.0, 1, 2, 0, 0, 0, 0, 0, 0],
[0.0, 0, 1, 2, 1, 0, 0, 0, 0]])
ds = dtw.distance_matrix_fast(series)
Sie können die Berechnung anweisen, nur einen Teil der Entfernungsmaßmatrix auszufüllen. Beispielsweise, um die Berechnungen auf mehrere Knoten zu verteilen oder nur Quellreihen mit Zielreihen zu vergleichen.
from dtaidistance import dtw
import numpy as np
series = np.matrix([
[0., 0, 1, 2, 1, 0, 1, 0, 0],
[0., 1, 2, 0, 0, 0, 0, 0, 0],
[1., 2, 0, 0, 0, 0, 0, 1, 1],
[0., 0, 1, 2, 1, 0, 1, 0, 0],
[0., 1, 2, 0, 0, 0, 0, 0, 0],
[1., 2, 0, 0, 0, 0, 0, 1, 1]])
ds = dtw.distance_matrix_fast(series, block=((1, 4), (3, 5)))
Die Ausgabe lautet in diesem Fall:
# 0 1 2 3 4 5
[[ inf inf inf inf inf inf] # 0
[ inf inf inf 1.4142 0.0000 inf] # 1
[ inf inf inf 2.2360 1.7320 inf] # 2
[ inf inf inf inf 1.4142 inf] # 3
[ inf inf inf inf inf inf] # 4
[ inf inf inf inf inf inf]] # 5
Für die Clusterung von Zeitreihen kann eine Distanzmatrix verwendet werden. Sie können vorhandene Methoden wie scipy.cluster.hierarchy.linkage oder eine der beiden enthaltenen Clustering-Methoden verwenden (letztere ist ein Wrapper für die SciPy-Verknüpfungsmethode).
from dtaidistance import clustering
# Custom Hierarchical clustering
model1 = clustering.Hierarchical(dtw.distance_matrix_fast, {})
cluster_idx = model1.fit(series)
# Augment Hierarchical object to keep track of the full tree
model2 = clustering.HierarchicalTree(model1)
cluster_idx = model2.fit(series)
# SciPy linkage clustering
model3 = clustering.LinkageTree(dtw.distance_matrix_fast, {})
cluster_idx = model3.fit(series)
Für Modelle, die den gesamten Clustering-Baum ( HierarchicalTree oder LinkageTree ) verfolgen, kann der Baum visualisiert werden:
model.plot("myplot.png")
Optional:
Entwicklung:
DTAI distance code.
Copyright 2016-2022 KU Leuven, DTAI Research Group
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
