Dans le monde d’aujourd’hui, la mise en œuvre des modèles d’apprentissage automatique est de plus en plus effectuée dans les entreprises pour la segmentation des clients et la détection des anomalies. Et si vous souhaitez devenir Data Scientist ou tout autre métier de la data, il devient primordial d’avoir des connaissances sur les différents algorithmes de machine learning. Dans cet article, nous étudierons l’un d’eux, le plus populaire et facile des algorithmes d’apprentissage non supervisé : les K Means.
Après avoir lu cet article, vous n’aurez plus besoin de vous remettre à niveau sur les sujets concernant les k-means avant de vous présenter à un entretien d’embauche de data scientist. Alors, excité d’apprendre ?
Contexte général
Beaucoup de choses autour de nous peuvent être catégorisées comme « ceci et cela« . Pour être moins vagues et plus spécifiques, nous avons des groupements qui peuvent être binaires ou plus de deux, comme un type de base de pizza ou un type de voiture que vous pourriez vouloir acheter.
À l’époque, les scientifiques classaient une population à l’aide d’étiquettes qu’ils ont préétablies. Ainsi, tout individu qui respectait certaines des caractéristiques était mis manuellement dans une classe avec des individus respectant les mêmes caractéristiques.
Le même raisonnement était appliqué dans les débuts du web par Yahoo! pour classer les pages web.
Cette manière de procéder a vite atteint ses limites avec la volonté d’étudier des ensembles de données de plus en plus grands et de sources différentes. Ce qui a entrainé l’apparition de nouvelles techniques de classification automatique : l’apprentissage automatique supervisé et non supervisé. L’une des techniques d’apprentissage automatique les plus utilisées est le clustering.
Qu’est-ce que le clustering ?
Le clustering consiste à regrouper selon un lien (critère) de similarité, une grande quantité de données en plusieurs sous-ensembles appelés clusters. Les éléments contenus dans un cluster sont similaires les uns aux autres, mais différents des éléments des autres clusters. Le but du clustering est de trouver la structure inhérente aux données et de l’exprimer sous la forme d’une collection de clusters.
En fait, lorsqu’il existe plusieurs modèles concurrents dans les données, il est difficile d’extraire un modèle spécifique, c’est pourquoi la création de clusters peut réduire la complexité en organisant les données en clusters.
On divise les techniques de clustering en deux catégories : celles dites hiérarchiques et celles dites non hiérarchiques.
L’approche hiérarchique construit une hiérarchie de clusters et de partitions individuelles d’objets. Dans ces technologies, on ne demande pas le nombre de clusters, et on utilise généralement une matrice de distance comme critère de segmentation. On les appelle souvent les méthodes de clustering de meilleure qualité.
Cependant, la complexité de la distribution hiérarchique est généralement d’au moins O(n2), ce qui rend ces techniques trop lentes pour les grands ensembles de données.
Au contraire, la complexité de l’algorithme non hiérarchique est principalement linéaire. Ceux-ci divisent les données en groupes sans chevauchement pour maximiser le temps de traitement. Afin de déterminer quelles données sont les plus similaires, On utilise généralement une fonction de distance pour calculer la différence entre chaque instance. Il existe de nombreuses façons de définir cette fonction de distance.
Les fonctions de distance en clustering
La plupart des techniques de clustering utilisent la distance euclidienne comme mesure de similarité. La distance entre deux instances a et b avec k attributs est définie comme la somme des différences au carré de chacun de leurs attributs, exprimée par la formule suivante :
Où aiet bi(i = l, n) sont les attributs des instances a et b respectivement. En pratique, on n’effectue pas la racine carrée, car on peut comparer directement le carré de la distance.
Une autre option pour la distance euclidienne est la distance de Manhattan, qui ajoute simplement la distance entre les attributs sans les mettre au carré, mais prend leur valeur absolue.
Une autre métrique est la distance de Minkowski. Nous utilisons des paramètres variables au lieu d’utiliser des carrés comme puissances. Plus la puissance sélectionnée est élevée, plus la grande différence est amplifiée par rapport à la petite différence. Habituellement, la distance euclidienne représente un bon compromis entre les deux autres.
Un autre détail important dans l’utilisation de ces distances est de les normaliser entre 0 et 1. Tout cela vise à obtenir une bonne segmentation, et la qualité des clusters sera d’autant plus importante, que la similarité intraclasse sera élevée et une similarité interclasse faible. La mesure de similarité est l’un des principaux facteurs qui affectent la qualité du cluster, et elle dépend de la distance utilisée et de sa réalisation. On évalue la méthode de segmentation par sa capacité à trouver tout ou partie des modèles cachés dans les données. Plus il y a de modèles, mieux c’est.
Nous allons étudier dans le reste de cet article l’un des algorithmes de clustering non hiérarchique le plus simple à implémenté et qui permet d’obtenir un clustering efficace et facile à interprété : l’algorithme des K-Means.
Qu’est-ce que K-Means ?
K-Means est un algorithme simple d’apprentissage non supervisé utilisé pour résoudre les problèmes de clustering. Il suit une procédure simple consistant à classer un ensemble de données dans un nombre de clusters, défini par la lettre « k« , qui est fixé au préalable.
On positionne ensuite les clusters comme des points. On associe tous les observations ou points de données au cluster le plus proche, calculés et ajustés. Puis, le processus recommence en utilisant les nouveaux ajustements jusqu’à ce qu’un résultat souhaité soit atteint.
Pourquoi KMeans ?
L’algorithme de clustering K-means est déployé pour découvrir des groupes qui n’ont pas été explicitement définis. Aujourd’hui, on l’utilise activement dans une grande variété d’applications commerciales, notamment :
- La segmentation de la clientèle : on regroupe les clients afin de mieux adapter les produits et les offres ;
- Le regroupement de textes, de documents ou de résultats de recherche : regroupement pour trouver des sujets dans un texte ;
- Le regroupement d’images ou compression d’images : regroupe les images ou les couleurs similaires ;
- La détection d’anomalies : trouver ce qui n’est pas similaire ou les aberrations des clusters ;
- L’apprentissage semi-supervisé : on combine les clusters à un ensemble plus petit de données étiquetées et à l’apprentissage automatique supervisé afin d’obtenir des résultats plus valables.
KMeans possède des avantages qui font de lui l’un des algorithmes de clustering préféré des data scientist :
- Il s’agit d’un algorithme classique de résolution des problèmes de clustering, simple et rapide ;
- Pour le traitement de grands ensembles de données, l’algorithme conserve son évolutivité et son efficacité ;
- Lorsque les données suivent une distribution gaussienne, son effet est meilleur.
Comment fonctionne K Means
L’algorithme K-means identifie un certain nombre de centroïdes dans un ensemble de données, un centroïde étant la moyenne arithmétique de tous les points de données appartenant à un cluster particulier.
L’algorithme attribue ensuite chaque point de données au cluster le plus proche en essayant de maintenir les clusters aussi petits que possible (le terme « means » dans K-means fait référence à la tâche consistant à faire la moyenne des données ou à trouver le centroïde).
En même temps, K-means tente de garder les autres clusters aussi différents que possible.
En pratique, il fonctionne comme suit :
Initialisation de « K » centres de cluster
L’algorithme K-means commence par initialiser « K » centres de cluster de façon aléatoire. (Le nombre K est une variable d’entrée et les emplacements peuvent également être donnés en entrée).
Assignation des points à un centre de cluster
À chaque passage de l’algorithme, on assigne chaque point à son centre de cluster le plus proche.
Mise à jour des centres de cluster
Les centres des clusters sont ensuite mis à jour pour être les « centres » de tous les points qui lui sont assignés dans ce passage. Cela se fait en recalculant les centres de cluster comme la moyenne des points dans chaque cluster respectif.
Répétition de l’algorithme kmeans
L’algorithme se répète jusqu’à ce qu’il y ait un changement minimum des centres de cluster par rapport à la dernière itération.
K-means est équivalent à l’algorithme d’espérance-maximisation avec une petite matrice de covariance diagonale, entièrement égale.
L’algorithme peut également être compris à travers le concept des diagrammes de Voronoï. Tout d’abord, on calcule le diagramme de Voronoï des points en utilisant les centroïdes actuels. Chaque segment du diagramme de Voronoï devient un cluster séparé.
Ensuite, on met à jour les centroïdes en fonction de la moyenne de chaque segment. L’algorithme répète ensuite cette opération jusqu’à ce que l’on remplit un critère d’arrêt.
Habituellement, l’algorithme s’arrête lorsque la diminution relative de la fonction objective entre les itérations est inférieure à la valeur de tolérance donnée. Ce n’est pas le cas dans cette implémentation : l’itération s’arrête lorsque les centroïdes se déplacent moins que la tolérance.
Avec suffisamment de temps, K-means convergera toujours, mais cela peut être vers un minimum local. Cela dépend fortement de l’initialisation des centroïdes. Par conséquent, on effectue souvent le calcul plusieurs fois, avec différentes initialisations des centroïdes.
Une méthode permettant de résoudre ce problème est le schéma d’initialisation k-means++, qui a été implémenté dans scikit-learn (utilisez le paramètre init=’k-means++’).
Il initialise les centroïdes pour qu’ils soient (généralement) distants les uns des autres, ce qui conduit à des résultats probablement meilleurs que l’initialisation aléatoire, comme indiqué dans la référence.
L’algorithme supporte les poids d’échantillon, qui peuvent être donnés par un paramètre sample_weight.
Cela permet d’attribuer plus de poids à certains échantillons lors du calcul des centres de clusters et des valeurs d’inertie. Par exemple, l’attribution d’un poids de 2 à un échantillon équivaut à ajouter un double de cet échantillon à l’ensemble de données.
On peut utiliser la méthode K-means pour la quantification vectorielle. On réalise ceci en utilisant la méthode de transformation d’un modèle entraîné de KMeans.
Il existe une variante de l’algorithme KMeans qui converge plus rapidement que KMeans : le MiniBatchKMeans. Etudions cet algorithme.
Qu’est-ce que le MiniBatchKMeans ?
Le MiniBatchKMeans est une variante de l’algorithme KMeans, qui utilise de petits lots pour réduire le temps de calcul tout en essayant d’optimiser la même fonction objective.
Le mini-lot est un sous-ensemble des données d’entrée, qui est échantillonné au hasard à chaque itération d’apprentissage. Ces petits lots réduisent considérablement la quantité de calcul nécessaire pour converger vers une solution locale.
Contrairement à d’autres algorithmes qui réduisent le temps de convergence de k-means, les résultats produits par les mini-lots de k-means ne sont généralement que légèrement inférieurs à ceux des algorithmes standards. L’algorithme itère entre deux étapes principales.
Dans la première étape, on sélectionne au hasard les échantillons dans l’ensemble de données pour former un petit lot. Attribuez-les ensuite au centre de gravité le plus proche.
La deuxième étape consiste à mettre à jour le centroïde. Contrairement à la méthode k-means, on effectue cette mise à jour par échantillon. Pour chaque échantillon du mini-lot, le centroïde attribué est mis à jour par l’échantillon et la moyenne continue de tous les échantillons précédents attribués à ce centroïde.
Cela a pour effet de réduire la vitesse de variation du centre de masse au cours du temps. Effectuez ces étapes jusqu’à ce que la convergence ou un nombre prédéterminé d’itérations soit atteint.
MiniBatchKMeans converge plus rapidement que KMeans, mais la qualité des résultats est réduite. En pratique, cette différence de qualité peut être faible, comme le montrent les exemples et les références citées.
Dans la prochaine section, nous appliquerons l’algorithme des K-means afin de classer les fleurs d’iris en groupes homogènes.
Clustering d’Iris en Python
Nous allons utiliser le jeu de données des plantes d’iris. Cet ensemble de données se compose de quatre champs, à savoir la longueur du sépale, la largeur du sépale, la longueur du pétale et la largeur du pétale.
Pourquoi utilisons-nous cet ensemble de données ? Nous savons au préalable que cet ensemble de données est divisé en trois classes différentes : Iris setosa, Iris versicolor et Iris virginica.
Nous appliquerons sur cet ensemble de données l’algorithme K-Means pour confirmer ou infirmer cette classification.
Afin de mieux appréhender cette section, nous vous invitons de lire notre article sur la programmation python pour avoir les bases nécessaires sur ce langage.
Tout abord, importons tous les bibliothèques dont nous aurons besoin dans ce tutoriel.
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn import datasets
Étape #1 : chargement l’ensemble de données
Nous travaillerons sur les iris. C’est un dataset déjà inclus dans la bibliothèque sklearn et très utilisé en clustering.
Nous pouvons utiliser la méthode load_iris() pour extraire les données et ensuite, nous les chargeons dans un dataframe pour mieux les visualiser :
#chargement des données
iris = datasets.load_iris()
df = pd.DataFrame(iris.data)
df.columns=["Longueur_sepale", "Largeur_sepale", "Longueur_petale", "Largeur_petale"]
df
Voici ce que cela donne :
Maintenant, notre ensemble de données est prêt et nous pouvons passer au clustering de nos données.
Étape #2 : Détermination de la valeur K (le nombre de clusters optimal)
Selon l’algorithme de K-Means, on doit définir au préalable le nombre K de clusters. Le problème qui se pose et de trouver un K optimal. L’une des méthodes les plus populaires pour y arriver est la méthode d’Elbow.
L’idée est d’exécuter le clustering k-means pour une gamme de clusters k (disons de 1 à 10) et pour chaque valeur, nous calculons l’inertie intraclasse.
Lorsque l’on trace les distorsions et que le tracé ressemble à un bras, le « coude » (le point d’inflexion de la courbe) est la meilleure valeur de k.
#Détermination de la valeur optimale de K
tab=[]
for i in range(1,10):
kmeans=KMeans(n_clusters=i)
kmeans.fit(df)
tab.append(kmeans.inertia_)
plt.plot(range(1,10),tab)
plt.title("La méthode Eblow")
plt.xlabel("nombre de cluster")
plt.ylabel("Inertie intra-classe")
plt.show()
À partir de ces instructions, nous obtenons ceci :
Nous remarquons sur ce graphique une courbe ayant la forme d’un bras. Selon la méthode d’Elbow, la valeur optimale de K est 3. Ce qui concorde avec l’ensemble de données utilisé divisé en 3 classes.
Étape #3 : Application de l’algorithme de K Means
Nous allons maintenant implémenter l’algorithme de K-Means avec les codes ci-dessous :
#Application deKMeans
kmeans = KMeans(n_clusters=3)
kmeans.fit(df)
#Visualisation
colormap=np.array(["red", "green", "blue"])
plt.scatter(df.Longueur_petale, df.Largeur_petale, c=colormap[kmeans.labels_], s=20)
plt.show()
Le résultat de cette application est :
Le graphique nous montre bien 3 classes d’observations respectivement en vert, rouge et bleue.
Maintenant, on va essayer de vérifier si l’algorithme de KMeans et notre démarche ont bien marché en comparant cette classification obtenue à la classification initiale.
plt.scatter(df.Longueur_petale, df.Largeur_petale, c=colormap[iris.target], s=20)
plt.show()
Parfait ! Nous obtenons à quelque millimètre près le même graphique.
Les limites de KMeans
Malgré ses nombreux avantages, K-Means montre certaines limites, à savoir :
- On ne peut l’utiliser que lorsque l’on peut définir la valeur moyenne du cluster, ce qui peut ne pas convenir à certaines applications ;
- Dans l’algorithme K-means, on donne K à l’avance, et le choix de cette valeur K est très difficile à estimer. Souvent, on ne sait pas à l’avance en combien de catégories on doit diviser un ensemble de données donné;
- Lorsque l’on veut appliquer l’algorithme K-means, il est d’abord nécessaire de déterminer une partition initiale basée sur le centre de regroupement initial, puis d’optimiser la partition initiale. La sélection de ce centre de clustering initial a un impact plus important sur les résultats du clustering. Si l’on ne sélectionne pas bien la valeur initiale, on risque de ne pas obtenir de résultats de clustering efficaces ;
- L’algorithme doit continuellement ajuster la classification de l’échantillon et calculer continuellement les nouveaux centres de cluster ajustés. Par conséquent, lorsque la quantité de données est très grande, le coût en temps de l’algorithme est très grand ；
- Si le cluster contient des points anormaux, la valeur moyenne déviera sérieusement
- Ne conviens pas à la découverte de clusters de formes non convexes ou de clusters de tailles très différentes.
Conclusion
Voilà, nous arrivons au terme de cet article. Nous avons donc abordé l’une des techniques de clustering les plus populaires : K-Means. Vous avez découvert ses mécanismes internes, vous l’avez mis en œuvre à l’aide d’un ensemble de données en Python. Bref, cet algorithme n’a plus aucun secret pour vous.
Si vous souhaitez en savoir plus sur ces techniques de machine learning, nous avons dédié plusieurs articles sur ce sujet, notamment Introduction au machine learning avec Python.
Et si vous souhaitez aller plus loin dans le domaine du Big Data, nous vous proposons de télécharger cette formation sur l’écosystème Hadoop.
