网站建设的初期目标,网页制作手机版,wordpress海报插件,十堰网站开发原文地址#xff1a;https://blog.csdn.net/qcyfred/article/details/53824507 https://zhuanlan.zhihu.com/p/43247215 动态时间规整#xff08;DTW#xff09;算法简介相忘天涯#xff0c;深藏于心19 人赞同了该文章DTW最初用于识别语音的相似性。我们用数字表示音调高低…原文地址https://blog.csdn.net/qcyfred/article/details/53824507 https://zhuanlan.zhihu.com/p/43247215
动态时间规整DTW算法简介相忘天涯深藏于心19 人赞同了该文章DTW最初用于识别语音的相似性。我们用数字表示音调高低例如某个单词发音的音调为1-3-2-4。现在有两个人说这个单词一个人在前半部分拖长其发音为1-1-3-3-2-4另一个人在后半部分拖长其发音为1-3-2-2-4-4。现在要计算1-1-3-3-2-4和1-3-2-2-4-4两个序列的距离距离越小相似度越高。因为两个序列代表同一个单词我们希望算出的距离越小越好这样把两个序列识别为同一单词的概率就越大。先用传统方法计算两个序列的欧几里得距离即计算两个序列各个对应的点之间的距离之和。距离之和 |A(1)-B(1)| |A(2)-B(2)| |A(3)-B(3)| |A(4)-B(4)| |A(5)-B(5)| |A(6)-B(6)||1-1| |1-3| |3-2| |3-2| |2-4| |4-4|6如果我们允许序列的点与另一序列的多个连续的点相对应相当于把这个点所代表的音调的发音时间延长然后再计算对应点之间的距离之和。如下图B(1)与A(1)、A(2)相对应B(2)与A(3)、A(4)相对应A(5)与B(3)、B(4)相对应A(6)与B(5)、B(6)相对应。这样的话 距离之和|A(1)-B(1)| |A(2)-B(1)| |A(3)-B(2)| |A(4)-B(2)| |A(5)-B(3)| |A(5)-B(4)| |A(6)-B(5)| |A(6)-B(6)| |1-1| |1-1| |3-3| |3-3| |2-2| |2-2| |4-4| |4-4|0我们把这种“可以把序列某个时刻的点跟另一时刻多个连续时刻的点相对应”的做法称为时间规整Time Warping。现在我们用一个6*6矩阵M表示序列A1-1-3-3-2-4和序列B1-3-2-2-4-4各个点之间的距离M(i, j)等于A的第i个点和B的第j个点之间的距离即我们看到传统欧几里得距离里对应的点A(1)-B(1)A(2)-B(2)A(3)-B(3)A(4)-B(4)A(5)-B(5)A(6)-B(6)它们正好构成了对角线对角线上元素和为6。时间规整的方法里对应的点为A(1)A(2)-B(1)A(3)A(4)-B(2)A(5)-B(3)B(4)A(6)-B(5)B(6)这些点构成了从左上角到右下角的另一条路径路径上的元素和为0。因此DTW算法的步骤为计算两个序列各个点之间的距离矩阵。寻找一条从矩阵左上角到右下角的路径使得路径上的元素和最小。我们称路径上的元素和为路径长度。那么如何寻找长度最小的路径呢矩阵从左上角到右下角的路径长度有以下性质当前路径长度 前一步的路径长度 当前元素的大小路径上的某个元素(i, j)它的前一个元素只可能为以下三者之一a) 左边的相邻元素 (i, j-1)b) 上面的相邻元素 (i-1, j)c) 左上方的相邻元素 (i-1, j-1)假设矩阵为M从矩阵左上角(1,1)到任一点(i, j)的最短路径长度为Lmin(i, j)。那么可以用递归算法求最短路径长度起始条件 递推规则 递推规则这样写的原因是因为当前元素的最短路径必然是从前一个元素的最短路径的长度加上当前元素的值。前一个元素有三个可能我们取三个可能之中路径最短的那个即可。编辑于 2018-08-29算法时间序列分析赞同 195 条评论分享收藏
