सभी समूहों के लिए समान अर्थ संपत्ति प्राप्त करने के लिए वस्तुओं को समूहीकृत करना

Question

मेरे पास ऑब्जेक्ट्स का संग्रह है, जिनमें से प्रत्येक का संख्यात्मक 'भार' है। मैं इन वस्तुओं के समूह बनाना चाहता हूं जैसे कि प्रत्येक समूह में वस्तु वजन के लगभग अंकगणितीय अर्थ होते हैं।

समूहों के पास सदस्यों की संख्या समान नहीं होगी, लेकिन समूहों का आकार एक दूसरे के भीतर होगा। संख्याओं के संदर्भ में, 50 से 100 वस्तुओं के बीच होगा और अधिकतम समूह आकार लगभग 5

क्या यह एक प्रसिद्ध प्रकार की समस्या है? यह एक knapsack या विभाजन की समस्या की तरह थोड़ा लगता है। कुशल एल्गोरिदम इसे हल करने के लिए जाना जाता है?

पहले चरण के रूप में, मैंने एक पायथन लिपि बनाई है जो वजन से वस्तुओं को क्रमबद्ध करके, इन वस्तुओं को घटाना, और फिर प्रत्येक उपसमूह के सदस्य को अंतिम समूहों में से एक को वितरित करके औसत वजन के बहुत क्रूड समकक्ष प्राप्त करता है।

मैं पाइथन में आरामदायक प्रोग्रामिंग कर रहा हूं, इसलिए यदि मौजूदा कार्यक्षमता या मॉड्यूल इस कार्यक्षमता के हिस्से को प्राप्त करने के लिए मौजूद हैं, तो मैं उनके बारे में सुनवाई की सराहना करता हूं।

आपकी सहायता और सुझावों के लिए धन्यवाद।

Answer 1

आप k-means clustering आज़मा सकते हैं:

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

कोड ऊपर एन वजन का एक यादृच्छिक अनुक्रम उत्पन्न करता है। यह scipy.cluster.vq.kmeans का उपयोग करता है ताकि अनुक्रम को k संख्याओं के क्लस्टर में विभाजित किया जा सके जो एक साथ निकट हैं। यदि विरूपण एक सीमा से ऊपर है, तो k के साथ kmeans recomputed है। यह तब तक दोहराता है जब तक विरूपण दिए गए थ्रेसहोल्ड से नीचे न हो।

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 समूहों के केन्द्रों लेने के लिए:

यह इस जैसे समूहों अर्जित करता है। इसका मतलब है कि एक ही कोड के दोहराए गए रन अलग-अलग परिणाम उत्पन्न कर सकते हैं, खासकर अगर वजन स्पष्ट रूप से अलग समूहों में अलग नहीं होते हैं।

आपको वांछित संख्या समूहों का उत्पादन करने के लिए थ्रेसहोल्ड पैरामीटर को भी जोड़ना होगा।

Answer 2

आप एक केंद्रित-आधारित लिंकेज एल्गोरिदम भी आज़मा सकते हैं, जो इसे प्राप्त करता है।

कोड के लिए this और this समझने के लिए देखें।

यूपीजीएमए (उर्फ सेंट्रॉइड-आधारित) वह है जो आप शायद करना चाहते हैं।

Answer 3

निम्नानुसार कार्यक्रम एक कम लागत वाली ह्युरिस्टिक है। यह क्या करता है एक बाउंड पर एक क्रमबद्ध सूची के एक छोर से मूल्यों को चुनकर, और दूसरे छोर से दूसरे भाग से मूल्यों को चुनकर छोटे बालों के साथ बड़े मूल्यों को "बाल्टी" के बीच मूल्य वितरित करता है। राउंड-रॉबिन में वितरण करना गारंटी देता है कि प्रति बाल्टी तत्वों की संख्या के नियमों को पूरा किया जाता है। यह एक ह्युरिस्टिक है और एल्गोरिदम नहीं है क्योंकि यह अच्छे समाधान का उत्पादन करता है, लेकिन गारंटी के बिना कि बेहतर लोग मौजूद नहीं हैं।

सिद्धांत रूप में, अगर वहाँ पर्याप्त मूल्यों हैं, और वे समान रूप से या सामान्य रूप से वितरित कर रहे हैं, तो संभावना है कि सिर्फ बेतरतीब ढंग से बाल्टी में मान रखने के लिए बाल्टी एक जैसे साधन का परिणाम देगा रहे हैं।यह मानते हुए कि डेटासेट छोटा है, यह हेरिस्टिक एक अच्छे समाधान की संभावनाओं में सुधार करता है। डेटासेट के आकार और सांख्यिकीय वितरण के बारे में और जानना बेहतर हेरिस्टिक या एल्गोरिदम तैयार करने में मदद करेगा।

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 डाटुमस मिल जाएगा।

मैं इस उदारवादी सोच के साथ आया कि यह अलग-अलग संप्रदायों के बिलों का एक पैक सौंपने पर बच्चों का एक समूह होगा और उन्हें इस खेल के नियमों के अनुसार साझा करने के लिए कहा जाएगा। यह सांख्यिकीय रूप से उचित है, और ओ (लॉग (एन))।