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

Question

首先,我是R的新手(我昨天开始).

我有两个组的点,data和centers,大小中的第一个n和大小的第二K(例如,n = 3823和K = 10),并为每个i在第一盘,我需要找到j在第二位的最小距离.

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

每个点都是一个64双打数组,所以

> 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 

在我的笔记本上.