我有一个实数矩阵,我想找到这个矩阵的一个分区,这样每个部分的个数和个数的方差都最小。直觉上,我希望尽可能少的部分,但我也希望任何给定部分中的所有数字都紧密地结合在一起。
更正式地说,我想对于后者,我会找到每个部分的数字的方差,然后取所有部分的方差的平均值这将是给定解的“分数”的一部分,分数的另一部分将是,例如,矩阵中的元素总数减去分区中的部分数,因此更少的部分将导致这部分分数更高解决方案的最终得分将是这两部分的加权平均值,最好的解决方案是得分最高的解决方案。
很明显,这其中有很多是启发性的:我需要决定如何平衡零件数量和方差但我对解决这个问题的一般方法都很执着。
例如,给定以下简单矩阵:

10, 11, 12, 20, 21
 8, 13,  9, 22, 23
25, 23, 24, 26, 27

将其划分为以下子矩阵是一个合理的解决方案:
10, 11, 12    |   20, 21
 8, 13,  9    |   22, 23
--------------+----------
25, 23, 24    |   26, 27

只允许通过垂直和水平切片进行分区。
注意,我不需要最优的解决方案,我只需要一个方法来得到一个“好”的解决方案而且,这些矩阵都是几百乘几百,所以强制它可能不是一个合理的解决方案,除非有人能提出一个很好的方法来缩减搜索空间。

最佳答案

我想你最好从一个简单的问题开始。我们把这个叫做
问题A:给定固定数量的垂直和/或水平分区,它们应该去哪里以最小化方差之和(或者可能是一些其他的方差度量,例如每个块内的方差之和)。
我建议对问题a使用动态规划公式。
一旦你控制住了,你就可以应付
问题B:找到变化与垂直和水平分区数量之间的最佳折衷。
显然,可以通过将每个元素放入自己的块中,将方差减少到0。一般来说,问题B要求您为所考虑的每个垂直和水平分区计数选择解决问题A。
要对问题B使用动态编程方法,您必须制定一个目标函数,该函数封装您所寻求的权衡。我不确定这是否可行,所以我建议寻找不同的方法。
就目前的情况来看,问题b是一个2d问题。你可能会发现一些成功的二维聚类算法如果可以将其重新定义为1D问题,则可能有另一种选择:用块的数量(而不是垂直和水平分区的数量)来权衡变化然后您可以使用类似于Jenks natural breaks classification method的东西来决定在哪里画线。
无论如何,这个答案显然没有给你一个有效的算法。但我希望它至少能提供一种方法(这是你所要求的)。

关于algorithm - 分区矩阵以最小化零件的方差,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/22357065/

10-11 23:00
查看更多