使用最大聚类大小进行聚类

Question

我有一组n个节点，每个节点都有一个权重w。另外，我有一个矩阵，存储了这些点之间的差异。

我的目标是将这些节点分成固定大小的组，使得它们之间的距离最小。此外，每个组都有一个特定的容量限制，对于每个组而言相等，因此属于该组的节点的权重之和不能大于该容量。

我对此进行了一些研究，但只找到了像这篇论文一样的论文，仅导致每个聚类中有同样多的点，但没有添加每个点的权重。

我的问题是：是否有一种算法可以解决这个问题？

- PKuhn

---

对于额外的容量限制，所有群组是否有一个容量？如果没有，您知道将有多少聚类群组以及如何识别这些群组吗？除此之外，对我来说，这似乎是可以使用LP/QP解决的问题。例如，最小距离与约束sum(w_i,g) <= capacity_g和群集分配函数。 - bro

基本上是有容量限制的设施选址。 - David Eisenstat

Answer 1

一种可能的方法是遵循K-means相同的原则，同时确保满足约束条件。为此，您必须在步骤2-3之间进行迭代：

1. 将数据点分配到簇（随机）
2. 计算每个簇的质心
3. 将点分配给簇，使得：
   • 点到质心的平方距离总和最小
   • 每个簇中节点的权重之和不超过容量

该算法保证每一步都会有所改进。然而，像k-means一样，它收敛于局部最优解。与K-means的主要区别在于K-means中的第3步是一个简单的操作，可以在O(n)内执行，而在您的情况下，第3步是NP完全优化问题。但是，根据数据集，很有可能可以在合理的时间内解决此问题。

我有一个这个算法的Python 实现。您可以尝试在您的数据上运行它，并查看是否适用于您的情况。

- Behrouz Babaki

Answer 2

不要使用聚类，而是看看索引批量加载策略。

聚类通常涉及对数据集进行结构化处理。

面向磁盘的索引通常具有块大小以满足需求。在8k页面上，您只能存储8k的数据，因此需要将数据集拆分为最大大小的块。

还要看看DIANA。这种经典的聚类算法是自上而下的方法。它从完整的数据集开始，然后重复分割。您可以使用此方法并继续分割，直到达到所需的最大群集大小。

- Has QUIT--Anony-Mousse

Answer 3

与其将其建模为线性规划问题，不妨寻找“图割度量”以创建“平衡分区”，并寻找最大化“模块化”的算法。这些是活跃的学术研究领域。根据Parthasarathy和Faisal的论文（Aggarwal和Reddy的教科书《数据聚类，算法和应用》第17章），优化任何这些目标函数都是NP难问题（特别是在像您这样的附加约束条件下）。

- knb