algorithm - 将世界划分为一千个左右的位置

Question

背景：我想创建一个天气服务，由于大多数可用的 API 限制了每日调用的数量，我想将地球划分为一千个左右的区域。

显然，互联网用户的分布并不均匀，因此在人口稠密地区的采样应该更精细。

我应该如何实施呢？

• 我在哪里可以找到有关地理互联网用户密度的数据？
• 该算法可能类似于 k-means。然而，在一个有海洋的球体上实现它可能有点棘手。有什么见解吗？
• 最后，也许有一种方法可以避免我做这一切？

Answer 1

与 k-means非常相似的是质心 Voronoi 图（它是 k-means 的连续版本）。但是，这会产生一个统一的球体镶嵌，不会像您希望的那样考虑用户密度。

因此，类似的解决方案是相同的技术，但与Power Diagram一起使用：Power Diagram 是一个 Voronoi 图，它说明了密度（通过为每个 Voronoi 种子分配权重）。这样的图可以使用 3D 空间（而不是 2D）中的嵌入来计算，该空间由前两个 (x,y) 坐标加上第三个坐标组成，第三个坐标是 [任何大的正常数减去给定的权重的平方根观点]。

使用它，您可以获得针对用户密度的域的细分。

Answer 2

一般而言，您并不关心互联网用户密度。你关心使用你的服务的用户的密度——你不关心这些用户在哪里，你关心他们询问的地方。因此，一旦您的网站已经运行了一天以上，您就可以使用人们在前一天询问的位置来计算出第二天的区域应该是什么。

树上的动态编程很容易。我会为算法做的是构建一个连续更精细划分的单元格的树。更多的细胞意味着更小的误差，因为人们会得到更接近它们的点的预测，你可以计算出误差，或者至少是更多细胞和更少细胞之间的相对误差。从下往上算出每个子树贡献的最小可能总误差，允许它被划分为最多 1,2,3,..N。方法。您可以通过查看您已经为其每个后代计算的最小可能误差，并计算出如何最好地共享可用它们之间的 k 个分区。

我会尝试通过考虑不同的想法来避免这样做。根据您看待生活的方式，这至少有两个缺点：

1）你似乎没有在派对上添加任何东西。看起来您正在将自己置于实际进行天气预报的组织及其客户之间。组织失去与客户的直接联系，这可能会失去他们的广告收入。客户得到的天气预报更差。

2) 大多数网站都有合法的服务条款，客户可以无视，不用担心。我的猜测是，您将违反这些服务条款，如果您的服务变得足够受欢迎以引起注意，它们将被强制执行。