algorithm - 尽量减少备用容量的集群

Question

我正在尝试将约 3000 万个点(x 和 y 坐标)聚类到集群中 - 使它具有挑战性的补充是我正在尝试最小化每个集群的备用容量，同时确保集群与任​​何一点之间的最大距离不是很大(>5 公里左右)。

每个集群由可以服务 64 个点的设备组成，如果一个集群包含少于 65 个点，那么我们需要这些设备之一。但是，如果一个集群包含 65 个点，那么我们需要两台这样的设备，这意味着我们为该集群提供了 63 的备用容量。我们还需要将每个点连接到集群，因此每个点到集群的距离也是设备成本的一个因素。

最终，我试图将设备成本降至最低，这似乎与将平均备用容量降至最低是一个等价的问题，同时还要确保集群到任何一点的距离小于 5 公里(近似值，但可以满足思想实验——也许有更好的方法来施加这种限制)。

我尝试了多种方法:

• K 均值
  • 大多数人应该知道这是如何工作的
  • 平均备用容量为 32
  • 在 O(n^2) 中运行
• a-b 距离的排序列表
  • 我尝试了另一种方法，例如:
    1. 通过从数据中随机选择点来初始化聚类点
    2. 确定每个点和每个簇之间的距离矩阵
    3. 将其展平成一个列表
    4. 对列表进行排序
    5. 从最小距离到最长距离将点分配给集群
    6. 分配簇点直到达到64，然后不能再分配
    7. 一旦分配了所有点就停止遍历列表
    8. 根据分配的点更新簇质心
    9. 重复步骤 1 - 7 直到聚类位置收敛(如 K 均值)
    10. 将附近的集群位置收集到一个集群中
  • 根据设计，平均备用容量约为 0
  • 这对我的测试数据集很有效，但是当我扩展到完整的集合(3000 万个点)时，它花费的时间太长了，可能是因为我们必须对完整列表进行排序 O(NlogN) 然后迭代它直到所有点都被分配 O(NK) 然后重复直到收敛
• 线性规划
  • 这使用库实现起来非常简单，但由于复杂性又花费了太长时间

我愿意接受有关最适合执行此操作的可能算法/语言的任何建议。我有机器学习方面的经验，但想不出一种明显的方法来使用它。

如果我遗漏了任何信息，请告诉我。

Answer 1

既然你已经有了这两个部分，我的第一个新建议是使用 k-means 对点进行分区 k = n/6400(你可以调整这个参数)，然后在每个超集群上使用整数规划。当我有机会时，我会写下我的其他建议，其中涉及随机移动的四叉树解剖。

下面是旧的问题前编辑答案。

---

与尽可能紧凑的集群相比，您似乎更关心最小化设备和运行时间，所以这里有一个类似的建议。

想法是从单节点集群开始，然后使用(几乎)完美匹配将集群彼此配对，使规模加倍。这样做 6 次以获得 64 个簇。

为了计算匹配，我们使用每个聚类的质心来表示它。现在我们只需要对欧几里得平面中的一组点进行近似匹配。向许多关于欧几里德匹配的优秀论文的作者致歉，这里有一个 O(n log n) 启发式算法。如果有两个或更少的点，以明显的方式匹配它们。否则，选择一个随机点 P 并通过比较它们的(在 x- 和 y- 之间交替)坐标与 P(如在 kd 树中)来划分其他点，通过比较其他坐标来打破平局。如果可能，将 P 分配给奇数分的一半。 (如果两者都是偶数，则令 P 不匹配。)递归匹配两半。