python kmeans

python-kmeans

implémentation python du clustering k-means. k-means est une technique d'apprentissage non supervisée qui tente de regrouper des points de données similaires dans un nombre de groupes spécifié par l'utilisateur. L'exemple ci-dessous montre la progression des clusters pour l'ensemble de données Iris à l'aide de l'algorithme d'initialisation du centroïde k-means++.

Description

k-means tente d'identifier un nombre k (<N) de clusters spécifié par l'utilisateur à partir d'un ensemble de N vecteurs à valeur réelle de dimension d. L'algorithme procède en tentant de minimiser la somme des carrés des distances entre un centre de cluster et les membres du cluster. L'algorithme canonique se déroule en trois phases :

1. Initialiser k centroïdes aléatoires (centres de cluster) ;
2. attribuer des points de données au cluster le plus proche en fonction de la métrique de distance (généralement la distance euclidienne) ;
3. mettre à jour les centroïdes à la moyenne des membres du cluster ;
4. répétez les étapes 2 et 3 jusqu'à ce que les affectations de l'étape 2 ne changent pas.

Le résultat de l'algorithme est une affectation de cluster pour chaque point de données et un niveau final de « distorsion ». L'algorithme ne produit pas de solution dont il est prouvé qu'elle est optimale, et les centres de cluster initiaux peuvent bloquer l'algorithme dans une solution localement optimale qui est clairement sous-optimale (voir l'exemple de base en 2D dans la section Résultats).

De nombreuses recherches se sont concentrées sur :

• sélection des centres de cluster initiaux. K-Means++ est une méthode bien connue et est incluse dans cette implémentation, l'algorithme est décrit dans la sous-section suivante.
• calculer les distances, c'est à dire en utilisant des mesures autres qu'Euclidiennes voir ici.

K-Means++

Plutôt que d'initialiser des centroïdes aléatoires comme à l'étape 1 ci-dessus, k-means++ étale de manière probabiliste les centroïdes initiaux pour éviter une mauvaise configuration initiale, l'algorithme est le suivant :

1. Choisissez le premier centroïde au hasard.
2. Pour chaque point de données x, calculez la distance d(x), de x au centre de gravité le plus proche déjà choisi.
3. Sélectionnez un point de données pour être le prochain centroïde en utilisant une probabilité pondérée proportionnelle à d(x)2.

Cette technique privilégie les points de données qui ne sont pas proches d'un autre centroïde initial et utilise une politique de sélection qui rappelle la sélection à la roulette (ou proportionnelle à la condition physique) souvent utilisée dans les algorithmes génétiques.

Ressources

Algorithme de base

• K-Means est décrit dans les 10 meilleurs algorithmes pour l'exploration de données ;

• K-Means est décrit dans Théorie de l'information, inférence et algorithmes d'apprentissage, extrait ici ;

• Le professeur Andrew Moore de la CMU a ici quelques bonnes notes ;

• Exemple d'Edureka, utilisant des données sur la criminalité

Initialisation des clusters

• K-Means++, et article complet ici

• Une étude comparative des méthodes d'initialisation efficaces pour l'algorithme de clustering K-Means

Pourquoi ne pas utiliser SciPy ?

SciPy a une implémentation de k-means. L'objectif de ce travail est de construire une implémentation Python pure à des fins d'apprentissage et d'aider les autres à apprendre l'algorithme k-means. Les lecteurs intéressés ayant seulement une expérience minimale de Python seront capables de lire et de parcourir ce code sans la complexité supplémentaire d'une bibliothèque telle que SciPy. Il n'est en aucun cas destiné à un usage en production :)

Exécuter le code

Dépendances

• python 3.6.3
• matplotlib 2.1.1 - voir ici pour les instructions d'installation.

Exécution

Exécutez le code avec l'interpréteur python :

python kmeans.py ./resources/<config.cfg>

Où config.cfg est un fichier de configuration en texte brut. Le format du fichier de configuration est un dict python avec les champs suivants :

 {
   'data_file' : '\resources\iris.csv',
   'data_project_columns' : ['sepal_length','sepal_width','petal_length','petal_width','class'],
   'k' : 3,
   'cluster_atts' : ['sepal_length','sepal_width','petal_length','petal_width'],
   'init_cluster_func' : 'kmeans_plus_plus',
   'plot_config' :
    {'output_file_prefix' : 'iris',
     'plots_configs': [
        {'plot_atts' : ['sepal_length','sepal_width']},
        {'plot_atts' : ['sepal_length','petal_length']},
        {'plot_atts' : ['sepal_length','petal_width']},
        {'plot_atts' : ['sepal_width','petal_length']},
        {'plot_atts' : ['sepal_width','petal_width']},
        {'plot_atts' : ['sepal_width','petal_width']}
     ]
   }
}

Vous devez préciser :

• un fichier de données csv ;
• un sous-ensemble de champs à projeter à partir du fichier ;
• le nombre de clusters à former, k ;
• le sous-ensemble d'attributs utilisé dans le processus de clustering ;
• spécifiez éventuellement une fonction de cluster initiale (default='rand_init_centroids'), les auteurs intéressés doivent ajouter la leur au code et la spécifier ici ;
• une configuration de tracé qui comprend
  • préfixe pour les fichiers png créés lors du processus dans le répertoire de travail, si cela n'est pas spécifié, les images ne seront pas produites ;
  • les configurations de parcelles individuelles, limitées à 2 dimensions par parcelle.

Résultats

Ensemble de données sur l'iris

L'ensemble de données Iris (iris.config), de Lichman, M. (2013). Référentiel d'apprentissage automatique UCI . Irvine, Californie : Université de Californie, École d'information et d'informatique., est un ensemble de données très connu dans la communauté de l'apprentissage automatique. Voici les résultats de mes clusters initiaux aléatoires :

Données 2D synthétiques de base

Ces données ont été générées à des fins de débogage (voir basic2d.config) et illustrent l'effet d'un mauvais choix de clusters aléatoires initiaux. Les résultats ci-dessous démontrent une configuration initiale du centroïde qui empêche l'algorithme d'atteindre l'affectation de cluster évidente. Dans ce cas, l'emplacement du centroïde rouge signifie que le centroïde bleu capture tous les points de données dans les quadrants inférieur gauche et inférieur droit.

Crime

L'ensemble de données sur la criminalité (crime.config) provient d'Edureka, ici.