DTW算法时序应用与实现

关于dtw算法：

dtw算法最初应用于语音识别中的孤音识别。

即已知某个词的音频模板，给定一个新的音频序列之后，

通过检测该词的音频模板与新音频序列之间的相似度，来判断该音频是否是该词。

 

问题在于，即使是同一个词，由于人的发音有语速、节奏、习惯的不同，其音频也不可能完全一致。

 

这种不一致，体现在序列长度、某个音节的音长等方面。

 

DTW(动态时间规整)算法应运而生：

    通过将待比较的两个序列在时间维度上进行拉升、压缩操作，使其具有相同长度的同时，具有可能的最好的匹配度。

 

时序比较问题：

时间序列分析过程中，不可避免地需要计算两条时序的相似度或距离，用以解决诸如匹配、聚类等问题。

在时序数据的距离度量中遇到了与上述孤音识别类似的问题。

我们需要比较两条时序在形状上的相似度，而不考虑其数据scale、采样频率、时序长度等问题。

 

既然问题类似，那解决方案也肯定可以借鉴，我们考虑如下两条时序的距离度量问题：

 

这两条时序都表现为一个梯形形状，但不同的是其中一条时序的“梯顶”明显要更长。

但这并不妨碍我们将其看做形状“相似”的两条时序。

 

dtw匹配

我们使用dtw算法找到两条时序的最贱匹配模式，并基于此来计算其距离，结果如下：

 

其中两条时序之间的灰色连线即表示两条时序之间点的对应关系。
其中被多余一条连线链接的点，被沿着时间轴的方向拉伸，直观效果如下：
 

 

 

算法R代码如下：

dtw <- function(t,r){
    tl <- length(t);
    rl <- length(r);
    d  <- matrix(0,tl,rl);
    d_dist <- 0.0;
    w1 <- c();
    w2 <- c();
    for(i in 1:tl){
        for(j in 1:rl){
            d[i,j] <- (t[i] - r[j]) ^ 2;
        }
    }
    for (i in 2:tl){
        d[i,1] <- d[i,1] + d[(i-1),1];
    }
    for (j in 2:rl){
        d[1,j] <- d[1,j] + d[1,(j-1)];
    }
      
    for (i in 2:tl){
        for (j in 2:rl){
            d[i,j] <- d[i,j] + min(c(d[(i-1),(j-1)],d[(i-1),j],d[i,(j-1)]));
        }
    }

    i = tl; j = rl;
    d_dist <- d[i,j];
    w1 <- c(i,w1);
    w2 <- c(j,w2);
    while((i + j) > 2){
        if (i == 1){
            j <- j-1;
        } else if (j == 1){
            i <- i - 1;
        } else{
            if (d[(i-1),(j-1)] <= d[(i-1),j] && d[(i-1),(j-1)] <= d[i,(j-1)]){
                i <- i -1;
                j <- j -1;
            } else if (d[(i-1),j] <= d[i,(j-1)]){
                i <- i-1;
            } else {
                j <- j - 1;
            }
        }
        w1 <- c(i,w1);
        w2 <- c(j,w2);
    }
    W  <- matrix(0,2,length(w1));
    W[1,] <- w1;
    W[2,] <- w2;
    
    return (list('d' = d_dist, 'w' = W));
}