轨迹相似度度量有广泛的用途,如语音识别分类、模板匹配、信息检索等。下面介绍各种轨迹相似度度量方法。
轨迹定义
轨迹可由时间域到空间域的映射函数表示,如:
$$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.
$$
参考链接
- 如何判断两条轨迹(或曲线)的相似度?,by zhihu.
- 动态时间规整(DTW)算法简介,by 文均.
- DTW(Dynamic Time Warping)动态时间规整,by X-猪.
- Dynamic Time Warping 动态时间规整算法,by 阿凡卢.