我有一个矩形平面网格,每个单元格都分配了一些整数权重。我正在寻找一种算法来识别具有高于平均重量的 3 到 6 个相邻单元格的集群。这些斑点应具有近似圆形。
对于我的情况,不包含集群的单元格的平均权重约为 6,而包含集群的单元格的平均权重约为 6+4,即在 6 左右的某处存在“背景权重”。权重随泊松统计量波动。
对于小的背景贪婪或种子算法执行得相当好,但是如果我的集群单元的权重接近背景波动,这就会崩溃,即即使没有任何东西,它们也会倾向于找到一个集群。此外,我无法对所有可能的设置进行暴力搜索,因为我的网格很大(大约 1000x1000),我计划经常这样做(10^9 次)。我的印象是在图论中可能存在解决这个问题的方法。我听说过顶点覆盖和派系,但不知道如何最好地将我的问题翻译成他们的语言。我知道图论可能在输入的统计性质方面存在问题,但我很想看看那里的算法可以找到什么,即使它们无法识别每个集群。
这是一个示例裁剪:框架区域每个单元格平均有 10 个条目,所有其他单元格平均有 6 个。当然,网格会进一步扩展。
| 8| 8| 2| 8| 2| 3|
| 6| 4| 3| 6| 4| 4|
===========
| 8| 3||13| 7| 11|| 7|
|10| 4||10| 12| 3|| 2|
| 5| 6||11| 6| 8||12|
===========
| 9| 4| 0| 2| 8| 7|