2

我有一个矩形平面网格，每个单元格都分配了一些整数权重。我正在寻找一种算法来识别具有高于平均重量的 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|
4

4 回答 4

1

对于图论解决方案，wikipedia 中有几句话，但您最好在 MathOverflow 上发帖。这个问题也可能有用。

在计算中解决这些问题的传统方法（可能最好考虑其普遍性）是栅格分析 - 在 GIS 和遥感领域众所周知，因此有许多提供实现的工具。用于查找最适合您的问题的关键字是栅格、最近邻、重采样和聚类。GDAL 库通常是其他工具的基础。

例如http://clusterville.org/spatialtools/index.html

您可以尝试查看 GDAL 库和源代码，看看是否可以在您的情况下使用它，或者看看它是如何实现的。

为了检查圆形，您可以将剩余值转换为多边形并检查结果特征

http://www.gdal.org/gdal_polygonize.html

于 2010-04-17T17:32:46.747 回答
0

我不确定我是否看到了图论类比，但您可以通过预先计算面积积分来加快速度。这感觉像是一个多尺度的事情。

A[i,j] = Sum[Sum[p[u,v], {u, 0, i}, {v, 0, j}]];

那么矩形 (a,b), (c,d) 区域的平均亮度为

(A[c,d] - (A[c,b] + A[a,d]) + A[a,b])/((ca)(db))

如果您的单元格中有大量数字，溢出可能不是您的朋友。

于 2010-05-12T16:12:31.653 回答
0

使用联合查找算法进行聚类？它非常快。

我猜这个图是考虑到每对相邻的高价值单元相连的结果。使用 union-find 算法查找所有集群，并接受所有超过一定大小的集群，可能也有形状限制（例如，基于到集群中心的平均平方距离与集群大小）。这是 union-find 算法的一个微不足道的变体，用于收集您在进行时需要的统计信息（计数、x 的总和、x ^ 2 的总和、y 的总和、y ^ 2 的总和）。

于 2010-05-18T00:37:22.833 回答
0

如果您只是在寻找一种将问题转换为图形问题的方法，那么您可以做什么。

从每一点看你所有的邻居（这可能是 8 个相邻的正方形或 4 个相邻的，这取决于你想要什么）。寻找具有最大值的邻居，如果它比你大，然后将自己连接到这个正方形。如果它更小，那么什么也不做。

在此之后，您将拥有一片森林或可能有一棵树（尽管我认为这不太可能）。这是将矩阵转换为图形的一种可能方式。我不确定它是否是最有用的翻译。

于 2010-05-18T04:23:40.257 回答