Zauważ, że k-średnie są zaprojektowane dla odległości euklidesowej . Może przestać zbiegać się z innymi odległościami, gdy średnia nie jest już najlepszym oszacowaniem dla „środka” klastra.
WYJŚCIE - Anony-Mousse
2
dlaczego k-mean działa tylko z odległościami euklidesowymi?
ciekawy
9
@ Anony-Mousse Nieprawidłowe jest twierdzenie, że k-średnie są zaprojektowane tylko dla odległości euklidesowej. Można go zmodyfikować, aby działał z dowolną prawidłową metryką odległości zdefiniowaną w przestrzeni obserwacji. Na przykład spójrz na artykuł o k-medoidach .
ely
5
@curious: średnia minimalizuje kwadratowe różnice (= kwadratowa odległość euklidesowa). Jeśli potrzebujesz innej funkcji odległości, musisz zastąpić średnią odpowiednią estymacją środka. K-medoids jest takim algorytmem, ale znalezienie medoidu jest znacznie droższe.
ZAKOŃCZYŁO - Anony-Mousse
4
Nieco istotne tutaj: obecnie istnieje otwarte żądanie ściągnięcia implementujące jądro K-Means. Kiedy skończysz, będziesz mógł określić własne jądro do obliczeń.
jakevdp
Odpowiedzi:
77
Oto mały kmeans, który wykorzystuje dowolną z 20 nieparzystych odległości w
scipy.spatial.distance lub funkcji użytkownika.
Komentarze byłyby mile widziane (jak dotąd miał tylko jednego użytkownika, za mało); w szczególności, jakie są Twoje dane N, dim, k, metric?
#!/usr/bin/env python# kmeans.py using any of the 20-odd metrics in scipy.spatial.distance# kmeanssample 2 pass, first sample sqrt(N)from __future__ import division
import random
import numpy as np
from scipy.spatial.distance import cdist # $scipy/spatial/distance.py# http://docs.scipy.org/doc/scipy/reference/spatial.htmlfrom scipy.sparse import issparse # $scipy/sparse/csr.py
__date__ ="2011-11-17 Nov denis"# X sparse, any cdist metric: real app ?# centres get dense rapidly, metrics in high dim hit distance whiteout# vs unsupervised / semi-supervised svm#...............................................................................def kmeans( X, centres, delta=.001, maxiter=10, metric="euclidean", p=2, verbose=1):""" centres, Xtocentre, distances = kmeans( X, initial centres ... )
in:
X N x dim may be sparse
centres k x dim: initial centres, e.g. random.sample( X, k )
delta: relative error, iterate until the average distance to centres
is within delta of the previous average distance
maxiter
metric: any of the 20-odd in scipy.spatial.distance
"chebyshev" = max, "cityblock" = L1, "minkowski" with p=
or a function( Xvec, centrevec ), e.g. Lqmetric below
p: for minkowski metric -- local mod cdist for 0 < p < 1 too
verbose: 0 silent, 2 prints running distances
out:
centres, k x dim
Xtocentre: each X -> its nearest centre, ints N -> k
distances, N
see also: kmeanssample below, class Kmeans below.
"""ifnot issparse(X):
X = np.asanyarray(X)# ?
centres = centres.todense()if issparse(centres) \
else centres.copy()
N, dim = X.shape
k, cdim = centres.shape
if dim != cdim:raiseValueError("kmeans: X %s and centres %s must have the same number of columns"%(
X.shape, centres.shape ))if verbose:print"kmeans: X %s centres %s delta=%.2g maxiter=%d metric=%s"%(
X.shape, centres.shape, delta, maxiter, metric)
allx = np.arange(N)
prevdist =0for jiter in range(1, maxiter+1):
D = cdist_sparse( X, centres, metric=metric, p=p )# |X| x |centres|
xtoc = D.argmin(axis=1)# X -> nearest centre
distances = D[allx,xtoc]
avdist = distances.mean()# median ?if verbose >=2:print"kmeans: av |X - nearest centre| = %.4g"% avdist
if(1- delta)* prevdist <= avdist <= prevdist \
or jiter == maxiter:break
prevdist = avdist
for jc in range(k):# (1 pass in C)
c = np.where( xtoc == jc )[0]if len(c)>0:
centres[jc]= X[c].mean( axis=0)if verbose:print"kmeans: %d iterations cluster sizes:"% jiter, np.bincount(xtoc)if verbose >=2:
r50 = np.zeros(k)
r90 = np.zeros(k)for j in range(k):
dist = distances[ xtoc == j ]if len(dist)>0:
r50[j], r90[j]= np.percentile( dist,(50,90))print"kmeans: cluster 50 % radius", r50.astype(int)print"kmeans: cluster 90 % radius", r90.astype(int)# scale L1 / dim, L2 / sqrt(dim) ?return centres, xtoc, distances
#...............................................................................def kmeanssample( X, k, nsample=0,**kwargs ):""" 2-pass kmeans, fast for large N:
1) kmeans a random sample of nsample ~ sqrt(N) from X
2) full kmeans, starting from those centres
"""# merge w kmeans ? mttiw# v large N: sample N^1/2, N^1/2 of that# seed like sklearn ?
N, dim = X.shape
if nsample ==0:
nsample = max(2*np.sqrt(N),10*k )Xsample= randomsample( X, int(nsample))
pass1centres = randomsample( X, int(k))
samplecentres = kmeans(Xsample, pass1centres,**kwargs )[0]return kmeans( X, samplecentres,**kwargs )def cdist_sparse( X, Y,**kwargs ):""" -> |X| x |Y| cdist array, any cdist metric
X or Y may be sparse -- best csr
"""# todense row at a time, v slow if both v sparse
sxy =2*issparse(X)+ issparse(Y)if sxy ==0:return cdist( X, Y,**kwargs )
d = np.empty((X.shape[0], Y.shape[0]), np.float64 )if sxy ==2:for j, x in enumerate(X):
d[j]= cdist( x.todense(), Y,**kwargs )[0]elif sxy ==1:for k, y in enumerate(Y):
d[:,k]= cdist( X, y.todense(),**kwargs )[0]else:for j, x in enumerate(X):for k, y in enumerate(Y):
d[j,k]= cdist( x.todense(), y.todense(),**kwargs )[0]return d
def randomsample( X, n ):""" random.sample of the rows of X
X may be sparse -- best csr
"""
sampleix = random.sample( xrange( X.shape[0]), int(n))return X[sampleix]def nearestcentres( X, centres, metric="euclidean", p=2):""" each X -> nearest centre, any metric
euclidean2 (~ withinss) is more sensitive to outliers,
cityblock (manhattan, L1) less sensitive
"""
D = cdist( X, centres, metric=metric, p=p )# |X| x |centres|return D.argmin(axis=1)defLqmetric( x, y=None, q=.5):# yes a metric, may increase weight of near matches; see ...return(np.abs(x - y)** q).mean()if y isnotNone \
else(np.abs(x)** q).mean()#...............................................................................classKmeans:""" km = Kmeans( X, k= or centres=, ... )
in: either initial centres= for kmeans
or k= [nsample=] for kmeanssample
out: km.centres, km.Xtocentre, km.distances
iterator:
for jcentre, J in km:
clustercentre = centres[jcentre]
J indexes e.g. X[J], classes[J]
"""def __init__( self, X, k=0, centres=None, nsample=0,**kwargs ):
self.X = X
if centres isNone:
self.centres, self.Xtocentre, self.distances = kmeanssample(
X, k=k, nsample=nsample,**kwargs )else:
self.centres, self.Xtocentre, self.distances = kmeans(
X, centres,**kwargs )def __iter__(self):for jc in range(len(self.centres)):yield jc,(self.Xtocentre== jc)#...............................................................................if __name__ =="__main__":import random
import sys
from time import time
N =10000
dim =10
ncluster =10
kmsample =100# 0: random centres, > 0: kmeanssample
kmdelta =.001
kmiter =10
metric ="cityblock"# "chebyshev" = max, "cityblock" L1, Lqmetric
seed =1exec("\n".join( sys.argv[1:]))# run this.py N= ...
np.set_printoptions(1, threshold=200, edgeitems=5, suppress=True)
np.random.seed(seed)
random.seed(seed)print"N %d dim %d ncluster %d kmsample %d metric %s"%(
N, dim, ncluster, kmsample, metric)
X = np.random.exponential( size=(N,dim))# cf scikits-learn datasets/
t0 = time()if kmsample >0:
centres, xtoc, dist = kmeanssample( X, ncluster, nsample=kmsample,
delta=kmdelta, maxiter=kmiter, metric=metric, verbose=2)else:
randomcentres = randomsample( X, ncluster )
centres, xtoc, dist = kmeans( X, randomcentres,
delta=kmdelta, maxiter=kmiter, metric=metric, verbose=2)print"%.0f msec"%((time()- t0)*1000)# also ~/py/np/kmeans/test-kmeans.py
Niektóre notatki dodane 26 marca 2012:
1) dla odległości cosinusowej, najpierw znormalizuj wszystkie wektory danych do | X | = 1; następnie
cosinedistance( X, Y )=1- X . Y =Euclidean distance |X - Y|^2/2
jest szybki. W przypadku wektorów bitowych utrzymuj normy oddzielnie od wektorów, zamiast rozszerzać się do postaci zmiennoprzecinkowej (chociaż niektóre programy mogą się rozwijać). Dla rzadkich wektorów powiedz 1% z N, X. Y powinno zająć czas O (2% N), przestrzeń O (N); ale nie wiem, które programy to robią.
2)
Klastrowanie Scikit-Learn
daje doskonały przegląd k-średnich, mini-batch-k-średnich ... z kodem, który działa na macierzach scipy.sparse.
3) Zawsze sprawdzaj rozmiary klastrów po k-średnich. Jeśli spodziewasz się skupisk mniej więcej równych rozmiarów, ale one wychodzą
[44 37 9 5 5] %... (dźwięk drapania głowy).
+1 Przede wszystkim dziękujemy za udostępnienie swojej implementacji. Chciałem tylko potwierdzić, że algorytm działa świetnie dla mojego zbioru danych 900 wektorów w przestrzeni 700 wymiarowej. Zastanawiałem się tylko, czy można również ocenić jakość wygenerowanych klastrów. Czy którejkolwiek z wartości w kodzie można ponownie użyć do obliczenia jakości klastra, aby pomóc w wyborze liczby optymalnych klastrów?
Legenda,
6
Legenda, nie ma za co. (Zaktualizowano kod, aby wyświetlał promień klastra 50% / 90%). „Jakość klastra” to obszerny temat: ile posiadasz klastrów, czy masz próbki szkoleniowe ze znanymi klastrami, np. Od ekspertów? O liczbie klastrów, zobacz SO jak-do-i-określić-k-when-using-k- mean- clustering -when-using-k-średnich-clustering
denis
1
Dziękuję raz jeszcze. Właściwie nie mam próbek szkoleniowych, ale próbuję ręcznie zweryfikować klastry po klasyfikacji (próbuję również odgrywać rolę eksperta domeny). Dokonuję klasyfikacji na poziomie dokumentu po zastosowaniu SVD do niektórych oryginalnych dokumentów i zmniejszeniu ich wymiarów. Wyniki wydają się dobre, ale nie byłem pewien, jak je zweryfikować. Na początkowym etapie, badając różne wskaźniki trafności klastra, natknąłem się na indeks Dunna, metodę Elbow itp. Nie byłem pewien, którą z nich zastosować, więc pomyślałem, że zacznę od metody Elbow.
Legenda,
7
Wiem, że to jest usuwanie uziemienia czegoś naprawdę starego, ale właśnie zacząłem używać kmeans i natknąłem się na to. Dla przyszłych czytelników pokuszonych o użycie tego kodu: najpierw sprawdź komentarze @ Anony-Mousse do powyższego pytania! O ile widzę, implementacja ta przyjmuje błędne założenie, że można w jakiś sposób nadal używać „średniej punktów w klastrze” do określenia środka ciężkości tego klastra. Nie ma to sensu w przypadku niczego innego niż odległość euklidesowa (z wyjątkiem bardzo szczególnych przypadków na kuli jednostkowej itp.). Znowu komentarz Anony-Mousse do tego pytania trafia w dziesiątkę.
Niestety nie: obecna implementacja metody k-średnich scikit-learn wykorzystuje tylko odległości euklidesowe.
Nie jest trywialne rozszerzenie k-średnich na inne odległości, a powyższa odpowiedź denisa nie jest właściwym sposobem implementacji k-średnich dla innych metryk.
from nltk.cluster.kmeans importKMeansClusterer
NUM_CLUSTERS =<choose a value>
data =<sparse matrix that you would normally give to scikit>.toarray()
kclusterer =KMeansClusterer(NUM_CLUSTERS, distance=nltk.cluster.util.cosine_distance, repeats=25)
assigned_clusters = kclusterer.cluster(data, assign_clusters=True)
Jak wydajna jest ta realizacja? Wydaje się, że skupienie zaledwie 5k punktów (w wymiarze 100) zajmuje wieczność.
Nikana Reklawyks
3
W wymiarze 100 skupienie 1k punktów zajmuje 1 sekundę na przebieg ( repeats), 1,5k punktów zajmuje 2 minuty, a 2k trwa ... zbyt długo.
Nikana Reklawyks
2
W rzeczy samej; zgodnie z komentarzem @ Anony-Mousse poniżej, wydaje się, że odległość cosinusowa może powodować problemy ze zbieżnością. Dla mnie jest to naprawdę przypadek śmieci-w-śmieci-wyrzucenia: możesz użyć dowolnej funkcji odległości, ale jeśli ta funkcja narusza założenia algorytmu, nie oczekuj, że przyniesie znaczące wyniki!
Chiraz BenAbdelkader,
15
Tak, możesz użyć funkcji metryki różnicy; jednak z definicji algorytm grupowania k-średnich opiera się na odległości eukldieowskiej od średniej każdego klastra.
Możesz użyć innego wskaźnika, więc nawet jeśli nadal obliczasz średnią, możesz użyć czegoś takiego jak odległość mahalnobisa.
+1: Podkreślę, że przyjmowanie średniej jest właściwe tylko dla pewnych funkcji odległości, takich jak odległość euklidesowa . W przypadku innych funkcji odległości należałoby również zastąpić funkcję szacowania środka klastra!
WYJŚCIE - Anony-Mousse
2
@ Anony-Mousse. Co mam zmienić, gdy używam na przykład odległości cosinusowej?
ciekawy
6
Nie wiem Nie widziałem dowodu na zbieżność z Cosinusem. Wierzę, że zbiegnie się, jeśli twoje dane są nieujemne i znormalizowane do sfery jednostkowej, ponieważ wtedy są to zasadniczo k-średnie w innej przestrzeni wektorowej.
WYJŚCIE - Anony-Mousse
1
Zgadzam się z @ Anony-Mousse. Dla mnie to tylko przypadek śmieci-w-śmieci-wyrzuconych: możesz uruchomić K-średnie z dowolną funkcją odległości, ale jeśli ta funkcja narusza podstawowe założenia algorytmu, nie oczekuj, że da sensowne wyniki!
Chiraz BenAbdelkader
@ Anony-Mousse, ale jak wdrożyć K-środki za pomocą odległości mahalnobis?
Cecilia
7
Istnieje pyclustering, który jest python / C ++ (więc jest szybki!) I pozwala określić niestandardową funkcję metryczną
from pyclustering.cluster.kmeans import kmeans
from pyclustering.utils.metric import type_metric, distance_metric
user_function =lambda point1, point2: point1[0]+ point2[0]+2
metric = distance_metric(type_metric.USER_DEFINED, func=user_function)# create K-Means algorithm with specific distance metric
start_centers =[[4.7,5.9],[5.7,6.5]];
kmeans_instance = kmeans(sample, start_centers, metric=metric)# run cluster analysis and obtain results
kmeans_instance.process()
clusters = kmeans_instance.get_clusters()
Sklearn Kmeans używa odległości euklidesowej . Nie ma parametru metrycznego. To powiedziawszy, jeśli grupowanie szeregów czasowych , można użyć tslearnpakietu python, gdy można określić metrykę ( dtw, softdtw, euclidean).
Odpowiedzi:
Oto mały kmeans, który wykorzystuje dowolną z 20 nieparzystych odległości w scipy.spatial.distance lub funkcji użytkownika.
Komentarze byłyby mile widziane (jak dotąd miał tylko jednego użytkownika, za mało); w szczególności, jakie są Twoje dane N, dim, k, metric?
Niektóre notatki dodane 26 marca 2012:
1) dla odległości cosinusowej, najpierw znormalizuj wszystkie wektory danych do | X | = 1; następnie
jest szybki. W przypadku wektorów bitowych utrzymuj normy oddzielnie od wektorów, zamiast rozszerzać się do postaci zmiennoprzecinkowej (chociaż niektóre programy mogą się rozwijać). Dla rzadkich wektorów powiedz 1% z N, X. Y powinno zająć czas O (2% N), przestrzeń O (N); ale nie wiem, które programy to robią.
2) Klastrowanie Scikit-Learn daje doskonały przegląd k-średnich, mini-batch-k-średnich ... z kodem, który działa na macierzach scipy.sparse.
3) Zawsze sprawdzaj rozmiary klastrów po k-średnich. Jeśli spodziewasz się skupisk mniej więcej równych rozmiarów, ale one wychodzą
[44 37 9 5 5] %
... (dźwięk drapania głowy).źródło
Niestety nie: obecna implementacja metody k-średnich scikit-learn wykorzystuje tylko odległości euklidesowe.
Nie jest trywialne rozszerzenie k-średnich na inne odległości, a powyższa odpowiedź denisa nie jest właściwym sposobem implementacji k-średnich dla innych metryk.
źródło
Po prostu użyj nltk, gdzie możesz to zrobić, np
źródło
repeats
), 1,5k punktów zajmuje 2 minuty, a 2k trwa ... zbyt długo.Tak, możesz użyć funkcji metryki różnicy; jednak z definicji algorytm grupowania k-średnich opiera się na odległości eukldieowskiej od średniej każdego klastra.
Możesz użyć innego wskaźnika, więc nawet jeśli nadal obliczasz średnią, możesz użyć czegoś takiego jak odległość mahalnobisa.
źródło
Istnieje pyclustering, który jest python / C ++ (więc jest szybki!) I pozwala określić niestandardową funkcję metryczną
Właściwie nie testowałem tego kodu, ale złożyłem go razem z biletu i przykładowego kodu .
źródło
k-średnie Spectral Python pozwala na użycie odległości L1 (Manhattan).
źródło
Sklearn Kmeans używa odległości euklidesowej . Nie ma parametru metrycznego. To powiedziawszy, jeśli grupowanie szeregów czasowych , można użyć
tslearn
pakietu python, gdy można określić metrykę (dtw
,softdtw
,euclidean
).źródło