Матрица параллельного расстояния в R
В настоящее время я использую встроенную функцию dist для вычисления матрицы расстояний в R.
dist(featureVector,method="manhattan")
В настоящее время это является узким местом приложения, и поэтому идея состояла в том, чтобы парализовать эту задачу (концептуально это должно быть возможно)
Поиск в гугле и на этом форуме не удался.
У кого-нибудь есть идея?
6 ответов
Вот структура для одного маршрута, который вы могли бы пройти. Это не быстрее, чем просто использование 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)
Пакет R amap предоставляет надежные и распараллеленные функции для кластеризации и анализа основных компонентов. Среди этих функций метод Dist предлагает то, что вы ищете: вычисляет и возвращает матрицу расстояний параллельно.
Dist(x, method = "euclidean", nbproc = 8)
Приведенный выше код вычисляет евклидово расстояние с 8 потоками.
Вы также можете использовать parDist функция пакета parallelDist, специально созданного для параллельных вычислений матрицы расстояний. Преимущества заключаются в том, что пакет доступен в Mac OS, Windows и Linux и уже поддерживает 39 различных мер расстояния (см. ParDist).
Сравнение производительности для манхэттенского расстояния (спецификации системы: 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 Виньетка.
Я - пользователь Windows, который ищет эффективный способ вычисления матрицы расстояний, чтобы использовать ее в иерархической кластеризации (например, используя функцию hclust из пакета "stats"). Функция Dist не работает параллельно в Windows, поэтому мне пришлось искать что-то другое, и я обнаружил пакет "пространство слов" 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
Это не решает это параллельно, но этого достаточно во многих случаях.
Я также работаю с матрицами с большим расстоянием и пытаюсь ускорить вычисления. Уилл Бенсон выше, вероятно, будет прав, когда говорит, что "время запуска функции и экспорта переменных в кластер, вероятно, будет дольше, чем просто использование".
Тем не менее, я думаю, что это относится к матрицам расстояний с небольшим или средним размером. Смотрите пример ниже, используя функции 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 х 3103). Поэтому я бы предложил вам использовать функцию Dist из пакета amap, если у вас есть несколько доступных процессоров.
Я обнаружил, что параллельный Dist на несколько порядков быстрее, чем dist, и в процессе затрачивает гораздо меньше виртуальной памяти на моем Mac под Microsoft R Open 3.4.0. Слово предупреждения, хотя - мне не повезло, компилируя его на R 3.3.3. Это не перечисляет версию R как зависимость, но я подозреваю, что это так.