Matriz de distancia paralela en R

matrix parallel-processing

Question

Actualmente estoy usando la función build in dist para calcular mi matriz de distancia en R.

dist(featureVector,method="manhattan")

Este es actualmente el punto de partida de la aplicación y, por lo tanto, la idea era paralizar esta tarea (conceptualmente esto debería ser posible)

La búsqueda de google y este foro no tuvo éxito.

¿Alguien tiene una idea?

Answer 1

Aquí está la estructura para una ruta que podría ir. No es más rápido que simplemente usar la función dist() , sino que demora muchas veces más. Se procesa en paralelo, pero incluso si el tiempo de cálculo se redujera a cero, el tiempo para iniciar la función y exportar las variables al clúster probablemente sea más largo que solo usar 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 2

Descubrí que parallelDist son órdenes de magnitud más rápidas que dist, y consumen mucha menos memoria virtual en el proceso, en mi Mac bajo Microsoft R Open 3.4.0. Sin embargo, una advertencia: no he tenido la suerte de compilarlo en R 3.3.3. No enumera la versión de R como una dependencia, pero sospecho que lo es.

Answer 3

El paquete R amap proporciona funciones robustas y paralelizadas para la agrupación y el análisis de componentes principales. Entre estas funciones, el método Dist ofrece lo que está buscando: calcula y devuelve la matriz de distancia de forma paralela.

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

El código anterior calcula la distancia euclidiana con 8 hilos.

Answer 4

Soy un usuario de Windows que busca una manera eficiente de calcular la matriz de distancia para usarla en un agrupamiento jerárquico (por ejemplo, mediante la función hclust del paquete "stats"). La función Dist no funciona en paralelo en Windows, así que tuve que buscar algo diferente, y encontré el paquete de "espacio de palabras" de Stefan Evert que contiene la función dist.matrix . Puedes probar este código:

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") ))

Como puede ver, calcular la matriz de distancia para un marco de datos con 1000 funciones binarias y 5000 instancias es mucho más rápido con dist.matrix

Estos son los resultados en mi laptop (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 

Esto solucionó mi problema. Aquí puede consultar el hilo original donde lo encontré: http://r.789695.n4.nabble.com/Efficient-distance-calculation-on-big-matrix-td4633598.html

No se resuelve en paralelo, pero es suficiente en muchas ocasiones.

Answer 5

También estoy trabajando con matrices de distancia algo grandes y tratando de acelerar el cálculo. Es probable que Will Benson sea correcto cuando dice que "el tiempo para iniciar la función y exportar las variables al clúster probablemente sea más largo que solo usar".

Sin embargo, creo que esto se aplica a matrices de distancia de tamaño pequeño a moderado. Vea el ejemplo de abajo usando las funciones Dist del paquete amap con 10 procesadores, dist de las estadísticas del paquete y rdist de los campos del paquete, que llama a una función de Fortran. El primer ejemplo crea una matriz de 400 x 400 distancias. El segundo crea una matriz de distancia de 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

Observe cómo el tiempo de cálculo se redujo de 0.09845328 segundos a 0.05900002 segundos usando Dist comparación con dist cuando la matriz de distancia era grande (3103 x 3103). Como tal, sugeriría que use la función Dist del paquete amap siempre que tenga varios procesadores disponibles.

Answer 6

También puede usar la función parDist del paquete parallelDist , que se construye específicamente para cálculos de matriz de distancia paralelizados. Las ventajas son que el paquete está disponible en Mac OS, Windows y Linux y ya es compatible con 39 medidas de distancia diferentes (ver parDist ).

Comparación de rendimiento para la distancia de Manhattan (especificación del sistema: Mac OS; Intel Core i7 con 4 cores @ 2,5 GHz y hyperthreading habilitado):

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

Con una matriz más grande:

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

Otras comparaciones de rendimiento se pueden encontrar en la vignette parallelDist .