（速度挑战）根据通用汉明距离计算距离矩阵的任何更快的方法？

Question

我正在寻找一种更有效的方法来根据 Hamming distance 获得距离矩阵。

背景

我知道包 e1071 中有一个函数 hamming.distance() 可以计算距离矩阵，但我怀疑在涉及多行的大矩阵时它可能会很慢，因为它应用了嵌套for 循环计算。

到目前为止，我在下面的代码中有一个更快的方法（参见 methodB）。但是，它只适用于二进制域，即{0,1}^n。但是，当遇到由 2 个以上元素组成的域时，即 {0,1,2,...,K-1}^n 时，它不可用。从这个意义上说，methodB 不适用于通用汉明距离。

Objective

我的objective是寻找具有以下特点的方法：

仅由基本 R 的函数组成（不使用 Rcpp 重写函数以加快速度）
对于特殊情况 k=2

methodB()

可以泛化为任何正整数k
优于包 e1071

hamming.distance()

我的代码

library(e1071)
# vector length, i.e., number of matrix
n <- 7
# number of elements to consist of domain {0,1,...,k-1}^n
k <- 2
# matrix for computing hamming distances by rows
m <- as.matrix(do.call(expand.grid,replicate(n,list(0:k-1))))

# applying `hamming.distance()` from package "e1071", which is generic so it is available for any positive integer `k`
methodA <- function(M) hamming.distance(M)
# my customized method from base R function `dist()`, which is not available for cases `k >= 2`
methodB <- function(M) as.matrix(round(dist(M,upper = T,diag = T)**2))

基准给出

microbenchmark::microbenchmark(
  methodA(m),
  methodB(m),
  unit = "relative",
  check = "equivalent",
  times = 50
)

Unit: relative
       expr      min       lq   mean   median       uq      max neval
 methodA(m) 33.45844 33.81716 33.963 34.30313 34.92493 14.92111    50
 methodB(m)  1.00000  1.00000  1.000  1.00000  1.00000  1.00000    50

先睹为快！

Answer 1

methodM <- function(x) {
  xt <- t(x)
  sapply(1:nrow(x), function(y) colSums(xt != xt[, y]))
}
microbenchmark::microbenchmark(
  methodB(m), methodM(m),
  unit = "relative", check = "equivalent", times = 50
)
# Unit: relative
#       expr  min       lq     mean   median       uq      max neval cld
# methodB(m) 1.00 1.000000 1.000000 1.000000 1.000000 1.000000    50  a 
# methodM(m) 1.25 1.224827 1.359573 1.219507 1.292463 4.550159    50   b

Answer 2

您尝试使用 Rcpp 了吗？我有一个非常相似的问题！请在此处查看答案：

Answer 3

我发现这个博客有四篇关于计算汉明矩阵的文章。我不想为此声名狼藉，但也许可以看看它。 https://johanndejong.wordpress.com/2015/10/02/faster-hamming-distance-in-r-2/

hamming <- function(X) {
  D <- (1 - X) %*% t(X)
  D + t(D)
}

> microbenchmark::microbenchmark(
+   methodB(m),
+   hamming(m),
+   unit = "relative",
+   times = 50
+ )
Unit: relative
       expr    min       lq     mean   median       uq      max neval
 methodB(m) 1.0000 1.000000 1.000000 1.000000 1.000000 1.000000    50
 hamming(m) 1.2502 1.299844 1.436486 1.301461 1.302033 4.607748    50

PS：我没有足够的声望只留下评论。

（速度挑战）根据通用汉明距离计算距离矩阵的任何更快的方法？

(Speed Challenge) Any faster way to compute distance matrix in terms of generic Hamming distance?

algorithm

performance

r

matrix

hamming-distance