Project Icon

dtaidistance

快速时间序列距离计算库

dtaidistance是一个高效的时间序列距离计算Python库。它提供纯Python和优化的C实现,支持动态时间规整(DTW)等算法。该库与NumPy和Pandas兼容,避免了不必要的数据复制。支持多维时间序列、子序列搜索和聚类。dtaidistance为时间序列分析和机器学习提供了快速的距离计算工具,是处理时序数据的理想选择。

PyPi 版本 Conda 版本 文档状态 DOI

时间序列距离

这是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)

引用本工作:

Wannes Meert, Kilian Hendrickx, Toon Van Craenendonck, Pieter Robberechts, Hendrik Blockeel & Jesse Davis.
DTAIDistance (版本 v2). Zenodo.
http://doi.org/10.5281/zenodo.5901139

v2新特性

  • Numpy现在是可选依赖项,编译C库时也不再需要(只需要Cython)。
  • 对C代码进行了小幅优化以提高速度。
  • 一致使用ssize_t而非int,允许在64位机器上使用更大的数据结构,并与Numpy更兼容。
  • 并行化现在直接在C中实现(如果安装了OpenMP则包含)。
  • max_dist参数与Silva和Batista的PrunedDTW工作[7]类似。该工具箱现在实现了一个等同于PrunedDTW的版本,因为它修剪了更多的部分距离。此外,添加了use_pruning参数,可以自动将max_dist设置为欧几里得距离,如Silva和Batista所建议的那样,以加速计算(新方法ub_euclidean可用)。
  • C库中支持dtaidistance.dtw_ndim包中的多维序列。
  • 用于聚类的DTW重心平均(v2.2)。
  • 子序列搜索和局部并发(v2.3)。
  • 支持N维时间序列(v2.3.7)。

安装

$ pip install dtaidistance

$ conda install -c conda-forge dtaidistance

pip安装需要Numpy作为依赖项来编译与Numpy兼容的C代码(使用Cython)。但是,这个依赖项是可选的,可以移除。

源代码可在github.com/wannesm/dtaidistance获取。

如果在编译过程中遇到任何问题(例如,基于C的实现或OpenMP不可用),请参阅文档了解更多选项。

使用

动态时间规整(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)示例

两个序列之间的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,但需要数组作为输入(使用double类型),并且(可选)通过将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:基于欧几里得上界进行剪枝计算。

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 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 距离度量,请使用 dtw.distance_matrix 方法。 您可以设置变量以使用更多或更少的 C 代码(use_cuse_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 linkage方法的封装)。

from dtaidistance import clustering
# 自定义层次聚类
model1 = clustering.Hierarchical(dtw.distance_matrix_fast, {})
cluster_idx = model1.fit(series)
# 增强Hierarchical对象以跟踪完整树
model2 = clustering.HierarchicalTree(model1)
cluster_idx = model2.fit(series)
# SciPy linkage聚类
model3 = clustering.LinkageTree(dtw.distance_matrix_fast, {})
cluster_idx = model3.fit(series)

对于跟踪完整聚类树的模型(HierarchicalTreeLinkageTree),可以将树可视化:

model.plot("myplot.png")

动态时间规整(DTW)层次聚类

依赖

可选:

开发:

联系

参考文献

  1. T. K. Vintsyuk, 基于动态规划的语音识别。 Kibernetika, 4:81–88, 1968.
  2. H. Sakoe and S. Chiba, 用于口语识别的动态规划算法优化。 IEEE声学、语音和信号处理汇刊, 26(1):43–49, 1978.
  3. C. S. Myers and L. R. Rabiner, 几种动态时间规整算法在连续词识别中的比较研究。 贝尔系统技术期刊, 60(7):1389–1409, 1981年9月.
  4. Mueen, A and Keogh, E, 从动态时间规整中提取最优性能, 教程, KDD 2016
  5. D. F. Silva, G. E. A. P. A. Batista, and E. Keogh. 端点对动态时间规整的影响, SIGKDD时间序列挖掘与学习研讨会, II. 计算机协会-ACM, 2016.
  6. C. Yanping, K. Eamonn, H. Bing, B. Nurjahan, B. Anthony, M. Abdullah and B. Gustavo. [UCR时间序列分类档案](https://github.com/wannesm/dtaidistance/blob/master/www.cs.ucr.edu/~eamonn/time_series_data/, 2015.
  7. D. F. Silva and G. E. Batista. 加速全对动态时间规整矩阵计算, 2016年SIAM国际数据挖掘会议论文集, 837–845页. SIAM, 2016.

许可证

DTAI距离代码。

版权所有 2016-2022 KU Leuven, DTAI研究组

根据Apache许可证2.0版("许可证")授权;
除非遵守许可证,否则您不得使用此文件。
您可以在以下位置获取许可证副本:

    http://www.apache.org/licenses/LICENSE-2.0

除非适用法律要求或书面同意,否则根据许可证分发的软件是基于
"按原样"分发的,不附带任何明示或暗示的担保或条件。
有关许可证下的特定语言管理权限和限制,请参阅许可证。
项目侧边栏1项目侧边栏2
推荐项目
Project Cover

豆包MarsCode

豆包 MarsCode 是一款革命性的编程助手,通过AI技术提供代码补全、单测生成、代码解释和智能问答等功能,支持100+编程语言,与主流编辑器无缝集成,显著提升开发效率和代码质量。

Project Cover

AI写歌

Suno AI是一个革命性的AI音乐创作平台,能在短短30秒内帮助用户创作出一首完整的歌曲。无论是寻找创作灵感还是需要快速制作音乐,Suno AI都是音乐爱好者和专业人士的理想选择。

Project Cover

有言AI

有言平台提供一站式AIGC视频创作解决方案,通过智能技术简化视频制作流程。无论是企业宣传还是个人分享,有言都能帮助用户快速、轻松地制作出专业级别的视频内容。

Project Cover

Kimi

Kimi AI助手提供多语言对话支持,能够阅读和理解用户上传的文件内容,解析网页信息,并结合搜索结果为用户提供详尽的答案。无论是日常咨询还是专业问题,Kimi都能以友好、专业的方式提供帮助。

Project Cover

阿里绘蛙

绘蛙是阿里巴巴集团推出的革命性AI电商营销平台。利用尖端人工智能技术,为商家提供一键生成商品图和营销文案的服务,显著提升内容创作效率和营销效果。适用于淘宝、天猫等电商平台,让商品第一时间被种草。

Project Cover

吐司

探索Tensor.Art平台的独特AI模型,免费访问各种图像生成与AI训练工具,从Stable Diffusion等基础模型开始,轻松实现创新图像生成。体验前沿的AI技术,推动个人和企业的创新发展。

Project Cover

SubCat字幕猫

SubCat字幕猫APP是一款创新的视频播放器,它将改变您观看视频的方式!SubCat结合了先进的人工智能技术,为您提供即时视频字幕翻译,无论是本地视频还是网络流媒体,让您轻松享受各种语言的内容。

Project Cover

美间AI

美间AI创意设计平台,利用前沿AI技术,为设计师和营销人员提供一站式设计解决方案。从智能海报到3D效果图,再到文案生成,美间让创意设计更简单、更高效。

Project Cover

AIWritePaper论文写作

AIWritePaper论文写作是一站式AI论文写作辅助工具,简化了选题、文献检索至论文撰写的整个过程。通过简单设定,平台可快速生成高质量论文大纲和全文,配合图表、参考文献等一应俱全,同时提供开题报告和答辩PPT等增值服务,保障数据安全,有效提升写作效率和论文质量。

投诉举报邮箱: service@vectorlightyear.com
@2024 懂AI·鲁ICP备2024100362号-6·鲁公网安备37021002001498号