高效的多维动态时间规整实现

Question

高效的多维动态时间规整实现

5

以下是如何计算两个时间序列的多维动态时间规整的文献解释：

这里是如何计算两个时间序列的多维动态时间规整（Multidimensional Dynamic Time Warping）的文献解释：

 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距离并将其存储在专用矩阵中。这肯定是最耗费计算资源的解决方案。

- WAF

所以，你需要高效地计算变量var1和var2之间的距离矩阵（欧氏距离），它们都是长度相同的三维数组？也就是说，在x <- inDf[,c("var1t1","var1t2","var1t3")]和y <- inDf[,c("var2t1","var2t2","var2t3")]之间？ - redmode

你能澄清一下inDf与你的第一个例子有什么关系吗？var1t1是x，var2t1是y，然后在另外两个时间段中再次重复吗？你想要计算每个时间段每对变量的dtw距离吗？这些事情与图像有什么关系？此外，看起来dtw本身就计算了dist，所以你不需要进行那一步。 - BrodieG

第一个和第二个示例之间的区别在于每个样本测量的变量数量。在第一个示例中，x和y都是相同唯一变量随时间变化的时间序列。而在第二个示例中，每个x由两个变量，即两个时间序列所描述。希望现在更清晰了。 - WAF

在第二个例子中，cxdist的维度是什么？据我所知，它们应该是10x10。因此，我们正在计算var1中10个三维点和var2中10个三维点之间的成对距离。这是否正确？ - redmode

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- redmode · Accepted Answer

当处理密集运算时，考虑使用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语法糖，使代码更加简洁易读。但有时候为了检查类型、强制转换等更好地封装函数。这不是必需的 - 您可以直接调用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感兴趣，您可以在调用dtw()时传入distance.only=T参数进行一定的加速。