在Matlab中对布尔矩阵进行聚类

Question

假设我们有一个布尔矩阵，如下所示：

0 0 1 0 0 1 0
1 1 0 0 1 0 0
0 0 0 0 0 1 1
0 0 0 0 0 1 0
0 0 0 0 0 1 1

这样解释：每一行是一个水果，每一列是一个人。位置(i，j(中的"1"表示人j想要吃水果i。我想对这个矩阵进行"聚类"，创建子矩阵，指示人们争夺水果子集的子集。在上面的例子中，我想在输出中看到：

0 0 1 0 0 1 0
0 0 0 0 0 0 0
0 0 0 0 0 1 1
0 0 0 0 0 1 0
0 0 0 0 0 1 1

和

0 0 0 0 0 0 0
1 1 0 0 1 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

有没有一种简单的方法可以做到这一点，例如，在Matlab中？

谢谢。

Answer 1

描述过于非正式，基于单个示例进行设计可能不是一个好主意。

Howewer：如果这个例子只显示了一个2分区(这是我的解释(，这可以很容易地通过：来实现

- Create undirected graph G with one vertex for each row
- Iterate over all "N over 2" row-pairs (= nested i,j loop skipping symmetries)
- If the pair (rowA, rowB) shares some 1 in a column -> add edge (rowA, rowB) to G
- Compute all "connected components" of G

任何健全的图库都将提供所需的基元。