r - 在R中有效地计算一个点和一组点之间的所有距离

Question

首先，我是 R 的新手(我昨天开始的)。

我有两组积分，data和 centers ，第一个大小n和第二个大小 K (例如， n = 3823 和 K = 10 )，并且对于每个 i在第一组中，我需要找到 j在第二个最小距离。

我的想法很简单:对于每个 i , 让 dist[j]是 i 之间的距离和 j ，我只需要使用which.min(dist)找到我要找的东西。

每个点都是 64 的数组 double ，所以

> dim(data)
[1] 3823   64
> dim(centers)
[1] 10 64

我试过

for (i in 1:n) {
  for (j in 1:K) {
    d[j] <- sqrt(sum((centers[j,] - data[i,])^2))
  }
  S[i] <- which.min(d)
}

这是非常慢的(使用 n = 200 ，需要超过 40 秒!!)。我写的最快的解决方案是

distance <- function(point, group) {
  return(dist(t(array(c(point, t(group)), dim=c(ncol(group), 1+nrow(group)))))[1:nrow(group)])
}

for (i in 1:n) {
  d <- distance(data[i,], centers)
  which.min(d)
}

即使它做了很多我不使用的计算(因为 dist(m) 计算 m 的所有行之间的距离)，它也比另一个更快(谁能解释为什么？)，但它速度不够快，无法满足我的需要，因为它不会只使用一次。而且， distance代码非常丑陋。我试图用它替换它

distance <- function(point, group) {
  return (dist(rbind(point,group))[1:nrow(group)])
}

但这似乎慢了两倍。我也尝试使用 dist对于每一对，但它也更慢。

我现在不知道该怎么办。好像我做错了什么。关于如何更有效地做到这一点的任何想法？

ps:我需要这个来手动实现k-means(我需要这样做，这是作业的一部分)。我相信我只需要欧几里得距离，但我还不确定，所以我更喜欢有一些可以轻松替换距离计算的代码。 stats::kmeans在不到一秒的时间内完成所有计算。

Answer 1

您可以将其压缩为矩阵运算，而不是遍历数据点，这意味着您只需遍历 K .

# Generate some fake data.
n <- 3823
K <- 10
d <- 64
x <- matrix(rnorm(n * d), ncol = n)
centers <- matrix(rnorm(K * d), ncol = K)

system.time(
  dists <- apply(centers, 2, function(center) {
    colSums((x - center)^2)
})
)

运行于:

utilisateur     système      écoulé 
      0.100       0.008       0.108 

在我的笔记本电脑上。