给定一个对称的二进制相似度矩阵M
(1
=相似度),我想提取所有(可能重叠的)子集,其中一个集合中的所有元素都相互相似。
A B C D E A 1 1 0 0 0 B 1 1 1 1 0 C 0 1 1 1 1 D 0 1 1 1 1 E 0 0 1 1 1
另外,包含在其他集合中的集合也应丢弃(例如,{D,E}
中包含{C,D,E}
)。对于矩阵的结果将是:{A,B}
,{B,C,D}
,{C,D,E}
我如何轻松实现这一目标?
我怀疑有一些用于此目的的聚类算法,但是我不知道这些类型问题的名称。该任务属于哪一类(数学)问题?
码
M <- matrix(c(1,1,0,0,0, 1,1,1,1,0, 0,1,1,1,1, 0,1,1,1,1, 0,0,1,1,1), ncol = 5, byrow = TRUE) colnames(M) <- rownames(M) <- LETTERS[1:5]
PS。虽然这听起来像是一些家庭作业,但实际上是我在工作中遇到的问题:)