バケツに顧客を詰め込む

Question

私は25人の顧客を持っています。各顧客には、システムのユーザーが多数います（例：顧客1は45人のユーザー、顧客2は46人のユーザー、顧客25は1000人のユーザーです。

私は各顧客をバケットに入れておきたいと思います。バケットには、ほぼ同じ数のユーザーが含まれています。私は合計で5つのバケツが必要であることを知っています。

（ここでは、バケットはサーバーを表しています。サーバーのオーバーロードを防ぐために、サーバーあたりのユーザーの総数がほぼ等しい別のサーバーにクライアントを割り当てる必要があります。つまり、2つのサーバーで1つのクライアントを分割することはできません）。

バケットに顧客を配分するのに適した方法はありますか？いくつかのクラスタリング方法が効果的かもしれないと思っています。

これまで私が行ってきたことの一例として、私の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の問題としてこれをタグ付けしましたが、他のいくつかのパッケージでは簡単な解決策があるのなら、私は

Answer 1

このような「定合計サンプリング」に推奨される解決策は何か分かりません。ここで私のショットです - 項目を並べ替える、各列がサンプルを表す行列に変換、他のすべての行を逆にします。これは大丈夫ビンパッキング問題のように見える

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 

Answer 2

:-)すべての耳だというよりも非常にdiffefent問題を解決クラスタリング（即ち入れをしよう類似のの値をクラスタに追加した場合）、bin packing problemの古典的なバリエーションがあります。

これらはNP困難な傾向があるため、最適なソリューションを見つけることは非常にコストがかかります。代わりに、貪欲な戦略を試してみてください。最小バケットサイズをトータル/バケットとして見積もります。要素を降順に処理し、利用可能なスペースが最も多いバケットに常に配置します。より良い結果を得るには、バケットのペア間で要素を交換する最適化関数を追加して、結果が改善されるようにします。小さな値がたくさんある場合、そのような戦略はうまくいくかもしれません。