5

オブジェクトのコレクションがあり、それぞれに数値の「重み」があります。各グループのオブジェクトの重みの算術平均がほぼ同じになるように、これらのオブジェクトのグループを作成したいと思います。

グループのメンバー数は必ずしも同じではありませんが、グループのサイズは互いに 1 つの範囲内になります。数に関しては、50 ～ 100 個のオブジェクトがあり、最大グループ サイズは約 5 です。

これはよく知られたタイプの問題ですか? ナップザックまたはパーティションの問題に少し似ているようです。それを解決するために知られている効率的なアルゴリズムはありますか?

最初のステップとして、オブジェクトを重みでソートし、これらのオブジェクトをサブグループ化し、各サブグループのメンバーを最終的なグループの 1 つに分配することによって、平均重みの非常に大雑把な等価性を達成する Python スクリプトを作成しました。

私は Python でのプログラミングに慣れているので、この機能の一部を実現する既存のパッケージまたはモジュールが存在する場合は、それらについて聞いていただければ幸いです。

あなたの助けと提案に感謝します。

4

3 に答える 3

2

以下のプログラムは、低コストのヒューリスティックです。それが行うことは、あるラウンドでソートされたリストの一方の端から値を選択し、次のラウンドでもう一方の端から値を選択することにより、小さな値と一緒に大きな値を配置する「バケット」間で値を分配することです。ラウンド ロビンで配布を行うことで、バケットあたりの要素数に関する規則が満たされることが保証されます。これはヒューリスティックであり、アルゴリズムではありません。これは、優れたソリューションを生成する傾向があるためですが、より優れたソリューションが存在しないという保証はありません。

理論的には、十分な値があり、それらが均一または正規分布している場合、バケットに値をランダムに配置するだけで、バケットの平均が同じになる可能性があります。データセットが小さいと仮定すると、このヒューリスティックは適切なソリューションの可能性を高めます。データセットのサイズと統計的分布について詳しく知ることは、より優れたヒューリスティックまたはアルゴリズムを考案するのに役立ちます。

from random import randint, seed
from itertools import cycle,chain

def chunks(q, n):
    q = list(q)
    for i in range(0, len(q), n):
       yield q[i:i+n]

def shuffle(q, n):
    q = list(q)
    m = len(q)//2
    left =  list(chunks(q[:m],n))
    right = list(chunks(reversed(q[m:]),n)) + [[]]
    return chain(*(a+b for a,b in zip(left, right)))

def listarray(n):
    return [list() for _ in range(n)]

def mean(q):
    return sum(q)/len(q)

def report(q):
    for x in q:
        print mean(x), len(x), x

SIZE = 5
COUNT= 37

#seed(SIZE)
data = [randint(1,1000) for _ in range(COUNT)]
data = sorted(data)
NBUCKETS = (COUNT+SIZE-1) // SIZE

order = shuffle(range(COUNT), NBUCKETS)
posts = cycle(range(NBUCKETS))
buckets = listarray(NBUCKETS)
for o in order:
    i = posts.next()
    buckets[i].append(data[o])
report(buckets)
print mean(data)

複雑さは、並べ替えステップのために対数です。これらはサンプル結果です:

439 5 [15, 988, 238, 624, 332]
447 5 [58, 961, 269, 616, 335]
467 5 [60, 894, 276, 613, 495]
442 5 [83, 857, 278, 570, 425]
422 5 [95, 821, 287, 560, 347]
442 4 [133, 802, 294, 542]
440 4 [170, 766, 301, 524]
418 4 [184, 652, 326, 512]
440

バケットのサイズに関する要件が支配的であることに注意してください。これは、元のデータの分散が大きい場合、平均が近くにならないことを意味します。このデータセットで試すことができます：

data = sorted(data) + [100000]

含まれているバケット100000は、少なくとも別の 3 つのデータムを取得します。

私は、子供たちのグループがさまざまな額面の紙幣のパックを手渡され、このゲームのルールに従ってそれらを共有するように言われた場合に何をするかというヒューリスティックな考えを思いつきました. これは統計的に妥当であり、O(log(N)) です。

于 2010-12-30T15:50:26.973 に答える
1

同じことを達成する重心ベースのリンケージ アルゴリズムを試すこともできます。

コードについてはこちらを、理解についてはこちらを参照してください。

UPGMA (別名セントロイドベース) は、おそらくやりたいことです。

于 2010-12-16T16:59:55.270 に答える
1

k-means クラスタリングを使用してみてください:

import scipy.cluster.vq as vq
import collections
import numpy as np

def auto_cluster(data,threshold=0.1,k=1):
    # There are more sophisticated ways of determining k
    # See http://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set
    data=np.asarray(data)
    distortion=1e20
    while distortion>threshold:
        codebook,distortion=vq.kmeans(data,k)
        k+=1   
    code,dist=vq.vq(data,codebook)    
    groups=collections.defaultdict(list)
    for index,datum in zip(code,data):
        groups[index].append(datum)
    return groups

np.random.seed(784789)
N=20
weights=100*np.random.random(N)
groups=auto_cluster(weights,threshold=1.5,k=N//5)
for index,data in enumerate(sorted(groups.values(),key=lambda d: np.mean(d))):
    print('{i}: {d}'.format(i=index,d=data))

上記のコードは、N 個の重みのランダムなシーケンスを生成します。scipy.cluster.vq.kmeansを使用して、シーケンスをk互いに近い数値のクラスターに分割します。歪みがしきい値を超えている場合、kmeans はk増加して再計算されます。これは、歪みが所定のしきい値を下回るまで繰り返されます。

次のようなクラスターが生成されます。

0: [4.9062151907551366]
1: [13.545565038022112, 12.283828883935065]
2: [17.395300245930066]
3: [28.982058040201832, 30.032607500871023, 31.484125759701588]
4: [35.449637591061979]
5: [43.239840915978043, 48.079844689518424, 40.216494950261506]
6: [52.123246083619755, 53.895726546070463]
7: [80.556052179748079, 80.925071671718413, 75.211470587171803]
8: [86.443868931310249, 82.474064251040375, 84.088655128258964]
9: [93.525705849369416]

k-means クラスタリング アルゴリズムは、ランダムな推測を使用して、最初にkグループの中心を選択することに注意してください。これは、特に重みが明確に異なるグループに分離されていない場合、同じコードを繰り返し実行すると異なる結果が生じる可能性があることを意味します。

また、必要な数のグループを生成するために、しきい値パラメーターを調整する必要があります。

于 2010-12-16T16:53:09.093 に答える