Blog ENI : Toute la veille numérique !
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
  1. Livres et vidéos
  2. Data Science avec Microsoft Azure
  3. L’algorithme k
Extrait - Data Science avec Microsoft Azure Maîtrisez le Machine Learning sur Cortana Intelligence Suite
Extraits du livre
Data Science avec Microsoft Azure Maîtrisez le Machine Learning sur Cortana Intelligence Suite Revenir à la page d'achat du livre

L’algorithme k-means

Objectif du chapitre

Les chapitres précédents ont abordé des exemples de deux types d’algorithmes de Machine Learning, les algorithmes de régression et les algorithmes de classification. Ce chapitre porte sur l’algorithme k-means, appelé l’algorithme des k-moyennes en français, qui est l’un des algorithmes de clustering les plus connus et les plus utilisés.

L’algorithme k-means a été introduit par J. McQueen en 1967. C’est un algorithme non supervisé qui permet de regrouper un ensemble de images/eq16.PNG observations en images/eq157.PNG clusters. Chaque cluster contiendra des observations homogènes, et deux observations de deux clusters différents seront hétérogènes.

Les domaines d’application de l’algorithme k-means sont nombreux. Par exemple, il est très utilisé dans la segmentation des clients pour des fins de marketing, ou encore l’isolation des motifs dans les images, car justement les images présentent souvent des régions homogènes, notamment en matière d’intensité lumineuse.

De manière générale, le succès de l’algorithme k-means, et de ses versions, réside dans sa simplicité et sa capacité à traiter des données de grande taille.

À la fin de ce chapitre, le lecteur aura abordé :

  • Les notions de base...

k-means du point de vue géométrique

Comme précisé au début de ce chapitre, l’algorithme k-means est très intuitif et simple à comprendre. De façon informelle, étant donné images/eq16.PNG observations à répartir sur images/eq157.PNG clusters, k-means choisit de manière aléatoire images/eq157.PNG observations parmi les images/eq16.PNG observations, comme étant les centres des images/eq157.PNG clusters recherchés. Chacune des images/eq16.PNG observations sera associée au cluster dont le centre est le plus proche de cette observation par rapport à tous les centres des autres clusters. Une fois que toutes les observations sont associées à leurs clusters respectifs, alors le centre de chaque cluster sera recalculé en fonction des observations qu’il contient. Puis, de nouveau, chacune des observations sera associée au cluster dont le centre est le plus proche de cette observation par rapport à tous les centres des autres clusters. Ces opérations de recalcul des centres des clusters puis d’association des observations aux clusters les plus proches seront répétées jusqu’à ce qu’un critère d’arrêt soit atteint.

L’algorithme k-means utilise une fonction pour calculer les distances entre les observations et les centres des clusters. Ce calcul des distances peut être basé sur la distance euclidienne, la distance de Manhattan, etc.

Dans le chapitre R et Azure ML Studio - Développer un module R personnalisé, plusieurs distances seront définies et un module personnalisé sera entièrement développé pour le calcul des distances sur un ensemble de points.

Pour mieux comprendre cet algorithme, cette section déroule l’algorithme k-means sur un exemple simple. Soit six observations a, b, c, d, e et f à répartir sur deux clusters images/eq64.PNG et images/eq158.PNG et supposons que la distance utilisée est la distance euclidienne classique. Ces six observations sont définies dans un espace à deux dimensions et leurs coordonnées sont indiquées dans le tableau suivant.
images/06EPS01.png

Figure 6-1 : un simple jeu de données

Pour rappel, la distance euclidienne entre deux observations images/eq159.PNG et images/eq160.PNG est calculée par la formule : images/eq161.PNG

Avant de réaliser un traitement quelconque sur les données, il est toujours intéressant de...

k-means du point de vue algorithmique

L’exemple de la section précédente a montré le mécanisme de base de l’algorithme k-means. Les deux paramètres principaux de cet algorithme sont le nombre de clusters images/eq157.PNG à construire et la fonction de calcul de distance. Le schéma général de l’algorithme k-means est présenté par le code ci-dessous :

Entrées : un ensemble d'observations images/eq171.PNG; 
          Un nombre entier images/eq172.PNG correspondant au nombre de  
          Clusters à construire;  
          Une fonction de distance; 
Sortie :  une partition images/eq173.PNG de images/eq174.PNG en images/eq175.PNG clusters; 
1- Initialisation aléatoire des centres images/eq176.PNG 
2- Répété : 
      a) Association de chaque observation images/eq177.PNG au cluster 
dont le centre est le plus proche de images/eq178.PNG; 
      b) Recalculer les centres images/eq179.PNG 
3- Reprendre au point (2)jusqu'à ce que les centres images/eq180.PNG 
deviennent stable 
 
L’algorithme k-means prend en entrée un ensemble d’observations images/eq181.PNG, un paramètre images/eq182.PNG qui correspond au nombre de clusters que l’algorithme doit construire et une fonction de distance.
La première étape consiste en l’initialisation aléatoire des centres des images/eq182.PNG clusters. C’est-à-dire, k-means tire aléatoirement images/eq182.PNG observations qui seront considérées comme...

Exemple de k-means dans Azure ML

Dans cet exemple, le jeu de données de la figure 6-1 sera utilisé. L’algorithme k-means sera exécuté avec deux paramétrages différents afin d’influencer la méthode de sélection des centres initiaux et de comparer les résultats.

Pour illustrer l’algorithme k-means dans l’environnement Azure ML, veuillez suivre les étapes ci-dessous :

 Connectez-vous à votre environnement Azure ML.

 Créez une nouvelle expérience Machine Learning et donnez-lui le nom Algorithme k-means.

 Chargez dans un Dataset les données du fichier exemple_simple_kmeans.csv qui se trouve dans le dossier Data de ce chapitre. Attention, lorsque vous sélectionnez ce fichier, indiquez que c’est un fichier csv sans en-têtes.

 Recherchez le Dataset exemple_simple_kmeans.csv et ajoutez-le dans l’expérience.

 Recherchez et ajoutez le module K-Means Clustering à l’expérience. Ce module est l’algorithme k-means qui sera exécuté sur le Dataset de cet exemple. Ces paramètres sont définis comme suit :

  • Create trainer mode : ce paramètre est le même que celui du même nom du module Linear Regression vu au chapitre La régression linéaire et polynomiale. Pour rappel, il sert à indiquer si le programme doit se lancer une seule fois avec des paramètres fixes, ou bien si l’algorithme doit se lancer plusieurs fois avec une combinaison de paramètres différente à chaque lancement.

  • Number of Centroids : ce paramètre indique le nombre de clusters souhaités.

  • Initialization : ce paramètre indique la méthode à utiliser pour l’initialisation des centres.

  • Random number seed : le nombre aléatoire à utiliser avec la méthode d’initialisation choisie avec le paramètre Initialization. Les résultats peuvent être très différents en fonction de la valeur de ce paramètre.

  • Metric : la fonction de distance à utiliser.

  • Iterations : le nombre d’itérations maximum.

  • Assign Label Mode : ce paramètre indique comment traiter les colonnes de type label.

 Affectez les deux paramètres Initialization et Random number seed comme suit :

  • Initialization...

Conclusion

Après avoir déroulé l’algorithme k-means sur un exemple simple, ce chapitre a abordé le fonctionnement général de cet algorithme et discuté de ses avantages et inconvénients. Ce chapitre s’est terminé par une application de l’algorithme k-means dans Azure ML.