在大型稀疏矩阵中查找“最大”密集子矩阵

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

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子矩阵。

基本上,您将迭代直到找不到更多要添加的新行和列。这也会给你一个当地最低限额。您可以存储结果,然后使用另一个起点(可能是不适合当前解决方案的起点)重新开始。

过一会儿找不到了就停下来。

很明显,这需要很长时间,但我不知道你是否能更快地完成。

这是 Netflix problem ?

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

你打算自己写吗?

也许每行的1d方法都能帮助您。算法可能如下所示:

1. 每行循环
2. 查找第一个非零元素的索引
3. 查找每行中非零列之间跨度最大的非零行元素的索引,并存储这两个元素。
4. 对非零列之间的行范围从大到小排序。

在这一点上,我开始变得模糊(对不起,不是算法设计者)。我将尝试在每一行上循环,排列起始点的索引,寻找尽可能多的非零列索引运行。

您没有指定密集矩阵是否必须是方形的。我想不会。

我不知道这有多有效,也不知道它的大O行为会是什么。但这是一个蛮力的方法。

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

但根据下面最后一条评论,它可能与以下内容相同:

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

3. 那么你要找的水平区域就是这两对点之间的矩形?

   这个确切的问题是在乔恩·本特利的《编程珍珠》一书中讨论的,我记得,尽管有一个一维的解决方案,但是对于二维或更高维的变体,没有一个简单的答案……

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

循环遍历元素,跟踪特定上一个元素的连续合计,以及迄今为止看到的最大小计(以及生成它的开始和结束元素)。在每个元素上,如果maxrunning subtotal大于到目前为止看到的max total,则会重置到目前为止看到的max和endelement…如果最大运行总数低于零,则开始元素重置为当前元素,运行总数重置为零…

二维问题源于生成视觉图像处理算法的尝试,该算法试图在代表2色图像像素的亮度值流中找到图像中的“最亮”矩形区域。也就是说,找到包含亮度值总和最高的二维子矩阵,其中“亮度”是通过像素亮度值与整个图像的总体平均亮度之间的差来测量的(因此许多元素具有负值)。

编辑:为了查找我收集到的这本书第二版的1-D解决方案,乔恩·本特利在其中说:“这本书在1999年出版时,2-D版本仍未解决……”

我知道你不会再做这个了,但我想将来有人可能会和我有同样的问题。

因此,在意识到这是一个NP难题(通过减少到max-clique)之后,我决定想出一个迄今为止对我很有效的启发式方法:

给定一个 n X 米 二元/布尔矩阵,找到一个大的密集子矩阵:

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

1. 考虑每个 n 行为 米 -维二元向量, VII 在哪里 我 = 1 n
2. 计算的距离矩阵 n 使用汉明距离的向量
3. 使用UPGMA(算术平均的无权重对组法)算法对矢量进行聚类

最初,每个 VII 矢量是一个单粒子簇。上面的步骤3(集群)给出了向量应该组合成子矩阵的顺序。所以层次聚类树中的每个内部节点都是一个候选子矩阵。

第二部分 :评分和排名候选子指标

1. 对于每个子矩阵,计算 D ,子矩阵向量密集子集中的元素数,方法是用一个或多个零消除任何列。
2. 选择最大化的子矩阵 D

对于需要从初始完整矩阵中保留的最小行数,我也有一些考虑,在选择具有max的子矩阵之前,我将丢弃任何不符合此条件的候选子矩阵。 D 价值。