R语言DTW(Dynamic Time Warping) 动态时间规整算法分析序列数据和可视化

简介: R语言DTW(Dynamic Time Warping) 动态时间规整算法分析序列数据和可视化

动态时间规整(DTW,Dynamic time warping,动态时间归整/规整/弯曲)是一种衡量两个序列之间最佳排列的算法。线性序列数据如时间序列、音频、视频都可以用这种方法进行分析。DTW通过局部拉伸和压缩,找出两个数字序列数据的最佳匹配,同时也可以计算这些序列之间的距离。

DTW是干什么的?

动态时间规整算法,故名思议,就是把两个代表同一个类型的事物的不同长度序列进行时间上的“对齐”。比如DTW最常用的地方,语音识别中,同一个字母,由不同人发音,长短肯定不一样,把声音记录下来以后,它的信号肯定是很相似的,只是在时间上不太对整齐而已。所以我们需要用一个函数拉长或者缩短其中一个信号,使得它们之间的误差达到最小。

DTW怎么计算?

因此,动态时间规整要解决的问题就是:找到一条最优的规整路径 W = {\varpi \_1},{\varpi \_2}...{\varpi \_k} W=ϖ1,ϖ2...ϖk,其中 {w\_k} = (i,j) wk=(i,j),即认为时间序列1的第i个点和时间序列2的第j个点是类似的。全部类似点的距离之和做为规整路径距离,用规整路径距离来衡量两个时间序列的类似性。规整路径距离越小,类似度越高。

下面我们来总结一下DTW动态时间规整算法的简单的步骤:

1. 首先肯定是已知两个或者多个序列,但是都是两个两个的比较,所以我们假设有两个序列A={a1,a2,a3,...,am}  B={b1,b2,b3,....,bn},维度m>n

2. 然后用欧式距离计算出每序列的每两点之间的距离,D(ai,bj) 其中1≤i≤m,1≤j≤n

画出下表:

3.  接下来就是根据上图将最短路径找出来。从D(a1,a2)沿着某条路径到达D(am,bn)。找路径满足:假如当前节点是D(ai,bj),那么下一个节点必须是在D(i+1,j),D(i,j+1),D(i+1,j+1)之间选择,并且路径必须是最短的。计算的时候是按照动态规划的思想计算,也就是说在计算到达第(i,j)个节点的最短路径时候,考虑的是左上角也即第(i-1,j)、(i-1,j-1)、(i,j-1)这三个点到(i,j)的最短距离。

4. 接下来从最终的最短距离往回找到那条最佳的输出路径, 从D(a1,b1)到D(am,bn)。他们的总和就是就是所需要的DTW距离

【注】如果不回溯路径,直接在第3步的时候将左上角三个节点到下一个节点最短的点作为最优路径节点,就是贪婪算法了。DTW是先计算起点到终点的最小值,然后从这个最小值回溯回去看看这个最小值都经过了哪些节点。

R语言实现

在这篇文章中,我们将学习如何找到两个数字序列数据的排列。

创建序列数据

首先,我们生成序列数据,并在一个图中将其可视化。

plot(a, type = "l")
lines(b, col = "blue")

计算规整方式

dtw()函数计算出一个最佳规整方式。

align(a, b)

返回以下项目。你可以参考str()函数来了解更多信息。

现在,我们可以绘制组合。

用双向的方法作图

动态时间规整结果的绘图:点比较

显示查询和参考时间序列以及它们的排列方式,进行可视化检查。

Plot(align)

用密度作图

显示叠加了规整路径的累积成本密度 。

该图是基于累积成本矩阵的。它将最优路径显示为全局成本密度图中的 "山脊"。

PlotDensity(align)

小结

总而言之, DTW是一种非常有用的计算序列最小距离的方法, 不论是在语音序列匹配, 股市交易曲线匹配, 还是DNA碱基序列匹配等等场景, 都有其大展身手的地方. 它的最大特点是在匹配时允许时间上的伸缩, 因此可以更好的在一堆序列集合中找到最佳匹配的序列.

  1. Eamonn Keogh, Chotirat Ann Ratanamahatana, Exact indexing of dynamic time warping, Knowledge and Information Systems, 2005.

相关文章
|
4天前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
12天前
|
机器学习/深度学习 人工智能 算法
"拥抱AI规模化浪潮:从数据到算法,解锁未来无限可能,你准备好迎接这场技术革命了吗?"
【10月更文挑战第14天】本文探讨了AI规模化的重要性和挑战,涵盖数据、算法、算力和应用场景等方面。通过使用Python和TensorFlow的示例代码,展示了如何训练并应用一个基本的AI模型进行图像分类,强调了AI规模化在各行业的广泛应用前景。
23 5
|
3天前
|
存储 JSON 算法
TDengine 检测数据最佳压缩算法工具,助你一键找出最优压缩方案
在使用 TDengine 存储时序数据时,压缩数据以节省磁盘空间是至关重要的。TDengine 支持用户根据自身数据特性灵活指定压缩算法,从而实现更高效的存储。然而,如何选择最合适的压缩算法,才能最大限度地降低存储开销?为了解决这一问题,我们特别推出了一个实用工具,帮助用户快速判断并选择最适合其数据特征的压缩算法。
12 0
|
11天前
|
算法
PID算法原理分析
【10月更文挑战第12天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
20 0
|
13天前
|
人工智能 算法 前端开发
无界批发零售定义及无界AI算法,打破传统壁垒,累积数据流量
“无界批发与零售”是一种结合了批发与零售的商业模式,通过后端逻辑、数据库设计和前端用户界面实现。该模式支持用户注册、登录、商品管理、订单处理、批发与零售功能,并根据用户行为计算信用等级,确保交易安全与高效。
|
13天前
|
前端开发 算法 JavaScript
无界SaaS模式深度解析:算力算法、链接力、数据确权制度
私域电商的无界SaaS模式涉及后端开发、前端开发、数据库设计、API接口、区块链技术、支付和身份验证系统等多个技术领域。本文通过简化框架和示例代码,指导如何将核心功能转化为技术实现,涵盖用户管理、企业店铺管理、数据流量管理等关键环节。
|
17天前
|
算法
PID算法原理分析及优化
【10月更文挑战第6天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
23 0
|
2月前
|
数据采集 机器学习/深度学习 数据可视化
R语言从数据到决策:R语言在商业分析中的实践
【9月更文挑战第1天】R语言在商业分析中的应用广泛而深入,从数据收集、预处理、分析到预测模型构建和决策支持,R语言都提供了强大的工具和功能。通过学习和掌握R语言在商业分析中的实践应用,我们可以更好地利用数据驱动企业决策,提升企业的竞争力和盈利能力。未来,随着大数据和人工智能技术的不断发展,R语言在商业分析领域的应用将更加广泛和深入,为企业带来更多的机遇和挑战。
|
5天前
|
数据挖掘 C语言 C++
R语言是一种强大的统计分析工具,提供了丰富的函数和包用于时间序列分析。
【10月更文挑战第21天】时间序列分析是一种重要的数据分析方法,广泛应用于经济学、金融学、气象学、生态学等领域。R语言是一种强大的统计分析工具,提供了丰富的函数和包用于时间序列分析。本文将介绍使用R语言进行时间序列分析的基本概念、方法和实例,帮助读者掌握R语言在时间序列分析中的应用。
19 3
|
6月前
|
数据可视化 数据挖掘 API
【R语言实战】聚类分析及可视化
【R语言实战】聚类分析及可视化