时间序列的距离测度
dtaidistance的Python项目详细描述
时间序列距离
用于DTAI Research Group中的时间序列距离(例如动态时间扭曲)的库。 库提供纯python实现和更快的c实现。
文档:http://dtaidistance.readthedocs.io
安装
此软件包在pypi上可用(需要python 3):
$ pip install dtaidistance
如果基于C的版本不可用,请参阅文档以了解其他安装选项。
如果系统上没有openmp,请添加--noopenmp
全局选项。
源代码可以在github.com/wannesm/dtaidistance找到。
用法
动态时间扭曲(DTW)距离测量
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")
两个系列之间的DTW距离测量
只有基于两个数字序列的距离测量:
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,但需要一个数组作为输入(使用双类型):
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)
或者可以使用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)
有关可用参数的信息,请检查__doc__
:
print(dtw.distance.__doc__)
许多选项可以提前终止动态规划算法正在探索或调整的某些路径 距离测量计算:
window
:只允许从两条对角线移动到这个数量。max_dist
:如果返回的距离测量值大于此值,则停止。max_step
:不允许步数大于此值。max_length_diff
:如果两个序列的长度相差较大,则返回无穷大。penalty
:如果应用压缩或扩展(在距离的顶部),则添加惩罚。psi
:忽略序列开始和/或结束的psi松弛(对于循环序列)[2]。
DTW距离测量所有扭曲路径
如果在距离旁边,还希望完整矩阵看到所有可能的扭曲路径:
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 numpy as np
x = np.arange(0, 20, .5)
s1 = np.sin(x)
s2 = np.sin(x - 1)
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距离度量,请使用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)
系列之间的DTW距离测量,仅限于块
可以指示计算仅填充部分距离度量矩阵。 例如,将计算分布到多个节点上,或仅 比较源序列和目标序列。
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")
依赖关系
可选:
开发:
联系人
参考文献
- T.K.Vintsuk, 动态规划的语音识别。 基伯内蒂卡,4:81–88,1968年。
- Sakoe和S.Chiba, 语音识别的动态规划算法优化。 ieee声学、语音和信号处理汇刊,26(1):43-491978年。
- 迈尔斯和拉宾, 连通词识别中几种动态时间规整算法的比较研究。 贝尔系统技术期刊,60(7):1389-14091981年9月。
- 穆恩,A和基奥,E, Extracting Optimal Performance from Dynamic Time Warping, 教程,KDD 2016
- D.F.Silva,G.E.A.P.A.Batista和E.Keogh。 On the effect of endpoints on dynamic time warping, 在SIGKDD关于从时间序列中挖掘和学习的研讨会上,2。计算机械协会ACM,2016年。
- C.Yanping,K.Eamonn,H.Bing,B.Nurjahan,B.Anthony,M.Abdullah和B.Gustavo。 The UCR Time Series Classification Archive,2015年。
许可证
DTAI distance code.
Copyright 2016-2019 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.