Я пытаюсь поставить эту проблему теоретически, и мне интересно, если кто-нибудь мог бы помочь / направить меня в правильном направлении.
Предположим, у вас есть коллекция объектов (каждый из которых уникально обозначен ID),каждая из которых имеет некоторые особенности (содержится в свойстве FP). Сценарий R ниже создает коллекцию из N = 20 таких объектов в data.frame dd:
set.seed(12345)
d <- sample(1:5,20,replace = T)
dd <- setNames(data.frame(do.call(rbind,sapply(d,function(n) list(sample(LETTERS,n)),simplify = F))),"FP")
dd["ID"] <- 1:NROW(dd)
Мне нужно разделить эти объекты на 2 набора (или кластера), один из которых должен иметь точноn (скажем, 7) объектов таким образом, чтобы перекрытие функций FP между двумя кластерами было минимальным.
Чтобы было понятно, что я называю перекрытием, если бы я создал кластер с первыми 7строк dd (и, следовательно, другого кластера с последними 13 строками), перекрытие будет 12:
length(intersect(unique(unlist(dd[1:7,"FP"])),unique(unlist(dd[8:20,"FP"]))))
#[1] 12
. Для этого простого примера я могу решить проблему, перечислив все возможности и посмотрев накакие кластеры дают наименьшее перекрытие (которое показывает, что существуют вырожденные решения, а минимальное возможное перекрытие равно 4):
gr <- t(combn(1:20,7))
result <- apply(gr,1,function(ids) {
length(intersect(unique(unlist(dd[ids,"FP"])),unique(unlist(dd[(1:20)[!(1:20 %in% ids)],"FP"]))))
})
result <- data.frame("cl1"=apply(gr,1,function(ids) paste(ids,collapse=",")),"overlap"=result)
min(result$overlap)
#[1] 4
Однако как бы вы решили это для более крупных проблем, когда подход с применением грубой силы невозможен?
И в некоторых случаях мне может понадобиться создать более 2 кластеров, что не помогает.
Я думаю о линейном программировании для неподвижного тракта. В некоторых случаях, или какой-то приблизительный метод для более сложных, но я не знаю, с чего начать поиск пакетов или литературы.
Я знаю, как сделать выбор объектов, набор уникальных функций которых максимизируется или минимизируется. , используя LP, но это мне кажется совсем другим - или я не прав?
EDIT 1 : работа в процессе
Возможно, эта задача похожа напроблема р-дисперсии, которая уже обсуждалась здесь .
За исключением, конечно, того факта, что в этом случае мне нужно выбрать n объектов, которые находятся как можно дальше друг от друга, а не отмножество невыбранных Nn объектов. Я думаю, что код может быть адаптирован;пока точно не знаю, как именно.
Но необходимость расчета матрицы парных расстояний может быть большим ограничением, когда N больше 10000. Поэтому здесь могут быть полезны приближенные методы.
Если я собираю исходные данные, обрабатывая объекты в FP как двоичные переменные, а затем табулируя:
ddu <- do.call(rbind,sapply(dd$ID,function(x) {data.frame("ID"=x,"FP"=unlist(dd[dd$ID == x,"FP"]),stringsAsFactors = F)},simplify = F))
ddu.tab <- xtabs(~ID+FP,ddu,sparse = T)
ddu.tab
#20 x 23 sparse Matrix of class "dgCMatrix"
# [[ suppressing 23 column names ‘B’, ‘C’, ‘D’ ... ]]
#
#1 . . . . . . . . . . . . . . 1 . . . . 1 . 1 .
#2 1 . . . . . . . . . . . . . . . . 1 . . . . .
#3 . . 1 . . . 1 1 . . . . . . . . . . . . . 1 .
#4 . . . . 1 . . . . 1 . . . . . . . . . . . . .
#5 . . . 1 . . . 1 . . . . . 1 . 1 1 . . . . . .
#6 . . . 1 . . . . 1 . . . . . . 1 . . . . . . .
#7 . 1 . . . . . . . . . . . . . . 1 . . . . . .
#8 . 1 . . . . . . . . . 1 . . . 1 . . . . . . .
#9 . . . . . . . . 1 . . . . . . . . . . . 1 . .
#10 . . . . . . . . . 1 . . . . . . . . . . . . .
#11 . . . . . . . . . . . . . . . . . . . . . 1 .
#12 1 . . . . . . . . . 1 . . . . . . 1 . . 1 . .
#13 . 1 . . . . . . . . . 1 . . . . 1 . 1 . . . .
#14 . . . . . . . . 1 . . . . . . . . . . 1 . . .
#15 . . . . . 1 . . . . . . . 1 . . . . . 1 . . 1
#16 . . . 1 . . . . . . . . 1 . . . . . . 1 . . .
#17 . . . . . . . . . . 1 . . . . . . . . . . . .
#18 . 1 . 1 . . . . . 1 . . . . . . . . . . 1 . 1
#19 . . 1 . . . . . . 1 . . . . . 1 . . . . . 1 .
#20 . 1 . . . . . . 1 . . . . . . . . . . . . . .
Если бы у меня был один кластер со всеми N объектами, конечно, все функции присутствовали бы:
colSums(ddu.tab)
#B C D E F G H I J K L M N O P Q S T V W X Y Z
#2 5 2 4 1 1 1 2 4 4 2 2 1 2 1 4 3 2 1 4 3 4 2
Глядя на colSums для одного из оптимальных решений, найденных методом грубой силы (объекты 1,2,4,10,11,12,17):
colSums(ddu.tab[c(1,2,4,10,11,12,17),])
#B C D E F G H I J K L M N O P Q S T V W X Y Z
#2 0 0 0 1 0 0 0 0 2 2 0 0 0 1 0 0 2 0 1 1 2 0
И его дополнение:
colSums(ddu.tab[-c(1,2,4,10,11,12,17),])
#B C D E F G H I J K L M N O P Q S T V W X Y Z
#0 5 2 4 0 1 1 2 4 2 0 2 1 2 0 4 3 0 1 3 2 2 2
В итерационной процедуре можно начать с одного пустого кластера CL1 и полного набора в качестве другого кластера CL2, и на каждой итерации найти объект в CL2, чтобы перейти кCL1 ищет минимальное перекрытие, останавливаясь, когда CL1 имеет n объектов. Пример:
CL1 <- numeric(0)
CL2 <- 1:20
while (length(CL1) < 7) {
ov <- NULL
for (i in 1:length(CL2)) {
tCL1 <- c(CL1,CL2[i])
tCL2 <- CL2[-i]
ov <- c(ov,sum(as.logical(colSums(ddu.tab[tCL1,,drop=F]))*as.logical(colSums(ddu.tab[tCL2,,drop=F]))))
}
i <- which.min(ov)
CL1 <- c(CL1,CL2[i])
CL2 <- CL2[-i]
}
В этом случае это дает решение с перекрытием 6, поэтому не является оптимальным (4).
Если у кого-то есть предложения о том, как улучшить это (или сделатьэто совершенно по-другому), они будут приветствоваться.
РЕДАКТИРОВАТЬ 2
Довольно очевидный факт ускользнул от меня.
В приведенном выше примере естьвсего М = 23 функции. Если кластер 1 содержит объекты m1, а кластер 2 содержит объекты m2, во всех случаях M = m1 + m2 - перекрытие. Кажется, это подразумевает, что минимизация перекрытия (которое в приведенном выше коде требует произведение двух двоичных векторов) эквивалентно минимизации суммы m1 + m2 (которая является sum двухбинарные векторы). Я проверил это численно, используя решения грубой силы, и, действительно, ожидаемая линейная зависимость найдена.
Поскольку m1 + m2 можно получить путем линейного программирования с использованием N + 2 * M бинарных переменных, теоретически возможнорешить эту проблему, не вычисляя матрицу парных расстояний.