使用动态规划计算矩阵距离

Question

我有一个由值 0、1 和 2 组成的矩阵。99% 的值都是 0。该矩阵有 100 万行和 700 列。每行至少有一个非零值。

我需要使用以下公式计算每对列之间的距离，计算列 x 和 y 之间的距离： D=(Sum(|xi-yi|)/2L for i 从1到L，L=100万，即行数。

我写了一段 R 代码，但计算时间太长，是否可以使用动态编程来更快地完成它？这是我的代码：

#mac is the matrix
nCols=ncol(mac)
nRows=nrow(mac)
#the pairwise distance matrix
distMat=matrix(data=-1,nrow=nCols,ncol=nCols)

abs.dist=function(x){return(abs(x[1]-x[2]))} 

for(i in 1:(nCols-1)){
    for(j in (i+1):nCols){
        d1=apply(mac[,c(i,j),1,abs.dist)
        k=sum(d1)/(2*nRows)
        distMat[i,j]=k
        distMat[j,i]=k
    }
}

for(i in 1:nCols) distMat[i,i]=0

非常感谢您的帮助？

Answer 1

计算距离矩阵意味着您需要 (n^2-n)/2 次操作。我并不惊讶它需要一段时间。

由于您需要所有对，因此必须独立完成这些计算。动态规划将无济于事。当您从较小的部分构建解决方案时，DP 会有所帮助。这里的一切都是独立的，所以 DP 将无济于事（据我所知）。

你说大多数条目都是 0。尝试查看稀疏矩阵库。 blog post 可能会给您一些在 R 中执行此操作的想法。

Answer 2

我只是总结一下评论中已经存在的内容：

#mac is the matrix
nCols=ncol(mac)
nRows=nrow(mac)
#the pairwise distance matrix
distMat=matrix(data=-1,nrow=nCols,ncol=nCols)

for(i in 1:(nCols-1)){
    for(j in (i+1):nCols){
        d1=abs(mac[,i]-mac[,j])
        k=sum(d1)/(2*nRows)
        distMat[i,j]=k
        distMat[j,i]=k
    }
}

diag(distMat) <- 0

对于 2000x500 矩阵，这大约快 100 倍。一个1e6x700的矩阵大概用了半分钟。

使用动态规划计算矩阵距离

compute matrix distance using dynamic programming

r

dynamic

matrix