如何计算大型数据框的欧几里得距离（并仅保存摘要）。

Question

我已经编写了一个短小的“for”循环，以查找数据框中每一行与所有其他行之间的最小欧几里得距离（并记录最接近的行）。理论上，这避免了尝试计算非常大矩阵的距离度量所涉及的错误。然而，虽然在内存方面没有节省太多空间，但对于大矩阵来说非常慢（我的用例有约150K行仍在运行）。

我想知道是否有人能为我提供建议或指引，以便使用apply或类似工具向量化我的函数。对于这个可能看起来很简单的问题，我还在努力思考如何以向量化的方式解决。

谢谢你们的帮助和耐心。

require(proxy)

df<-data.frame(matrix(runif(10*10),nrow=10,ncol=10), row.names=paste("site",seq(1:10)))

min.dist<-function(df) {  
 #df for results
 all.min.dist<-data.frame()
 #set up for loop 
 for(k in 1:nrow(df)) {
     #calcuate dissimilarity between each row and all other rows
     df.dist<-dist(df[k,],df[-k,])
     # find minimum distance
     min.dist<-min(df.dist)
     # get rowname for minimum distance (id of nearest point)
     closest.row<-row.names(df)[-k][which.min(df.dist)]
     #combine outputs
     all.min.dist<-rbind(all.min.dist,data.frame(orig_row=row.names(df)[k],
     dist=min.dist, closest_row=closest.row))
    }
 #return results
 return(all.min.dist)
                        } 
 #example
 min.dist(df)

- nickb

---

我不够资格对向量化发表评论，但是通过找到距离的平方的最小值，然后只在返回时取平方根，您将获得一些好处。 - Mike Woolf

你有查看过 https://dev59.com/LXA75IYBdhLWcg3w7tx6?rq=1 吗？ - Ferdinand.kraft

你循环中的 all.min.dist <- rbind(all.min.dist, ...) 非常糟糕，因为它会在每次迭代时创建一个更大的对象。请阅读有关预分配的内容。 - flodel

谢谢您关于预分配的建议。我已经阅读了相关资料，也看到了@flodel的答案中如何将其整合进去。 - nickb

Answer 1

这应该是一个不错的开始。它使用快速矩阵操作，避免了在评论中建议的增长对象结构。

min.dist <- function(df) {

  which.closest <- function(k, df) {
    d <- colSums((df[, -k] - df[, k]) ^ 2)
    m <- which.min(d)
    data.frame(orig_row    = row.names(df)[k],
               dist        = sqrt(d[m]),
               closest_row = row.names(df)[-k][m])
  }

  do.call(rbind, lapply(1:nrow(df), which.closest, t(as.matrix(df))))
}

如果速度仍然太慢，可以提出建议的改进方法，即一次计算 k 个点的距离，而不是单个点。 k 的大小需要在速度和内存使用之间做出折衷。 编辑：还需阅读https://stackoverflow.com/a/16670220/1201032

- flodel

---

感谢flodel，这个方法同时利用了向量化和欧几里得距离计算的直接性。虽然速度仍然相对较慢，但可以尝试一次计算多个点。 - nickb

Answer 2

通常情况下，内置函数比自己编写的代码更快（因为是用Fortran或C/C++编写并进行了优化）。

似乎函数dist {stats}完美地回答了您的问题：

描述 此函数使用指定的距离度量计算数据矩阵行之间的距离，并计算并返回距离矩阵。

- Guillaume

---

OP说他的使用情况是一个有150k行的矩阵。dist会尝试返回一个完整的150k乘以150k的矩阵并且会崩溃...此外，OP并不关心那么多数据，他只想要每个点最接近的点。因此，逐行处理的方法更加节省内存。 - flodel