Выявление общих * не непрерывных * подпоследовательностей, представляющих события

Question

Рассмотрим следующий набор данных:

set.seed(50)
d = matrix(rbinom(1000, 1, 0.9), ncol = 20)

Каждая строка соответствует объекту, а каждый столбец соответствует измерению объекта. Например, строки могут быть отдельными лицами в исследовании, а столбцы могут повторяться во времени. В этом случае измерения имеют значение ИСТИНА / ЛОЖЬ, что указывает на наличие или отсутствие объекта.

Я ищу алгоритм, который позволит мне определить максимальную коллекцию строк, которые имеют n совпадающие наблюдения. Другими словами, я ищу способ фильтрации строк, которые все имеют n ИСТИННЫЕ значения в тех же столбцах. Член группы может иметь более n ИСТИННЫЕ значения, хотя.

Тривиальный пример: строки с 20 (всеми) ИСТИННЫМИ значениями захватываются

which(apply(d, 1, all))

который идентифицирует строки 3, 10, 12, 24, 36, 39, 48, 50, Точно так же легко идентифицировать все уникальные последовательности и идентифицировать группы с одинаковыми наблюдениями:

unique.series = d[which(!duplicated(d)),]
groups = vector("list", nrow(unique.series))
for(i in seq_along(groups))
  groups[[i]] = which(apply(d, 1, function(x) 
    identical(x, unique.series[i,])))

Но что, если мне нужны все группы с 19 или более наблюдениями? Например, гостиницы 3 (строки 3, 10, 12, 24, 36, 39, 48, 50) а также 21 (строки 23, 32, 40) отличаются только наблюдением 9 (группа 3 имеет наблюдение, но группа 21 не). Как я могу программно идентифицировать серии, которые частично совпадают, то есть содержат некоторое подмножество совпадающих наблюдений? Это кажется проблемой сопоставления подпоследовательности, но это немного более абстрактно, потому что подпоследовательности не должны быть непрерывными.

Одним из способов может быть использование регулярных выражений, но я не могу заставить его работать правильно:

unique.strings = lapply(
apply(unique.series, 1, function(x) 
    which(as.logical(x))),
  paste,
  collapse = ","
)
reg.strings = paste0("^", lapply(
  apply(unique.series, 1, function(x) 
    sprintf("(%d)", which(as.logical(x)))), 
  paste, collapse = "+(,[0-9],)*"), "$")  
lapply(unique.strings, grep, x =  unique.strings) # NOT CORRECT

Я был бы признателен за любые альтернативные алгоритмы, основанные на регулярных выражениях или другие.

Answer 1

Это не полный ответ, но я получил больше, чем на полпути. Я отказался от подхода регулярных выражений и вместо этого принял подход двоичной матрицы.

Коллекция совпадающих наблюдений будет представлена ​​в матрице вхождений в виде блока ИСТИННЫХ значений. Я не требую, чтобы наблюдения были последовательными, то есть порядок строк / столбцов матрицы не имеет значения. Поэтому я могу просто переставить свою матрицу так, чтобы вхождения были сгруппированы в блоки, а затем использовать алгоритмы обнаружения блоков или кластеризации для извлечения набора наблюдений. Эта процедура состоит из двух компонентов: во-первых, переставьте матрицу, чтобы сделать ее максимально "блочной" путем замены столбца / строки. Во-вторых, идентифицируйте блоки в упорядоченной матрице.

Аранжировка действительно очень проста. Я использовал seriation пакет для перестановки матрицы в блоки.

set.seed(50)
d = matrix(as.logical(rbinom(50, 1, 0.75)), ncol = 10)
rownames(d) = LETTERS[1:5]   # individual IDs
colnames(d) = month.abb[1:10]

library(seriation)
o = seriate(d)
d.a = permute(d, o)            # rearranged matrix

Я не определился с хорошим подходом к обнаружению блока, но есть несколько вопросов SO, которые касаются обнаружения наибольшего блока (например, 1, 2). Я надеюсь, что смогу адаптировать эти алгоритмы, чтобы найти самый большой блок ширины n или что-то в этом роде. Я обновлю этот ответ, если найду хорошее решение.