Матрица параллельного расстояния в R

Ответ 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)

Ответ 2

Пакет R amap обеспечивает надежные и параллельные функции для кластеризации и анализа основных компонентов. Среди этих функций метод Dist предлагает то, что вы ищете: вычисляет и возвращает матрицу расстояний параллельно.

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

В приведенном выше коде вычисляется эвклидовое расстояние с 8 потоками.

Ответ 3

Я - пользователь Windows, ищущий эффективный способ вычисления матрицы расстояния для ее использования в иерархической кластеризации (например, с помощью функции hclust из пакета "stats" ). Функция Dist не работает параллельно в Windows, поэтому мне пришлось искать что-то другое, и я нашел "wordpace" package Stefan Evert, который содержит 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

Он не решает его параллельно, но достаточно во многих случаях.

Ответ 4

Я также работаю с несколькими большими матрицами расстояний и стараюсь ускорить вычисление. Возможно, Бенсон, вероятно, будет прав, когда он скажет, что "время запуска функции и экспорта переменных в кластер, вероятно, будет больше, чем просто использование".

Однако, я думаю, это относится к матрицам расстояний с малым и средним размером. Ниже приведен пример ниже, используя функции Dist из пакета amap с 10 процессорами, Dist из пакета статистика и rdist из полей пакета , который вызывает функцию Fortran. В первом примере создается матрица расстояний 400 x 400. Второй создает матрицу расстояний 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

Обратите внимание на то, как время вычисления уменьшилось с 0.09845328 секунд до 0,05900002 с с использованием Dist по сравнению с Dist, когда матрица расстояния была большой (3103 x 3103). Поэтому я предлагаю вам использовать функцию Dist из пакета amap, если у вас есть несколько доступных процессоров.

Ответ 5

Вы также можете использовать функцию parDist пакета parallelDist, который специально создан для вычисления распараллелированных расстояний. Преимущества в том, что пакет доступен в Mac OS, Windows и Linux и уже поддерживает 39 различных дистанционных мер (см. parDist).

Сравнение производительности для расстояния в манхэттене (спецификация Sys: Mac OS, Intel Core i7 с 4 ядрами с частотой 2,5 ГГц и поддержкой гиперпотока):

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 vignette.

Ответ 6

Я обнаружил, что parallelDist на порядок быстрее, чем dist, и пережевывает гораздо меньше виртуальной памяти в процессе, на моем Mac под Microsoft R Open 3.4.0. Однако слово предупреждения - мне не удавалось скомпилировать его на R 3.3.3. Он не перечисляет версию R в качестве зависимости, но я подозреваю, что это так.