“UCR-DTW”和“UCR-ED”模型详解DTW（DynamicTimeWarping）和已知优化策略来计算两个时间序列之间的关系Q和C常用的测量方法是欧式距离（ED），计算公式如下图（1-1）：“UCR-DTW”和“UCR-ED”模型详解来自上图，我们可以看出欧氏距离的局限性：欧氏距离建立了两个序列之间的一一对应关系，使得Q和C之间的峰没有对齐，所以计算出的序列相似度存在较大偏差。DTW算法可以很好地解决这个问题。大多数时候，这两个序列总体上具有非常相似的形状，但形状在时间轴上并不对齐。因此，在计算两个序列之间的相似度之前，需要对其中一个（或两个）序列进行时间轴上的warping，从而使两个序列的峰能更好地对齐。DTW是实现这种翘曲的有效方法。也就是说，DTW算法是在两个序列之间寻找另一种非一对一的映射关系，也称为warpingpath。以上述Q和C为例，得到的对应关系如下图（1-2）灰色线段所示：DTW算法求解过程的直观理解就是构造一个nxn矩阵（这里，假设Q和C的时间序列的长度为n，矩阵中的元素(i,j)表示序列Q的时间点qi和序列Q的时间点cj之间的欧式距离sequenceC)目标是找到一条从(0,0)到(n,n)的路径，路径上所有元素的和最小。如下图（1-3）所示，红色标注的路径为warpingpath：目前已知的四种DTW顺序搜索的优化方法如下：去掉平方根计算，使用下界剪枝，因为下界的计算时间复杂度小于DTW的时间复杂度。例如：LBKimFLLBKimFL的时间复杂度为O(1)。在实现本文时，由于时间序列数据中的最大值和最小值在时间序列标准化后对整个下界距离的贡献较小，所以原来的LB_kim算法（时间复杂度为最大值和最小值）在O(n)中提取的四个特征点，使得时间复杂度降低到O(1)。但是，为了在实现中最大限度地发挥这种策略的效果，作者还提取了第2、第3和倒数第2个,级联修剪的第三个时间点。（具体可参考算法实现lb_kim_hierarchy方法）基于该优化策略，作者提出的Reorderearlyabandoning可以进一步降低计算成本。即在计算ED或LBKeoghLBKeogh时，如果两个当前序列的时间点(1,k)(注：k<=|Q|)之差的平方和大于最小距离两个当前序列best-so-far，则可以提前结束Q和C是否相似的判断。计算过程如下图（1-4）所示：4.EarlyAbandoningofDTW计算LBKeogh的完整LBKeogh值，还需要计算完整的DTW值。我们可以通过使用部分LBKeoghLBKeogh值来减少DTW的计算量。比如先从左到右计算时间点[1,k]的DTW值，然后在时间点[k+1,n]复用之前计算的LBKeogh。最终的距离值仍然是完整DTW值的下界。这样，我们就可以使用提前停止策略。每次计算当前时间点的DTW值，我们可以复用之前计算的LBKeoghLBKeogh，得到整个子序列的下界值。通过将该下界与当前best-so-far的最小距离值进行比较，如果当前下界值大于best-so-far，则可以提前结束DTW的计算。这种方法的直观表示如下（1-5）：上面详细解释了“UCR-DTW”和“UCR-ED”模型，前面介绍了DTW的四种优化方案。还有一个已知的提高DTW计算速度的策略，就是使用多核计算资源。UCRSuite的优化??策略相关概念和定义定义1：时间序列T是一个有序列表：T=t1,t2,?,tm。然而，源数据是一个很长的时间序列，我们最终需要将它与更短的子序列进行相似性比较。定义2：子序列Ti,k是时间序列T中的一个从ti开始，长度为k的子序列，即：Ti,k=ti,ti+1,...,ti+k?1，1≤i≤m?k+1。这里，我们将Ti，kTi，k表示为C，作为类似于查询Q的候选子序列。令Q的长度为|Q|=n。定义3：Q与C的欧式距离(|Q|=|C|)定义为(公式1)：路径P的第t个元素定义为pt=(i,j)tpt=(i,j)t，那么我们可以将warpingpath表示为（公式2）：P=p1,p2,?,pt,?,pT,n≤T≤2n?1优化策略：1.EarlyAbandoningZ-normalization是计算DTWdistance之前Q和C都需要标准化，但是标准化整个数据集的复杂度太高，所以这里使用在线Z-normalization，这样可以使用earlystopstrategy来结束normalization的计算进步。首先，计算序列C的均值和方差的公式如下（公式3）：当使用在线Z归一化时，当前遍历到源序列T中的第k个时间点，计算时间的累加和点元素和时间点元素的平方和的累积和表示为（公式4）：那么k-m+1到k之间的m个时间点对应的均值和方差的计算公式如下（公式4）5）因此，基于在线Z-normalization的abandonnormalizationearlystrategy的伪代码如下图（1-7）所示：论文中作者提到浮点计算存在累加问题错误。这里，每比较完100万个子序列后，就进行一次完整的Z-normalization，消除误差累积的问题。Reorder提前放弃前面的提前放弃策略的计算方法是从子序列的第一个时间点开始，从左到右计算。本文提出一种策略，快速找到Q和C的差和最大的子序列，然后据此判断该子序列是否大于best-so-far值，以降低计算成本。这两个订单的计算成本对比如下图（1-8）所示：“UCR-DTW”和“UCR-ED”模型详解左图为从左到右依次计算差值，和计算需要9小时可以通过Steps来判断是否提前结束，右图找到新的计算序列。此时判断是否提前结束只需要5个时间步。那么，现在的问题就变成了，如何找到这些差值之和最大的子序列呢？这里有个问题，找到的子序列是连续的吗？通过阅读源码可以看出，子序列不一定是连续的。本文的做法是先对Z归一化处理后的Q序列各时间点元素的绝对值进行排序。其理论依据是，在进行DTW获取序列间距离时，qi可以对应序列C中的多个时间点。z归一化后的C序列服从高斯分布，即均值为0。因此，离均值0最远的qiqi对距离值的贡献最大，所以对z-归一化的Q序列的绝对值进行排序，这样可以很快得到差值和最大的子序列。作者通过实验证明，这样找到计算顺序与真正的最佳计算顺序的相关性为0.999。在LBKeogh中反转查询/数据角色LBKeogh基于Q，并使用LBKeoghEQLBKeoghEQ进行剪枝。这里对于Q只需要计算一次U和L，可以节省大量的时间和空间开销；如果全部使用LBKeoghECLBKeoghEC进行剪枝，基于每个AC，计算U和L，会增加很多计算成本。因此，LBKeoghECLBKeoghEC策略是可选的。只有当LBKeoghEQLBKeoghEQ剪枝效果不理想时，才可以采用“即时”策略，使用LBKeoghECLBKeoghEC辅助LBKeoghEQLBKeoghEQ提高剪枝效率，从而大大降低空间开销。对于LBKeoghECLBKeoghEC的时间开销，可以通过剪枝来抵消，减少完整DTW的时间开销。两种计算策略的直观理解如下图（1-9）所示：“UCR-DTW”和“UCR-ED”模型详解Usecascadinglowerbounds目前有很多下界计算方法。每个下界都可以用来修剪DTW并且可以估计时间复杂度。到目前为止，至少有18个下限机制。作者都实现了，然后在50个不同的数据集上进行了测试比较。结果如下图（1-10）所示：根据上面的实验结果，作者通过级联各种下界方法对ED和DTW进行剪枝：首先使用LBKimFLLBKimFL，时间复杂度为O(1)，可以过滤掉很多候选子序列，然后，基于Q，使用LBKeoghEQLBKeoghEQ进行剪枝。如果LBKeoghEQLBKeoghEQ剪枝效果不理想，使用LBKeoghECLBKeoghEC辅助LBKeoghEQLBKeoghEQ提高剪枝效率。最后，如果以上所有的剪枝策略都失败了，你仍然可以通过提前放弃来计算出完整的DTW实验证明，上面使用的每一种下界策略都有助于提高DTW的速度，移除任何下界策略都会使搜索速度翻倍。在大规模搜索中，上述剪枝策略可以节省DTW算法99.9999%的时间开销。在实验结果分析论文中，对以下实现的性能进行了比较分析：朴素：每个子序列从零到z归一化。每一步都使用完整的欧氏距离或DTW。（大约2/3的文章都是基于这个思路来计算相似度）State-of-the-art：目前最好的模型是基于Z-normalization，earlyabandoning和使用lowerbound辅助完成DTW计算。战略来实现。（大约1/3的文章是基于这个思路计算相似度的）UCRSuiteGOd的算法（GOAL）直接根据均值和方差比较计算相似度，时间复杂度为O(1)GOAL模型相当于A解决未知长度的无限制序列搜索问题的所有最快模型的基线模型。对比实验中使用的四款机型均使用了UCRSuite的代码，不同之处在于将对应的加速代码注释掉了。基于随机生成数据集的实验结果对比从上图可以看出，对于一个长度为128的query，SOFA和UCRSuite算法集的性能差异非常大。不同长度查询的实验对比接下来我们看一下这些模型对于不同长度查询的性能对比：实施UCR-ED应用程序是：EarlyAbandoningofEDReorderearlyabandoningimportimporttimeimportmathclassUCR_ED(object):def__init__(self,input_file,query_file,m=128):self.fp=open(input_file,'r')self.qp=open(query_file,'r')self.m=m#query的长度self.Q=[None]*self.m#queryarrayself.T=[0.0](self.m2)#arrayofcurrentdataself.order=[]#查询顺序|z(q_i)|self.bsf=float('inf')self.loc=0#answer:迄今为止最佳匹配的位置self.ex,self。ex2,self.mean,self.std=0.0,0.0,0.0,0.0#用于统计运行时间self.t1=time.time()self.t2=0.0self.Q_normalize()#对查询数据进行排序self.sort_query_order()#readdatafile,onevalueatatimeex=0.0ex2=0.0i=0whileTrue:try:line=self.line_to_float(next(self.fp))ex+=lineex2+=line*lineself.T[i%m]=lineself.T[(i%m)+m]=lineexcept:break#如果有足够的数据inT,EDdistancecanbecalculatedifi>=m-1:#T的当前起始位置j=(i+1)%m#Z-norm(T[i])willbecalculatedontheflymean=ex/self.mstd=ex2/self.mstd=math.sqrt(std-mean*mean)#计算ED距离dist=self.distance(self.Q,self.T,j,self.m,mean,std,self.order,self.bsf)如果dist
