wake-up-neo.com

Python-K bedeutet Algorithmus

Ich suche nach einer Python-Implementierung des K-Means-Algorithmus mit Beispielen zum Clustering und Zwischenspeichern meiner Koordinatendatenbank.

46
Eeyore

Scipys Clustering - Implementierungen funktionieren gut, und sie enthalten eine k-means -Implementierung.

Es gibt auch scipy-cluster , das agglomeratives Clustering ausführt. Dies hat den Vorteil, dass Sie sich nicht vorab für die Anzahl der Cluster entscheiden müssen.

54
tom10

SciPys kmeans2 () hat einige numerische Probleme: Andere haben gemeldet Fehlermeldungen wie "Matrix ist nicht positiv bestimmt - Cholesky-Zerlegung kann nicht berechnet werden" in Version 0.6.0, und ich habe gerade das Gleiche gesehen Version 0.7.1.

Im Moment würde ich empfehlen, stattdessen PyCluster zu verwenden. Verwendungsbeispiel:

>>> import numpy
>>> import Pycluster
>>> points = numpy.vstack([numpy.random.multivariate_normal(mean, 
                                                            0.03 * numpy.diag([1,1]),
                                                            20) 
                           for mean in [(1, 1), (2, 4), (3, 2)]])
>>> labels, error, nfound = Pycluster.kcluster(points, 3)
>>> labels  # Cluster number for each point
array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2,
       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], dtype=int32)
>>> error   # The within-cluster sum of distances for the solution
1.7721661785401261
>>> nfound  # Number of times this solution was found
1
28
Vebjorn Ljosa

Für kontinuierliche Daten ist K-Means sehr einfach.

Sie benötigen eine Liste Ihrer Mittel und finden für jeden Datenpunkt den Mittelwert, der diesem am nächsten liegt, und ermitteln den Durchschnitt des neuen Datenpunkts. Ihre Mittelwerte repräsentieren die letzten herausragenden Punktcluster in den Eingabedaten.

Ich mache die Mittelwertbildung kontinuierlich, so dass die alten Daten nicht benötigt werden, um den neuen Durchschnitt zu erhalten. In Anbetracht des alten Durchschnitts k, des nächsten Datenpunkts x und einer Konstanten n, der die Anzahl der vergangenen Datenpunkte ist, deren Durchschnittswert beibehalten werden soll, ist der neue Durchschnitt

k*(1-(1/n)) + n*(1/n)

Hier ist der vollständige Code in Python

from __future__ import division
from random import random

# init means and data to random values
# use real data in your code
means = [random() for i in range(10)]
data = [random() for i in range(1000)]

param = 0.01 # bigger numbers make the means change faster
# must be between 0 and 1

for x in data:
    closest_k = 0;
    smallest_error = 9999; # this should really be positive infinity
    for k in enumerate(means):
        error = abs(x-k[1])
        if error < smallest_error:
            smallest_error = error
            closest_k = k[0]
        means[closest_k] = means[closest_k]*(1-param) + x*(param)

sie können die Mittel einfach ausdrucken, wenn alle Daten durchgelaufen sind, aber es macht viel mehr Spaß, zu sehen, wie sich die Daten in Echtzeit ändern. Ich benutzte dies auf Frequenzhüllkurven von 20-ms-Tonstücken, und nachdem ich ein oder zwei Minuten lang mit ihm gesprochen hatte, hatte es konsistente Kategorien für den kurzen Vokal 'a', den langen 'o' Vokal und den Konsonanten. komisch!

20
Nathan

Von wikipedia könnten Sie scipy verwenden, K-Mittel, die eine Vektorquantisierung zusammenfassen

Oder Sie könnten einen Python-Wrapper für OpenCV verwenden, ctypes-opencv .

Oder Sie könnten die neue Python-Schnittstelle von OpenCV und deren kmeans - Implementierung.

5
Jacob

(Jahre später) ist diese kmeans.py unter ist es möglich, Ihre eigene Distanz-Funktion unter Verwendung von Scikits-Learn-k-Mitteln anzugeben ist unkompliziert und relativ schnell; Es verwendet eine der rund 20 Messgrößen in scipy.spatial.distance.

5
denis

KMeans () von SciKit Learn ist der einfachste Weg, K-Means-Clustering in Python anzuwenden. Das Anpassen von Clustern ist einfach: kmeans = KMeans(n_clusters=2, random_state=0).fit(X).

Dieses Code-Snippet zeigt, wie Centroid-Koordinaten gespeichert und Cluster für ein Koordinaten-Array vorhergesagt werden.

>>> from sklearn.cluster import KMeans
>>> import numpy as np
>>> X = np.array([[1, 2], [1, 4], [1, 0],
...               [4, 2], [4, 4], [4, 0]])
>>> kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
>>> kmeans.labels_
array([0, 0, 0, 1, 1, 1], dtype=int32)
>>> kmeans.predict([[0, 0], [4, 4]])
array([0, 1], dtype=int32)
>>> kmeans.cluster_centers_
array([[ 1.,  2.],
       [ 4.,  2.]])

(mit freundlicher Genehmigung der SciKit Learn-Dokumentation, oben verlinkt)

0
gsilv

Sie können auch GDAL verwenden, das viele Funktionen für die Arbeit mit räumlichen Daten bietet.

0
George Silva