聚类而试图尽量减少备用容量

Question

我试图聚集约30万点（x和y坐标）到集群 - 加入，使得它具有挑战性的是，我试图尽量减少每个群集的备用容量，同时也保证了集群和任何一个之间的最大距离点不是巨大（>5公里左右）。

每个集群从设备，能够满足64个点，如果一个群不到65点，然后我们需要这些设备中的一种制成。但是，如果一个群65分，然后我们需要两个这些设备的，这意味着我们有63群集的备用容量。我们还需要各点连接到群集，所以从每个点到集群的距离也是在设备成本的一个因素。

最后我想以尽量减少设备的，这似乎是一个相当的问题，同时也确保对任何一个点从群集中的距离最小化平均备用容量小于5公里（近似的成本，但对于思想实验会做 - 也许有更好的方式来强加此限制）。

我曾尝试多种方法：

• K-手段 最应该知道如何工作的 32平均余力 运行在O（N ^ 2）
• A-B距离排序列表 我试着像这样的替代方法： 通过从数据中随机选择点初始化群集点 确定每一个点和每个簇之间的距离矩阵 其平整成一个列表 对列表进行排序 从最小转到距离最长的分配点集群 指定集群点，直到他们达到64，则没有更多的可分配 通过停止一旦所有点都被分配列表迭代 更新基于指定的点聚类中心 重复步骤1 - 7，直到簇位置会聚（如在K-装置） 收集在附近为一个群组群集位置 这不得不接近于0的平均剩余产能，通过设计 这很适合于我的测试数据集，但只要我扩展到全套（30万点）花的时间太长了，可能是因为我们要排序的完整列表O(NlogN)，然后迭代它，直到所有点都被分配O(NK)然后重复直到收敛
• 线性规划 这是非常简单的使用库来实现，还拿了由于复杂的时间太长了再次

我愿意在可能的算法/语言最适合做的任何建议。我有一个机器学习经验，但想不出这样使用的一种明显的方式。

让我知道如果我错过任何信息了。

Answer 1

既然你有两件已经，我的第一个新建议是划分为具有k均值的点K = N / 6400（你可以调整这个参数），然后每个超级群集上使用整数规划。当我有机会我会写我的其他建议，其中涉及随机转移四叉树解剖。

下面旧预问题编辑答案。

---

你似乎更关心的是最大限度地减少设备和运行时间比拥有最紧密的集群，所以这里是沿着这些线路的建议。

我们的想法是从1开始节点的群集，然后使用（几乎）完美匹配配对簇彼此，尺寸加倍。这样做6次获得的64簇。

为了计算匹配，我们使用每个集群的质心来代表它。现在，我们只需要在欧几里德平面上的一组点的近似匹配。随着道歉的欧几里得匹配许多优秀论文的作者，这里是一个为O​​（n log n）的启发。如果有两个或更少的点，在明显的方式匹配。否则，选择随机点P和通过比较它们的分区的其他点（x轴之间交替和y）与P（如在KD树）坐标，通过比较所述其他坐标断裂的关系。分配P至A一半奇数点，如果可能的。 （如果两者都均匀，令P是无与伦比的。）递归匹配半。

Answer 2

令p =小区（N / 64）。

这是设备的最佳数量。

令s =小区（SQRT（P））。

排序由所述x轴的数据。切片数据转换成每个（除了最后幻灯片）64个* S条目切片。

在每个切片，由y轴的数据进行排序。以64个对象中的每个并将它们分配到一个设备。人们很容易看到，但所有可能的最后设备的最佳利用，并关闭。

排序是如此难以置信的便宜，这将是非常快的。试试看吧，你很可能会在质量与运行时的权衡感到惊讶！我不会感到惊讶，如果发现有竞争力的结果，你试过除了LP的做法最，它会在短短几秒钟内运行。

或者：按自己的希尔伯特曲线的所有对象的坐标。分割成p个分区，分配每一个设备。

第二个是更难实现和可能更慢。它有时是好，但有时也差。

如果距离是对你更重要，请尝试以下策略：建立一个空间索引（例如，K-d树，或者如果你有半正弦波，A R *树）。对于每一个点，找到了63个最近的邻居和存储此。按距离排序，降。这会给你一个“困难”的分数。现在不要把设备在最困难的一点，但附近的 - 它的邻居用最小的MAX（距离难点，距离它63近邻）。重复这个几个点，但之后的数据的10％左右，再开始与其余各点的整个过程。问题是，你没有很好指定何时宁愿保持距离小，即使使用更多的设备，当...您可以结合这一点，只考虑邻居在一定约束。与邻居内结合最少的点则是最难的;和它的最好方法是用内绑定等最裸露点邻居覆盖