每个簇大小具有上限要求的聚类算法

Question

我需要将大约 50000 个点划分为不同的簇。有一个要求：每个簇的大小不能超过K。有没有任何聚类算法可以完成这项工作？

请注意，每个簇的上限 K 都是相同的，比如 100。

Answer 1

大多数聚类算法可用于创建树，其中最低级别只是单个元素 - 要么是因为它们自然地通过连接成对元素然后连接元素组来“自下而上”地工作，要么因为 - 就像 K 均值一样，它们可用于反复将组分成更小的组。

一旦你有了一棵树，你就可以决定在哪里分割子树以形成大小 <= 100 的簇。修剪现有的树通常非常容易。假设您想要划分现有树以最小化您创建的集群的一些成本总和。您可能有：

f(tree-node, list_of_clusters)
{
  cost = infinity;
  if (size of tree below tree-node <= 100)
  {
    cost = cost_function(stuff below tree-node);
  }
  temp_list = new List();
  cost_children = 0;
  for (children of tree_node)
  {
    cost_children += f(child, temp_list);
  }
  if (cost_children < cost)
  {
    list_of_clusters.add_all(temp_list);
    return cost_children;
  }
  list_of_clusters.add(tree_node);
  return cost;
}

Answer 2

一种方法是使用分层 K-means，但是你不断地分裂每个大于K的簇，直到它们都变小。

另一种（在某种意义上相反的方法）是使用分层凝聚聚类 ，即一种自下而上的方法，并再次确保如果它们将形成一个大小为 > 的新簇，则不要合并簇。 K.

Answer 3

朴素聚类的问题在于，您确实必须计算一个距离矩阵，该距离矩阵保存 A 与集合中每个其他成员的距离。这取决于您是否对总体进行了预处理，或者是否将聚类合并为典型个体，然后再次重新计算距离矩阵。