计算两个整数矩阵/数据帧的所有行之间的成对汉明距离

Question

我有两个数据框，df1包含参考数据和df2新数据。对于 中的每一行，我需要根据汉明距离df2找到最佳（和第二最佳）匹配行。df1

我使用e1071包来计算汉明距离。两个向量之间的汉明距离x可以y计算如下：

x <- c(356739, 324074, 904133, 1025460, 433677, 110525, 576942, 526518, 299386,
       92497, 977385, 27563, 429551, 307757, 267970, 181157, 3796, 679012, 711274,
       24197, 610187, 402471, 157122, 866381, 582868, 878)

y <- c(356739, 324042, 904133, 959893, 433677, 110269, 576942, 2230, 267130,
       92496, 960747, 28587, 429551, 438825, 267970, 181157, 36564, 677220,
       711274, 24485, 610187, 404519, 157122, 866413, 718036, 876)

xm <- sapply(x, intToBits)
ym <- sapply(y, intToBits)

distance <- sum(sapply(1:ncol(xm), function(i) hamming.distance(xm[,i], ym[,i])))

结果距离是 25。但是我需要对df1和的所有行执行此操作df2。一个简单的方法需要一个双循环嵌套，看起来非常慢。

有什么想法可以更有效地做到这一点吗？最后我需要附加到df2：

• df1具有距离最短距离的行 id 的列；
• 距离最近的一列；
• 具有行 id 的列df1给出第二小的距离；
• 距离第二短的列。

谢谢。

Answer 1

快速计算两个等长整数向量之间的汉明距离

正如我在评论中所说，我们可以这样做：

hmd0 <- function(x,y) sum(as.logical(xor(intToBits(x),intToBits(y))))

计算两个长度相等的整数向量 x和之间的汉明距离y。这仅使用 R 基，但比 更有效e1071::hamming.distance，因为它是矢量化的！

对于示例x和y您的帖子，这给出了 25。（我的其他答案将显示如果我们想要成对汉明距离，我们应该做什么。）

矩阵和向量之间的快速汉明距离

如果我们想计算单个y和多个xs之间的汉明距离，即向量和矩阵之间的汉明距离，我们可以使用以下函数。

hmd <- function(x,y) {
  rawx <- intToBits(x)
  rawy <- intToBits(y)
  nx <- length(rawx)
  ny <- length(rawy)
  if (nx == ny) {
    ## quick return
    return (sum(as.logical(xor(rawx,rawy))))
    } else if (nx < ny) {
    ## pivoting
    tmp <- rawx; rawx <- rawy; rawy <- tmp
    tmp <- nx; nx <- ny; ny <- tmp
    }
  if (nx %% ny) stop("unconformable length!") else {
    nc <- nx / ny  ## number of cycles
    return(unname(tapply(as.logical(xor(rawx,rawy)), rep(1:nc, each=ny), sum)))
    }
  }

注意：

1. hmd按列执行计算。它被设计为CPU 缓存友好。这样，如果我们想做一些按行计算，我们应该先转置矩阵；
2. 这里没有明显的循环；相反，我们使用tapply().

两个矩阵/数据帧之间的快速汉明距离计算

这就是你想要的。以下函数foo采用两个数据框或矩阵df1和，计算和 每行df2之间的距离。参数是一个整数，显示您要保留的结果数量。将保留行 id 中最小的 3 个距离。df1df2pp = 3df1

foo <- function(df1, df2, p) {
  ## check p
  if (p > nrow(df2)) p <- nrow(df2)
  ## transpose for CPU cache friendly code
  xt <- t(as.matrix(df1))
  yt <- t(as.matrix(df2))
  ## after transpose, we compute hamming distance column by column
  ## a for loop is decent; no performance gain from apply family
  n <- ncol(yt)
  id <- integer(n * p)
  d <- numeric(n * p)
  k <- 1:p
  for (i in 1:n) {
    distance <- hmd(xt, yt[,i])
    minp <- order(distance)[1:p]
    id[k] <- minp
    d[k] <- distance[minp]
    k <- k + p
    }
  ## recode "id" and "d" into data frame and return
  id <- as.data.frame(matrix(id, ncol = p, byrow = TRUE))
  colnames(id) <- paste0("min.", 1:p)
  d <- as.data.frame(matrix(d, ncol = p, byrow = TRUE))
  colnames(d) <- paste0("mindist.", 1:p)
  list(id = id, d = d)
  }

注意：

1. 换位是在开始时根据之前的原因进行的；
2. for这里使用了一个循环。但这实际上是有效的，因为每次迭代都会进行大量计算。它也比使用*applyfamily 更优雅，因为我们要求多个输出（行 idid和 distance d）。

实验

这部分使用小数据集来测试/演示我们的功能。

一些玩具数据：

set.seed(0)
df1 <- as.data.frame(matrix(sample(1:10), ncol = 2))  ## 5 rows 2 cols
df2 <- as.data.frame(matrix(sample(1:6), ncol = 2))  ## 3 rows 2 cols

先测试hmd（需要转置）：

hmd(t(as.matrix(df1)), df2[1, ])  ## df1 & first row of df2
# [1] 2 4 6 2 4

测试foo：

foo(df1, df2, p = 2)

# $id
#   min1 min2
# 1    1    4
# 2    2    3
# 3    5    2

# $d
#   mindist.1 mindist.2
# 1         2         2
# 2         1         3
# 3         1         3

如果您想向 追加一些列df2，您知道该怎么做，对吗？