查找大型矩阵行之间的最小距离：分配限制错误

Question

我想计算一个大矩阵的所有行之间的距离。对于每一行，我需要找到距离最短的另一行。最终输出应该是一个列表，其中包含距离最短的行的 ID（参见下面示例中的 low_dis_ids）。

我能够找到针对小样本的解决方案（如下例）。但是，我无法使用更大的样本执行这些步骤，因为具有距离的矩阵变得太大了。有没有办法省略这么大的矩阵？我只需要带有 ID 的列表（如 low_dis_ids）。

可重现的例子：

set.seed(123)

# Calculation of distances with small samplesize is working well
N <- 100
data_100 <- data.frame(x1 = rnorm(N, 5, 10),
                       x2 = rnorm(N, 5, 10),
                       x3 = rnorm(N, 5, 10),
                       x4 = rnorm(N, 5, 10),
                       x5 = rnorm(N, 5, 10))

# Matrix with all distances (no problem for the smaller samplesize)
dist_100 <- as.matrix(dist(data_100))

# Find the row with the smallest distance
for(i in 1:nrow(dist_100)) {
  dist_100[i, i] <- Inf
}

low_dis <- numeric()
for(i in 1:nrow(dist_100)) {
  low_dis[i] <- as.numeric(sort(dist_100[ , i]))[1]
}

low_dis_ids <- list()
for(i in 1:length(low_dis)) {
  low_dis_ids[[i]] <- as.numeric(names(dist_100[ , i][dist_100[ , i] == low_dis[i]]))
}

# low_dis_ids is the desired output and stores the rows with the smallest distances



# The same procedure is not working for larger samplesizes
N <- 100000
data_100000 <- data.frame(x1 = rnorm(N, 5, 10),
                          x2 = rnorm(N, 5, 10),
                          x3 = rnorm(N, 5, 10),
                          x4 = rnorm(N, 5, 10),
                          x5 = rnorm(N, 5, 10))
dist_100000 <- dist(data_100000)

# Error: cannot allocate vector of size 37.3 Gb

Answer 1

您绝对可以避免因使用 dist 而产生的大型矩阵。一种这样的解决方案是一次计算一行的距离，我们可以编写一个函数，给定整个数据框和一个行 id，找到哪一行对应于最小距离。例如：

f = function(rowid, whole){
  d = colSums((whole[rowid,] - t(whole))^2) # calculate distance
  d[rowid] = Inf # replace the zero
  which.min(d)
}

colSums 函数优化得相当好，因此速度相对较快。我怀疑 which.min 也是一种更快且可能更整洁的循环遍历距离向量的方法。

为了制定一个适用于任何此类数据框的解决方案，我编写了另一个短函数，将其应用于每一行并为您提供行 ID 向量

mindists = function(dat) do.call(c,lapply(1:nrow(dat),f,whole = as.matrix(dat)))

如果您想要列表而不是向量，只需省略 do.call 函数即可。我这样做是为了更容易检查输出是否符合您的预期。

all(do.call(c,low_dis_ids) == mindists(data_100))
[1] TRUE

这也适用于我笔记本电脑上的较大示例。它并不快，因为您正在对 f 进行 nrow(data) 调用，但它确实避免了创建一个大对象。可能有更好的解决方案，但这是第一个浮现在脑海中的有效解决方案。希望对您有所帮助。

编辑：

已编辑，因为 Roland 有一个额外的 C++ 答案我对较小的数据集进行了快速基准测试。在这种情况下，C++ 答案肯定更快。如果您是纯粹的 R 程序员（无需学习 C++ 和 RCpp），我认为这个答案的一些额外推销是更容易理解的。使用 lapply 的并行替换，R 版本很容易并行化。我会注意到这并不是要剥夺 Rolands 的回答，我个人喜欢 Rcpp，只是为了为这个问题的任何未来读者提供额外的信息。

Answer 2

使用 Rcpp，因为基础 R 解决方案太慢：

library(Rcpp)
library(inline)
cppFunction(
"  IntegerVector findLowestDist(const NumericMatrix X) {
    const int n = X.nrow();
    const int m = X.ncol();
    IntegerVector minind(n);
    NumericVector minsqdist(n);
    double d;
    for (int i = 0; i < n; ++i) {
      if (i == 0) {
        d = 0;
        for (int k = 0; k < m; ++k) {
          d += pow(X(i, k) - X(1, k), 2.0);

        }
        minsqdist(i) = d;
        minind(i) = 1;
      } else {
        d = 0;
        for (int k = 0; k < m; ++k) {
          d += pow(X(i, k) - X(0, k), 2.0);

        }
        minsqdist(i) = d;
        minind(i) = 0;
      }

      for (int j = 1; j < n; ++j) {
        if (i == j) continue;
        d = 0;
        for (int k = 0; k < m; ++k) {
          d += pow(X(i, k) - X(j, k), 2.0);

        }
        if (d < minsqdist(i)) {
          minsqdist(i) = d;
          minind(i) = j;
        }
      }
    }
    return minind + 1;
  }"
)

all.equal(findLowestDist(as.matrix(data_100)),
          unlist(low_dis_ids))
#[1] TRUE

findLowestDist(as.matrix(data_100000))
#works

算法或许可以改进。

查找大型矩阵行之间的最小距离：分配限制错误

Find lowest distances between rows of a large matrix: Allocation limit error

allocation

r

distance

euclidean-distance