algorithm - 在尝试最小化备用容量的同时进行集群

Question

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

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

最终我试图最小化设备成本，这似乎是一个与最小化平均备用容量相同的问题，同时还确保从集群到任何一点的距离小于 5 公里（一个近似值，但可以用于思想实验- 也许有更好的方法来施加这个限制）。

我尝试了多种方法：

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

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

如果我错过了任何信息，请告诉我。

标签： algorithmmachine-learningtime-complexitycluster-analysislinear-programming

Answer 1

由于您已经拥有这两个部分，我的第一个新建议是使用 k-means 对 k = n/6400 的点进行分区（您可以调整此参数），然后在每个超集群上使用整数编程。当我有机会时，我会写下我的另一个建议，其中涉及随机移动的四叉树解剖。

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

---

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

这个想法是从 1 节点集群开始，然后使用（几乎）完美匹配将集群相互配对，使规模翻倍。这样做 6 次以获得 64 个集群。

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