时间经线编辑距离

时间翘曲编辑距离（TWED）是一种具有时间"弹性"的离散时间序列匹配的相似性（或不相似性）的测量。与其他距离测量方法相比，（如DTW（动态时间扭曲）或LCS（最长共同子序列问题）），TWED是一个度量。它的计算时间复杂度是，但在某些特定情况下，通过使用走廊来减少搜索空间，可以大幅减少。其内存空间复杂度可以降低到.它是由P.-F.Marteau在2009年首次提出的。Marteau首次提出。{displaystyledelta_{lambda,nu}}初始化为{displaystylea'_{0}=b'_{0}=0}实现TWED算法的C语言实现和Python包装器可在以下网站找到TWED也在时间序列后续搜索Python包（简称TSSEARCH）中实现，见[1]。TWED的R实现已被整合到TraMineR中，TraMineR是一个用于挖掘、描述和可视化状态或事件序列的R包，以及更普遍的离散序列数据。此外，cuTWED是一个CUDA加速实现的TWED，它使用了G.Wright（2020）的改进算法。cuTWED是用CUDAC/C++编写的，带有Python绑定，还包括Marteau的参考C实现的Python绑定。Python导入numpy作为npdefdlp(A,B,p=2):cost=np.sum(np.power(np.abs(A-B),p))returnnp.power(cost,1/p)deftwed(A,timeSA,B,timeSB,nu,_lambda):#

[distance,DP]=TWED(A,timeSA,B,timeSB,lambda,nu)#计算给定时间序列A和B的时间扭曲编辑距离(TWED)#A:=时间序列A(例如：[102304])#timeSA:=时间序列A的时间戳(例如：1：4)g.1:4)#B:=时间序列B#timeSB:=时间序列B的时间戳#lambda:=删除操作的惩罚#nu:=弹性参数-距离测量需要nu>=0#参考文献：#Marteau,P.;F.(2009)."时间序列匹配的刚度调整的时间扭曲编辑距离"。#IEEE模式分析和机器智能的交易。31(2):306-318.arXiv:cs/0703033#http://people.irisa.fr/Pierre-Francois.Marteau/

如果len(A)!=len(timeSA):print("A的长度不等于timeSA的长度")returnNone,None如果len(B)!=len(timeSB):print("B的长度不等于timeSB的长度")返回None,None#初始化DP矩阵，将xxx行和xxx列设置为无穷大DP[0,:]=np.infDP[:,0]=np.infDP[0,0]=0#计算r中i的最小成本