高效的多維動態時間規整實施

Question

這裏是如何的文獻介紹瞭如何計算的兩個時間序列多維動態時間規整：

library(dtw) 
x<- cbind(1:10,1) 
y<- cbind(11:15,2) 
cxdist <-dist(x,y,method="euclidean") 
dtw(cxdist)$distance 

事實上，它首先計算交叉距離矩陣，然後用它作爲輸入dtw功能。

我想在圖像分類中使用具有相當大圖像的多維動態時間扭曲。 圖像值被存儲在數據幀中可能看起來像這樣：

inDf <- data.frame(matrix(rnorm(60), ncol = 6)) 
colnames(inDf) <- c('var1t1','var2t1','var1t2','var2t2','var1t3','var2t3') 

在這個例子中，有兩個變量（VAR1和VAR2）觀察到三次。

問題是如何在計算強度時儘可能多地獲得dtw距離矩陣？

這裏有一些想法： - 迭代通過輸入圖像矩陣的每個值，將矢量重塑爲矩陣，以便能夠計算交叉距離，然後計算dtw距離並將其存儲在專用矩陣中。 這當然是最計算密集型解決方案

Answer 1

當處理密集型計算總是有意義考慮Rcpp包。如果你想獲得與歐氏距離的距離矩陣快，可以實現相應的功能Rcpp：

library(Rcpp) 
library(inline) 

# Rcpp function for euclidean distance 
fastdist <- cxxfunction(signature(x="matrix", y="matrix"), plugin="Rcpp", 
body=' 
    Rcpp::NumericMatrix dx(x); 
    Rcpp::NumericMatrix dy(y); 

    const int N = dx.nrow(); 
    const int M = dy.nrow(); 

    Rcpp::NumericMatrix res(N, M); 

    for(int i=0; i<N; i++){ 
    for(int j=0; j<M; j++){ 
     res(i,j) = sqrt(sum((dx(i,_)-dy(j,_))*(dx(i,_)-dy(j,_)))); 
    } 
    } 

    return res; 
') 

它採用Rcpp句法sugar爲了讓代碼更緊湊和可讀性。但是，有時最好使用包裝函數來檢查類型，強制等。這不是必需的 - 您可以直接撥打fastdist。但是，無論如何，包裝可以看起來像這樣：

# Wrapper R function 
fast.dist <- function(x, y){ 
    stopifnot(class(x) %in% c("data.frame","matrix") & 
      class(y) %in% c("data.frame","matrix") & 
      ncol(x)==ncol(y)) 

    fastdist(as.matrix(x), as.matrix(y)) 
} 

現在我們可以轉向文學的例子。

library(dtw) 

# EXAMPLE 1 
x<- cbind(1:10,1) 
y<- cbind(11:15,2) 
# Check results 
all.equal(fast.dist(x,y), dist(x,y,method="euclidean"), check.attributes=F) 
# [1] "target is matrix, current is crossdist" 
all.equal(fast.dist(x,y), matrix(dist(x,y,method="euclidean"), ncol=nrow(y))) 
# [1] TRUE 

注意，那dist返回結果crossdist類的。所以，爲了比較，它應該被強制爲matrix。

現在你的首要問題 - 我們首先生成數據：

# EXAMPLE 2 
set.seed(1234) 
N <- 100 
inDf <- data.frame(matrix(rnorm(6*N), ncol = 6)) 
colnames(inDf) <- c('var1t1','var2t1','var1t2','var2t2','var1t3','var2t3') 

# Extracting variables 
var1 <- inDf[,c("var1t1","var1t2","var1t3")] 
var2 <- inDf[,c("var2t1","var2t2","var2t3")] 

我不能完全肯定你的數據結構，但在任何情況下，你可以根據自己的需要隨時準備變量。

比較和基準：

library(rbenchmark) 

all.equal(fast.dist(var1,var2), matrix(dist(var1,var2), ncol=N)) 
# [1] TRUE 
benchmark(fast.dist(var1,var2), dist(var1,var2), order="relative")[,1:4] 
#     test replications elapsed relative 
# 1 fast.dist(var1, var2)   100 0.081 1.000 
# 2  dist(var1, var2)   100 0.246 3.037 

fast.dist比dist在這種情況下更快的大致3倍。然而，雖然N正在增長，相對加速將下降。

另請注意，如評論中所述，dtw可以自行計算距離矩陣。不過，預先計算距離矩陣會更有效率。請參見下面的快速測試：

cxdist <- fast.dist(var1,var2) 
benchmark(dtw(cxdist)$distance, dtw(var1,var2)$distance, order="relative")[,1:4] 
#      test replications elapsed relative 
# 1  dtw(cxdist)$distance   100 0.476 1.000 
# 2 dtw(var1, var2)$distance   100 0.736 1.546 

另外，如果你只關心$distance你可以通過distance.only=T到dtw() - 它提供了一些加速。