小编Ada*_*var的帖子

我试图将约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)然后重复,直到收敛
• 线性规划
  • 使用库实现起来非常简单,但由于复杂性,也花了太长时间

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

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