के-मतलब ++ कैसे काम करता है?

Question

मुझे के-साधन ++ एल्गोरिदम को पूरी तरह से समझने में समस्या हो रही है। मुझे वास्तव में दिलचस्पी है कि पहले के सेंट्रॉइड कैसे चुने जाते हैं (शेष मूल के-साधनों की तरह है)।

1. क्या दूरी या गाऊसी के आधार पर उपयोग की जाने वाली संभावना कार्य है?
2. उसी समय एक नए केंद्र के लिए सबसे लंबा दूर बिंदु (अन्य सेंट्रॉइड से) चुना जाता है।

मैं चरण-दर-चरण स्पष्टीकरण और एक उदाहरण की सराहना करता हूं। विकिपीडिया में से एक पर्याप्त स्पष्ट नहीं है। इसके अलावा एक बहुत अच्छी तरह से टिप्पणी स्रोत कोड भी मदद मिलेगी। यदि आप 6 सरणी का उपयोग कर रहे हैं तो कृपया हमें बताएं कि कौन सा है।

Answer 1

दिलचस्प सवाल। इस पेपर को मेरे ध्यान में लाने के लिए धन्यवाद। PDF link here of the original paper.

सरल शब्दों में, क्लस्टर केन्द्रों शुरू में इनपुट अवलोकन वैक्टर के सेट, जहां वेक्टर x चुनने की संभावना अधिक है अगर x किसी भी पहले से चुना केंद्रों के पास नहीं है से यादृच्छिक पर चुना जाता है।

यहां एक आयामी उदाहरण है। हमारे अवलोकन [0, 1, 2, 3, 4] हैं। पहले केंद्र, c1, 0 हो। संभावना है कि अगला क्लस्टर केंद्र, c2, x ||c1-x||^2 के आनुपातिक है। तो, पी (सी 2 = 1) = 1 ए, पी (सी 2 = 2) = 4 ए, पी (सी 2 = 3) = 9 ए, पी (सी 2 = 4) = 16 ए, जहां एक = 1/(1 + 4 + 9 + 16)।

मान लीजिए c2 = 4। फिर, पी (सी 3 = 1) = 1 ए, पी (सी 3 = 2) = 4 ए, पी (सी 3 = 3) = 1 ए, जहां एक = 1/(1 + 4 + 1)।

मैंने पायथन में प्रारंभिक प्रक्रिया को कोड किया है; मुझे नहीं पता कि यह आपकी मदद करता है या नहीं। स्पष्टीकरण के साथ

def initialize(X, K): 
    C = [X[0]] 
    for k in range(1, K): 
     D2 = scipy.array([min([scipy.inner(c-x,c-x) for c in C]) for x in X]) 
     probs = D2/D2.sum() 
     cumprobs = probs.cumsum() 
     r = scipy.rand() 
     for j,p in enumerate(cumprobs): 
      if r < p: 
       i = j 
       break 
     C.append(X[i]) 
    return C 

संपादित करें: cumsum के उत्पादन में हमें सीमाओं अंतराल [0,1] विभाजन देता है। इन विभाजनों में केंद्र के रूप में चुने गए इसी बिंदु की संभावना के बराबर लंबाई होती है। तो फिर, r के बीच समान रूप से [0,1] के बीच चुना गया है, यह इन अंतराल में से एक में गिर जाएगा (break की वजह से)। for पाश चेकों को देखने के लिए जो विभाजन r में है

उदाहरण:।

probs = [0.1, 0.2, 0.3, 0.4] 
cumprobs = [0.1, 0.3, 0.6, 1.0] 
if r < cumprobs[0]: 
    # this event has probability 0.1 
    i = 0 
elif r < cumprobs[1]: 
    # this event has probability 0.2 
    i = 1 
elif r < cumprobs[2]: 
    # this event has probability 0.3 
    i = 2 
elif r < cumprobs[3]: 
    # this event has probability 0.4 
    i = 3 

Answer 2

मैं k-साधन ++ पुस्तक "कलेक्टिव खुफिया" टोबी Segaran और k से के आधार पर की एक पूरी स्रोत कार्यान्वयन तैयार किया है -मेनस ++ प्रारंभिकरण यहां प्रदान किया गया।

वास्तव में यहां दो दूरस्थ कार्य हैं। प्रारंभिक सेंट्रॉइड के लिए एक मानक एक numpy.inner आधारित होता है और फिर सेंट्रॉइड फिक्सेशन के लिए पियरसन का उपयोग किया जाता है। शायद पियरसन को प्रारंभिक सेंट्रॉइड के लिए भी इस्तेमाल किया जा सकता है। वे कहते हैं कि यह बेहतर है।

from __future__ import division 

def readfile(filename): 
    lines=[line for line in file(filename)] 
    rownames=[] 
    data=[] 
    for line in lines: 
    p=line.strip().split(' ') #single space as separator 
    #print p 
    # First column in each row is the rowname 
    rownames.append(p[0]) 
    # The data for this row is the remainder of the row 
    data.append([float(x) for x in p[1:]]) 
    #print [float(x) for x in p[1:]] 
    return rownames,data 

from math import sqrt 

def pearson(v1,v2): 
    # Simple sums 
    sum1=sum(v1) 
    sum2=sum(v2) 

    # Sums of the squares 
    sum1Sq=sum([pow(v,2) for v in v1]) 
    sum2Sq=sum([pow(v,2) for v in v2])  

    # Sum of the products 
    pSum=sum([v1[i]*v2[i] for i in range(len(v1))]) 

    # Calculate r (Pearson score) 
    num=pSum-(sum1*sum2/len(v1)) 
    den=sqrt((sum1Sq-pow(sum1,2)/len(v1))*(sum2Sq-pow(sum2,2)/len(v1))) 
    if den==0: return 0 

    return 1.0-num/den 

import numpy 
from numpy.random import * 

def initialize(X, K): 
    C = [X[0]] 
    for _ in range(1, K): 
     #D2 = numpy.array([min([numpy.inner(c-x,c-x) for c in C]) for x in X]) 
     D2 = numpy.array([min([numpy.inner(numpy.array(c)-numpy.array(x),numpy.array(c)-numpy.array(x)) for c in C]) for x in X]) 
     probs = D2/D2.sum() 
     cumprobs = probs.cumsum() 
     #print "cumprobs=",cumprobs 
     r = rand() 
     #print "r=",r 
     i=-1 
     for j,p in enumerate(cumprobs): 
      if r 0: 
     for rowid in bestmatches[i]: 
      for m in range(len(rows[rowid])): 
      avgs[m]+=rows[rowid][m] 
     for j in range(len(avgs)): 
      avgs[j]/=len(bestmatches[i]) 
     clusters[i]=avgs 

    return bestmatches 

rows,data=readfile('/home/toncho/Desktop/data.txt') 

kclust = kcluster(data,k=4) 

print "Result:" 
for c in kclust: 
    out = "" 
    for r in c: 
     out+=rows[r] +' ' 
    print "["+out[:-1]+"]" 

print 'done' 

data.txt:

 
p1 1 5 6 
p2 9 4 3 
p3 2 3 1 
p4 4 5 6 
p5 7 8 9 
p6 4 5 4 
p7 2 5 6 
p8 3 4 5 
p9 6 7 8 

Answer 3

एक लाइनर।मान लें कि हमें उन सभी को यादृच्छिक रूप से चुनने के बजाय 2 क्लस्टर केंद्रों का चयन करने की आवश्यकता है {जैसे हम सरल के माध्यम से करते हैं}, हम पहले व्यक्ति को यादृच्छिक रूप से चुनेंगे, फिर उन बिंदुओं को ढूंढें जो पहले केंद्र से सबसे दूर हैं {ये बिंदु सबसे अधिक संभवतः करते हैं पहले क्लस्टर सेंटर से संबंधित नहीं हैं क्योंकि वे इससे दूर हैं} और उन दूरदराज के नजदीक दूसरे क्लस्टर सेंटर को असाइन करें।