如何在R中建立快速成对Tanimoto距离函数

Question

我有一个由整数属性ID标识的项的ID，它也是data.frame的行号。

每个项目都有一个与其关联的特性向量( FP )。每个FP的元素都是唯一的(在该FP中)。例如，c(1,2,7)，但从来没有c(1,7,7)。

任意两个ID之间的Tanimoto距离定义为1减去它们的FP's交集中的唯一元素数，除以它们的FP's的合并中的唯一元素数。

我需要在“maxmin”算法的上下文中计算这样的距离。例如，参见这篇博客文章。

需要注意的最重要的一点是，我必须而不是计算一个全距离矩阵(即使使用最好的算法，在我所使用的数据集的规模上也是不可行的)。

正如上面的文章所解释的，根据Roger Sayle的方法，迭代maxmin选择器的强度是可以避免计算大部分成对距离的，而只计算少数相关的距离。这就是我的问题。

到目前为止，我能想到的是：

# make a random dataset

set.seed(1234567)
d <- sample(30:45, 1000, replace = T)
dd <- setNames(data.frame(do.call(rbind, sapply(d,function(n) list(sample(as.character(1:(45*2)), n, replace = F)), simplify = F))), "FP")
dd["ID"] <- 1:NROW(dd)

# define a pairwise distance function for ID's

distfun <- function(ID1,ID2) {
  FP1 <- dd$FP[[ID1]]
  FP2 <- dd$FP[[ID2]]
  int <- length(intersect(FP1,FP2))
  1 - int/(d[ID1]+d[ID2]-int)
}

# test performance of distance function

x <- sample(dd$ID, 200, replace = F)
y <- sample(dd$ID[!(dd$ID %in% x)], 200, replace = F)

pairwise.dist <- NULL

system.time(
  for(i in x) {
    for (j in y) {
      dij <- distfun(i,j)
      #pairwise.dist <- rbind(pairwise.dist,c(min(i,j),max(i,j),dij))
    }
  }
)   
#   user  system elapsed 
#   0.86    0.00    0.86 

问题1：你认为距离函数可以变得更快吗？

我尝试为这些特性创建一个稀疏矩阵(在下面的代码中，我省略了分母，这是从交集中计算出来的)，并将距离函数定义为向量操作，但这要慢得多(我不得不说，这让我有点惊讶)。

ddu <- do.call(rbind, sapply(dd$ID, function(x) {data.frame("ID"=x, "FP"=dd$FP[[x]], stringsAsFactors = F)}, simplify = F))
ddu.tab <- xtabs(~ID+FP, ddu, sparse = T)
system.time(
  for(i in x) {
    for (j in y) {
      dij <- t(ddu.tab[i,]) %*% ddu.tab[j,]
      #pairwise.dist <- rbind(pairwise.dist,c(min(i,j),max(i,j),dij))
    }
  }
)
#   user  system elapsed 
#  32.35    0.03   32.66 

问题2：实际上不像距离计算那么重要，但是如果有人能建议.pairwise.dist的rbind更新(显然)非常昂贵。我不知道我是否可以以不同的方式(意思是在每次迭代中不添加新元素)，因为在maxmin应用程序中，要计算距离的ID对并不像本例中那样预先知道，而且pairwise.dist是连续读取和追加新元素的。

过去有人向我建议，列表可能比读/写矩阵更好。如果是这样的话，我可以将pairwise.dist写成一个命名列表。

顺便说一下，FYI，在这个具体的例子中，全距离矩阵计算得相当快：

system.time(ddu.dist <- dist(ddu.tab, method = "binary"))
#   user  system elapsed 
#   0.61    0.00    0.61 

这似乎表明，确实有一种快速计算二进制距离的方法。

如果有人能给我建议和/或指出相关的资源，那就太好了。

谢谢!

Answer 1

不确定是否要加快距离函数本身，但是您可以使用tidyverse替换双循环

library(tidyverse)

results <- crossing(x = x, y = y) %>%             #all x,y combinations
  filter(x < y) %>%                               #remove duplicates
  mutate(pairwise.dist = map2_dbl(x, y, distfun)) #apply distance function