Qu’est-ce que le clustering k-means ?

Il s’agit de l’une des méthodes de partitionnement les plus utilisées dans le machine learning. Contrairement à l’apprentissage supervisé, cet algorithme utilise des données d’entraînement non étiquetées, ce qui veut dire que les points de données n’ont pas une structure de classification définie.

Il existe différents types d’algorithmes de clustering (par exemple, exclusifs, superposés, hiérarchiques et probabilistes). L’algorithme de clustering k-means est une méthode exclusive, ou « dure », qui stipule qu’un point de données peut exister dans un seul cluster. Ce type d’analyse des clusters est couramment utilisé dans la science des données à des fins de segmentation du marché, de regroupement des documents, de segmentation ou encore de compression des images. L’algorithme k-means est une méthode largement employée dans l’analyse des clusters en raison de son efficience, de son efficacité et de sa simplicité.

K-means est un algorithme itératif de partitionnement basé sur les centroïdes qui partitionne un jeu de données en groupes similaires en fonction de la distance entre leurs centroïdes. Le centroïde, ou centre du cluster, est soit la moyenne, soit la médiane de tous les points du cluster en fonction des caractéristiques des données.

Le clustering k-means est un processus itératif visant à minimiser la somme des distances entre les points de données et le centroïde des clusters.

L’algorithme de clustering k-means classe les points de données en clusters à l’aide d’une mesure de distance mathématique, généralement la distance euclidienne, par rapport au centre du cluster. L’objectif est de réduire la somme des distances entre les points de données et leurs clusters. Les points de données les plus proches d’un centroïde sont regroupés au sein d’une même catégorie. Si la valeur k (le nombre de clusters) est élevée, les clusters sont petits et comportent davantage de détails. En revanche, si la valeur k est faible, les clusters seront plus grands et comporteront moins de détails.

L’algorithme de clustering k-means conventionnel nécessite quelques étapes. La première étape consiste à initialiser k centroïdes où k est égal au nombre de clusters choisis pour un jeu de données spécifique. Cette approche utilise soit la sélection aléatoire, soit la méthode d’échantillonnage du centroïde initial.

L’étape suivante comprend un processus itératif en deux étapes basé sur l’algorithme de machine learning d’espérance-maximisation¹. L’étape d’espérance attribue chaque point de données à son centroïde le plus proche en fonction de la distance (à nouveau, généralement euclidienne). L’étape de maximisation calcule la moyenne de tous les points pour chaque cluster et réattribue le centre du cluster, ou le centroïde. Ce processus se répète jusqu’à ce que les positions du centroïde aient atteint la convergence ou que le nombre maximal d’itérations ait été atteint.

Le clustering k-means est simple, mais sensible aux conditions initiales et aux données aberrantes. Optimiser l’initialisation du centroïde et le nombre de clusters k est essentiel pour obtenir les clusters significatifs. Il existe plusieurs manières d’évaluer et d’optimiser les composants de clustering de l’algorithme : on associe indicateurs d’évaluation et méthodes d’échantillonnage centroïde initial.

Les clusters de qualité contiennent au moins deux propriétés : 

1. Tous les points de données du cluster doivent être similaires.
   
2. Les clusters doivent être distincts les uns des autres.

Ces propriétés sont obtenues en minimisant la distance intracluster et en maximisant la distance intercluster de tous les points de données d’un jeu de données. En d’autres termes, plus un cluster est compact et isolé des autres, mieux c’est. L’objectif de l’algorithme de clustering k-means est de minimiser la somme des erreurs quadratiques (SSE)². Le calcul de la SSE de la distance euclidienne quadratique de chaque point par rapport à son centroïde le plus proche permet d’évaluer la qualité des attributions de cluster en mesurant la variation totale au sein de chaque cluster.

Les métriques d’évaluation de cluster vérifient la qualité et fournissent différentes perspectives pour analyser les résultats de clustering. Cela permet de sélectionner le nombre optimal de clusters et d'initialiser les centroïdes. Les indicateurs d’évaluation suivants sont des moyens courants de mesurer les distances intra et interclusters dans le partitionnement.

L’algorithme de clustering k-means vise à choisir des centroïdes, ou centres de clusters, qui minimisent l’inertie, un indicateur d’évaluation qui évalue la qualité du partitionnement d’un jeu de données sur la base d’indicateurs de distance. L’inertie est calculée en mesurant la distance entre un point de données et son centroïde, en élevant cette distance au carré et en additionnant ces carrés pour chaque point de données dans le cluster. La somme ou valeur inertielle est la distance intracluster. Plus la somme est faible, mieux c’est, car cela signifie que les points de données au sein du cluster sont compacts ou plus similaires³.

La deuxième propriété est mesurée avec l’indice de Dunn. L’indice de Dunn représente la relation entre la distance minimale intercluster et la distance maximale intracluster. Les clusters avec une distance intercluster élevée indiquent une meilleure qualité, car cela signifie que les clusters sont aussi différents que possible les uns des autres⁴.

L’optimisation est essentielle pour obtenir les meilleurs résultats de clustering.

L’algorithme k-means est non déterministe en raison de son étape d’initialisation aléatoire. Cette méthode implique que si l’algorithme est effectué deux fois sur des données identiques, les affectations de cluster peuvent différer. Pour obtenir des résultats de regroupement optimaux, il est judicieux de sélectionner correctement les centroïdes initiaux et le nombre optimal de clusters pour améliorer la précision et la vitesse de l’algorithme k-means.

Chaque cluster est représenté par un centroïde, un point de données qui représente le centre du cluster. L’algorithme k-means regroupe les points de données similaires en clusters en minimisant la distance entre les points de données d’un cluster avec leur centroïde ou leur valeur k-means. L’objectif principal de l’algorithme k-means est de réduire la distance totale entre les points et le centroïde de cluster qui leur est attribué. L’algorithme opère de manière itérative, et la sélection initiale des partitions peut avoir un impact considérable sur les clusters résultants.

L’initialisation aléatoire risque d’aboutir à des résultats incohérents. Des méthodes d’initialisation des centroïdes existent pour atténuer ces risques. Une étude de NUS Computing explique et compare des méthodes telles que le populaire k-means++ à l’initialisation aléatoire⁵.

K-means++ est un algorithme k-means qui optimise la sélection du ou des centroïdes initiaux du cluster. Développé par les chercheurs Arthur et Vasilvitskii, k-means++ améliore la qualité de l’attribution finale du cluster⁶.

La première étape de l’initialisation en utilisant la méthode k-means++ consiste à choisir un centroïde dans l’ensemble de données. Pour chaque centroïde ultérieur, calculez la distance de chaque point de données par rapport à son centre de cluster le plus proche. Le centroïde suivant est sélectionné en tenant compte de la probabilité qu'un point se trouve à une distance proportionnelle du centroïde le plus proche choisi précédemment. Le processus exécute des itérations jusqu’à ce que le nombre choisi de centres de cluster ait été initialisé.

Voici un tutoriel d’IBM Developer qui utilise la méthode k-means++ pour l’initialisation.

Idéalement, l’algorithme k-means itère jusqu’à ce que le nombre optimal de clusters soit atteint. Le nombre maximal d’itérations est atteint une fois que les centroïdes ont atteint la convergence.

La méthode du coude est l’une des méthodes qui permettent d’atteindre le nombre optimal de clusters. Il s’agit d’une méthode graphique qui permet de trouver le nombre optimal de clusters dans un algorithme de clustering k-means. Elle consiste à mesurer la distance euclidienne entre chaque point de données et son centre de cluster et à choisir le nombre de clusters en fonction de l’endroit où la valeur de la somme des carrés (WCSS) se stabilise. Cette valeur représente la variance totale au sein de chaque cluster, qui est tracée en fonction du nombre de clusters⁷.

La première étape de la méthode du coude consiste à calculer le WCSS pour chaque cluster (k). Ensuite, la valeur WCSS est représentée sur l’axe des y et le nombre de clusters est tracé sur l’axe des x. À mesure que le nombre de clusters augmente, les points du diagramme doivent former un schéma cohérent. De ce schéma, on obtient une fourchette pour le nombre optimal de clusters⁸. Lorsque vous décidez du nombre de clusters, tenez compte des coûts de calcul. Plus le nombre de clusters est élevé, plus la puissance de traitement requise est importante, en particulier avec les jeux de données volumineux.

Cette méthode n’est pas nécessairement la meilleure, en particulier pour les jeux de données à dimensionnalité élevée ou de forme irrégulière. Une autre méthode permettant de choisir le nombre optimal de clusters est l’analyse de la silhouette⁹.

L’algorithme de clustering k-means est utilisé dans chaque domaine et chaque secteur, ou presque. On l’applique généralement aux données de machine learning qui ont peu de dimensions, qui sont numériques et faciles à partitionner.

Les chercheurs ont intégré le clustering k-means à des méthodes d’apprentissage profond telles que les CNN et les RNN pour améliorer les performances de diverses tâches de machine learning telles que la vision par ordinateur, le NLP et de nombreux autres domaines. Voici une liste d’applications courantes de clustering k-means :

Segmentation des clients : cette pratique consiste à diviser les clients d'une entreprise en groupes en fonction de caractéristiques communes qui reflètent des similitudes. Cette stratégie permet aux entreprises de cibler des clusters ou des groupes de clients spécifiques pour des campagnes publicitaires spécifiques.

Classification des documents : procédure visant à attribuer différentes classes ou catégories aux documents. Cette méthode est utilisée par de nombreuses entreprises pour modérer le contenu. Consultez cette documentation Watson Discover pour créer un classificateur de documents.

Segmentation d’image : technique de vision par ordinateur qui divise une image numérique en ensembles distincts de pixels. Cette recherche examine comment les modèles k-means sont utilisés pour aider à identifier les limites des images médicales¹⁰.

Moteurs de recommandation : de nombreuses applications sur le Web utilisent des moteurs de recommandation. L’analyse des composantes principales et les techniques de clustering k-means sont utilisées pour formuler des recommandations de produits pour les entreprises d’e-commerce¹¹.

Pour une expérience d’apprentissage pratique, consultez ce tutoriel, qui explique les principes fondamentaux de la réalisation du clustering k-means dans Python en utilisant IBM Watson Studio sur watsonx.ai.

Ce tutoriel utilise un module de la bibliothèque scikit-learn (sklearn) qui effectue le clustering k-means. Le module comprend des techniques d’optimisation intégrées qui sont manipulées par ses paramètres de classe. La classe du module ressemble à ceci :

class sklearn.cluster.KMeans(n_clusters=8, *, init='k-means++', n_init='auto', max_iter=300, tol=0.0001, verbose=0, random_state=None, copy_x=True, algorithm='lloyd')12

Les paramètres incluent le nombre de clusters à former et le nombre de centroïdes à générer (n_clusters). Il existe deux méthodes d’initialisation disponibles : k-means++andrandom. Il comprend également des attributs permettant de définir le nombre maximal d'itérations. Chaque itération commence par la partition du jeu de données selon la valeur du paramètre n_clusters.

Ces bibliothèques sont utilisées pour générer un jeu de données de test et réaliser un partitionnement :

import pandas as pd 
import sklearn
import matplotlib.pyplot as plt
import seaborn as sns
import numpy

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.decomposition import PCA
from sklearn.preprocessing import StandardScaler

Voici les principaux avantages du clustering k-means dans les applications de machine learning :

Simple : le clustering k-means est simple à comprendre et à mettre en œuvre. Il s’agit de la technique de machine learning non supervisé la plus utilisée.

Rapide : le clustering k-means est conçu avec une approche itérative simple et efficace. L’algorithme de clustering k-means est plus rapide que le partitionnement hiérarchique, qui implique la création d’une structure arborescente de clusters et nécessite de calculer la distance par paires entre tous les points de données.

Évolutif : K-means est également facilement adaptable à de grands jeux de données et peut s’appliquer à des clusters de formes et de tailles différentes, ce qui est idéal pour l’analyse des clusters. Comme l’algorithme est très efficace sur le plan des calculs, il est plus évolutif et convient mieux aux jeux de données volumineux que d’autres méthodes.

Voici quelques défis courants associés au clustering k-means :

Dépendance à l'égard des paramètres d'entrée : le clustering K-means dépend du réglage correct des paramètres d'entrée. L’initialisation du centroïde et du nombre de clusters appropriés est impeccable pour obtenir des résultats de cluster significatifs. Une mauvaise initialisation du centroïde peut entraîner une augmentation de la durée d'exécution et une mauvaise qualité des attributions de clusters. De nombreuses recherches ont été consacrées à l'amélioration de la procédure d'initialisation des centroïdes afin d'obtenir de meilleurs résultats de clustering et d'accélérer le temps de convergence.

Sous-performance possible sur certains jeux de données : K-means fonctionne efficacement lorsque le jeu de données contient des clusters de taille similaire et qu’il n’y a pas de valeurs aberrantes ou de variations de densité notables. Il fonctionne mal lorsque le jeu de données contient de nombreuses variations ou qu’il est très dimensionnel. Lorsque les données ne s’alignent pas sur certaines hypothèses du jeu de données, k-means peut produire des clusters de mauvaise qualité¹³. Par exemple, des clusters de taille inégale peuvent dévier les centroïdes vers les plus grands clusters, ce qui entraîne des biais et des erreurs de classification parmi les plus petits clusters. Pour résoudre ce problème, k-means peut être généralisé à l’aide de modèles probabilistes comme le nœud de mélange gaussien.

Incidence significativ des données aberrantes : les données aberrantes ont un impact significatif sur les résultats du regroupement k-means. Les différents clusters doivent être éloignés, mais pas trop loin pour fausser les points de données. Il est important de prendre en compte les hypothèses de données avant d’appliquer des k-means. Le k-means est particulièrement sensible aux données aberrantes, car il vise à déterminer les centroïdes en calculant la moyenne des valeurs d'un cluster. Cette sensibilité les rend sujets au surajustement pour inclure ces données aberrantes.