12

首先，我是 R 新手（我昨天开始的）。

我有两组点，data和centers，第一组大小n和第二组大小K（例如，n = 3823和K = 10），对于i第一组中的每一个，我需要j在第二组中找到最小距离。

我的想法很简单：对于每个i，让和dist[j]之间的距离，我只需要用来找到我要找的东西。ijwhich.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在不到一秒的时间内完成所有计算。

4

5 回答 5

14

您可以将其压缩为矩阵运算，而不是遍历数据点，这意味着您只需遍历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

在我的笔记本电脑上。

于 2010-06-12T21:35:15.587 回答
4

rdist() 是来自 {fields} 包的 R 函数，它能够以矩阵格式快速计算两组点之间的距离。

https://www.image.ucar.edu/~nychka/Fields/Help/rdist.html

用法 ：

library(fields)
#generating fake data
n <- 5
m <- 10
d <- 3

x <- matrix(rnorm(n * d), ncol = d)
y <- matrix(rnorm(m * d), ncol = d)

rdist(x, y)
          [,1]     [,2]      [,3]     [,4]     [,5]
 [1,] 1.512383 3.053084 3.1420322 4.942360 3.345619
 [2,] 3.531150 4.593120 1.9895867 4.212358 2.868283
 [3,] 1.925701 2.217248 2.4232672 4.529040 2.243467
 [4,] 2.751179 2.260113 2.2469334 3.674180 1.701388
 [5,] 3.303224 3.888610 0.5091929 4.563767 1.661411
 [6,] 3.188290 3.304657 3.6668867 3.599771 3.453358
 [7,] 2.891969 2.823296 1.6926825 4.845681 1.544732
 [8,] 2.987394 1.553104 2.8849988 4.683407 2.000689
 [9,] 3.199353 2.822421 1.5221291 4.414465 1.078257
[10,] 2.492993 2.994359 3.3573190 6.498129 3.337441
于 2016-10-20T09:30:25.000 回答
1

dist工作速度很快，因为没有矢量化并调用内部 C 函数。
您可以通过多种方式对循环中的代码进行矢量化。

例如计算和之间的距离data，centers你可以使用outer：

diff_ij <- function(i,j) sqrt(rowSums((data[i,]-centers[j,])^2))
X <- outer(seq_len(n), seq_len(K), diff_ij)

这为您提供n x K了距离矩阵。并且应该比循环快得多。

然后您可以使用max.col在每一行中找到最大值（请参阅帮助，当有很多最大值时会有一些细微差别）。X必须是否定的，因为我们搜索最小值。

CL <- max.col(-X)

为了在 R 中高效，您应该尽可能矢量化。在许多情况下，循环可以被矢量化替代替代。检查帮助rowSums（也描述rowMeans, colSums, rowSums）, pmax, cumsum. 您可以搜索一些示例，例如 https://stackoverflow.com/search?q=[r]+avoid+loop（复制并粘贴此链接，我不知道如何使其可点击）。

于 2010-06-12T21:22:34.853 回答
1

你可能想看看这些apply功能。

例如，这段代码

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

可以很容易地被类似的东西代替

dt <- data[i,]
d <- apply(centers, 1, function(x){ sqrt(sum(x-dt)^2)})

您绝对可以对其进行更多优化，但我希望您明白这一点

于 2010-06-12T18:52:06.603 回答
1

我的解决方案：

# data is a matrix where each row is a point
# point is a vector of values
euc.dist <- function(data, point) {
  apply(data, 1, function (row) sqrt(sum((point - row) ^ 2)))
}

你可以试试，比如：

x <- matrix(rnorm(25), ncol=5)
euc.dist(x, x[1,])
于 2016-09-23T17:16:37.797 回答