Jak dokładnie działa k-means++?
Mam problem ze zrozumieniem algorytmu k-means++. Interesuje mnie dokładnie jak dobierane są pierwsze centroidy k (reszta jest jak w oryginale K-oznacza).
- czy funkcja prawdopodobieństwa jest używana na podstawie odległości Czy Gaussa?
- w tym samym czasie najbardziej odległy punkt (od innych centroidów) jest wybierany dla nowego centroida.
Będę wdzięczny za wyjaśnienie krok po kroku i przykład. Ten w Wikipedii nie jest wystarczająco jasny. Bardzo dobrze skomentowany kod źródłowy również by pomógł. Jeśli używasz 6 tablic, powiedz nam, który z nich jest dla czego.
3 answers
Ciekawe pytanie. Dziękuję za zwrócenie mojej uwagi na ten artykuł. link do oryginalnej pracy w formacie PDF.
W prostych słowach, centra klastrów są początkowo wybierane losowo ze zbioru wejściowych wektorów obserwacyjnych, gdzie prawdopodobieństwo wyboru wektora x
jest wysokie, jeśli x
nie znajduje się w pobliżu żadnego wcześniej wybranego ośrodka.
Oto jednowymiarowy przykład. Nasze obserwacje to [0, 1, 2, 3, 4]. Niech pierwszy środek c1
będzie równy 0. Prawdopodobieństwo, że następny środek klastra, c2
, to x jest proporcjonalne do ||c1-x||^2
. Więc, P (c2 = 1) = 1a, P (c2 = 2) = 4a, P (c2 = 3) = 9a, P(c2 = 4) = 16A, gdzie A = 1/(1+4+9+16).
Załóżmy, że c2=4. Następnie, P(c3 = 1) = 1a, P (c3 = 2) = 4a, P(c3 = 3) = 1A, gdzie A = 1/(1+4+1).
Zakodowałem procedurę inicjalizacji w Pythonie; Nie wiem, czy to ci pomoże.
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
Edycja z wyjaśnieniem: wyjście cumsum
daje nam granice do podziału interwału [0,1]. Te partycje mają długość równa prawdopodobieństwu wybrania odpowiedniego punktu jako środka. Tak więc, ponieważ {[8] } jest jednolicie dobrane pomiędzy [0,1], będzie to dokładnie jeden z tych przedziałów (ze względu na break
). Pętla for
sprawdza, w której partycji r
się znajduje.
Przykład:
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
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-03-29 15:18:22
Przygotowałem pełną implementację źródłową k-means++ opartą na książce" Collective Intelligence "Toby' ego Segarana i dostarczonej tutaj inicjalizacji K-menas++.
Rzeczywiście są tu dwie funkcje odległości. Dla początkowych centroidów stosuje się standardowy numpy.wewnętrzne, a następnie do mocowania centroidów stosuje się Pearsona. Może Pearson one może być również używany do początkowych centroidów. Mówią, że jest lepiej.
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:
{[1]}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-04-04 15:54:36
One Liner.
Powiedzmy, że musimy wybrać 2 centra klastra, zamiast wybierać je wszystkie losowo{jak to robimy w prostych k oznacza}, wybierzemy pierwszy losowo, a następnie znaleźć punkty, które są najdalej do pierwszego Centrum{te punkty najprawdopodobniej nie należą do pierwszego centrum klastra, ponieważ są daleko od niego} i przypisać drugie centrum klastra w pobliżu tych odległych punktów.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-04-07 05:48:38