У меня есть data.frame элементов, идентифицируемых целочисленным свойством ID, которое также является номером строки data.frame.
Каждый элемент имеет связанный с ним вектор признаков FP. Элементы каждого FP уникальны (в пределах этого FP). Так, например, c(1,2,7), но никогда c(1,7,7).
Расстояние Танимото между любыми двумя ID определяется как 1 минус число уникальных элементов на пересечении их FP, деленное на количество уникальных элементов в объединении их FP.
Мне нужно вычислить такие расстояния в контексте алгоритма '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.tab в приведенном ниже коде, где я опустил знаменатель, который тривиально вычислить на пересечении) и определил функцию расстояния как векторные операции, но это было намного медленнее (немного к моему удивлению, я должен сказать).
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 в качестве именованного списка.
Кстати, только к вашему сведению, в этом конкретном примере c матрица полной дистанции вычисляется довольно быстро:
system.time(ddu.dist <- dist(ddu.tab, method = "binary"))
# user system elapsed
# 0.61 0.00 0.61
, что, по-видимому, указывает на то, что действительно существует быстрый метод для вычисления двоичных расстояний.
Если кто-то мог бы посоветовать и / или указать мне соответствующие ресурсы, было бы здорово.
Спасибо!