DTW优化：使用DTW实现万亿级别序列匹配「文献阅读笔记 ...
DTW(Dynamic Time Warping) 是一种序列匹配和序列距离计算的经典算法。DTW的适用范围极其广泛， 语音识别，搜索引擎，基因组数据分析等都有DTW的身影。 自从1994年DTW算法最先被报道出来以来， 各种围绕DTW的性能和准确性优化层出不穷。 本文将对一个2012年发表的DTW性能优化算法进行解读，介绍DTW的性能优化过程。参考文献：
一、DTW算法回顾
DTW出现之前对于序列相似度测测量主要基于ED（Euclidean Distance）但是ED距离对于序列来说会有很多问题，比如每一个时间步不能很好对齐， 或者序列长短不一等等。 DTW出现以后在很多场景逐步取代ED的位置， 但DTW有一个很大的缺陷，就是算的慢算法复杂度位 https://www.zhihu.com/equation?tex=O%28nm%29 而ED只有 https://www.zhihu.com/equation?tex=O%EF%BC%88n%EF%BC%89 。 随后的一系列研究成果都是围绕如何加快DTW的速度展开，比如寻找更好的 LB（low bound）, 创建更好的 index 简化计算， 使用部分计算代替全部计算的 early abandon 方法等等。 这些都会在后文中详细说明。 不过在这之前先回顾一下到底什么是DTW算法。
简单对比一下ED和DTW算法， 示意图如下：
左边是ED算法， 只能解决时间步万全匹配的距离计算。
右面是DTW算法， 可以存在时间步骤之间多对一的情况。 很显然对于复杂序列，DTW更靠谱。
DTW算法定义如下，假设我们有两条序列 Q（query）和 C (candidates), 分别长度为 https://www.zhihu.com/equation?tex=n 和 https://www.zhihu.com/equation?tex=m ，他们不一定相等。
https://www.zhihu.com/equation?tex=Q%3Dq_1%2C+q_2%2C......%2Cq_i%2C......%2Cq_n
https://www.zhihu.com/equation?tex=C%3Dc_1%2C+c_2%2C......%2Cc_j%2C......%2Cc_m
为了比对Q和C，组成一个n by m的矩阵， 每两个对齐后的元素之间的距离下标定义为 https://www.zhihu.com/equation?tex=%EF%BC%88i%5E%7Bth%7D%2C+j%5E%7Bth%7D%EF%BC%89 距离定义为 https://www.zhihu.com/equation?tex=d%28q_i%2C+c_j%29 比如 https://www.zhihu.com/equation?tex=d%28q_i%2C+c_j%29%3D%28q_i+-+c_j%29%5E2 。 有一条 warping path 穿越这个矩阵， 定义为。的第 https://www.zhihu.com/equation?tex=K 个元素，定义为 https://www.zhihu.com/equation?tex=w_k%3D%28i%2C+j%29_k。
https://www.zhihu.com/equation?tex=W%3Dw_1%2C+w_2%2C+...%2Cw_k%2C+...%2C+w_K
示意图如下：
A) 表示两条序列Q，C， B) 两条序列对比矩阵，以及warping path， C) 对比结果
DTW 的约束条件如下：
[*]Boundary conditions: https://www.zhihu.com/equation?tex=w_1+%3D+%281%2C+1%29 和 https://www.zhihu.com/equation?tex=w_k+%3D+%28m%2C+n%29表示两条序列收尾必须匹配。
[*]Continuity: 如果 https://www.zhihu.com/equation?tex=w_k+%3D+%28a%2C+b%29 且 https://www.zhihu.com/equation?tex=w_%7Bk-1%7D%3D%28a%5E%7B%27%7D%2C+b%5E%7B%27%7D%29 则 https://www.zhihu.com/equation?tex=a+-+a%5E%7B%27%7D++%5Cle+1 且 https://www.zhihu.com/equation?tex=b+-+b%7B%27%7D+%5Cle+1 。 这条约束表示在匹配过程中多对一和一对多的情况只能匹配周围一个时间步的的情况。
[*]Monotonicity: https://www.zhihu.com/equation?tex=%E5%A6%82%E6%9E%9C+w_k%3D%28a%2C+b%29+%E4%B8%94+w_%7Bk-1%7D%3D%28a%5E%7B%27%7D%2C+b%5E%7B%27%7D%29+%E5%88%99+a-a%5E%7B%27%7D+%5Cle+0+%E4%B8%94b-b%5E%7B%27%7D+%5Cle+0这条约束表示 warping path 一定是单调增的， 不能走回头路。
当然有指数级别个 warping path 满足这些约束。 因此这个问题就变成寻找一条最优路径的问题。 问题描述如下：
https://www.zhihu.com/equation?tex=DTW%28Q%2C+C%29+%3D+min+%5Cleft%5C%7B+++++%5Csqrt%7B%5Csum_%7Bk-1%7D%5E%7BK%7D%7Bw_k%7D%7D+%5Cright.+++
这条最优路径可以通过动态规划的算法求解， 每个时间步的累计距离 。
https://www.zhihu.com/equation?tex=%5Cgamma%28i%2C+j%29+%3D+d%28q_i%2C+c_j%29+%2B+min+%5C%7B+%5Cgamma%28i-1%2Cj-1%29%2C+%5Cgamma%28i-1%2C+j%29%2C+%5Cgamma%28i%2C+j-1%29%5C%7D
整体算法复杂度 https://www.zhihu.com/equation?tex=O%28mn%29
二、 DTW的主流优化手段
[*]使用平方距离代替平方根距离
原生的DTW 和 ED 算法在在距离求解上都是用平方根距离，其实这一步可以省略。 对于搜索和排序任务， 有没有平方对于结果没影响。 但平方根求解在CPU底层计算开销其实很大。
2. Lower Bounding 算法
主要思想是在搜索数据很大的时候， 逐个用DTW算法比较每一条是否匹配非常耗时。那我们能不能使用一种计算较快的近似方法计算LB， 通过LB处理掉大部分不可能是最优匹配序列的序列，对于剩下的序列在使用DTW逐个比较呢？ 答案是肯定的。 体现为伪代码如下：
Algorithm Lower_Bounding_Sequential_Scan(Q)
best_so_far = infinity;
for all sequences in database
LB_dist = lower_bound_distance(Ci,Q);
if LB_dist < best_so_far
true_dist = DTW(Ci,Q);
if true_dist < best_so_far
best_so_far = true_dist;
index_of_best_match= i;
endif
endif
endfor对于Lower Bounding具体的计算方法这些年学界有很多积累。 这里只提文中提到的两种。 LB_Kim和LB_keogh
LB_kim 示意图：
LB_kim 的计算需要参考Q和C四个位置的平方距离。图中的ABCD。 A：起始点的平方距离， B：Q,C 最低点的平方距离， C： Q和C的最高点之间的平方距离， D：结尾处的平方距离。
LB_keogh距离定义：
LB_keogh的定义相对复杂，包括两部分。
第一部分为Q的{U， L} 包络曲线（具体如图）， 给Q序列的每个时间步定义上下界。 定义如下
https://www.zhihu.com/equation?tex=U_i+%3D+max%28q_%7Bi-r%7D%3Aq_%7Bi%2Br%7D%29
https://www.zhihu.com/equation?tex=L_%7Bi%7D+%3D+min%28q_%7Bi-r%7D%3Aq_%7Bi%2Br%7D%29
https://www.zhihu.com/equation?tex=s.t%3Aj-r+%5Cle+i+%5Cle+j%2Br+
其中 r 是一段滑行窗距离，可以自定义。
示意图如下：
U 为上包络线，就是把每个时间步为Q当前时间步前后r的范围内最大的数。L 下包络线同理。
那么LB_Keogh定义如下：
https://www.zhihu.com/equation?tex=LB%5C_Keogh%28Q%2C+C%29+%3D+%5Csqrt+%7B+%5Csum_%7Bn%7D%5E%7Bi%3D1%7D+++++%5Cbegin%7Bequation%7D+++++++%5Cleft%5C%7B++++++++++++++++%5Cbegin%7Barray%7D%7Blr%7D++++++++++++++++%28c_i+-+U_i%29%5E2++%26+%5Ctext%7Bif+%7D+c_i+%5Clt+U_i%2C+%5C%5C++++++++++++++%28c_i+-+L_i%29%5E2++%26+%5Ctext%7Bif+%7D+c_i+%5Clt+L_i+%5C%5C++++++++++++++++0+%26+%5Ctext%7Botherwise%7D++++++++++++++++++%5Cend%7Barray%7D+++++++%5Cright.+++++++%5Cend%7Bequation%7D+++%7D
用图像描述如下：
阴影部分对LB贡献。
3.Early Abandoning 算法。
Early Abandoning 顾名思义， 无论在使用ED搜索还是LB_keogh搜索， 每次比较都没有必要把整条序列全部比对完，当发现距离大于当前历史最好的记录时候，就可以停止放弃当前的C序列， 如图：
Early Abandoning 也可以用作DTW， 并结合LB_keogh. 如图：
左边为计算LB_keogh距离， 但发现并不能通过这个距离判断是不是最优。 那么从 K=0 开始逐步计算DTW并且和K后面的LB_keogh部分累加，判断距离是否大于目前最好的匹配序列，在这个过程中，一旦发现大于当前最好匹配得距离，则放弃该序列停止DTW。 实际的lower bound 可以写成： https://www.zhihu.com/equation?tex=DTW%28Q_%7B1%3AK%7D%2C+C_%7B1%3AK%7D%29+%2B+LB_%7BKeogh%7D%28Q_%7BK%2B1%3An%7D%EF%BC%8CC_%7BK%2B1%3An%7D+%29
Early Abandoning 除了可以用在计算LB，ED， DTW上， 也可以用于对序列进行 Z-Normalization。 公式如下：
https://www.zhihu.com/equation?tex=%5Cmu+%3D+%5Cdfrac%7B1%7D%7Bm%7D%28%5Csum_%7Bi%3D1%7D%5E%7Bk%7D%7Bx_i+-+%5Csum_%7Bi%3D1%7D%5E%7Bk-m%7D%7Bx_i%7D%7D%29
https://www.zhihu.com/equation?tex=%5Csigma%5E2+%3D+%5Cdfrac%7B1%7D%7Bm%7D%28%5Csum_%7Bi%3D1%7D%5E%7Bk%7D%7Bx%5E2%7D+-+%5Csum_%7Bi%3D1%7D%5E%7Bk-m%7D%7Bx%5E2%7D%29+-+%5Cmu%5E2
4. Reordering Early Abandoning
这个优化的基本思想是这样的。 假如我们计算两条序列的ED距离， 为了达到Early Aandoning 的目的， 从第一个元素开始用滑窗往后尝试并不是一个最好的选择。 因为开始地序列未必区分度很强。 很可能只通过中间某一段序列就可以判断这个C不是最优匹配序列，可以提前终止算法。 示意图如下：
左图是是正常的从头比较。 右图是跳过一部分只比较最有区分度的一部分。
但问题来了， 如何快速的找到全局最优比较顺序呢。 这里引入一个先验假设。 首先，每两条序列在比较之前都是要做 z-normalize 的， 因此每个时间步的数值分布应该是服从标准高斯分布。 他们的均值应该是0。因此对于距离计算贡献最大的时间步一定是远离均值0的数。 那么我们就可以提前对序列的下标排序，从大到小依次比较，这样在计算ED距离和LB_Keogh 的时候就可以尽量早的Early abandon, 而排序过程可以再搜索之前批量完成并不影响搜索的实时性能。
5. 在计算 LB_keogh 的时候颠倒 Query/Data 的角色
上个图：
左边是给Q序列算上下包络线 {U， L}， 其实同样可以为 C 序列加上下包络，反过来比。 筛选效果相同。但是通过两种方式算出来的 https://www.zhihu.com/equation?tex=LB%5C_keoghEQ+%5Cne+LB%5C_keoghEC 。因此可以先用前一种方式做筛选，通过后再用后一种方式筛一遍， 更大程度的减少剩余候选序列。
6. Cascading Lower Bounds:
通过 Low Bounding 做预匹配的方式有非常多。总体而言 Low Bounding的计算方法也积累了很多，在不同的数据集上各有优缺点， 并没有一个全局一定最好的方式。 因此我们可以考虑把不同的Low Bounding的方法按照LB(A, B)/DTW(A, B) tightness 层级聚合起来。从计算开销小单但是 tightness 低的LB， 一直到计算开销大但tightness 高的LB，逐步去除无效的候选序列。 这样的好处是，用开销低的LB去掉大部分的序列， 类似起到一个从粗粒度到细粒度的清洗过程。 LB(A, B)/DTW(A, B)的tightness排序方式如图下：
计算复杂度和逼近DTW的距离。
三、总结与讨论
自然语言处理DTW与一些聚类算法结合， 比如经典的kmeans, 可以把里面的距离矩阵换成DTW距离， 这样就可以更好的用于序列数据的聚类，而在距离矩阵的准备过程中， 也可以用到以上的各种优化思想进行性能优化。 LBkeogh 的公式在计算上界的时候写错了 是 c_i > U_i 多谢指出 文章最前面的DTW彩图是用什么工具画的呢？谢谢 google 图片 你们落地了了亿级样本了？ 1978年算法到你这成了1994年了，做学问够烂
页:
[1]