在介绍DTW的相似度计算之前，我们可以先说说一个更基础也更简单的时间序列相似度计算方法: Euclidean Distance。通过下图，我们可以看到一个时间序列Q和一个时间序列C，这两个时间序列的长度都是N。那么ED的计算方法就是在每个时间段将Q的值减去C的值，再把这些值加起来。比方说在第i个时间点，用Qi - Ci，我们将会得到每个时间段对应的Di，然后我们把从i=1到i=N的Di都算出来然后相加，得到的就是这两个时间序列之间的总距离D，总距离越大，这两个时间序列的相似度就越小。当然，我们往往不是单纯相减，因为会有正负的问题会相互抵消，所以我们会用平方距离或者用绝对值，公式如下：
2.2 Dynamic Time Warping (DTW)
接下来我们来介绍DTW，在介绍DTW之前我们需要说明一下，其实我们在对比两个时间序列的时候，这两个时间序列的长度不一定是相同的，比方说你喝醉酒之后说“我要开门”就很有可能比清醒的时候说语速要慢很多，所以一个时间序列的长度是n，一个时间序列的长度可能是m。因此，DTW里我们也不需要将Q和C完全一一对应，DTW求的是最匹配的Q和C之间的距离，而定义最匹配也就到这个时间段为止哪个C和Q对应的总距离最短，那么就是这个Q和这个C对应。也就是说某个时间段的Qi可能完全没有与之匹配的Ci(如"喝醉的时候发出奇怪的噪音，不需要匹配“），而某个时间段的Qi可能匹配3个Ci（如“喝醉的时候发‘我’的音拖了3个时间段“）。以上只是让你大概了解一下背后的intuition，我们可以正式的介绍了，请看下图。
2.2.1 Dynamic Programming Implementation
首先，我们如上图右建立一个Matrix(我们称该Matrix为"DA")，y轴是时间序列Q，长度是N，x轴是时间序列C，长度是M，因此是个NxM的matrix。这个matrix上的左下角就是Q的第一个时间段的值，Q(1)，和C的第一个时间段的值，C(1)，的绝对差。而右上角的点是Q的最后一个时间段的值，Q(N)，和C的最后一个时间段的值，C(M)，的绝对差。DTW就是需要求从左下角的起点到右上角的终点，如何匹配才能让总距离最短(注意：Q的起点需要匹配C的起点，Q的终点需要匹配C的终点，其余的点由匹配程度确定)，也就是找到一条从起点到终点的使总距离最短的‘路径‘。
如果你觉得有点难理解的话，没有关系，我们现在先一起把Matrix填满：
从上图我们可以看出，Matrix左边第一列填满的方式为：|R(i) - V(j)| + DA[i-1, 0]，这是什么意思呢？举个例子，如果我们看标记出来的红色框内的一个值20，这个值代表的是，如果“R”时间序列(Y轴)的第5个时间段的值R(4) 和“V“时间序列(X轴)的第一个时间段的值V(0)匹配的话【注：index从0开始】，那么截止到目前的最短总距离该会是多少？也就是说不仅仅要求这两个点之间的距离（8-1=7），还要加上之前的匹配所计算出来的最短总距离，而我们很显然之前匹配出来的最短总距离DA[3, 0]是13(也就是下方的格子)，那就是7+13 =20。
同理，如果你看红色框选出来的另一个值11，这个值对应的是“R”时间序列(Y轴)的第4个时间段的值R(3)和“V“时间序列(X轴)的第4个时间段的值V(3)匹配的话，这事这两个点之间的距离为（9-3=6），而之前的匹配出来的最短总距离是多少呢，这时我们看与这个格子相近的左下方的3个格子，看看哪个数最小，我们就选哪个，很明显最小值是5，所以这个格子的值为（6+5=11）。
你可能会纳闷为什么是左下方这3个格子呢？其实你要回想，这个matrix的每个格子都代表的是：如果匹配这个格子，到目前为止的最短距离是多少，所以你只要不断的把目前的距离加上之前的最短距离，直到最后，你就会找到一个最短总距离的解了。而另外一个红框算出来是9，具体细节我就不解释了，其实计算方法和之前两个红框都是异曲同工。
【注：为了简化，我们的序列是不会有配对交叉的情况出现的，如R(2)配对C(3), R(3)配对C(2)，这样就出现了交叉，你也可以想象在现实生活中确实也不太常见(语序颠倒？)，这也是为什么我们的表格计算只需要考虑这个格子的左下方的三个格子，而不是他附近的全部格子， 比方说如果你考虑右上方的格子就必然会产生交叉了】
2.2.2 Code Snapshot
DTW的原理以及算法实现基本上就是这样，但其实DTW也存在一些缺点，比如时间复杂度太高: O(NM)，我们的前辈也尝试了非常多提高DTW效率的优化方法，接下来我们一起来探讨。
从上述的过程中你可以直观感受到，基本上每个时间序列上的每个点都要做计算，所以时间复杂度为O(NM)，然而对于现实生活中的问题，这两个序列可能是非常大的，如万亿级别，因此我们很明显需要做大量的效率优化。不过为了更好地理解，我们先考虑一个情形，比方说你现在有一个很长很长的时间序列“T"，然后你有一个较短的时间序列“Q”，你需要在这个很长的时间序列“T”里看看能不能找到和这个“Q”非常相近的时间序列。于是乎，你把“T”分解成一个个小一点的时间序列“C”(如分成了m个“C”)，然后你会使用我们以上学到的办法来尝试计算每个“C”和“Q”的相似度，从而找到最接近的“C”有多接近。好，接下来就让我们开始吧。
3.1 Early Abandoning Z-Normalisation
首先，什么是Early Abandoning？我们先通过下图来了解一下。
好的，那接下来我们说Normalisation，首先我们也需要说明为什么要normalisation呢？其实normalisation是非常重要的一步，而且其实我们每次对比一个"C"和"Q"的时候，都需要确保这两个时间序列已经normalised过了(当然Q只需要normalised一次，因为都是同一个Q)。为什么有这个必要呢，我们看下图。
因此，Early Abandoning Z-Normalisation背后的想法就是，如果你可以使用online Z-normalisation(即计算两个序列的距离同时，同步normalised时间序列)，那么每当你Early Abandoning时，你不仅仅可以节省掉继续计算该序列的距离的时间复杂度，你还可以减掉normalisation的时间复杂度。实现的办法则是通过针对每次要对比的“C”，如果我们把“C”设置成为长度m，也就是每个“C”的长度都是m，那么我们可以使用下方公式先求出这个“C”时间序列的平均值和标准差。
了解了Early Abandoning后，其实Reordering也比较好理解，我们一起来看下图。
那么这个最优秀顺序要如何确定呢？其实你想求的是要看看Q的每个时间段对应C的哪个时间段的距离最大，就从哪个开始，可是这样好像运算量也有点大。而一个比较好的办法就是，我们知道通过normalised，许多C序列都会是高斯分布，因此，我们如果从离C序列的平均值最远的点开始，往往就是对距离的增长贡献最大的点。
3.3 Reversing the Query/Data Role
在介绍这个方法之前，需要简单介绍一下什么是Lower Bounding。
U和L的制定有非常多的方法，包括：LBKeogh、LB_kim。。。，在这里我们就不一一介绍了，我在下面给出了LB_Keogh的公式，相信结合上面的图片都能很容易理解。而这些不同的LB方法的区别主要在upper bound和lower bound离原来的Q线有多接近，过于接近的话就没有起到太多效率优化的效果，离原来的Q线太远的话，就会少算太多的点，需要权衡。
之前提到了Lower Bounds，确实这是一个提高时间序列计算效率的最有效的方法之一了，因此也有不少不同的Lower Bounds，也很难定义哪个比别的就优秀，像我们前面说的，这是一个权衡的问题。我们的前辈就试过把一些主要的Lower Bounds在50个不同的数据集上做了测试，并制作了以下的图，Y轴是U线与L线离Q线的紧凑度(Tightness)，X轴是时间复杂度，而作者指出在一般情况下，应该选择虚线上的Lower Bounds方法，因为根据这个图，如果不在这个虚线上，意味着在同一个紧凑程度下，存在更有效率的Lower Bounds。