группировка объектов для достижения аналогичного среднего свойства для всех групп
У меня есть набор объектов, каждый из которых имеет численный «вес». Я хотел бы создать группы этих объектов, так что каждая группа имеет примерно одно и то же среднее арифметическое весов объектов.
Группы не обязательно будут иметь одинаковое количество членов, но размер групп будет находиться в пределах друг от друга. В терминах чисел будет от 50 до 100 объектов, а максимальный размер группы будет около 5.
Это хорошо известный тип проблемы? Это похоже на проблему с рюкзаком или разделом. Известны ли эффективные алгоритмы для решения этой проблемы?
В качестве первого шага я создал скрипт python, который обеспечивает очень грубую эквивалентность средних весов, сортируя объекты по массе, подгруппируя эти объекты, а затем распределяя член каждой подгруппы в одну из конечных групп.
Мне удобнее программировать на python, поэтому, если существующие пакеты или модули существуют для достижения части этой функциональности, я был бы рад услышать о них.
Благодарим вас за помощь и предложения.
3 Solutions collect form web for “группировка объектов для достижения аналогичного среднего свойства для всех групп”
Вы можете попробовать использовать кластеризацию k-mean :
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-mean использует случайные догадки, чтобы изначально выбрать центры k групп. Это означает, что повторные прогоны одного и того же кода могут давать разные результаты, особенно если весы не разделяются на четко определенные группы.
Вам также придется обвести пороговый параметр, чтобы создать желаемое количество групп.
Следующая программа – недорогая эвристика. То, что он делает, – это распределять значения между «ведрами», размещая большие значения вместе с небольшими, выбирая значения с одного конца отсортированного списка за один раунд, а с другого конца на следующий. Выполнение распределения в round-robin гарантирует соблюдение правил о количестве элементов на ведро. Это эвристический алгоритм, а не алгоритм, потому что он имеет тенденцию производить хорошие решения, но без гарантии, что лучших не существует.
Теоретически, если есть достаточно значений, и они равномерно или нормально распределены, то вероятность того, что просто случайное размещение значений в ведрах приведет к одинаковым средствам для ведер. Предполагая, что набор данных невелик, эта эвристика улучшает шансы на хорошее решение. Знание больше о размере и статистическом распределении наборов данных поможет разработать более эффективную эвристику или алгоритм.
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 (aka centroid-based) – это то, что вы, вероятно, захотите сделать.