从成对比较构建集合

Question

尝试概括地表述我的问题：我对多个元素进行了成对比较，并希望从该邻接矩阵构建集合（组）（即，成对比较等于 TRUE 的元素构建组） .

例如：我有6个形状。形状 1 与形状 2 重叠，形状 2 与形状 3 重叠。形状 4 单独存在，形状 5 与形状 6 重叠（见下文）

如果我对所有形状进行成对比较并询问它们是否与另一个形状重叠，我会收到以下矩阵。

(请注意：这是我提问的起点，上面的图片和形状的故事只是一个例子)

      [,1]  [,2]  [,3]  [,4]  [,5]  [,6]
[1,]  TRUE  TRUE FALSE FALSE FALSE FALSE # shape 1 overlaps shapes 1 and 2
[2,]  TRUE  TRUE  TRUE FALSE FALSE FALSE # shape 2 overlaps shapes 1, 2 and 3
[3,] FALSE  TRUE  TRUE FALSE FALSE FALSE # etc...
[4,] FALSE FALSE FALSE  TRUE FALSE FALSE
[5,] FALSE FALSE FALSE FALSE  TRUE  TRUE
[6,] FALSE FALSE FALSE FALSE  TRUE  TRUE

我正在寻找一种可以建立以下组的方法（组顺序无关紧要）：

a 组：形状 1、2 和 3
b组：形状4
c 组：形状 5 和 6

您可以使用以下代码重现成对比较矩阵：

adjacency_matrix <- matrix(c(TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE),nrow = 6)

Answer 1

我自己找到解决方案后写的问题。希望这可以帮助任何在找不到合适的词来表述它的情况下努力解决这个问题的人。

事实证明，这是图论领域中非常简单的问题。您可以使用 igraph 将邻接矩阵转换为图形，然后确定它的组件：

library(igraph)

mygraph <- graph_from_adjacency_matrix(adjacency_matrix)

mycomponents <- components(mygraph) # you can vary between "weak" and "strong", depending on your context

mycomponents$membership # the memberships in the order as they appear in the matrix

[1] 1 1 1 2 3 3

plot(mygraph)

从成对比较构建集合

Building sets from pairwise comparisons

r

graph

igraph

pairwise