確定共同*非連續*代表出現

Question

子序列考慮以下數據集：

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

每行對應於一個對象，並且每一列對應於一個 測量的物體的。例如，行可以是個人在 研究和列可以重複測量時間。在這個 的情況下，測量結果爲TRUE/FALSE，表示存在或不存在 對象。

我在尋找一種算法，讓我能夠發現n一致意見行 最大的集合。 換句話說，我正在尋找一種方法來篩選所有 具有相同列中的TRUE值的行。該組的成員 可能具有超過n的TRUE值。

的簡單的例子：用20（全部）TRUE值的行被

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

這不是一個完整的答案，但我確實得到了超過一半。我放棄了正則表達式方法，而是採用了二元矩陣方法。

一致性觀測值的集合將在出現 矩陣中表示爲一個TRUE值塊。我不要求觀測值是連續的，即矩陣的行/列順序不重要。因此，我可以簡單地重新排列我的矩陣，以便將事件分組爲塊，然後使用塊檢測 或聚類算法來提取一組觀察值。此過程有兩個組件：首先，重新排列矩陣，使其儘可能通過列/行交換儘可能地「塊狀」（ ）。其次，確定排列矩陣中的 塊。

排列部分其實很簡單。我使用了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 

我還沒有決定用於塊檢測一個好辦法，但有幾個使之與最大的塊檢測（例如1，2）處理的問題。我希望我可以適應這些算法找到最大的寬度塊n或類似的東西。如果我找到一個好的解決方案，我會更新這個答案。