12

まず第一に、私はRに不慣れです（私は昨日始めました）。

ポイントの2つのグループがdataありcenters、最初のグループはサイズn、2番目のグループはサイズK（たとえば、n = 3823）K = 10であり、最初のセットのそれぞれについて、最小距離で2番目のグループiを見つける必要があります。j

私の考えは単純です。それぞれiについて、dist[j]との間の距離をとるiと、探しているものを見つけるためjに使用するだけで済みます。which.min(dist)

各ポイントは64doubleの配列であるため、

> 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)])
}

しかし、これは2倍遅いようです。distペアごとに使ってみましたが、遅いです。

今どうしたらいいのかわからない。私は何か非常に間違ったことをしているようです。これをより効率的に行う方法について何かアイデアはありますか？

ps：k-meansを手動で実装するには、これが必要です（これを実行する必要があります。これは、割り当ての一部です）。必要なのはユークリッド距離だけだと思いますが、まだわからないので、距離の計算を簡単に置き換えることができるコードを用意したいと思います。stats::kmeansすべての計算を1秒未満で実行します。

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関数であり、行列形式の2セットの点間の距離をすばやく計算できます。

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

関数を調べたいと思うかもしれません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

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のヘルプを確認してください。いくつかの例については、 SOを検索できます（例： https ：//stackoverflow.com/search？q = [r] + avoid + loop（このリンクをコピーして貼り付けます。クリック可能にする方法はありません）。rowSumspmaxcumsum

于 2010-06-12T21:22:34.853 に答える
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 に答える