dtaidistance
v2.3.10
Библиотека расстояний временных рядов (например, динамическое искажение времени), используемая в исследовательской группе DTAI. Библиотека предлагает чистую реализацию Python и быструю реализацию на C. Реализация C имеет в качестве зависимости только Cython. Он совместим с Numpy и Pandas и реализован таким образом, чтобы избежать ненужных операций копирования данных.
Документация: http://dtaidistance.readthedocs.io.
Пример:
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)
Ссылаясь на эту работу:
Ваннес Меерт, Килиан Хендрикс, Тун Ван Краенендонк, Питер Робберехтс, Хендрик Блокил и Джесси Дэвис.
DTAIDistance (Версия v2). Зенодо.
http://doi.org/10.5281/zenodo.5901139
Новое в версии 2 :
ssize_t вместо int позволяет использовать более крупные структуры данных на 64-битных машинах и быть более совместимым с Numpy.max_dist оказался похож на работу Сильвы и Батисты над PrunedDTW [7]. В наборе инструментов теперь реализована версия, равная PrunedDTW, поскольку она сокращает больше частичных расстояний. Кроме того, добавляется аргумент use_pruning для автоматической установки max_dist на евклидово расстояние, как предложили Сильва и Батиста, чтобы ускорить вычисления (доступен новый метод ub_euclidean ).dtaidistance.dtw_ndim . $ pip install dtaidistance
или
$ conda install -c conda-forge dtaidistance
Для установки pip требуется Numpy в качестве зависимости для компиляции кода C, совместимого с Numpy (с использованием Cython). Однако эта зависимость необязательна и ее можно удалить.
Исходный код доступен по адресу github.com/wannesm/dtaidistance.
Если у вас возникнут какие-либо проблемы во время компиляции (например, реализация на основе C или OpenMP недоступна), дополнительные параметры см. в документации.
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")
Только мера расстояния основана на двух последовательностях чисел:
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)
Самая быстрая версия (30-300 раз) использует c напрямую, но требует массив в качестве входных данных (с двойным типом) и (необязательно) также сокращает вычисления, устанавливая max_dist равным евклидовой верхней границе:
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)
Или вы можете использовать массив numpy (с dtype double или 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)
Проверьте __doc__ для получения информации о доступных аргументах:
print(dtw.distance.__doc__)
Предусмотрен ряд опций для ранней остановки некоторых путей, которые исследует алгоритм динамического программирования, или настройки вычисления меры расстояния:
window : разрешается сдвиг только на эту величину от двух диагоналей.max_dist : Остановиться, если возвращаемая мера расстояния будет больше этого значения.max_step : не разрешать шаги, превышающие это значение.max_length_diff : Возвращает бесконечность, если разница в длине двух серий больше.penalty : штраф, добавляемый в случае применения сжатия или расширения (сверх расстояния).psi : Psi-релаксация для игнорирования начала и/или конца последовательности (для циклических последовательностей) [2].use_pruning : Сокращает вычисления на основе евклидовой верхней границы. Если помимо расстояния вы также хотите, чтобы полная матрица видела все возможные пути деформации:
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)
Матрицу со всеми путями деформации можно визуализировать следующим образом:
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)
Обратите внимание на параметр psi , который ослабляет соответствие в начале и конце. В этом примере это приводит к идеальному совпадению, даже несмотря на то, что синусоидальные волны слегка смещены.
Чтобы вычислить меры расстояния DTW между всеми последовательностями в списке последовательностей, используйте метод dtw.distance_matrix . Вы можете установить переменные для использования большего или меньшего количества кода C ( use_c и use_nogil ) и параллельного или последовательного выполнения ( parallel ).
Метод distance_matrix ожидает список списков/массивов:
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)
или матрица (в случае, если все серии имеют одинаковую длину):
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)
Вы можете указать вычислению заполнить только часть матрицы мер расстояний. Например, чтобы распределить вычисления по нескольким узлам или сравнивать только исходные серии с целевыми сериями.
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)))
Результатом в этом случае будет:
# 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
Матрицу расстояний можно использовать для кластеризации временных рядов. Вы можете использовать существующие методы, такие как scipy.cluster.hierarchy.linkage , или один из двух включенных методов кластеризации (последний является оболочкой для метода связывания 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)
Для моделей, которые отслеживают полное дерево кластеризации ( HierarchicalTree или LinkageTree ), дерево можно визуализировать:
model.plot("myplot.png")
Необязательный:
Разработка:
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.
