动态时间规整(DTW)算法简介 java

收集者 7月前 131

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表示序列A(1-1-3-3-2-4)和序列B(1-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算法的步骤为:

  1. 计算两个序列各个点之间的距离矩阵。
  2. 寻找一条从矩阵左上角到右下角的路径,使得路径上的元素和最小。

我们称路径上的元素和为路径长度。那么如何寻找长度最小的路径呢?

矩阵从左上角到右下角的路径长度有以下性质:

  1. 当前路径长度 = 前一步的路径长度 + 当前元素的大小
  2. 路径上的某个元素(i, j),它的前一个元素只可能为以下三者之一:
a) 左边的相邻元素 (i, j-1)
b) 上面的相邻元素 (i-1, j)
c) 左上方的相邻元素 (i-1, j-1)

假设矩阵为M,从矩阵左上角(1,1)到任一点(i, j)的最短路径长度为Lmin(i, j)。那么可以用递归算法求最短路径长度:

起始条件:

递推规则这样写的原因是因为当前元素的最短路径必然是从前一个元素的最短路径的长度加上当前元素的值。前一个元素有三个可能,我们取三个可能之中路径最短的那个即可。


少客联盟- 版权声明 1、本主题所有言论和图片纯属会员个人意见,与少客联盟立场无关。
2、本站所有主题由该帖子作者发表,该帖子作者收集者少客联盟享有帖子相关版权。
3、少客联盟管理员和版主有权不事先通知发贴者而删除本文。
4、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者收集者少客联盟的同意。
5、帖子作者须承担一切因本文发表而直接或间接导致的民事或刑事法律责任。
6、本帖部分内容转载自其它媒体,但并不代表本站赞同其观点和对其真实性负责。
7、如本帖侵犯到任何版权问题,请立即告知本站,本站将及时予与删除并致以最深的歉意。
8、官方反馈邮箱:chinasuc@chinasuc.cn


上一篇:LiteIDE搭建Go语言开发环境
下一篇:你的编程能力从什么时候开始突飞猛进?
人生的价值,并不是用时间,而是用深度去衡量的。
最新回复 (0)
    • 少客联盟
      2
        登录 注册 QQ登录(停用)
返回