最近读了SIGKDD在2010年的最佳论文，Searching and Mining Trillions of Time Series Subsequences under Dynamic。这篇文章对DTW（Dynamic Time Warping）算法改进并成功的应用在了万亿级别的数据集上。
DTW
DTW有三个约束条件：
- 边界条件：所选路径必须从左下角出发，右上角结束
- 连续性：不能跨过某个点去匹配，只能匹配和自己相邻的点
-
单调性：点与点的匹配是单调的，不可以跨越点。
结合连续性和单调性约束，每一个格点的路径就只有三个方向了。例如如果路径已经通过了格点(i, j)，那么下一个通过的格点只可能是下列三种情况之一：(i+1, j)，(i, j+1)或者(i+1, j+1)。
使用改进DTW的四个前提
-
Time Series Subsequences must be Normalized
为了使两个子序列的比较更有意义，所以子序列必须被归一化。论文使用有枪和无枪举了例子，在归一化后的准确率更高。
来自论文
- Dynamic Time Warping is the Best Measure
DTW经过很多的测试，验证了DTW在搜索子序列上是最好的方式了。 - Arbitrary Query Lengths cannot be Indexed
无法索引任意长度的索引。如果长度太长，可能会超出内存的承受范围，并在使用任意长度的时候，会使归一化没有多少意义。 - There Exists Data Mining Problems that we
are Willing to Wait Some Hours to Answer
对于亿级别的数据，可能会花费一些时间等待结果，所以如果你没有要求立即得出结果，就可以使用这种方法。
当前对DTW的优化
- Using the Squared Distance
DTW和欧式距离在计算的时候都使用了开根的操作，然而这一操作显然是多余的。当我们不开根号时，其距离排序也不会因此而改变，反而会减低时间的消耗。 -
Lower Bounding
一个典型的加快序列搜索速度的方式是计算一个相似度下界，一旦当前序列的相似度低于下界，就停止计算，转去计算下一个子序列。文中提了两种计算下界的方式
来自论文
-
只计算Q和C的开头或结尾作为LB,时间复杂度为
,还有一种方式是计算两段序列的最大值和最小值的差值作为
-
Early Abandoning of
and
在计算ED或的时候，当累计的误差大于best-so-far时，停止计算。
图片来自于论文
-
Early Abandoning of
在计算之前需要计算
,一旦
图片来自于论文
-
Exploiting Multicores
Exploiting Multicores指的是多核计算，很简单，不用过多解释。
新的优化方式（UCR优化）
-
Early Abandoning Z-Normalization
在对子序列进行比较前，需要计算均值和方差来对序列进行归一化。然后可以在标准化的过程中计算DTW,这样就可以节约大量时间。并且此方法可以和提前停止结合起来，一旦超过LB，就停止归一化和计算DTW。这样节约了大量时间。伪代码如下：
来自论文
为了避免累计浮点误差，每一百万条子序列执行一次完全标准化
-
Reordering Early Abandoning
传统计算距离或者归一化的时候，直接从左到右计算。然而这种方式一定是最好的吗？论文提出使用重排的方式，可以减少计算。下图的左边是传统方式，右边是新的方式，左边计算了9次才知道这段不可以用，右边找了5次。
来自论文
文章给出了选择最优顺序的方法，对Q序列Normalized后的绝对值排序作索引，选择Q是因为搜索时Q序列会和很多序列比较。因为
原文如下：
We conjecture that the universal optimal ordering is to sort the
indices based on the absolute values of the Z-normalized Q. The
intuition behind this idea is that the value at Qi will be compared
to many Ci’s during a search. However, for subsequence search,
with Z-normalized candidates, the distribution of many Ci’s will
be Gaussian, with a mean of zero. Thus, the sections of the query that are farthest from the mean, zero, will on average have the largest contributions to the distance measure. -
Reversing the Query/Data Role in
在这里需要交换Q和C的角色，对C做Lower Bounding
来自论文
-
Cascading Lower Bounds
使用多种方式计算LB而不是局限于一种方式计算LB，这是为最有效的方式。具体的
在计算LB时，按照时间复杂度从低到高，一步步的使用不同的方式计算LB，每一步都可以剪枝掉很多计算，并不同的剪枝方式侧重点不同，可以更有效地剪枝。
使用这种方式可以在大数据集上计算DTW时剪枝掉超过99.9999%的运算。
来自论文
实验和结论
为了确保改进的DTW的有效性，作者使用改进的DTW共进行了分别在金融、EEG数据集、DNA、姿势数据上进行了四个实验。在这四个实验上都取得了较大的领先。
参考文献
- https://zhuanlan.zhihu.com/p/87630320
- Searching and Mining Trillions of Time Series Subsequences under Dynamic
Time Warping - https://blog.csdn.net/zhaoyin214/article/details/102651244
- https://blog.csdn.net/zouxy09/article/details/9140207
网友评论