arrays - 检测矩阵(二维数组)中的精确 block

Question

我正在寻找一种有效的算法来识别具有许多 0 条目的矩阵中的 block 结构。

例如6×7矩阵

0.0975    0.9575         0         0         0         0         0
0.2785    0.9649         0         0         0         0         0
0.5469    0.1576         0         0         0         0         0
     0         0    0.9706    0.9572         0         0         0
     0         0         0         0    0.8235    0.3171    0.0344
     0         0         0         0    0.6948    0.9502    0.4387

由三个大小分别为 3×2、1×2 和 2×3 的 block 组成。

block 由一组行和一组列定义。 block 结构的特点是所有不属于 block 的条目都恰好为 0。但是， block 内也可能存在精确 0 的条目。

一个简单的解决方案是始终将整个矩阵声明为一个 block ；因此，寻求一种解决方案，使 block 内条目的数量尽可能少。

为了让事情变得更难(或者更容易？)， block 不必是连续的。上述矩阵的排列版本，

     0    0.9572         0         0         0         0    0.9706
     0         0    0.0975         0         0    0.9575         0
0.4387         0         0    0.9502    0.6948         0         0
0.0344         0         0    0.3171    0.8235         0         0
     0         0    0.2785         0         0    0.9649         0
     0         0    0.5469         0         0    0.1576         0

因此也有一个三 block 结构，可以描述为:

• 包含第 3、4 行和第 1、4、5 列的 block
• 包含第 1 行和第 2、7 列的 block
• 包含第 2、5、6 行和第 3、6 列的 block 。

我想到的解决方案是:

• 使用基于连接权重的聚类算法。然而，矩阵不必是对称的，甚至不必是正方形的。特定行和特定列之间没有对应关系。

• 最初定义一个由一个(非 0)条目(由其行和列描述)组成的 block ，在其行和列中查找非 0 条目，并添加相应的列和行，这样迭代增长，直到没有添加行或列；标识一个 block 。从 block 中未包含的条目开始执行相同的操作。重复此操作，直到没有留下任何非 0 条目。在这里我怀疑这个算法能否有效地扩展到具有许多 block 的大矩阵。

我正在寻找一种算法或算法的其他想法，而不是为了实现。然而，一个实现例如欢迎使用 Matlab 或 Python。

Answer 1

这是一般表达式分析中的标准场景。

这种算法称为双聚类(因为它们同时对行和列进行聚类)。 Cheng 和 Church 提出了一种早期方法。