dtaidistance
v2.3.10
Bibliothèque pour les distances des séries temporelles (par exemple Dynamic Time Warping) utilisée dans le groupe de recherche DTAI. La bibliothèque propose une implémentation Python pure et une implémentation rapide en C. L'implémentation C n'a que Cython comme dépendance. Il est compatible avec Numpy et Pandas et mis en œuvre de manière à éviter les opérations de copie de données inutiles.
Documentation : http://dtaidistance.readthedocs.io
Exemple:
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)
Citant cet ouvrage :
Wannes Meert, Kilian Hendrickx, Toon Van Craenendonck, Pieter Robberechts, Hendrik Blockeel et Jesse Davis.
DTAIDistance (Version v2). Zénodo.
http://doi.org/10.5281/zenodo.5901139
Nouveau dans la v2 :
ssize_t au lieu de int permet des structures de données plus grandes sur les machines 64 bits et est plus compatible avec Numpy.max_dist s'est avéré être similaire au travail de Silva et Batista sur PrunedDTW [7]. La boîte à outils implémente désormais une version égale à PrunedDTW car elle élague davantage de distances partielles. De plus, un argument use_pruning est ajouté pour définir automatiquement max_dist sur la distance euclidienne, comme suggéré par Silva et Batista, afin d'accélérer le calcul (une nouvelle méthode ub_euclidean est disponible).dtaidistance.dtw_ndim . $ pip install dtaidistance
ou
$ conda install -c conda-forge dtaidistance
L'installation de pip nécessite Numpy comme dépendance pour compiler du code C compatible avec Numpy (en utilisant Cython). Toutefois, cette dépendance est facultative et peut être supprimée.
Le code source est disponible sur github.com/wannesm/dtaidistance.
Si vous rencontrez des problèmes lors de la compilation (par exemple, l'implémentation basée sur C ou OpenMP n'est pas disponible), consultez la documentation pour plus d'options.
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")
Uniquement la mesure de distance basée sur deux séquences de nombres :
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)
La version la plus rapide (30 à 300 fois) utilise c directement mais nécessite un tableau en entrée (avec le type double) et (éventuellement) élague également les calculs en définissant max_dist sur la limite supérieure euclidienne :
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)
Ou vous pouvez utiliser un tableau numpy (avec dtype double ou 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)
Consultez le __doc__ pour plus d'informations sur les arguments disponibles :
print(dtw.distance.__doc__)
Un certain nombre d'options sont prévues pour arrêter prématurément certains chemins explorés par l'algorithme de programmation dynamique ou ajuster le calcul de la mesure de distance :
window : Autoriser uniquement les décalages jusqu'à ce montant par rapport aux deux diagonales.max_dist : Arrêtez si la mesure de distance renvoyée est supérieure à cette valeur.max_step : N'autorisez pas de pas supérieurs à cette valeur.max_length_diff : Renvoie l'infini si la différence de longueur de deux séries est plus grande.penalty : Pénalité à ajouter si une compression ou une expansion est appliquée (en plus de la distance).psi : Relaxation Psi pour ignorer le début et/ou la fin des séquences (pour les séquences cycliques) [2].use_pruning : Élaguez les calculs basés sur la limite supérieure euclidienne. Si, en plus de la distance, vous souhaitez également que la matrice complète voie tous les chemins de déformation possibles :
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)
La matrice avec tous les chemins de déformation peut être visualisée comme suit :
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)
Notez le paramètre psi qui assouplit la correspondance au début et à la fin. Dans cet exemple, cela donne une correspondance parfaite même si les ondes sinusoïdales sont légèrement décalées.
Pour calculer les mesures de distance DTW entre toutes les séquences d'une liste de séquences, utilisez la méthode dtw.distance_matrix . Vous pouvez définir des variables pour utiliser plus ou moins de code C ( use_c et use_nogil ) et une exécution parallèle ou série ( parallel ).
La méthode distance_matrix attend une liste de listes/tableaux :
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)
ou une matrice (dans le cas où toutes les séries ont la même longueur) :
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)
Vous pouvez demander au calcul de remplir uniquement une partie de la matrice des mesures de distance. Par exemple pour répartir les calculs sur plusieurs nœuds, ou pour comparer uniquement les séries sources aux séries cibles.
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)))
Le résultat dans ce cas sera :
# 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
Une matrice de distance peut être utilisée pour le regroupement de séries chronologiques. Vous pouvez utiliser des méthodes existantes telles que scipy.cluster.hierarchy.linkage ou l'une des deux méthodes de clustering incluses (cette dernière est un wrapper pour la méthode de liaison SciPy).
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)
Pour les modèles qui assurent le suivi de l'arborescence de clustering complète ( HierarchicalTree ou LinkageTree ), l'arborescence peut être visualisée :
model.plot("myplot.png")
Facultatif:
Développement:
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.
