r - Rの平行距離行列

Question

現在、組み込み関数 dist を使用して、R で距離行列を計算しています。

dist(featureVector,method="manhattan")

これは現在、アプリケーションのボトルネックであるため、このタスクを並列化するというアイデアがありました (概念的には可能であるはずです)。

Google とこのフォーラムを検索してもうまくいきませんでした。

誰かアイデアがありますか？

Answer 1

R パッケージamapは、クラスタリングと主成分分析のための堅牢で並列化された関数を提供します。これらの関数の中で、Distメソッドは探しているものを提供します: 距離行列を並列に計算して返します。

Dist(x, method = "euclidean", nbproc = 8)

上記のコードは、8 つのスレッドでユークリッド距離を計算します。

Answer 2

これは、あなたが行くことができる 1 つのルートの構造です。関数を使用するよりも高速ではdist()なく、何倍も時間がかかります。並列に処理されますが、計算時間がゼロに短縮されたとしても、関数を起動して変数をクラスターにエクスポートする時間は、単に使用するよりもおそらく長くなります。dist()

library(parallel)

vec.array <- matrix(rnorm(2000 * 100), nrow = 2000, ncol = 100)

TaxiDistFun <- function(one.vec, whole.matrix) {
    diff.matrix <- t(t(whole.matrix) - one.vec)
    this.row <- apply(diff.matrix, 1, function(x) sum(abs(x)))
    return(this.row)
}

cl <- makeCluster(detectCores())
clusterExport(cl, list("vec.array", "TaxiDistFun"))

system.time(dist.array <- parRapply(cl, vec.array,
                        function(x) TaxiDistFun(x, vec.array)))

stopCluster(cl)

dim(dist.array) <- c(2000, 2000)

Answer 3

また、並列化された距離行列計算用に特別に構築されたparallelDistparDistパッケージの関数を使用することもできます。利点は、パッケージが Mac OS、Windows、および Linux で利用可能であり、すでに 39 の異なる距離尺度をサポートしていることです ( parDistを参照)。

マンハッタン距離のパフォーマンス比較(システム仕様: Mac OS、4 コア @ 2,5 GHz およびハイパースレッディングが有効な Intel Core i7):

library(parallelDist)
library(amap)
library(wordspace)
library(microbenchmark)

set.seed(123)
x <- matrix(rnorm(2000 * 100), nrow = 2000, ncol = 100)

microbenchmark(parDist(x, method = "manhattan"),
               Dist(x, method = "manhattan", nbproc = 8),
               dist.matrix(x, method = "manhattan"),
               times = 10)

Unit: milliseconds
                                      expr      min       lq     mean   median       uq      max neval
          parDist(x, method = "manhattan") 210.9478 214.3557 225.5894 221.3705 237.9829 247.0844    10
 Dist(x, method = "manhattan", nbproc = 8) 749.9397 755.7351 797.6349 812.6109 824.4075 844.1090    10
      dist.matrix(x, method = "manhattan") 256.0831 263.3273 279.0864 275.1882 296.3256 311.3821    10

より大きな行列の場合:

x <- matrix(rnorm(10000 * 100), nrow = 10000, ncol = 100)
microbenchmark(parDist(x, method = "manhattan"),
+                Dist(x, method = "manhattan", nbproc = 8),
+                dist.matrix(x, method = "manhattan"),
+                times = 10)
Unit: seconds
                                      expr       min        lq      mean    median        uq       max neval
          parDist(x, method = "manhattan")  6.298234  6.388501  6.737168  6.894203  6.947981  7.221661    10
 Dist(x, method = "manhattan", nbproc = 8) 22.722947 24.113681 24.326157 24.477034 24.658145 25.301353    10
      dist.matrix(x, method = "manhattan")  7.156861  7.505229  7.544352  7.567980  7.655624  7.800530    10

さらなるパフォーマンスの比較は、parallelDist's vignetteにあります。

Answer 4

私は、距離行列を計算して階層的クラスタリングで使用する効率的な方法を探しているWindowsユーザーです（たとえば、「統計」パッケージの関数hclustを使用します）。関数Dist は Windows では並列に動作しないため、別のものを探す必要があり、関数を含む Stefan Evertの「wordspace」パッケージを見つけました。dist.matrixこのコードを試すことができます：

X <- data.frame(replicate(1000,sample(0:1,5000,rep=TRUE)))
system.time(d <- dist(X, method = "manhattan"))
system.time(d2 <- as.dist( dist.matrix(as.matrix(X), method="manhattan") ))

ご覧のとおり、1000 個のバイナリ機能と 5000 個のインスタンスを含むデータフレームの距離行列を計算すると、はるかに高速になります。dist.matrix

これらは私のラップトップ (i7-6500U) での結果です。

> system.time(d <- dist(X, method = "manhattan"))
   user  system elapsed 
 151.79    0.04  152.59 
> system.time(d2 <- as.dist( dist.matrix(as.matrix(X), method="manhattan") ))
   user  system elapsed 
  19.19    0.22   19.56 

これで私の問題は解決しました。ここで、私が見つけた元のスレッドを確認できます: http://r.789695.n4.nabble.com/Efficient-distance-calculation-on-big-matrix-td4633598.html

並行して解決するわけではありませんが、多くの場合は十分です。

Answer 5

また、やや大きな距離行列を使用して計算を高速化しようとしています。上記の Will Benson は、「関数を起動して変数をクラスターにエクスポートする時間は、単に使用するよりもおそらく長くなるだろう」と述べているため、おそらく正しいでしょう。

ただし、これは小規模から中程度のサイズの距離行列に当てはまると思います。Fortran 関数を呼び出すDistパッケージamapと 10 個のプロセッサ、distパッケージstats、およびrdistパッケージfieldsの関数を使用した以下の例を参照してください。最初の例では、400 x 400 の距離行列を作成します。2 つ目は、3103 x 3103 の距離行列を作成します。

require(sp)
require(fields)
require(amap)
data(meuse.grid)
meuse.gridA <- meuse.grid[1:400, 1:2]
meuse.gridB <- meuse.grid[, 1:2]

# small distance matrix
a <- Sys.time()
invisible(dist(meuse.gridA, diag = TRUE, upper = TRUE))
Sys.time() - a
Time difference of 0.002138376 secs
a <- Sys.time()
invisible(Dist(meuse.gridA, nbproc = 10, diag = TRUE, upper = TRUE))
Sys.time() - a
Time difference of 0.005409241 secs
a <- Sys.time()
invisible(rdist(meuse.gridA))
Sys.time() - a
Time difference of 0.02312016 secs

# large distance matrix
a <- Sys.time()
invisible(dist(meuse.gridB, diag = TRUE, upper = TRUE))
Sys.time() - a
Time difference of 0.09845328 secs
a <- Sys.time()
invisible(Dist(meuse.gridB, nbproc = 10, diag = TRUE, upper = TRUE))
Sys.time() - a
Time difference of 0.05900002 secs
a <- Sys.time()
invisible(rdist(meuse.gridB))
Sys.time() - a
Time difference of 0.8928168 secs

を使用すると、距離行列が大きい場合 (3103 x 3103)Distと比較して、計算時間が 0.09845328 秒から 0.05900002 秒に短縮されたことに注意してください。そのため、複数のプロセッサが利用可能な場合は、amapパッケージのdist関数を使用することをお勧めします。Dist