Beachten Sie, dass k-means für die euklidische Entfernung ausgelegt ist . Es kann aufhören, mit anderen Entfernungen zu konvergieren, wenn der Mittelwert nicht mehr die beste Schätzung für das Cluster- "Zentrum" ist.
Hat aufgehört - Anony-Mousse
2
Warum funktioniert k-means nur mit euklidischer Entfernung?
neugierig
9
@ Anony-Mousse Es ist falsch zu sagen, dass k-means nur für die euklidische Distanz ausgelegt ist. Es kann geändert werden, um mit jeder gültigen Entfernungsmetrik zu arbeiten, die im Beobachtungsraum definiert ist. Schauen Sie sich zum Beispiel den Artikel über k-Medoide an .
ely
5
@curious: Der Mittelwert minimiert quadratische Differenzen (= quadratischer euklidischer Abstand). Wenn Sie eine andere Distanzfunktion wünschen, müssen Sie den Mittelwert durch eine geeignete Mittelschätzung ersetzen . K-Medoide sind ein solcher Algorithmus, aber das Finden des Medoids ist viel teurer.
Hat aufgehört - Anony-Mousse
4
Etwas relevant hier: Derzeit gibt es eine Open-Pull-Anforderung, die Kernel K-Means implementiert. Wenn es fertig ist, können Sie Ihren eigenen Kernel für die Berechnung angeben.
Jakevdp
Antworten:
77
Hier ist ein kleiner Kilometerstand, der eine der 20 ungeraden Entfernungen in
scipy.spatial.distance oder eine Benutzerfunktion verwendet.
Kommentare wären willkommen (dies hatte bisher nur einen Benutzer, nicht genug); Was ist insbesondere Ihre N, dim, k, Metrik?
#!/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 divisionimport randomimport numpy as npfrom 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.shapeif 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"% avdistif(1- delta)* prevdist <= avdist <= prevdist \or jiter == maxiter:break
prevdist = avdistfor 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.shapeif 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 ddef 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 = Xif 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 randomimport sysfrom 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
Einige Notizen hinzugefügt 26. März 2012:
1) Für den Kosinusabstand normalisieren Sie zuerst alle Datenvektoren auf | X | = 1; dann
cosinedistance( X, Y )=1- X . Y =Euclidean distance |X - Y|^2/2
ist schnell. Halten Sie bei Bitvektoren die Normen getrennt von den Vektoren, anstatt sie auf Floats auszudehnen (obwohl einige Programme möglicherweise für Sie erweitert werden). Für spärliche Vektoren sagen wir 1% von N, X. Y sollte Zeit O (2% N), Raum O (N) brauchen; aber ich weiß nicht, welche Programme das tun.
2)
Scikit-Learn-Clustering
bietet einen hervorragenden Überblick über k-means, Mini-Batch-k-means ... mit Code, der auf scipy.sparse-Matrizen funktioniert.
3) Überprüfen Sie die Clustergrößen immer nach k-means. Wenn Sie ungefähr gleich große Cluster erwarten, diese aber herauskommen
[44 37 9 5 5] %... (Kratzgeräusch).
+1 Zunächst einmal vielen Dank, dass Sie Ihre Implementierung geteilt haben. Ich wollte nur bestätigen, dass der Algorithmus für meinen Datensatz von 900 Vektoren in einem 700-dimensionalen Raum hervorragend funktioniert. Ich habe mich nur gefragt, ob es auch möglich ist, die Qualität der generierten Cluster zu bewerten. Kann einer der Werte in Ihrem Code zur Berechnung der Clusterqualität wiederverwendet werden, um die Auswahl der Anzahl der optimalen Cluster zu erleichtern?
Legende
6
Legende, du bist willkommen. (Der Code wurde aktualisiert, um Cluster mit einem Radius von 50% / 90% zu drucken.) "Clusterqualität" ist ein großes Thema: Wie viele Cluster haben Sie, haben Sie Trainingsbeispiele mit bekannten Clustern, z. B. von Experten? Informationen zur Anzahl der Cluster finden Sie unter SO, wie Sie k bestimmen, wenn Sie k-Mittel-Clustering verwenden, wenn Sie k-Mittel-Clustering verwenden
denis
1
Vielen Dank noch mal. Eigentlich habe ich keine Trainingsbeispiele, aber ich versuche, die Cluster nach der Klassifizierung manuell zu überprüfen (ich versuche auch, die Rolle des Domain-Experten zu spielen). Ich führe eine Klassifizierung auf Dokumentebene durch, nachdem ich SVD auf einige Originaldokumente angewendet und deren Dimension reduziert habe. Die Ergebnisse scheinen gut zu sein, aber ich war mir nicht sicher, wie ich sie validieren sollte. Als ich in der Anfangsphase verschiedene Cluster-Validitätsmetriken untersuchte, stieß ich auf Dunns Index, Elbow-Methode usw. Ich war mir nicht sicher, welche ich verwenden sollte, also dachte ich, ich werde mit der Elbow-Methode beginnen.
Legende
7
Ich weiß, dass dies etwas wirklich Altes ist, aber ich habe gerade mit der Verwendung von kmean angefangen und bin darauf gestoßen. Für zukünftige Leser, die versucht sind, diesen Code zu verwenden: Lesen Sie zuerst die Kommentare von @ Anony-Mousse zu der obigen Frage! Soweit ich sehen kann, geht diese Implementierung von der falschen Annahme aus, dass Sie irgendwie immer noch den "Mittelwert der Punkte in einem Cluster" verwenden können, um den Schwerpunkt dieses Clusters zu bestimmen. Dies ist für nichts anderes als die euklidische Entfernung sinnvoll (außer in ganz bestimmten Fällen auf der Einheitskugel usw.). Wieder sind Anony-Mousses Kommentare zu dieser Frage direkt in der Nase.
Leider nein: scikit-learn aktuelle Implementierung von k-means verwendet nur euklidische Entfernungen.
Es ist nicht trivial, k-means auf andere Entfernungen auszudehnen, und die obige Antwort von denis ist nicht der richtige Weg, um k-means für andere Metriken zu implementieren.
Verwenden Sie stattdessen einfach nltk, wo Sie dies tun können, z
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)
Wie effizient ist diese Implementierung? Es scheint ewig zu dauern, nur 5k Punkte (in Dimension 100) zu gruppieren.
Nikana Reklawyks
3
In Dimension 100 dauert das Clustering von 1k Punkten 1 Sekunde pro Lauf ( repeats), 1,5k Punkte 2 Minuten und 2k ... zu lange.
Nikana Reklawyks
2
Tatsächlich; Laut @ Anony-Mousse-Kommentar unten scheint es, dass die Kosinusentfernung Konvergenzprobleme haben kann. Für mich ist dies wirklich ein Fall von Garbage-In-Garbage-Out: Sie können jede gewünschte Distanzfunktion verwenden, aber wenn diese Funktion die Annahmen des Algorithmus verletzt, erwarten Sie nicht, dass sie aussagekräftige Ergebnisse liefert!
Chiraz BenAbdelkader
15
Ja, Sie können eine Differenzmetrikfunktion verwenden. Per Definition stützt sich der k-Mittelwert-Clustering-Algorithmus jedoch auf den eukldischen Abstand vom Mittelwert jedes Clusters.
Sie könnten eine andere Metrik verwenden, und obwohl Sie immer noch den Mittelwert berechnen, könnten Sie so etwas wie die Mahalnobis-Entfernung verwenden.
+1: Lassen Sie mich betonen, dass der Mittelwert nur für bestimmte Distanzfunktionen geeignet ist, z. B. für die euklidische Distanz . Für andere Distanzfunktionen müssten Sie auch die Cluster-Center-Schätzfunktion ersetzen!
Hat aufgehört - Anony-Mousse
2
@ Anony-Mousse. Was soll ich ändern, wenn ich zum Beispiel den Kosinusabstand benutze?
neugierig
6
Ich weiß es nicht. Ich habe keinen Beweis für die Konvergenz mit Cosine gesehen. Ich glaube, es wird konvergieren, wenn Ihre Daten nicht negativ und auf die Einheitskugel normalisiert sind, denn dann ist es im Wesentlichen k-bedeutet in einem anderen Vektorraum.
Hat aufgehört - Anony-Mousse
1
Ich stimme @ Anony-Mousse zu. Für mich ist dies nur ein Fall von Garbage-In-Garbage-Out: Sie könnten K-means mit jeder gewünschten Distanzfunktion ausführen, aber wenn diese Funktion die zugrunde liegenden Annahmen des Algorithmus verletzt, erwarten Sie nicht, dass sie aussagekräftig ist Ergebnisse!
Chiraz BenAbdelkader
@ Anony-Mousse aber wie implementiert man K-Mittel unter Verwendung der Mahalnobis-Distanz?
Cecilia
7
Es gibt Pyclustering, das Python / C ++ ist (also schnell!) Und mit dem Sie eine benutzerdefinierte Metrikfunktion angeben können
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 verwendet die euklidische Distanz . Es hat keinen metrischen Parameter. Das heißt, wenn Sie Clustering Zeitreihe , die Sie verwenden können tslearnPython - Paket, wenn Sie eine Metrik angeben ( dtw, softdtw, euclidean).
Antworten:
Hier ist ein kleiner Kilometerstand, der eine der 20 ungeraden Entfernungen in scipy.spatial.distance oder eine Benutzerfunktion verwendet.
Kommentare wären willkommen (dies hatte bisher nur einen Benutzer, nicht genug); Was ist insbesondere Ihre N, dim, k, Metrik?
Einige Notizen hinzugefügt 26. März 2012:
1) Für den Kosinusabstand normalisieren Sie zuerst alle Datenvektoren auf | X | = 1; dann
ist schnell. Halten Sie bei Bitvektoren die Normen getrennt von den Vektoren, anstatt sie auf Floats auszudehnen (obwohl einige Programme möglicherweise für Sie erweitert werden). Für spärliche Vektoren sagen wir 1% von N, X. Y sollte Zeit O (2% N), Raum O (N) brauchen; aber ich weiß nicht, welche Programme das tun.
2) Scikit-Learn-Clustering bietet einen hervorragenden Überblick über k-means, Mini-Batch-k-means ... mit Code, der auf scipy.sparse-Matrizen funktioniert.
3) Überprüfen Sie die Clustergrößen immer nach k-means. Wenn Sie ungefähr gleich große Cluster erwarten, diese aber herauskommen
[44 37 9 5 5] %
... (Kratzgeräusch).quelle
Leider nein: scikit-learn aktuelle Implementierung von k-means verwendet nur euklidische Entfernungen.
Es ist nicht trivial, k-means auf andere Entfernungen auszudehnen, und die obige Antwort von denis ist nicht der richtige Weg, um k-means für andere Metriken zu implementieren.
quelle
Verwenden Sie stattdessen einfach nltk, wo Sie dies tun können, z
quelle
repeats
), 1,5k Punkte 2 Minuten und 2k ... zu lange.Ja, Sie können eine Differenzmetrikfunktion verwenden. Per Definition stützt sich der k-Mittelwert-Clustering-Algorithmus jedoch auf den eukldischen Abstand vom Mittelwert jedes Clusters.
Sie könnten eine andere Metrik verwenden, und obwohl Sie immer noch den Mittelwert berechnen, könnten Sie so etwas wie die Mahalnobis-Entfernung verwenden.
quelle
Es gibt Pyclustering, das Python / C ++ ist (also schnell!) Und mit dem Sie eine benutzerdefinierte Metrikfunktion angeben können
Eigentlich habe ich diesen Code nicht getestet, sondern aus einem Ticket und einem Beispielcode zusammengeschustert .
quelle
k-means von Spectral Python ermöglicht die Verwendung der Entfernung L1 (Manhattan).
quelle
Sklearn Kmeans verwendet die euklidische Distanz . Es hat keinen metrischen Parameter. Das heißt, wenn Sie Clustering Zeitreihe , die Sie verwenden können
tslearn
Python - Paket, wenn Sie eine Metrik angeben (dtw
,softdtw
,euclidean
).quelle