21

行列があり、ポイント間のユークリッド距離NxMの行列を計算したいと考えています。私の問題では、約100,000です。この行列を k 最近傍アルゴリズムに使用する予定であるため、最小距離のみを保持する必要があるため、結果の行列は非常にまばらになります。これは、たとえば、密な行列になる (およびおそらく私のサイズのストレージの問題) から得られるものとは対照的です。NxNMNkNxNdist()N

これまでに見つけた kNN のパッケージ ( knnflex、kknnなど) はすべて、密行列を使用しているようです。また、Matrixパッケージはペアワイズ距離機能を提供しません。

私の目標に近づくと、spamパッケージには、nearest.dist()あるしきい値未満の距離のみを考慮することができる機能があることがわかりますdelta。ただし、私の場合、特定の値deltaによって生成される距離が多すぎる (行列を密に格納する必要があるNxN) か、距離が少なすぎる (kNN を使用できない) 場合があります。

パッケージを使用してk-means クラスタリングを実行しようとする以前の議論を見bigmemory/biganalyticsたことがありますが、この場合、これらの方法を活用できないようです。

Rで疎な方法で距離行列を計算する関数/実装を知っている人はいますか? 私の (恐ろしい) バックアップ計画は、2 つのforループを持ち、結果をMatrixオブジェクトに保存することです。

4

3 に答える 3

3

今のところ、この回答に触発されて、次を使用しています。出力は、要素が にth 番目に近いデータ ポイントのインデックスであるn x k行列です。(i,k)ki

n <- 10
d <- 3
x <- matrix(rnorm(n * d), ncol = n)

min.k.dists <- function(x,k=5) {
  apply(x,2,function(r) {
    b <- colSums((x - r)^2)
    o <- order(b)
    o[1:k]
  })
}

min.k.dists(x)  # first row should be 1:ncol(x); these points have distance 0
dist(t(x))      # can check answer against this

ネクタイの扱いなど気になる方はrank()取り入れたほうがいいかもしれません。

C上記のコードはやや高速に見えますが、改善できると確信しています (ただし、 orfortranルートに行く時間はありません)。だから私はまだ上記の高速でまばらな実装にオープンです。

以下に、最終的に使用することになった並列化されたバージョンを含めます。

min.k.dists <- function(x,k=5,cores=1) {
  require(multicore)
  xx <- as.list(as.data.frame(x))
  names(xx) <- c()
  m <- mclapply(xx,function(r) {
    b <- colSums((x - r)^2)
    o <- order(b)
    o[1:k]
  },mc.cores=cores)
  t(do.call(rbind,m))
}
于 2011-04-06T16:03:00.573 に答える
1

min.k.dist 関数のロジックを保持し、重複した距離を返したい場合は、少し変更することを検討してください。最初の行を距離 0 で返すのは無意味に思えますよね? ...そして、私の他の回答にいくつかのトリックを組み込むことで、バージョンを約 30% 高速化できます。

min.k.dists2 <- function(x, k=4L) {
  k <- max(2L, k + 1L)
  apply(x, 2, function(r) {
    sort.list(colSums((x - r)^2), na.last=NA, method='quick')[2:k]
  })
}

> n<-1e4; m<-3; m=matrix(runif(n*m), n)
> system.time(d <- min.k.dists(t(m), 4)) #To get 3 nearest neighbours and itself
   user  system elapsed 
  17.26    0.00   17.30 
> system.time(d <- min.k.dists2(t(m), 3)) #To get 3 nearest neighbours
   user  system elapsed 
   12.7     0.0    12.7
于 2011-04-07T15:54:59.147 に答える