Algorithme k-means de Python

Question

Je recherche une implémentation Python de l'algorithme k-means avec des exemples pour regrouper et mettre en cache ma base de données de coordonnées.

Answer 1

Mise à jour : (Onze ans après cette réponse originale, il est probablement temps de faire une mise à jour).

Tout d'abord, tu es sûr de vouloir les k-means ? Cette page donne un excellent résumé graphique de différents algorithmes de clustering. Je suggère qu'au-delà du graphique, vous regardiez surtout les paramètres que chaque méthode requiert et que vous décidiez si vous pouvez fournir le paramètre requis (par exemple, k-means requiert le nombre de clusters, mais peut-être ne le savez-vous pas avant de commencer le clustering).

Voici quelques ressources :

• sklearn k-means y sklearn d'autres algorithmes de clustering

• scipy k-means y scipy k-means2

Vieille réponse :

Le clustering de Scipy fonctionnent bien, et elles comprennent une k-means mise en œuvre.

Il y a aussi scipy-cluster qui fait du clustering agglomératif ; cela a l'avantage que vous n'avez pas besoin de décider du nombre de clusters à l'avance.

Answer 2

SciPy kmeans2() a quelques problèmes numériques : d'autres ont signalé des messages d'erreur tels que "Matrix is not positive definite - Cholesky decomposition cannot be computed" dans la version 0.6.0, et je viens de rencontrer le même problème dans la version 0.7.1.

Pour l'instant, je recommande d'utiliser PyCluster à la place. Exemple d'utilisation :

>>> 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

Answer 3

Pour les données continues, la méthode k-means est très simple.

Vous avez besoin d'une liste de vos moyennes, et pour chaque point de données, trouvez la moyenne dont il est le plus proche et faites la moyenne du nouveau point de données par rapport à celle-ci. Vos moyennes représenteront les groupes de points saillants récents dans les données d'entrée.

Je fais la moyenne en continu, il n'est donc pas nécessaire d'avoir les anciennes données pour obtenir la nouvelle moyenne. Étant donné l'ancienne moyenne k ,le point de données suivant x et une constante n qui est le nombre de points de données passés dont il faut conserver la moyenne, la nouvelle moyenne est de

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

Voici le code complet en 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)

Vous pourriez simplement imprimer les moyennes lorsque toutes les données sont passées, mais c'est beaucoup plus amusant de les voir changer en temps réel. Je l'ai utilisé sur des enveloppes de fréquences de sons de 20 ms et, après lui avoir parlé pendant une minute ou deux, il a trouvé des catégories cohérentes pour la voyelle "a" courte, la voyelle "o" longue et la consonne "s".

Answer 4

(Des années plus tard) ce kmeans.py sous est-il possible de spécifier sa propre fonction de distance à l'aide de la méthode d'apprentissage des sciences est simple et raisonnablement rapide ; il utilise l'une des 20 métriques de scipy.spatial.distance.

Answer 5

De wikipedia vous pouvez utiliser scipy, Regroupement K-means et quantification vectorielle

Ou bien, vous pouvez utiliser un wrapper Python pour OpenCV, ctypes-opencv .

Ou vous pourriez La nouvelle interface Python d'OpenCV et leurs kmeans mise en œuvre.