DTW(动态时间扭曲)和已知的优化策略
计算两个时间序列Q和C的相似度，常用的度量方法是欧氏距离(ed)，计算公式如下图(1-1):
从上图可以看出欧氏距离的局限性:欧氏距离通过在两个序列之间建立一对一的对应关系，使Q和C之间的峰发生错位，因此计算出的序列相似度存在较大偏差。DTW算法可以很好地解决这个问题。
在大多数情况下，这两个序列作为一个整体具有非常相似的形状，但是这些形状在时间轴上没有对齐。因此，在计算两个序列之间的相似性之前，需要对一个(或两个)序列在时间轴上进行扭曲，以便两个序列的峰值能够更好地对齐。
DTW是实现这种翘曲的有效方法。换句话说，DTW算法在两个序列之间找到了另一种非一一对应的映射关系，也称为扭曲路径。以上面的q和c为例，对应关系用下图(1-2)中的灰色线段表示:
DTW算法求解过程的直观理解是构造一个nxn的矩阵(这里假设q和c的时间序列长度都是n，矩阵中的元素(I，j)表示序列q的时间点qi和序列c的时间点cj之间的欧氏距离)。目标是在矩阵中找到一条从(0，0)到(n，n)的路径，使路径上所有元素的和最小。
如下图(1-3)所示，红色标记的路径就是翘曲路径:
欧式距离相当于DTW的特例，对应的warping path为从矩阵左下角到右上角的对角线。目前，DTW序贯搜索的四种已知优化方法如下:
去掉平方根计算通过使用lower bounds来剪枝，因为lower bounds的计算时间复杂度都小于DTW的时间复杂度。比如：LBKimFLLBKimFL的时间复杂度为O(1)本文在实现时，由于对时间序列进行标准化后，时间序列数据中的最大和最小值对于整个lower bound距离贡献较小，因此，去掉原来LB_kim算法(时间复杂度为O(n))中提取的四个特征点中的最大值和最小值，使得时间复杂度降为O(1)。但是，实现中为了使此策略发挥最大作用，作者还提取了第2,3和倒数第2,3个时间点，来进行级联剪枝。(详情参考算法实现lb_kim_hierarchy方法)LBKeoghLBKeogh的时间复杂度为O(n)Early Abandoning of ED and LBKeoghLBKeogh基于这条优化策略，作者提出的Reorder early abandoning可以进一步降低计算成本。即在计算ED或LBKeoghLBKeogh时，如果当前两个序列的时间点(1，k)(注:k
4.早期抛弃DTW
为了计算完整的LBKeoghLBKeogh值，我们仍然需要计算完整的DTW值。我们可以通过使用一些LBKeoghLBKeogh值来减少DTW计算量。
例如，首先从左到右计算时间点[1，k]处的DTW值，然后重用计算出的时间点[k+1，n]处的LBKeoghLBKeogh值。最终距离值仍然是完整DTW值的下限。这样就可以使用提前停止策略，每次计算当前时间点的DTW值时，都可以重用之前计算的LBKeoghLBKeogh，得到整个子序列的下界值。
将该下限与目前为止最好的最小距离值进行比较，如果目前的下限大于目前为止最好的，则可以提前结束DTW计算。
这种方式的可视化表示如下(1-5):
以上，介绍了DTW的四种优化方案。
还有一个已知的提高DTW计算速度的策略，就是使用多核计算资源。
UCR套房的优化策略
相关概念和定义
定义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 | Q | = n n。
定义3:
Q和C之间的欧氏距离(|Q|=|C|)定义为(公式1):
路径p的第t个元素定义为pt=(i，j)tpt=(i，j)t，因此我们可以将翘曲路径表示为(公式2):
P=p1,p2,⋯,pt,⋯,pT,n≤T≤2n−1
优化策略:
1.早期放弃Z-规范化
在计算DTW距离之前需要对Q和C进行标准化，但是对整个数据集进行标准化的复杂度太高，所以这里采用在线Z-归一化，可以采用早停策略提前结束归一化计算。
序列c的均值和方差的计算公式如下(公式3):
使用在线Z-归一化时，目前遍历源序列t中的第k个时间点，计算出的时间点元素累计和与时间点元素平方累计和表示为(公式4):
那么k-m+1和k之间的这m个时间点对应的均值和方差的计算公式如下(公式5)
因此，基于在线Z-规格化的放弃规格化早期策略的伪代码如下图(1-7):
在本文中，作者提到了浮点计算中存在的误差积累问题。在这里，每次比较一百万个子序列时，都会执行一次完整的Z-归一化，从而消除了误差累积的问题。
Reorder early abandoning以前的弃早策略的计算方法是从子序列的第一个时间点开始，从左到右。本文提出的一种策略是快速找到Q和C差之和最大的子序列，然后根据它判断这个子序列是否大于目前为止最好的值，从而降低计算成本。这两个序列的计算成本对如下图(1-8)所示:
左图表示从左到右的顺序计算差值，它需要计算9个时间步才能判断是否提前结束，而右图找到一个新的计算顺序，这时候只需要计算5个时间步就能判断是否提前结束。那么，现在的问题就变成了，如何找到这些差值之和最大的子序列？这里有一个疑问，找到的这些子序列是否是连续的？通过阅读源码，可知子序列不一定是连续的。本文中的做法是，首先对被Z-normalization 处理过的Q序列所有时间点元素的绝对值进行排序，这样做的理论依据是，在进行DTW获取序列之间的距离时，qi可以对应多个序列C中的时间点。进行z-normalization后的C序列服从高斯分布，意味着均值为0，因此，距离均值0最远的qiqi对距离值贡献最大，因此对z-normalizated Q序列的绝对值进行排序，从而可以快速差值之和最大的子序列。作者通过实验证明，使用这样的方式找到计算顺序与真实的最好计算顺序的相关度为0.999。Reversing the query/data role in LBKeoghLBKeogh基于Q，使用LBKeoghEQLBKeoghEQ来进行剪枝，这里只需要对Q计算一次的U和L，从而可以节省很多时间和空间开销；如果全部采用LBKeoghECLBKeoghEC来进行剪枝，基于每一个C，计算U和L，那么会增加很多的计算成本。因此，LBKeoghECLBKeoghEC策略是可选项，只有当LBKeoghEQLBKeoghEQ剪枝效果不太理想的时候，可以“just-in-time” 的策略来使用LBKeoghECLBKeoghEC来辅助LBKeoghEQLBKeoghEQ提高剪枝效率，从而大大降低空间开销。对于LBKeoghECLBKeoghEC的时间开销，可以通过剪枝来降低完整DTW的时间开销来抵消掉。对两种计算策略的直观理解如下图(1-9)所示:
实验结果分析
本文对以下实现的性能进行了比较和分析:
Naive:每个子序列都是从零开始归一化z的。每一步都使用完整的欧氏距离或DTW。(大约有2/3的文章是基于这种思想来进行相似度计算的)State-of-the-art: 当前最好的模型基于Z-normalization,early abandoning以及使用lower bound来辅助完整DTW计算这些策略来实现的。(大约有1/3的文章基于这种思想来进行相似度计算的)UCR SuiteGOd’s ALgorithm (GOAL) 直接基于均值、方差来进行比较计算相似度的，时间复杂度为O(1)GOAL模型相当于所有解决长度未知无限制的序列搜索问题的最快模型的一个baseline model。对比实验中用到的四个模型都使用了UCR Suite代码，模型之间唯一的区别就是标注了对应的加速代码。
基于随机生成数据集的实验结果比较
从上图可以看出，对于128长度的查询，SOFA和UCR Suite算法集的性能差别很大。
不同长度查询的实验比较
接下来，查看这些模型对于不同长度查询的性能比较:
UCR-DTW python实现
UCR-DTW应用了上述所有优化策略
GitHub:ucr-suite-python
UCR-埃德python实现
UCR-埃德应用的优化策略如下:
Early Abandoning of EDReorder early abandoning参考数据
Searching and mining trillions -blog时间序列的搜索DTW(Dynamic Time Warping)动态时间规整Time Series Classification and Clustering1.《dtw “UCR-DTW”和“UCR-ED”模型详解》援引自互联网，旨在传递更多网络信息知识，仅代表作者本人观点，与本网站无关，侵删请联系页脚下方联系方式。
2.《dtw “UCR-DTW”和“UCR-ED”模型详解》仅供读者参考，本网站未对该内容进行证实，对其原创性、真实性、完整性、及时性不作任何保证。
3.文章转载时请保留本站内容来源地址，https://www.lu-xu.com/guonei/1079573.html
