clustering k-means

Le clustering k -means est une méthode de quantification vectorielle , issue du traitement du signal , qui vise à partitionner n observations en k clusters dans lesquels chaque observation appartient au cluster de moyenne la plus proche (centres de cluster ou centroïde de cluster ), servant de prototype du cluster. Il en résulte un partitionnement de l'espace de données en cellules de Voronoi . Le clustering k -means minimise les variances intra-cluster ( distances euclidiennes au carré ), mais pas les distances euclidiennes régulières, ce qui serait le problème de Weber le plus difficile : la moyenne optimise les erreurs au carré, alors que seule la médiane géométrique minimise les distances euclidiennes. Par exemple, de meilleures solutions euclidiennes peuvent être trouvées en utilisant des k -médianes et des k -médoïdes .

Le problème est difficile à calculer ( NP-difficile ) ; cependant, les algorithmes heuristiques efficaces convergent rapidement vers un optimum local . Ceux-ci sont généralement similaires à l' algorithme d'espérance-maximisation pour les mélanges de distributions gaussiennes via une approche de raffinement itératif utilisée à la fois par la modélisation k-means et par la modélisation par mélange gaussien . Ils utilisent tous deux des centres de cluster pour modéliser les données ; cependant, le clustering k -means tend à trouver des clusters d'étendue spatiale comparable, tandis que le modèle de mélange gaussien permet aux clusters d'avoir des formes différentes.

L' algorithme k -means non supervisé a une relation lâche avec le classificateur k -nearest neighbor , une technique populaire d'apprentissage automatique supervisé pour la classification qui est souvent confondue avec k -means en raison de son nom. L'application du classificateur 1-nearest neighbor aux centres de cluster obtenus par k -means classe les nouvelles données dans les clusters existants. C'est ce qu'on appelle le classificateur du centroïde le plus proche ou algorithme de Rocchio .

Étant donné un ensemble d'observations ( x ₁ , x ₂ , ..., x _n ) , où chaque observation est un vecteur réel de dimension , le clustering k -means vise à partitionner les n observations en k ( ≤ n ) ensembles S = { S ₁ , S ₂ , ..., S _k } de manière à minimiser la somme des carrés intra-cluster (WCSS) (c'est-à-dire la variance ). Formellement, l'objectif est de trouver : où μ _i est la moyenne (également appelée centroïde) des points de , c'est-à -dire est la taille de , et est la norme L ² habituelle . Cela équivaut à minimiser les écarts au carré deux à deux des points d'un même cluster : L'équivalence peut être déduite de l'identité . Puisque la variance totale est constante, cela équivaut à maximiser la somme des écarts au carré entre les points de différents clusters (somme des carrés inter-clusters, BCSS). Cette relation déterministe est également liée à la loi de la variance totale en théorie des probabilités.

Le terme « k -means » a été utilisé pour la première fois par James MacQueen en 1967, bien que l'idée remonte à Hugo Steinhaus en 1956. L'algorithme standard a été proposé pour la première fois par Stuart Lloyd de Bell Labs en 1957 comme technique de modulation par impulsions codées , bien qu'il n'ait été publié sous forme d'article de revue qu'en 1982. En 1965, Edward W. Forgy a publié essentiellement la même méthode, c'est pourquoi elle est parfois appelée algorithme de Lloyd-Forgy.

L'algorithme le plus courant utilise une technique de raffinement itératif. En raison de son omniprésence, il est souvent appelé « algorithme k -means » ; il est également appelé algorithme de Lloyd , en particulier dans la communauté informatique. Il est parfois également appelé « k -means naïf », car il existe des alternatives beaucoup plus rapides.

Étant donné un ensemble initial de k moyennes m ₁ ⁽¹⁾ , ..., m _k ⁽¹⁾ (voir ci-dessous), l'algorithme procède en alternant entre deux étapes :

1. Étape d'affectation : Affectez chaque observation au cluster ayant la moyenne la plus proche : celui ayant la plus petite distance euclidienne au carré . (Mathématiquement, cela signifie partitionner les observations selon le diagramme de Voronoi généré par les moyennes.) où chacune est affectée exactement à une seule , même si elle pourrait être affectée à deux ou plusieurs d'entre elles.
2. Étape de mise à jour : recalculer les moyennes ( centroïdes ) des observations attribuées à chaque cluster.

La fonction objective dans k -means est la somme des carrés au sein du cluster (WCSS). Après chaque itération, la WCSS diminue et nous avons donc une séquence décroissante monotone non négative. Cela garantit que les k -means convergent toujours, mais pas nécessairement vers l'optimum global.

L'algorithme a convergé lorsque les affectations ne changent plus ou, de manière équivalente, lorsque le WCSS est devenu stable. L'algorithme n'est pas assuré de trouver l'optimum.

L'algorithme est souvent présenté comme une affectation d'objets au groupe le plus proche en fonction de la distance. L'utilisation d'une fonction de distance différente de la distance euclidienne (au carré) peut empêcher l'algorithme de converger. Diverses modifications de k -means telles que les k -means sphériques et les k -medoids ont été proposées pour permettre l'utilisation d'autres mesures de distance.

Pseudo-code

Le pseudo-code ci-dessous décrit l'implémentation de l' algorithme de clustering k -means standard. L'initialisation des centroïdes, la mesure de distance entre les points et les centroïdes et le calcul de nouveaux centroïdes sont des choix de conception et varient selon les différentes implémentations. Dans cet exemple de pseudo-code, argmin est utilisé pour trouver l'index de la valeur minimale.

définition 
de k_means_cluster ( k , 
points ):
# Initialisation : choisir k centroïdes (Forgy, Random Partition, etc.)
centroïdes 
= 
[ c1 , 
c2 , 
... , 
ck ]
# Initialiser la liste des clusters
clusters 
= 
[[] 
pour 
_ 
dans 
la plage ( k )]
# Boucle jusqu'à convergence
convergé 
= 
faux
bien que 
non 
convergé :
# Effacer les clusters précédents
clusters 
= 
[[] 
pour 
_ 
dans 
la plage ( k )]
# Affecter chaque point au centroïde « le plus proche »
pour 
point 
en 
points :
distances_to_each_centroid 
= 
[ distance ( point , 
centroïde ) 
pour 
centroïde 
dans 
centroïdes ]
cluster_assignment 
= 
argmin ( distances_à_chaque_centroïde )
clusters [ cluster_assignment ] . append ( point )
# Calculer de nouveaux centroïdes
# (l'implémentation standard utilise la moyenne de tous les points d'un
# cluster pour déterminer le nouveau centroïde)
new_centroids 
= 
[ calculate_centroid ( cluster ) 
pour 
cluster 
dans 
clusters ]
convergé 
= 
( new_centroids 
== 
centroïdes )
centroïdes 
= 
nouveaux_centroïdes
si 
convergé :
retourner 
les clusters

Les méthodes d'initialisation couramment utilisées sont Forgy et Random Partition. La méthode Forgy choisit au hasard k observations dans l'ensemble de données et les utilise comme moyennes initiales. La méthode Random Partition attribue d'abord au hasard un cluster à chaque observation, puis passe à l'étape de mise à jour, calculant ainsi la moyenne initiale comme étant le centroïde des points attribués au hasard au cluster. La méthode Forgy tend à étaler les moyennes initiales, tandis que Random Partition les place toutes près du centre de l'ensemble de données. Selon Hamerly et al., la méthode Random Partition est généralement préférable pour les algorithmes tels que les moyennes k -harmoniques et les k -moyennes floues. Pour les algorithmes de maximisation des espérances et les k -moyennes standard, la méthode d'initialisation Forgy est préférable. Cependant, une étude approfondie menée par Celebi et al., , a révélé que les méthodes d'initialisation populaires telles que Forgy, Random Partition et Maximin ont souvent de faibles performances, alors que l'approche de Bradley et Fayyad fonctionne « systématiquement » dans « le meilleur groupe » et que k -means++ fonctionne « généralement bien ».

• Démonstration de l'algorithme standard
• 
  1. k « moyennes » initiales (dans ce cas k = 3) sont générées aléatoirement dans le domaine de données (affichées en couleur).
• 
  2. k clusters sont créés en associant chaque observation à la moyenne la plus proche. Les partitions ici représentent le diagramme de Voronoi généré par les moyennes.
• 
  3. Le centroïde de chacun des k clusters devient la nouvelle moyenne.
• 
  4. Les étapes 2 et 3 sont répétées jusqu’à ce que la convergence soit atteinte.

L'algorithme ne garantit pas la convergence vers l'optimum global. Le résultat peut dépendre des clusters initiaux. Comme l'algorithme est généralement rapide, il est courant de l'exécuter plusieurs fois avec des conditions de départ différentes. Cependant, les performances dans le pire des cas peuvent être lentes : en particulier, certains ensembles de points, même en deux dimensions, convergent en temps exponentiel, c'est -à-dire 2 ^{Ω( n )} . Ces ensembles de points ne semblent pas se produire dans la pratique : cela est corroboré par le fait que le temps d'exécution lissé de k -means est polynomial.

L'étape « d'affectation » est appelée « étape d'attente », tandis que l'« étape de mise à jour » est une étape de maximisation, faisant de cet algorithme une variante de l' algorithme d'attente-maximisation généralisé .

Trouver la solution optimale au problème de clustering k -means pour les observations en d dimensions est :

• NP-dur dans l'espace euclidien général (de dimensions d ) même pour deux clusters,
• NP-dur pour un nombre général de clusters k même dans le plan,
• si k et d (la dimension) sont fixes, le problème peut être résolu exactement en temps , où n est le nombre d'entités à regrouper.

Ainsi, une variété d' algorithmes heuristiques tels que l'algorithme de Lloyd donné ci-dessus sont généralement utilisés.

Le temps d'exécution de l'algorithme de Lloyd (et de la plupart des variantes) est , où :

• n est le nombre de vecteurs de dimension d (à regrouper)
• k le nombre de clusters
• i le nombre d'itérations nécessaires jusqu'à la convergence.

Sur des données qui ont une structure de clustering, le nombre d'itérations jusqu'à la convergence est souvent faible et les résultats ne s'améliorent que légèrement après la première douzaine d'itérations. L'algorithme de Lloyd est donc souvent considéré comme ayant une complexité « linéaire » dans la pratique, bien qu'il soit dans le pire des cas superpolynomial lorsqu'il est exécuté jusqu'à la convergence.

• Dans le pire des cas, l'algorithme de Lloyd nécessite des itérations, de sorte que la complexité du pire des cas de l'algorithme de Lloyd est superpolynomiale .
• L'algorithme k -means de Lloyd a un temps d'exécution lissé polynomial. Il est démontré que pour un ensemble arbitraire de n points dans , si chaque point est perturbé indépendamment par une distribution normale de moyenne 0 et de variance , alors le temps d'exécution attendu de l'algorithme k -means est limité par , qui est un polynôme en n , k , d et .
• De meilleures limites sont prouvées pour les cas simples. Par exemple, il est démontré que le temps d'exécution de l'algorithme k -means est limité par pour n points dans un treillis entier .

L'algorithme de Lloyd est l'approche standard pour ce problème. Cependant, il passe beaucoup de temps de traitement à calculer les distances entre chacun des centres de cluster k et les points de données n . Étant donné que les points restent généralement dans les mêmes clusters après quelques itérations, une grande partie de ce travail est inutile, ce qui rend l'implémentation naïve très inefficace. Certaines implémentations utilisent la mise en cache et l'inégalité triangulaire afin de créer des limites et d'accélérer l'algorithme de Lloyd.

Trouver le nombre optimal de clusters ( k ) pour le clustering k -means est une étape cruciale pour garantir que les résultats du clustering sont significatifs et utiles. Plusieurs techniques sont disponibles pour déterminer un nombre approprié de clusters. Voici quelques-unes des méthodes couramment utilisées :

• Méthode du coude (clustering) : Cette méthode consiste à tracer la variation expliquée en fonction du nombre de clusters et à choisir le coude de la courbe comme nombre de clusters à utiliser. Cependant, la notion de « coude » n'est pas bien définie et elle est connue pour être peu fiable.
• Silhouette (clustering) : L'analyse de silhouette mesure la qualité du clustering et fournit un aperçu de la distance de séparation entre les clusters résultants. Un score de silhouette plus élevé indique que l'objet correspond bien à son propre cluster et mal aux clusters voisins.
• Statistique d'écart : La statistique d'écart compare la variation totale au sein du cluster pour différentes valeurs de k avec leurs valeurs attendues sous une distribution de référence nulle des données. Le k optimal est la valeur qui produit la statistique d'écart la plus grande.
• Indice de Davies-Bouldin : L'indice de Davies-Bouldin est une mesure du degré de séparation entre les clusters. Des valeurs plus faibles de l'indice de Davies-Bouldin indiquent un modèle avec une meilleure séparation.
• Indice de Calinski-Harabasz : cet indice évalue les clusters en fonction de leur compacité et de leur séparation. L'indice est calculé en utilisant le rapport entre la variance inter-clusters et la variance intra-clusters, les valeurs les plus élevées indiquant des clusters mieux définis.
• Indice de Rand : Il calcule la proportion de concordance entre les deux groupes, en considérant les paires d'éléments correctement assignées au même groupe ou à des groupes différents. Des valeurs plus élevées indiquent une plus grande similarité et une meilleure qualité de clustering. Pour fournir une mesure plus précise, l'indice de Rand ajusté (ARI), introduit par Hubert et Arabie en 1985, corrige l'indice de Rand en ajustant la similarité attendue de tous les appariements dus au hasard.

• Optimisation des ruptures naturelles de Jenks : k -means appliqué aux données univariées
• Le clustering k -medians utilise la médiane dans chaque dimension au lieu de la moyenne, et minimise ainsila norme ( géométrie Taxicab ).
• k -medoids (également : Partitioning Around Medoids, PAM) utilise le médoïde au lieu de la moyenne, et minimise ainsi la somme des distances pour des fonctions de distance arbitraires .
• Le clustering flou C-Means est une version souple du clustering k -means, où chaque point de données a un degré flou d'appartenance à chaque cluster.
• Les modèles de mélange gaussien formés avec l'algorithme d'espérance-maximisation (algorithme EM) conservent des affectations probabilistes aux clusters, au lieu d'affectations déterministes, et des distributions gaussiennes multivariées au lieu de moyennes.
• k -means++ choisit les centres initiaux d'une manière qui donne une limite supérieure prouvable sur l'objectif WCSS.
• L'algorithme de filtrage utilise des arbres k -d pour accélérer chaque étape k -means.
• Certaines méthodes tentent d'accélérer chaque étape k -means en utilisant l' inégalité triangulaire .
• Échappez aux optima locaux en échangeant des points entre les clusters.
• L'algorithme de clustering sphérique k -means convient aux données textuelles.
• Les variantes hiérarchiques telles que le clustering k -means, le clustering X-means et le clustering G-means divisent à plusieurs reprises les clusters pour créer une hiérarchie et peuvent également essayer de déterminer automatiquement le nombre optimal de clusters dans un ensemble de données.
• Les mesures d'évaluation internes des clusters telles que la silhouette des clusters peuvent être utiles pour déterminer le nombre de clusters .
• La méthode des k -moyennes pondérées de Minkowski calcule automatiquement les pondérations des caractéristiques spécifiques aux clusters, étayant l'idée intuitive selon laquelle une caractéristique peut avoir différents degrés de pertinence selon les caractéristiques. Ces pondérations peuvent également être utilisées pour redimensionner un ensemble de données donné, augmentant ainsi la probabilité qu'un indice de validité de cluster soit optimisé au nombre attendu de clusters.
• Mini-lot k -means : variation de k -means à l'aide d'échantillons « mini-lot » pour les ensembles de données qui ne rentrent pas dans la mémoire.
• La méthode d'Otsu

La méthode de Hartigan et Wong fournit une variante de l'algorithme k -means qui progresse vers un minimum local du problème de somme des carrés minimum avec différentes mises à jour de solution. La méthode est une recherche locale qui tente de manière itérative de relocaliser un échantillon dans un cluster différent tant que ce processus améliore la fonction objective. Lorsqu'aucun échantillon ne peut être relocalisé dans un cluster différent avec une amélioration de l'objectif, la méthode s'arrête (dans un minimum local). De la même manière que l'algorithme k -means classique, l'approche reste une heuristique car elle ne garantit pas nécessairement que la solution finale soit globalement optimale.

Soit le coût individuel de défini par , avec le centre du cluster.

Étape d'affectation

La méthode de Hartigan et Wong commence par partitionner les points en clusters aléatoires .

Étape de mise à jour

Ensuite, il détermine le et pour lesquels la fonction suivante atteint un maximum. Pour ceux qui atteignent ce maximum, elle se déplace du cluster au cluster .

Terminaison

L'algorithme se termine une fois que la valeur est inférieure à zéro pour tous les .

Différentes stratégies d'acceptation des déplacements peuvent être utilisées. Dans une stratégie de première amélioration , toute relocalisation d'amélioration peut être appliquée, tandis que dans une stratégie de meilleure amélioration , toutes les relocalisations possibles sont testées de manière itérative et seule la meilleure est appliquée à chaque itération. La première approche favorise la vitesse, tandis que la seconde privilégie généralement la qualité de la solution au détriment d'un temps de calcul supplémentaire. La fonction utilisée pour calculer le résultat d'une relocalisation peut également être évaluée efficacement en utilisant l'égalité

L'algorithme classique k -means et ses variantes sont connus pour converger uniquement vers les minima locaux du problème de clustering à somme minimale des carrés défini comme De nombreuses études ont tenté d'améliorer le comportement de convergence de l'algorithme et de maximiser les chances d'atteindre l'optimum global (ou au moins, des minima locaux de meilleure qualité). Les techniques d'initialisation et de redémarrage décrites dans les sections précédentes sont une alternative pour trouver de meilleures solutions. Plus récemment, les algorithmes d'optimisation globale basés sur la programmation branch-and-bound et semi-définie ont produit des solutions « prouvées optimales » pour des ensembles de données contenant jusqu'à 4 177 entités et 20 531 caractéristiques. Comme prévu, en raison de la difficulté NP du problème d'optimisation sous-jacent, le temps de calcul des algorithmes optimaux pour k -means augmente rapidement au-delà de cette taille. Les solutions optimales pour les petites et moyennes échelles restent toujours précieuses comme outil de référence, pour évaluer la qualité d'autres heuristiques. Pour trouver des minima locaux de haute qualité dans un temps de calcul contrôlé mais sans garanties d'optimalité, d'autres travaux ont exploré les métaheuristiques et d'autres techniques d'optimisation globale , par exemple, basées sur des approches incrémentales et l'optimisation convexe, les échanges aléatoires (c'est-à-dire la recherche locale itérée ), la recherche de voisinage variable et les algorithmes génétiques . Il est en effet connu que trouver de meilleurs minima locaux du problème de clustering de somme minimale des carrés peut faire la différence entre l'échec et le succès pour récupérer des structures de cluster dans des espaces de caractéristiques de grande dimension.

Trois caractéristiques clés de k -means qui le rendent efficace sont souvent considérées comme ses plus gros inconvénients :

• La distance euclidienne est utilisée comme métrique et la variance est utilisée comme mesure de la dispersion des clusters.
• Le nombre de clusters k est un paramètre d'entrée : un choix inapproprié de k peut donner de mauvais résultats. C'est pourquoi, lors de l'exécution de k -means, il est important d'exécuter des contrôles de diagnostic pour déterminer le nombre de clusters dans l'ensemble de données .
• La convergence vers un minimum local peut produire des résultats contre-intuitifs (« erronés ») (voir l’exemple dans la Fig.).

Une limitation clé de k -means est son modèle de cluster. Le concept est basé sur des clusters sphériques qui sont séparables de sorte que la moyenne converge vers le centre du cluster. Les clusters sont censés être de taille similaire, de sorte que l'affectation au centre du cluster le plus proche est l'affectation correcte. Lorsque, par exemple, l'application de k -means avec une valeur de sur le célèbre ensemble de données sur les fleurs d'iris , le résultat ne parvient souvent pas à séparer les trois espèces d'iris contenues dans l'ensemble de données. Avec , les deux clusters visibles (l'un contenant deux espèces) seront découverts, tandis qu'avec l'un des deux clusters sera divisé en deux parties égales. En fait, est plus approprié pour cet ensemble de données, bien que l'ensemble de données contienne 3 classes . Comme pour tout autre algorithme de clustering, le résultat de k -means suppose que les données satisfont à certains critères. Il fonctionne bien sur certains ensembles de données et échoue sur d'autres.

Le résultat de k -means peut être vu comme les cellules de Voronoi des moyennes de cluster. Étant donné que les données sont divisées à mi-chemin entre les moyennes de cluster, cela peut conduire à des divisions sous-optimales comme on peut le voir dans l'exemple de la « souris ». Les modèles gaussiens utilisés par l' algorithme d'espérance-maximisation (sans doute une généralisation de k -means) sont plus flexibles en ayant à la fois des variances et des covariances. Le résultat EM est ainsi capable de s'adapter à des clusters de taille variable bien mieux que k -means ainsi qu'à des clusters corrélés (pas dans cet exemple). En contrepartie, EM nécessite l'optimisation d'un plus grand nombre de paramètres libres et pose certains problèmes méthodologiques en raison de clusters qui disparaissent ou de matrices de covariance mal conditionnées. k -means est étroitement lié à la modélisation bayésienne non paramétrique .

Le clustering k -means est assez facile à appliquer même à des ensembles de données volumineux, en particulier lors de l'utilisation d'heuristiques telles que l'algorithme de Lloyd . Il a été utilisé avec succès dans la segmentation de marché , la vision par ordinateur et l'astronomie , entre autres domaines. Il est souvent utilisé comme étape de prétraitement pour d'autres algorithmes, par exemple pour trouver une configuration de départ.

La quantification vectorielle , une technique couramment utilisée dans le traitement du signal et l'infographie, consiste à réduire la palette de couleurs d'une image à un nombre fixe de couleurs, appelé k . Une méthode courante pour réaliser la quantification vectorielle consiste à utiliser le clustering k -means. Dans ce processus, k -means est appliqué à l'espace colorimétrique d'une image pour le partitionner en k clusters, chaque cluster représentant une couleur distincte de l'image. Cette technique est particulièrement utile dans les tâches de segmentation d'images, où elle permet d'identifier et de regrouper des couleurs similaires.

Exemple : Dans le domaine de l'infographie , le clustering k -means est souvent utilisé pour la quantification des couleurs dans la compression d'images. En réduisant le nombre de couleurs utilisées pour représenter une image, la taille des fichiers peut être considérablement réduite sans perte significative de qualité visuelle. Par exemple, considérons une image avec des millions de couleurs. En appliquant le clustering k -means avec k défini sur un nombre plus petit, l'image peut être représentée à l'aide d'une palette de couleurs plus limitée , ce qui donne une version compressée qui consomme moins d'espace de stockage et de bande passante. D'autres utilisations de la quantification vectorielle incluent l'échantillonnage non aléatoire , car les k -means peuvent facilement être utilisés pour choisir k objets différents mais prototypiques à partir d'un grand ensemble de données pour une analyse plus approfondie.

L'analyse de cluster , une tâche fondamentale dans l'exploration de données et l'apprentissage automatique , consiste à regrouper un ensemble de points de données en clusters en fonction de leur similarité. Le clustering k -means est un algorithme populaire utilisé pour partitionner les données en k clusters, où chaque cluster est représenté par son centroïde.

Cependant, l' algorithme k -means pur n'est pas très flexible et, par conséquent, son utilité est limitée (sauf lorsque la quantification vectorielle comme ci-dessus est en fait le cas d'utilisation souhaité). En particulier, le paramètre k est connu pour être difficile à choisir (comme indiqué ci-dessus) lorsqu'il n'est pas donné par des contraintes externes. Une autre limitation est qu'il ne peut pas être utilisé avec des fonctions de distance arbitraires ou sur des données non numériques. Pour ces cas d'utilisation, de nombreux autres algorithmes sont supérieurs.

Exemple : En marketing, le clustering k -means est fréquemment utilisé pour la segmentation du marché , où les clients ayant des caractéristiques ou des comportements similaires sont regroupés. Par exemple, une entreprise de vente au détail peut utiliser le clustering k -means pour segmenter sa clientèle en groupes distincts en fonction de facteurs tels que le comportement d'achat, la démographie et la situation géographique. Ces segments de clientèle peuvent ensuite être ciblés avec des stratégies marketing et des offres de produits sur mesure pour maximiser les ventes et la satisfaction des clients.

Le clustering k -means a été utilisé comme une étape d'apprentissage de caractéristiques (ou d'apprentissage par dictionnaire ), soit dans l'apprentissage ( semi- ) supervisé , soit dans l'apprentissage non supervisé . L'approche de base consiste d'abord à former une représentation de clustering k -means, en utilisant les données d'apprentissage d'entrée (qui n'ont pas besoin d'être étiquetées). Ensuite, pour projeter toute donnée d'entrée dans le nouvel espace de caractéristiques, une fonction « d'encodage », telle que le produit matriciel seuillé de la donnée avec les emplacements des centroïdes, calcule la distance de la donnée à chaque centroïde, ou simplement une fonction indicatrice pour le centroïde le plus proche, ou une transformation douce de la distance. Alternativement, en transformant la distance échantillon-cluster via un RBF gaussien , on obtient la couche cachée d'un réseau de fonctions de base radiale .

Cette utilisation de k -means a été combinée avec succès avec des classificateurs simples et linéaires pour l'apprentissage semi-supervisé en PNL (en particulier pour la reconnaissance d'entités nommées ) et en vision par ordinateur . Sur une tâche de reconnaissance d'objets, on a constaté qu'elle présentait des performances comparables à celles d'approches d'apprentissage de caractéristiques plus sophistiquées telles que les autoencodeurs et les machines de Boltzmann restreintes . Cependant, elle nécessite généralement plus de données, pour des performances équivalentes, car chaque point de données ne contribue qu'à une seule « caractéristique ».

Exemple : dans le traitement du langage naturel (NLP), le clustering k -means a été intégré à des classificateurs linéaires simples pour des tâches d'apprentissage semi-supervisées telles que la reconnaissance d'entités nommées (NER). En regroupant d'abord les données textuelles non étiquetées à l'aide de k -means, des caractéristiques significatives peuvent être extraites pour améliorer les performances des modèles NER. Par exemple, le clustering k -means peut être appliqué pour identifier des groupes de mots ou de phrases qui coexistent fréquemment dans le texte d'entrée, qui peuvent ensuite être utilisés comme caractéristiques pour l'entraînement du modèle NER. Il a été démontré que cette approche permet d'obtenir des performances comparables à celles de techniques d'apprentissage de caractéristiques plus complexes telles que les autoencodeurs et les machines de Boltzmann restreintes , bien qu'avec une plus grande exigence en matière de données étiquetées.

Les avancées récentes dans l'application du clustering k -means incluent des améliorations dans les techniques d'initialisation, telles que l'utilisation de l'initialisation k -means++ pour sélectionner les centroïdes de cluster initiaux de manière plus efficace. De plus, les chercheurs ont exploré l'intégration du clustering k -means avec des méthodes d'apprentissage profond, telles que les réseaux neuronaux convolutifs (CNN) et les réseaux neuronaux récurrents (RNN), pour améliorer les performances de diverses tâches en vision par ordinateur , en traitement du langage naturel et dans d'autres domaines.

L'algorithme standard lent pour le clustering k -means et son algorithme d'espérance-maximisation associé sont un cas particulier de modèle de mélange gaussien, en particulier le cas limite où toutes les covariances sont fixées comme diagonales, égales et ont une variance infinitésimale. Au lieu de petites variances, une affectation de cluster dur peut également être utilisée pour montrer une autre équivalence du clustering k -means à un cas particulier de modélisation de mélange gaussien « dur ». Cela ne signifie pas qu'il est efficace d'utiliser la modélisation de mélange gaussien pour calculer les k -moyennes, mais simplement qu'il existe une relation théorique et que la modélisation de mélange gaussien peut être interprétée comme une généralisation des k -moyennes ; au contraire, il a été suggéré d'utiliser le clustering k -moyennes pour trouver des points de départ pour la modélisation de mélange gaussien sur des données difficiles.

Une autre généralisation de l' algorithme k -means est l' algorithme k -SVD, qui estime les points de données comme une combinaison linéaire clairsemée de « vecteurs de livre de codes ». k -means correspond au cas particulier de l'utilisation d'un seul vecteur de livre de codes, avec un poids de 1.

La solution relâchée du clustering k -means, spécifiée par les indicateurs de cluster, est donnée par l'analyse en composantes principales (ACP). L'intuition est que les k -means décrivent des clusters de forme sphérique (en forme de boule). Si les données ont 2 clusters, la ligne reliant les deux centroïdes est la meilleure direction de projection unidimensionnelle, qui est également la première direction de l'ACP. Couper la ligne au centre de masse sépare les clusters (c'est la relaxation continue de l'indicateur de cluster discret). Si les données ont trois clusters, le plan bidimensionnel couvert par trois centroïdes de cluster est la meilleure projection 2D. Ce plan est également défini par les deux premières dimensions de l'ACP. Les clusters bien séparés sont efficacement modélisés par des clusters en forme de boule et donc découverts par les k -means. Les clusters non en forme de boule sont difficiles à séparer lorsqu'ils sont proches. Par exemple, deux clusters en forme de demi-lune entrelacés dans l'espace ne se séparent pas bien lorsqu'ils sont projetés sur le sous-espace de l'ACP. On ne devrait pas s'attendre à ce que les k -moyennes fonctionnent bien sur ces données. Il est simple de produire des contre-exemples à l'affirmation selon laquelle le sous-espace centroïde du cluster est couvert par les directions principales.

Les algorithmes de clustering à décalage moyen de base conservent un ensemble de points de données de la même taille que l'ensemble de données d'entrée. Initialement, cet ensemble est copié à partir de l'ensemble d'entrée. Tous les points sont ensuite déplacés de manière itérative vers la moyenne des points qui les entourent. En revanche, k -means restreint l'ensemble de clusters à k clusters, généralement bien inférieur au nombre de points dans l'ensemble de données d'entrée, en utilisant la moyenne de tous les points du cluster précédent qui sont plus proches de ce point que tout autre pour le centroïde (par exemple dans la partition de Voronoi de chaque point de mise à jour). Un algorithme de décalage moyen qui est alors similaire à k -means, appelé décalage moyen de vraisemblance , remplace l'ensemble de points en cours de remplacement par la moyenne de tous les points de l'ensemble d'entrée qui se trouvent à une distance donnée de l'ensemble changeant. Un avantage du clustering à décalage moyen par rapport à k -means est la détection d'un nombre arbitraire de clusters dans l'ensemble de données, car il n'y a pas de paramètre déterminant le nombre de clusters. Le décalage moyen peut être beaucoup plus lent que k -means et nécessite toujours la sélection d'un paramètre de bande passante.

Sous des hypothèses de parcimonie et lorsque les données d'entrée sont prétraitées avec la transformation de blanchiment , k -means produit la solution à la tâche d'analyse des composantes indépendantes linéaires (ICA). Cela aide à expliquer l'application réussie de k -means à l'apprentissage des caractéristiques.

Le filtre k -means suppose implicitement que l'ordre de l'ensemble des données d'entrée n'a pas d'importance. Le filtre bilatéral est similaire au filtre k -means et au décalage moyen dans la mesure où il conserve un ensemble de points de données qui sont remplacés de manière itérative par des moyennes. Cependant, le filtre bilatéral restreint le calcul de la moyenne (pondérée par le noyau) pour inclure uniquement les points qui sont proches dans l'ordre des données d'entrée. Cela le rend applicable à des problèmes tels que le débruitage d'images, où la disposition spatiale des pixels dans une image est d'une importance cruciale.

L'ensemble des fonctions de cluster minimisant l'erreur au carré comprend également l' algorithme k -médoïdes , une approche qui force le point central de chaque cluster à être l'un des points réels, c'est-à-dire qu'il utilise des médoïdes à la place des centroïdes .

Les différentes implémentations de l'algorithme présentent des différences de performances, la plus rapide sur un ensemble de données de test se terminant en 10 secondes, la plus lente prenant 25 988 secondes (~ 7 heures). Les différences peuvent être attribuées à la qualité de l'implémentation, aux différences de langage et de compilateur, aux différents critères de terminaison et niveaux de précision, et à l'utilisation d'index pour l'accélération.

Les implémentations suivantes sont disponibles sous des licences de logiciels libres/open source , avec un code source accessible au public.

• Accord.NET contient des implémentations C# pour k -means, k -means++ et k -modes.
• ALGLIB contient des implémentations C++ et C# parallélisées pour k -means et k -means++.
• AOSP contient une implémentation Java pour k -means.
• CrimeStat implémente deux algorithmes spatiaux k -means, dont l'un permet à l'utilisateur de définir les emplacements de départ.
• ELKI contient k -means (avec itération Lloyd et MacQueen, ainsi que différentes initialisations telles que l'initialisation k -means++) et divers algorithmes de clustering plus avancés.
• Smile contient k -means et divers autres algorithmes et visualisation des résultats (pour Java, Kotlin et Scala).
• Julia contient une implémentation k -means dans le package de clustering JuliaStats.
• KNIME contient des nœuds pour les k -moyennes et les k -médoïdes.
• Mahout contient un k -means basé sur MapReduce .
• mlpack contient une implémentation C++ de k -means.
• L'octave contient k -means.
• OpenCV contient une implémentation k -means.
• Orange inclut un composant pour le clustering k -means avec sélection automatique de k et notation de la silhouette du cluster.
• PSPP contient k -means. La commande QUICK CLUSTER effectue un clustering k -means sur l'ensemble de données.
• R contient trois variantes de k -means.
• SciPy et scikit-learn contiennent plusieurs implémentations k -means.
• Spark MLlib implémente un algorithme k -means distribué.
• Torch contient un package unsup qui fournit un clustering k -means.
• Weka contient des k -moyennes et des x -moyennes.

Les implémentations suivantes sont disponibles sous des conditions de licence propriétaires et peuvent ne pas avoir de code source accessible au public.