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

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;
}