在尝试最小化备用容量时进行群集

Question

我试图将约3000万点(x和y坐标)聚集成簇 - 这使得它具有挑战性的增加是我试图最小化每个簇的备用容量,同时还确保簇与任何一个簇之间的最大距离点不是很大(> 5km左右).

每个集群由可以提供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)然后重复,直到收敛
• 线性规划
  • 使用库实现起来非常简单,但由于复杂性,也花了太长时间

我对可能最适合的算法/语言的建议持开放态度.我有机器学习的经验,但想不出用这种方法做这个的明显方法.

如果我错过任何信息,请告诉我.

Answer 1

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

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

您似乎更关心最大限度地减少设备和运行时间，而不是拥有尽可能紧密的集群，因此这里有一个类似的建议。

这个想法是从 1 节点集群开始，然后使用（几乎）完美匹配将集群彼此配对，从而使大小加倍。执行此操作 6 次以获得 64 个簇。

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