小编Pie*_*ger的帖子

可能重复:
具有相等簇大小的K均值算法变化

编辑:像casperOne指出,这个问题是重复的.无论如何,这是一个更普遍的问题,涵盖这一个:https://stats.stackexchange.com/questions/8744/clustering-procedure-where-each-cluster-has-an-equal-number-of-points

我的要求

在一个项目中,我需要将n个点(x,y)分组为相同大小的k个簇(n/k).其中x和y是双浮点数,n的范围可以是100到10000,k的范围是2到100.在算法运行之前k也是已知的.

我的实验

我开始使用http://en.wikipedia.org/wiki/K-means_clustering算法来解决这个问题,该算法非常快速地生成大致相同大小的k个簇.

但我的问题是,K-means产生大小相同的簇,我需要簇的大小完全相同(或者更精确:我需要它们的大小介于地板之间(n/k)和ceil(n/k)).

在你向我指出之前,是的,我在这里尝试了第一个答案K-means算法变化具有相同的簇大小,这听起来是个好主意.

主要思想是通过K-means对集群产生的数组进行后处理.从最大的集群到最小的集群.我们通过将额外的点移动到其他最近的集群来减少具有超过n/k成员的集群的大小.单独留下已经减少的集群.

这是我实现的伪代码:

n is the number of point
k is the number of cluster
m = n / k (the ideal cluster size)
c is the array of cluster after K-means
c' = c sorted by size in descending order
for each cluster i in c' where i = 1 to k - 1
    n = size of cluster i - m (the number …

场景(我简化了一些事情):

• 许多最终用户可以从前端Web应用程序(生产者)开始工作(繁重的工作,例如渲染大型PDF).
• 作业将发送到单个持久的RabbitMQ队列.
• 许多工作者应用程序(使用者)处理这些作业并将结果写回数据存储区.

这个相当标准的模式工作正常.

问题是:如果用户在同一分钟内启动了10个作业,并且在一天中的那个时间只有10个工作者应用程序启动,则该最终用户有效地接管了他自己的所有计算时间.

问题:如何确保每个最终用户只能处理一个作业？(奖励:一些最终用户(例如管理员)不得受到限制)

此外,我不希望前端应用程序阻止最终用户启动并发作业.我只希望最终用户等待他们的并发作业一次完成一个.

解决方案？:我应该为每个最终用户动态创建一个自动删除独占队列吗？如果是,我如何告诉worker应用程序开始使用此队列？如何确保一个(并且只有一个)工作者将从此队列中消耗？