R中的平行距离矩阵

Question

目前我在R中使用内置函数dist来计算距离矩阵。

dist(featureVector,method="manhattan")

目前这是应用程序的瓶颈，因此想法是并行化这个任务（从概念上讲应该是可能的）。

在谷歌和这个论坛中搜索都没有成功。

有人有什么主意吗？

- Vespasian

---

你能提供一个featureVector的例子吗？ - Arun

特征向量只是一个数据框，有100列和大约2000行。这些列是单个维度的值。 - Vespasian

在我的机器上，执行需要大约0.05秒，你的情况呢？我觉得任何并行操作可能会有更长的开销。只是为了确认一下，你期望的输出是一个100乘以100的矩阵，对吗？ - flodel

你应该提供完整的R代码来创建输入数据和system.time调用的输出，以便更容易地重现和理解你的问题。 - Karl Forner

请提供一个可重现的示例并进行基准测试。 - Karl Forner

Answer 1

R软件包amap提供了用于聚类和主成分分析的鲁棒且可并行化的函数。其中，Dist方法提供了您要查找的内容：以并行方式计算并返回距离矩阵。

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

上面的代码使用8个线程计算欧几里得距离。

- Zhilong Jia

---

R函数amap::Dist是dist函数的多线程版本（并行化），我认为这是最好的选择！参考链接：http://www.inside-r.org/packages/cran/amap/docs/Dist - Zhilong Jia

我完全同意，这是最好的答案！ - WAF

谢谢您的回答。然而，我无法确定amap的hcluster()是否可以使用距离矩阵，或者它是否绝对需要原始数据？ - Maxim.K

从手册中可以看出，@Maxim.K只接受原始数据而不是距离数据，并且在设置了nbproc和method参数之后，距离矩阵应该在内部进行并行计算。参考链接：http://www.inside-r.org/packages/cran/amap/docs/hcluster - Zhilong Jia

请注意，根据文档，此软件包不支持在Windows上进行并行处理。 - Omri374

Answer 2

你还可以使用parallelDist包的parDist函数，该函数专门用于并行计算距离矩阵。这个包在Mac OS、Windows和Linux上都可用，并且已经支持了39种不同的距离测量方法（请参见parDist）。对于曼哈顿距离的性能比较（系统规格：Mac OS；Intel Core i7，4个核心@2.5 GHz和超线程启用）：

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 中找到更多的性能比较信息。

- Aeck

Answer 3

这里是可能使用的一条路径的结构。 这种方法不比只使用 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)

- Will Beason

Answer 4

我是一个Windows用户，正在寻找一种高效的方法来计算距离矩阵，以便在分层聚类中使用（例如使用“stats”包中的hclust函数）。由于在Windows系统中，Dist函数不能并行运行，因此我必须寻找其他解决方案，然后我发现了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") ))

可以看到，使用dist.matrix计算具有1000个二进制特征和5000个实例的数据框的距离矩阵速度更快。

以下是在我的笔记本电脑(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

虽然它不能并行解决问题，但在许多情况下已足够。

- Ángel De Jaén Gotarredona

---

dist.matrix确实非常快，但无法处理NA值。是否有解决方案也能处理NA值？ - Omry Atia

Answer 5

我也在处理较大的距离矩阵，并尝试加快计算速度。当Will Benson说“启动函数和向集群导出变量的时间可能比直接使用更长”时，他很可能是正确的。

然而，我认为这适用于小到中等大小的距离矩阵。请参见以下示例，其中使用来自软件包 amap 的 Dist 函数（使用10个处理器），来自软件包 stats 的 dist 函数以及调用Fortran函数的软件包 fields 的 rdist 。第一个示例创建了一个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

请注意，当距离矩阵较大（3103 x 3103）时，使用Dist相比于dist计算时间从0.09845328秒降至0.05900002秒。因此，如果您有多个处理器可用，我建议您使用amap包中的Dist函数。

- Samuel-Rosa

Answer 6

我发现在我的Mac上，Microsoft R Open 3.4.0下的parallelDist比dist快了几个数量级，并且在过程中消耗的虚拟内存要少得多。但是需要注意的是 - 我在R 3.3.3上编译它没有成功。虽然它没有将R版本列为依赖项，但我认为它是必须的。

- Nick