0

私はそれぞれが単一のスコアを持っている多くの科目を持っています。結果として得られるグループがすべて（ほぼ）等しい平均スコアを持つように、これらのサブジェクトをいくつかの（ほぼ）等しいサイズのグループに割り当てたいと思います。概念的に、これを実行するための最も賢い方法は何ですか？コードをMATLABで実装します。

私の最初の解決策は、科目をスコアで並べ替えることです。次に、カードディーラーが多くのプレーヤーにカードを配るのと同じように、グループを交互に分けてサブジェクトをグループに割り当てます。これはかなりうまくいきますが、もっと良い方法があるかどうか疑問に思っています。

n = 200; %number of subjects
k = 5; %number of desired groups
subjects = linspace(1,n,n)'; %subject ids
scores = randi(100,n,1); %scores
data = [subjects,scores];
data = sortrows(data,-2);
group_subjects = cell(1,k);
group_scores = cell(1,k);
x=1;
for i = 1:n
   if x>k, x=1; end
   group_subjects{x} = [group_subjects{x},data(i,1)];
   group_scores{x} = [group_scores{x},data(i,2)];
   x = x+1;
end
avg_scores = cellfun(@mean,group_scores)

私の最終的な目標は、のようにグループごとに主題を出力することgroup_subjectsです。

4

1 に答える 1

0

これまでのところ、「開始」パーティションとして保持することをお勧めします。

このような開始パーティションができたら、平均が最大および最小のパーティションを取得し、平均をグローバル平均に近づけるために、何らかのルールでそれらの間でメンバーを交換することをお勧めします。最大と最小のパーティションを持つ現在のパーティションに切り替える適切なメンバーのペアが見つからなくなるまでループでそれを繰り返す場合（つまり、各スワップ後に最大と最小のパーティションを選択する）、次のようになります。少なくとも局所最適を残しました。

では、交換する適切な番号のペアをどのように選択しますか？さて、あなたはそれらの差がそれらの平均を等しくするために必要な合計の変化からどれだけ離れているかを最小にするような数を探しています、そしてそれらが平均を過剰に補償してそれらをさらに大きくすることを引き起こしてはならないという追加の制限があります離れて。

while 1
 sm_idx=find(avg_scores==min(avg_scores),1); %Choose a set with the smallest average
 lg_idx=find(avg_scores==max(avg_scores),1); %Same with largest average
 pcorr=round((avg_scores(lg_idx)-avg_scores(sm_idx))*...
  (length(group_scores{lg_idx})*length(group_scores{sm_idx}))/...
  (length(group_scores{lg_idx})+length(group_scores{sm_idx}))); %Calculate perfect correction
 M = group_scores{lg_idx}'*ones(size(group_scores{sm_idx}))-...
  ones(size(group_scores{lg_idx}'))*group_scores{sm_idx}; %note: assumes group_scores are row vectors
 Midx=find(abs(M-pcorr)==min(abs(M-pcorr)(:)),1);
 if (abs(M(Midx)-pcorr)>=pcorr)
     break;
 end
 [l_c_idx,s_c_idx] = ind2sub(size(M),Midx);
 temp=group_scores{lg_idx}(l_c_idx);
 group_scores{lg_idx}(l_c_idx)=group_scores{sm_idx}(s_c_idx);
 group_scores{sm_idx}(s_c_idx)=temp;
 temp=group_subjects{lg_idx}(l_c_idx);
 group_subjects{lg_idx}(l_c_idx)=group_subjects{sm_idx}(s_c_idx);
 group_subjects{sm_idx}(s_c_idx)=temp;
 avg_scores(lg_idx)=avg_scores(lg_idx)-M(Midx)/length(group_scores{lg_idx});
 avg_scores(sm_idx)=avg_scores(sm_idx)+M(Midx)/length(group_scores{sm_idx});
end

コードのフォローアップとしてテストすると、次のような結果が得られます。

私のループの前に：

avg_scores =
 54.000
 53.525
 53.050
 52.500
 51.925

私のループの後：

avg_scores =
 53.000
 53.000
 53.000
 53.000
 53.000

ご覧のとおり、完璧な結果が得られる場合があります。

コードに関するちょっとした好奇心の1つは、記述されているように、結果を生成する最初の一致を常に優先することです。最適なソリューションを見つける可能性をもう少し高くするためのもう少しランダム性については、次のように置き換えることができます

Midx=find(abs(M-pcorr)==min(abs(M-pcorr)(:)),1);

と

Midx_options=find(abs(M-pcorr)==min(abs(M-pcorr)(:)));
Midx=Midx(randi(length(Midx)));

これにより、最適なスイッチのセットからランダムに最適なスイッチが選択されます。

于 2013-03-22T01:29:30.200 に答える