группировка объектов для достижения аналогичного среднего свойства для всех групп

Вы можете попробовать использовать кластеризацию k-средних:

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-средних использует случайные предположения для первоначального выбора центров k групп. Это означает, что повторные запуски одного и того же кода могут давать разные результаты, особенно если веса не разделяются на четко различимые группы.

Вам также придется изменить параметр порога, чтобы получить желаемое количество групп.

Следующая программа представляет собой недорогую эвристику. Что он делает, так это распределяет значения по «сегментам», помещая большие значения вместе с маленькими, выбирая значения с одного конца отсортированного списка в одном раунде и с другого конца в следующем. Выполнение распределения в циклическом режиме гарантирует соблюдение правил о количестве элементов в корзине. Это эвристика, а не алгоритм, потому что он имеет тенденцию давать хорошие решения, но не гарантирует, что лучших не существует.

Теоретически, если значений достаточно и они распределены равномерно или нормально, то есть вероятность, что просто случайное размещение значений в корзинах приведет к одинаковым средним значениям для корзин. Предполагая, что набор данных небольшой, эта эвристика повышает шансы на хорошее решение. Знание большего размера и статистического распределения наборов данных поможет разработать лучшую эвристику или алгоритм.

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)).

Вы также можете попробовать алгоритм связи на основе центроида, который достигает того же.

См. это для кода и это для понимания.

UPGMA (на основе центроида) — это то, что вы, вероятно, захотите сделать.