| 动态时间弯曲距离精确计算的Dijkstra方法 |
| |
| 引用本文： | 李兴芳.动态时间弯曲距离精确计算的Dijkstra方法[J].四川职业技术学院学报,2011,21(6):101-103. |
| |
| 作者姓名： | 李兴芳 |
| |
| 作者单位： | 重庆财政学校,重庆北部新区,401121 |
| |
| 摘 要： | 将动态时间弯曲距离（DTW）的差异矩阵一一对应于点阵,按DTW定义的行走规则对该点阵连线定向,使所对应点阵成为一个有向图,然后使用一个加权技巧对该有向图的边加权后得到一个加权有向图,于是把求DTW的精确计算问题等价地转化为求一个有向图起点到终点的最短路长,从而使图论中求两点间最短路径的方法如目前公认的经典Dijkstra算法均可用于求DTW,因此间接地找到了精确计算DTW的一个新方法.
|
| 关 键 词： | 动态时间弯曲距离(DTW) 有向加权图 最短路径 Dijkstra算法 时间序列 |
The Directed Graph Method for Dynamic Time Warping |
| |
| Li Xingfang.The Directed Graph Method for Dynamic Time Warping[J].Journal of Sichuan Vocational and Technical College,2011,21(6):101-103. |
| |
| Authors: | Li Xingfang |
| |
| Institution: | Li Xingfang (Chongqing Finance School,Chongqing,400060) |
| |
| Abstract: | Map the difference matrix of dynamic time warping(DTW) to a corresponding point matrix,and connect those points according to the walking rout in the definition of DTW to obtain a directed graph.Then weight the edges by using some trick,a appropriate directed and weighted graph is given out.As a result,to find DTW is equally to find the shortest distance path,therefore all those algorithms that used to find shortest distance path such as Dijkstra’s algorithm well known as the best one until now can be used to find DTW,which improves solving the problem of calculating DTW. |
| |
| Keywords: | Dynamic Time Warping Directed Graph Shortest Path Dijkstra’s Algorithm Time Series Data mining Cluster Analysis Euclidean Distance |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
