轨迹相似度度量方法总结

发表于 | 更新于 | 评论数： | 阅读次数：

轨迹相似度度量有广泛的用途，如语音识别分类、模板匹配、信息检索等。下面介绍各种轨迹相似度度量方法。

轨迹定义

轨迹可由时间域到空间域的映射函数表示，如：

$$t\stackrel{F}{\longrightarrow}R^d, d>1$$

度量方法

轨迹相似度度量方法主要有：

  • 基于点方法： EDR，LCSS，DTW等

  • 基于形状的方法： Frechet， Hausdorff

  • 基于分段的方法：One Way Distance, LIP distance

  • 基于特定任务的方法：TRACLUS， Road Network，grid等

基于点的方法

DTW

DTW（Dynamic Time Warping, 动态时间规整）可以计算两个时间序列的相似度，尤其适用于不同长度、不同节奏的时间序列（比如不同的人读同一个词的音频序列）。DTW将自动warping扭曲 时间序列（即在时间轴上进行局部的缩放），使得两个序列的形态尽可能的一致，得到最大可能的相似度。

Dynamic Time Warping（DTW）诞生有一定的历史了（日本学者Itakura提出），它出现的目的也比较单纯，是一种衡量两个长度不同的时间序列的相似度的方法。应用也比较广，主要是在模板匹配中，比如说用在孤立词语音识别（识别两段语音是否表示同一个单词），手势识别，数据挖掘和信息检索等中。

设 $P=<p_1,p_2,…,p_m>$ 和 $Q=<q_1,q_2,…,q_n>$ 是两个时间序列，则 $P$ 和 $Q$的距离 $DTW(P,Q)$ 定义如下：

$$DTW(P,Q)= \left{
\begin{array}{lcl}
0 & &if\ m=n=0\
\infty & &if\ m=0\ or\ n=0\
dist(p_1,q_1)+min
\left{
\begin{aligned}
DTW(Rest(P),Rest(Q))\
DTW(Rest(P),Q)\
DTW(P,Rest(Q))\
\end{aligned}
\right} & & otherwise
\end{array}
\right.
$$

参考链接

  1. 如何判断两条轨迹（或曲线）的相似度？,by zhihu.
  2. 动态时间规整（DTW）算法简介,by 文均.
  3. DTW(Dynamic Time Warping)动态时间规整,by X-猪.
  4. Dynamic Time Warping 动态时间规整算法,by 阿凡卢.