10

给定一个大的稀疏矩阵（比如 10k+ x 1M+）​​，我需要找到一个子集，不一定是连续的，形成密集矩阵（所有非零元素）的行和列。我希望这个子矩阵在某些纵横比约束内尽可能大（不是最大的总和，而是最大的元素数量）。

是否有任何已知的确切或近似的解决方案来解决这个问题？

在 Google 上快速浏览一下似乎会给出很多接近但不完全准确的结果。我应该寻找哪些条款？

编辑：只是为了澄清；子矩阵不必是连续的。事实上，行和列的顺序是完全任意的，所以相邻性是完全无关的。

基于 Chad Okere 的想法

  1. 将行从最大计数排序到最小计数（不是必需的，但可能有助于提高性能）
  2. 选择具有“大”重叠的两行
  3. 添加不会减少重叠的所有其他行
  4. 记录那套
  5. 添加任何行以最少的方式减少重叠
  6. 在 #3 重复，直到结果变小
  7. 使用不同的起始对从 #2 重新开始
  8. 继续直到你认为结果足够好
4

4 回答 4

2

我假设你想要这样的东西。你有一个像这样的矩阵

1100101
1110101
0100101

您想要第 1、2、5、7 列和第 1 行和第 2 行，对吗？该子矩阵将是 8 个元素的 4x2。或者您可以使用第 1、5、7 列和第 1、2、3 行，这将是一个 3x3 矩阵。

如果您想要一个“近似”方法，您可以从一个非零元素开始，然后继续找到另一个非零元素并将其添加到您的行和列列表中。在某些时候你会遇到一个非零元素，如果它的行和列被添加到你的集合中，你的集合将不再是完全非零的。

所以对于上面的矩阵，如果你添加了 1,1 和 2,2，你的集合中就会有 1,2 行和 1,2 列。如果您尝试添加 3,7，则会导致问题，因为 1,3 为零。所以你不能添加它。不过，您可以添加 2,5 和 2,7。创建 4x2 子矩阵。

您基本上会进行迭代，直到找不到更多要添加的新行和列。那会让你也成为当地的最低限度。您可以存储结果并从另一个起点（可能不适合您当前解决方案的起点）重新开始。

然后在一段时间后找不到更多内容时停下来。

显然，这需要很长时间，但我不知道你是否能够更快地做到这一点。

于 2009-08-01T21:58:05.537 回答
2

我知道您不再从事此工作，但我认为将来有人可能会遇到与我相同的问题。

因此，在意识到这是一个 NP 难题（通过简化为 MAX-CLIQUE）之后，我决定提出一个迄今为止对我来说效果很好的启发式算法：

给定一个N x M二进制/布尔矩阵，找到一个大的密集子矩阵：

第一部分：生成合理的候选子矩阵

  1. 将N行中的每一行视为一个M维二进制向量v_i，其中i =1 到N
  2. 使用汉明距离计算N个向量的距离矩阵
  3. 使用 UPGMA（具有算术平均值的未加权对组方法）算法对向量进行聚类

最初，每个v_i向量都是一个单例集群。上面的步骤 3（聚类）给出了向量应该组合成子矩阵的顺序。所以层次聚类树中的每个内部节点都是一个候选子矩阵。

第二部分：对候选子矩阵进行评分和排名

  1. 对于每个子矩阵，通过消除具有一个或多个零的任何列，计算D ，即子矩阵向量的密集子集中的元素数。
  2. 选择最大化D的子矩阵

I also had some considerations regarding the min number of rows that needed to be preserved from the initial full matrix, and I would discard any candidate submatrices that did not meet this criteria before selecting a submatrix with max D value.

于 2011-10-20T18:06:38.150 回答
1

编辑。这与下面的问题不同..我的错...

但根据下面的最后一条评论，它可能等同于以下内容：

  1. 找到最远的垂直分隔的零点对，它们之间没有零点。
  2. 找到它们之间没有零的最远水平分隔的零点对？

  3. 那么你正在寻找的水平区域是适合这两对点之间的矩形吗？

    这个确切的问题在 Jon Bentley 的一本名为“Programming Pearls”的书中进行了讨论，而且，我记得，虽然在一个维度上有一个解决方案，但对于二维或更高维度的变体没有简单的答案。 ..

1=D 问题实际上是找到一组数字的连续子集的最大和：

遍历元素，跟踪来自特定前一个元素的运行总计，以及到目前为止看到的最大小计（以及生成它的开始和结束元素）......在每个元素处，如果 maxrunning 小计大于到目前为止看到的最大总数，到目前为止看到的最大值和 endelemnt 被重置...如果最大运行总数低于零，则开始元素被重置为当前元素，并且运行总数被重置为零......

二维问题来自于尝试生成视觉图像处理算法，该算法试图在表示 2 色图像中像素的亮度值流中找到图像中“最亮”的矩形区域。即，找到包含的具有最高亮度值总和的二维子矩阵，其中“亮度”是通过像素的亮度值与整个图像的整体平均亮度之间的差异来衡量的（很多元素都有负值）

编辑：为了查找 1-D 解决方案，我挖掘了本书第二版的副本，在其中，Jon Bentley 说“随着该版本的印刷，2-D 版本仍未解决……” 1999 年。

于 2009-08-01T20:07:01.203 回答
1

这是Netflix 的问题吗？

MATLAB或其他一些稀疏矩阵库可能有办法处理它。

你打算自己写吗？

也许每一行的一维方法会对你有所帮助。该算法可能如下所示：

  1. 循环遍历每一行
  2. 查找第一个非零元素的索引
  3. 找到每行中非零列之间跨度最大的非零行元素的索引，并将两者都存储起来。
  4. 对非零列之间从最大到最小跨度的行进行排序。

在这一点上，我开始变得模糊（对不起，不是算法设计师）。我会尝试遍历每一行，排列起点的索引，寻找我能找到的最大非零列索引运行。

您没有指定密集矩阵是否必须是正方形。我假设不会。

我不知道这是多么有效，也不知道它的 Big-O 行为是什么。但这是一种蛮力方法。

于 2009-08-01T20:18:46.110 回答