把顾客装进桶里
Packing customers into buckets
我有 25 个客户。每个客户都有我们系统的多个用户，例如客户 1 有 45 个用户，客户 2 有 46 个用户……客户 25 有 1000 个用户。
我想将每个客户放入一个桶中，每个桶包含大致相等数量的用户。我知道我一共要5桶
(这里的桶代表服务器，我想把我的客户端分配到不同的服务器，每个服务器的用户总数大致相等，以防止服务器过载。1个客户端必须在同一台服务器上（即不能将 1 个客户端拆分到 2 个服务器上）。
是否知道将客户分配到桶中的合适方法？我认为某些聚类方法可能有效（我尝试使用 R 的 kmeans），但我似乎无法找到规定每个集群中的用户总数大致相同的方法。
这是我的 R 代码，作为我到目前为止所做的示例：
#Create dataset
r <- data.frame(users=c(1000, 960, 920, 870, 850, 700, 600, 550, 520, 500, 420, 400, 390, 300, 210, 200, 160, 80, 70, 50, 49, 48, 47, 46, 45))
#Try kmeans clustering
fit <- kmeans(r, 5)
#get cluster means
aggregate(r, by=list(fit$cluster),FUN = mean)
#append cluster assignment
r <- data.frame(r,fit$cluster)
#Plot cluster
library(cluster)
clusplot(r, fit$cluster, color=TRUE, shade=TRUE, labels=2, lines=0)
library(fpc)
plotcluster(r, fit$cluster)
这会将我的客户聚类到桶中，但每个桶中的用户数量并不大致相等。
我已将其标记为 R 问题，但如果其他软件包中有简单的解决方案，我会洗耳恭听:-)
而不是尝试聚类（这解决了一个非常不同的问题，即将 相似 值放入聚类中）你在这里有 bin packing problem 的经典变体。
这些往往是 NP 难的，因此找到最优解的代价非常高。相反，尝试一种贪心策略：将最小桶大小估计为 total/buckets。以递减大小处理元素，并始终将它们放入具有最多 space 可用空间的桶中。为了获得更好的结果，添加一个优化函数，如果这可以改善结果，则可以在成对的桶之间交换元素。如果你有很多小值，这样的策略可能会很有效。
我不知道这种 'constant sum sampling ' 的推荐解决方案是什么。这是我的尝试——对项目进行排序，转换为每列代表一个样本的矩阵，每隔一行反转一次。
代码如下：
set.seed(1024)
r <- data.frame(users=c(1000, 960, 920, 870, 850, 700, 600, 550, 520, 500, 420, 400, 390, 300, 210, 200, 160, 80, 70, 50, 49, 48, 47, 46, 45))
a<- r$users #runif(n = 25, 100,400) #rnorm(25,100,100) # 1:25
#hist(a)
df<- data.frame(id=1:25,x=a)
# sort
x<- df$id[order(df$x)]
# convert to matrix
#each column of this matrix represetns one sample
xm<-matrix(x,ncol=5,byrow = T); xm
oldsum<-apply(matrix(df$x,ncol=5,byrow = T), 2,sum)
#flip alternate rows of this sorted matrix
i= 1:nrow(xm)
im=i[c(F,T)]
xm[im,]
xm[im,]<- rev(xm[im,])
# new matrix of indeices
xm
#hence the new matrix of values
xm2<- matrix(a[c(xm)],ncol = 5, byrow = F)
xm
xm2
newsum<- (apply(xm2, 2,sum))
# improvement
rbind(oldsum,newsum)
barplot(rbind(oldsum,newsum)[1,])
barplot(rbind(oldsum,newsum)[2,])
# each column of following matrix represents one sample
#(values are indices in original vector a)
xm
我有 25 个客户。每个客户都有我们系统的多个用户，例如客户 1 有 45 个用户，客户 2 有 46 个用户……客户 25 有 1000 个用户。
我想将每个客户放入一个桶中，每个桶包含大致相等数量的用户。我知道我一共要5桶
(这里的桶代表服务器，我想把我的客户端分配到不同的服务器，每个服务器的用户总数大致相等，以防止服务器过载。1个客户端必须在同一台服务器上（即不能将 1 个客户端拆分到 2 个服务器上）。
是否知道将客户分配到桶中的合适方法？我认为某些聚类方法可能有效（我尝试使用 R 的 kmeans），但我似乎无法找到规定每个集群中的用户总数大致相同的方法。
这是我的 R 代码，作为我到目前为止所做的示例：
#Create dataset
r <- data.frame(users=c(1000, 960, 920, 870, 850, 700, 600, 550, 520, 500, 420, 400, 390, 300, 210, 200, 160, 80, 70, 50, 49, 48, 47, 46, 45))
#Try kmeans clustering
fit <- kmeans(r, 5)
#get cluster means
aggregate(r, by=list(fit$cluster),FUN = mean)
#append cluster assignment
r <- data.frame(r,fit$cluster)
#Plot cluster
library(cluster)
clusplot(r, fit$cluster, color=TRUE, shade=TRUE, labels=2, lines=0)
library(fpc)
plotcluster(r, fit$cluster)
这会将我的客户聚类到桶中，但每个桶中的用户数量并不大致相等。
我已将其标记为 R 问题，但如果其他软件包中有简单的解决方案，我会洗耳恭听:-)
而不是尝试聚类（这解决了一个非常不同的问题，即将 相似 值放入聚类中）你在这里有 bin packing problem 的经典变体。
这些往往是 NP 难的，因此找到最优解的代价非常高。相反，尝试一种贪心策略：将最小桶大小估计为 total/buckets。以递减大小处理元素，并始终将它们放入具有最多 space 可用空间的桶中。为了获得更好的结果，添加一个优化函数，如果这可以改善结果，则可以在成对的桶之间交换元素。如果你有很多小值，这样的策略可能会很有效。
我不知道这种 'constant sum sampling ' 的推荐解决方案是什么。这是我的尝试——对项目进行排序，转换为每列代表一个样本的矩阵，每隔一行反转一次。
代码如下：
set.seed(1024)
r <- data.frame(users=c(1000, 960, 920, 870, 850, 700, 600, 550, 520, 500, 420, 400, 390, 300, 210, 200, 160, 80, 70, 50, 49, 48, 47, 46, 45))
a<- r$users #runif(n = 25, 100,400) #rnorm(25,100,100) # 1:25
#hist(a)
df<- data.frame(id=1:25,x=a)
# sort
x<- df$id[order(df$x)]
# convert to matrix
#each column of this matrix represetns one sample
xm<-matrix(x,ncol=5,byrow = T); xm
oldsum<-apply(matrix(df$x,ncol=5,byrow = T), 2,sum)
#flip alternate rows of this sorted matrix
i= 1:nrow(xm)
im=i[c(F,T)]
xm[im,]
xm[im,]<- rev(xm[im,])
# new matrix of indeices
xm
#hence the new matrix of values
xm2<- matrix(a[c(xm)],ncol = 5, byrow = F)
xm
xm2
newsum<- (apply(xm2, 2,sum))
# improvement
rbind(oldsum,newsum)
barplot(rbind(oldsum,newsum)[1,])
barplot(rbind(oldsum,newsum)[2,])
# each column of following matrix represents one sample
#(values are indices in original vector a)
xm