logo标签列表

高效算法：计算地理地图上密度最高的点的面积

algorithmdata-structuresdictionarymappinggeolocation
4
假设我有一张地理地图，其中点由纬度\经度表示。我在这个地图上有许多点，可以随时添加\删除\移动点。
我需要的是找到“最热门的区域” - 即包含最多点数的区域除以面积 - 或者换句话说，具有最高点密度的区域。
我需要一种高效的数据结构和算法来重新计算任何更改后的最热门的区域。计算复杂度和内存复杂度必须尽可能小，因为点的数量可能非常大。
我希望知道并维护一个最热门区域的列表，按降序排列 - 首先是最拥挤的区域，然后是不太拥挤的区域。列表大小可以有限 - 例如，最热门的100个区域。
当然，为了防止一个孤立点达到100％密度，有一个最小的区域（定义为常量）。
这里的“区域”定义为地图上包含点的任何可感知区域。它可以是整张地图，但算法当然不应将其视为热点=）
提前感谢！如果需要任何澄清，请告诉我...
我主要是在调查，因为我甚至不知道算法中哪个知识领域可以帮助我回答这个问题... 有一个“原始力量”的解决方案，但如你所想，它并不是非常高效。 - SirKnigget
你如何定义一个区域？两点被视为在同一区域内的最大距离是多少？或者你已经事先定义好了这些区域吗？ - Mario Duarte
因为我需要一个按降序排列的结果，只要第一个结果的密度比第二个高，依此类推，就无所谓了......当然，必须有一个“区域”的最小值，以防止一个孤立点的100%密度（当然，我会将其添加到主要问题中）。 - SirKnigget
也许聚类算法可以帮忙。搜索“k-means”或者甚至是“SVM”可能是个好的开端。这个问题很难精确地陈述，也同样难以解决。 - Alexandre C.
3个回答
5
你正在进行的统计学上被称为“二维密度估计”的工作（这样你就知道该去哪里查找了）。
一种常见的方法是“核平滑”。想象一下，每个数据点上都有一个圆盘。覆盖该区域的核平滑是每个点处重叠的圆盘数量。这是使用固定半径的均匀核的核平滑。
您不必使用均匀核，也不必在所有点上使用相同大小的核 - 这现在是“自适应带宽核平滑”。
这给您提供了一个网格，您可以很容易地更新它，特别是如果您有一个有限的核（您可以使用高斯（又名正态）核，它是无限的，但将被剪裁到您的研究区域）。每次添加或删除一个点时，您都会添加或删除其核对密度的贡献。
所以这是问题的一半 - 现在您有了一个密度网格。然后，您可以使用聚类算法对其进行分区，并根据定义“峰值”的任何标准和将其定义为与相邻峰值不同的标准来查找单独的峰值。其他人已经建议过聚类算法。我曾经使用“R”统计包中的聚类函数进行过此操作（十年前）。但速度不是它的强项...

您可能想将此转至http://stats.stackexchange.com。

好主意。现在，原帖的作者可能想要找到一个光滑函数的等高线，这可以在本地完成。问题是点会移动。 - Alexandre C.
一种改进方法是将点存储到四叉树中，并使用紧支持径向核以便能够快速计算地图上任意点的估计密度。然后，在固定高度（假设为10，假设为单位峰值核）处计算轮廓级别 - 如果您想要，我可以详细说明。每次点移动、删除或添加时，需要重新计算的轮廓级别曲线部分都可以通过四叉树和核函数的有界支持来确定。热点由轮廓级别线内部的连通组件给出。 - Alexandre C.
我理解了磁盘类比的含义，但除此之外似乎还需要涉足更多领域的知识，或者找到其他人来帮忙。你有什么好的参考资料推荐吗？你会如何处理分区问题？为了澄清一下，假设我在纽约市有很多点集中，其中一个集中在中央公园，另一个集中在自由女神像。我想区分这两个独立的热点，但同时也将整个城市作为第三个最密集的热点（根据面积/点数定义）。 - SirKnigget
2
这段文字有些长，但以下是我的想法，我会尝试一些方法，看看是否能得出有趣的结果。但有一件事是确定的：下面这个过程可以变得非常快。
这个过程能否轻松转换为离散问题？首先，您需要将所有坐标与大地图对齐（您定义每个方格的大小，并使每个条目映射到一个这样的点）。然后您会得到像这样的结果：
0000000000000000000000000000
00XX000000000000000000X00000
00X00000000000000X0000000000
0000000000000000000000000000
0000000000000000000000000000
000000X00000000X000000000000
0000000000000000000000000000
000000000000X000000000X00000
00000000000000000000000X0000
0000000000000000000000000000

然后，您需要计算每个条目及其相邻邻居的数量：
0000000000000000000000000000
0033000000000000000001000000
0030000000000000010000000000
0000000000000000000000000000
0000000000000000000000000000
0000001000001001000000000000
0000000000000000000000000000
0000000000001010000000200000
0000000000000000000000020000
0000000000000100000000000000

然后你可以增加正方形的大小，比如增加两个单位，从而划分地图：

（这张地图不准确，只是为了让你了解我所思考的内容）

09001001000000
00000000000000
00100001100000
00000110002000
00000002000000
00000100000000

然后您重新计算相邻的邻居等。

对我来说，这将允许根据您的“分辨率”找到热点：您只需寻找最大的数字，那就是您的“热点”。

因为在这种情况下：

0000X00000
0000XX0000
0000000000
0000000000
0Y0Y000000
0000000000
0Y0Y000000

无论是'X'还是'Y'都可以成为最热门的地点（三个相邻的有趣点）或'Y'（四个点彼此相邻，但它们不像'X'那样接近）。

因为您说需要速度，所以我将这个问题转化为离散问题，并将我的图形表示为数组。然后，我会允许可变的“区域”大小。

看起来是一个有趣的问题 :)

很好的开始想法，此外还有一个补充 - 在您的表示中，“点”可以包含多个条目，因此需要考虑这一点。将“X”替换为该坐标中的条目数，然后进行精细计算。 - SirKnigget
1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接