k -signifie le regroupement

Le k -means clustering 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 dont la moyenne est la plus proche (centres de cluster ou centroïde de cluster ), servant de prototype de la grappe. Il en résulte un partitionnement de l’espace de données en cellules de Voronoi . k -means clustering 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 quadratiques, 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 les k-médianes et les k-Médoïdes .

Le problème est difficile en termes de calcul ( NP-difficile ); cependant, les algorithmes heuristiques efficaces convergent rapidement vers un optimum local . Celles-ci sont généralement similaires à l’ Algorithme de maximisation des attentes pour les mélanges de distributions gaussiennes via une approche de raffinement itérative employée à la fois par les k-moyennes et la modélisation des mélanges gaussiens . Ils utilisent tous les deux des centres de clusters pour modéliser les données ; cependant, le clustering k -means a tendance à 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 -plus proche voisin , une technique d’ apprentissage automatique supervisée populaire pour la classification qui est souvent confondue avec k -means en raison de son nom. L’application du classificateur 1-plus proche voisin 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 centroïde le plus proche ou l’algorithme de Rocchio .

La description

Étant donné un ensemble d’observations ( x ₁ , x ₂ , …, x _n ), où chaque observation est un vecteur réel d -dimensionnel, k -means clustering 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 :

un r g m je n S ∑ je = 1 k ∑ X ∈ S i ‖ x − μ i ‖ 2 = a r g m i n S ∑ i = 1 k | S i | Var ⁡ S i {displaystyle {underset {mathbf {S} }{operatorname {arg,min} }}sum _{i=1}^{k}sum _{mathbf {x} in S_{i }}left|mathbf {x} -{boldsymbol {mu }}_{i}right|^{2}={underset {mathbf {S} }{operatorname {arg, min} }}sum _{i=1}^{k}|S_{i}|nomopérateur {Var} S_{i}} ${displaystyle {underset {mathbf {S} }{operatorname {arg,min} }}sum _{i=1}^{k}sum _{mathbf {x} in S_{i}}left|mathbf {x} -{boldsymbol {mu }}_{i}right|^{2}={underset {mathbf {S} }{operatorname {arg,min} }}sum _{i=1}^{k}|S_{i}|operatorname {Var} S_{i}}$ ${displaystyle {underset {mathbf {S} }{operatorname {arg,min} }}sum _{i=1}^{k}sum _{mathbf {x} in S_{i}}left|mathbf {x} -{boldsymbol {mu }}_{i}right|^{2}={underset {mathbf {S} }{operatorname {arg,min} }}sum _{i=1}^{k}|S_{i}|operatorname {Var} S_{i}}$

où μ _i est la moyenne des points de S _i . Cela équivaut à minimiser les écarts au carré deux à deux des points dans le même cluster :

a r g m i n S ∑ i = 1 k 1 | S i | ∑ x , y ∈ S i ‖ x − y ‖ 2 {displaystyle {underset {mathbf {S} }{operatorname {arg,min} }}sum _{i=1}^{k},{frac {1}{|S_{i} |}},sum _{mathbf {x} ,mathbf {y} in S_{i}}left|mathbf {x} -mathbf {y} right|^{2} } ${displaystyle {underset {mathbf {S} }{operatorname {arg,min} }}sum _{i=1}^{k},{frac {1}{|S_{i}|}},sum _{mathbf {x} ,mathbf {y} in S_{i}}left|mathbf {x} -mathbf {y} right|^{2}}$ ${displaystyle {underset {mathbf {S} }{operatorname {arg,min} }}sum _{i=1}^{k},{frac {1}{|S_{i}|}},sum _{mathbf {x} ,mathbf {y} in S_{i}}left|mathbf {x} -mathbf {y} right|^{2}}$

L’équivalence peut être déduite de l’identité | S i | ∑ x ∈ S i ‖ x − μ i ‖ 2 = ∑ x ≠ y ∈ S i ‖ x − y ‖ 2 {displaystyle |S_{i}|sum _{mathbf {x} in S_{i}}left|mathbf {x} -{boldsymbol {mu }}_{i}right |^{2}=sum _{mathbf {x} neq mathbf {y} in S_{i}}left|mathbf {x} -mathbf {y} right|^{ 2}} ${displaystyle |S_{i}|sum _{mathbf {x} in S_{i}}left|mathbf {x} -{boldsymbol {mu }}_{i}right|^{2}=sum _{mathbf {x} neq mathbf {y} in S_{i}}left|mathbf {x} -mathbf {y} right|^{2}}$ ${displaystyle |S_{i}|sum _{mathbf {x} in S_{i}}left|mathbf {x} -{boldsymbol {mu }}_{i}right|^{2}=sum _{mathbf {x} neq mathbf {y} in S_{i}}left|mathbf {x} -mathbf {y} right|^{2}}$ . 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-cluster, BCSS), ^[1] . Cette relation déterministe est également liée à la loi de la variance totale dans la théorie des probabilités.

Histoire

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

Algorithmes

Algorithme standard (k-means naïf)

Convergence des k -moyennes

L’algorithme le plus courant utilise une technique de raffinement itérative. En raison de son omniprésence, il est souvent appelé “l’ algorithme k -means” ; il est également appelé algorithme de Lloyd , en particulier dans la communauté informatique. Il est parfois aussi appelé ” k -means naïf”, car il existe des alternatives beaucoup plus rapides. ^[6]

Etant donné un ensemble initial de k moyens m ₁⁽¹⁾ ,…, m _k⁽¹⁾ (voir ci-dessous), l’algorithme procède en alternant entre deux étapes : ^[7]

Étape d’affectation : Attribuez chaque observation au cluster dont la moyenne est la plus proche : celle dont la distance euclidienne est la plus petite au carré . ^[8] (Mathématiquement, cela revient à partitionner les observations selon le diagramme de Voronoi généré par les moyennes.) S i ( t ) = { x p : ‖ x p − m i ( t ) ‖ 2 ≤ ‖ x p − m j ( t ) ‖ 2 ∀ j , 1 ≤ j ≤ k } , {displaystyle S_{i}^{(t)}=left{x_{p} :left|x_{p}-m_{i}^{(t)}right|^{2} leq left|x_{p}-m_{j}^{(t)}right|^{2} forall j,1leq jleq kright},} ${displaystyle S_{i}^{(t)}=left{x_{p}:left|x_{p}-m_{i}^{(t)}right|^{2}leq left|x_{p}-m_{j}^{(t)}right|^{2} forall j,1leq jleq kright},}$ ${displaystyle S_{i}^{(t)}=left{x_{p}:left|x_{p}-m_{i}^{(t)}right|^{2}leq left|x_{p}-m_{j}^{(t)}right|^{2} forall j,1leq jleq kright},}$ où chacun x p {displaystyle x_{p}} $x_{p}$ $x_{p}$ est attribué à exactement un S ( t ) {displaystyle S^{(t)}} $S^{(t)}$ $S^{(t)}$ , même s’il pouvait être attribué à deux ou plusieurs d’entre eux. Étape de mise à jour : recalculez les moyennes ( centres de gravité ) pour les observations affectées à chaque cluster. m i ( t + 1 ) = 1 | S i ( t ) | ∑ x j ∈ S i ( t ) x j {displaystyle m_{i}^{(t+1)}={frac {1}{left|S_{i}^{(t)}right|}}sum _{x_{j} dans S_{i}^{(t)}}x_{j}} ${displaystyle m_{i}^{(t+1)}={frac {1}{left|S_{i}^{(t)}right|}}sum _{x_{j}in S_{i}^{(t)}}x_{j}}$ ${displaystyle m_{i}^{(t+1)}={frac {1}{left|S_{i}^{(t)}right|}}sum _{x_{j}in S_{i}^{(t)}}x_{j}}$

L’algorithme a convergé lorsque les affectations ne changent plus. L’algorithme n’est pas garanti pour trouver l’optimum. ^[9]

L’algorithme est souvent présenté comme attribuant des objets au cluster 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 la convergence de l’algorithme. Diverses modifications des k -moyennes telles que les k -moyennes sphériques et les k –Médoïdes ont été proposées pour permettre d’utiliser d’autres mesures de distance.

Méthodes d’initialisation

Les méthodes d’initialisation couramment utilisées sont Forgy et Random Partition. ^[10] La méthode Forgy choisit au hasard k observations dans l’ensemble de données et les utilise comme moyennes initiales. La méthode de partition aléatoire attribue d’abord au hasard un groupe à 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 du groupe. La méthode Forgy a tendance à étaler les moyens initiaux, tandis que Random Partition les place tous près du centre de l’ensemble de données. Selon Hamerly et al., ^[10] la méthode de partition aléatoire est généralement préférable pour les algorithmes tels que les k -moyennes harmoniques et les k -moyennes floues. Pour la maximisation des attentes et la normealgorithmes k -means, la méthode d’initialisation Forgy est préférable. Une étude approfondie de Celebi et al. ^[11] a cependant révélé que les méthodes d’initialisation populaires telles que Forgy, Random Partition et Maximin fonctionnent souvent mal, alors que l’approche de Bradley et Fayyad ^[12] fonctionne “constamment” dans “le meilleur groupe”. et k -means++ fonctionne “généralement bien”.

Démonstration de l’algorithme standard
1. k “moyens” initiaux (dans ce cas k = 3) sont générés aléatoirement dans le domaine de données (en couleur).
2. k clusters sont créés en associant chaque observation à la moyenne la plus proche. Les partitions représentent ici le diagramme de Voronoi généré par les moyens.
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 différentes conditions de démarrage. Cependant, les performances au pire peuvent être lentes : en particulier certains ensembles de points, même en deux dimensions, convergent en temps exponentiel, soit 2 ^{Ω( n )} . ^[13] Ces ensembles de points ne semblent pas se présenter en pratique : ceci est corroboré par le fait que le temps d’exécution lissé des k -means est polynomial. ^[14]

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 généralisé d’ attente-maximisation .

Complexité

Trouver la solution optimale au problème de regroupement des k -moyennes pour les observations en d dimensions est :

NP-difficile dans l’ espace euclidien général (de dimension d ) même pour deux clusters, ^{[15] [16]}
NP-difficile pour un nombre général de clusters k même dans le plan, ^[17]
si k et d (la dimension) sont fixes, le problème peut être résolu exactement dans le temps O ( n d k + 1 ) {displaystyle O(n^{dk+1})} ${displaystyle O(n^{dk+1})}$ ${displaystyle O(n^{dk+1})}$ , où n est le nombre d’entités à regrouper. ^[18]

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 k d i ) {displaystyle O(nkdi)} $O(nkdi)$ $O(nkdi)$ , ^{[9] [19]} où :

n est le nombre de vecteurs d -dimensionnels (à regrouper)
k le nombre de grappes
i le nombre d’itérations nécessaires jusqu’à convergence.

Sur les 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 de complexité “linéaire” en pratique, bien qu’il soit dans le pire des cas superpolynomial lorsqu’il est exécuté jusqu’à convergence. ^[20]

Dans le pire des cas, l’algorithme de Lloyd nécessite i = 2 Ω ( n ) {displaystyle i=2^{Oméga ({sqrt {n}})}} ${displaystyle i=2^{Omega ({sqrt {n}})}}$ ${displaystyle i=2^{Omega ({sqrt {n}})}}$ itérations, de sorte que la complexité dans le pire des cas de l’algorithme de Lloyd est superpolynomiale . ^[20]
L’algorithme k -means de Lloyd a un temps d’exécution polynomial lissé. On montre que ^[14] pour un ensemble arbitraire de n points dans [ 0 , 1 ] d {style d’affichage [0,1]^{d}} $[0,1]^{d}$ $[0,1]^{d}$ , si chaque point est indépendamment perturbé par une loi normale de moyenne 0 et de variance σ 2 {displaystyle sigma ^{2}} $sigma ^{2}$ $sigma ^{2}$ , alors le temps d’exécution attendu de l’ algorithme k -means est borné par O ( n 34 k 34 d 8 log 4 ⁡ ( n ) / σ 6 ) {displaystyle O(n^{34}k^{34}d^{8}log ^{4}(n)/sigma ^{6})} ${displaystyle O(n^{34}k^{34}d^{8}log ^{4}(n)/sigma ^{6})}$ ${displaystyle O(n^{34}k^{34}d^{8}log ^{4}(n)/sigma ^{6})}$ , qui est un polynôme en n , k , d et 1 / σ {displaystyle 1/sigma} $1/sigma$ $1/sigma$ .
De meilleures bornes sont prouvées pour des cas simples. Par exemple, on montre que le temps d’ exécution de l’algorithme k -means est borné par O ( d n 4 M 2 ) {displaystyle O(dn^{4}M^{2})} $O(dn^{4}M^{2})$ $O(dn^{4}M^{2})$ pour n points dans un réseau entier { 1 , … , M } d {displaystyle {1,dots ,M}^{d}} ${1,dots ,M}^{d}$ ${1,dots ,M}^{d}$ . ^[21]

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 k centres de cluster et les n points de données. É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. ^{[9] [22] [23] [24] [25]}

Variantes

Optimisation des ruptures naturelles de Jenks : k -moyennes appliquées aux données univariées
le clustering k -medians utilise la médiane dans chaque dimension au lieu de la moyenne, et de cette façon minimise L 1 {displaystyle L_{1}} $L_{1}$ $L_{1}$ norme ( géométrie Taxicab ).
k -medoids (également : Partitioning Around Medoids, PAM) utilise le medoid au lieu de la moyenne, et minimise ainsi la somme des distances pour les fonctions de distance arbitraires .
Le clustering flou C-Means est une version logicielle de 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 de maximisation des attentes (algorithme EM) maintiennent les affectations probabilistes aux clusters, au lieu des affectations déterministes, et les distributions gaussiennes multivariées au lieu des 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 kd-trees pour accélérer chaque étape k -means. ^[26]
Certaines méthodes tentent d’accélérer chaque étape de k -means en utilisant l’ inégalité triangulaire . ^{[22] [23] [24] [27] [25]}
Échappez aux optima locaux en échangeant des points entre les clusters. ^[9]
L’algorithme de clustering Spherical k -means convient aux données textuelles. ^[28]
Des variantes hiérarchiques telles que Bisecting k -means, ^[29] X-means clustering ^[30] et G-means clustering ^[31] 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 des grappes internes telles que la silhouette des grappes peuvent être utiles pour déterminer le nombre de grappes .
Minkowski pondéré k -means calcule automatiquement les poids des caractéristiques spécifiques au cluster, soutenant l’idée intuitive qu’une entité peut avoir différents degrés de pertinence à différentes caractéristiques. ^[32] Ces pondérations peuvent également être utilisées pour remettre à l’échelle un ensemble de données donné, augmentant la probabilité qu’un indice de validité de cluster soit optimisé au nombre de clusters attendu. ^[33]
Mini-batch k -means : k -means variation utilisant des échantillons de « mini-lots » pour les ensembles de données qui ne rentrent pas dans la mémoire. ^[34]
La méthode d’Otsu

Méthode Hartigan-Wong

La méthode de Hartigan et Wong ^[9] fournit une variante de l’algorithme des k -moyennes qui progresse vers un minimum local du problème de la 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 déplacer un échantillon dans un cluster différent tant que ce processus améliore la fonction objectif. 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 les k -means classiques, l’approche reste une heuristique puisqu’elle ne garantit pas nécessairement que la solution finale soit globalement optimale.

Laisser φ ( S j ) {displaystyle varphi (S_{j})} ${displaystyle varphi (S_{j})}$ ${displaystyle varphi (S_{j})}$ être le coût individuel de S j {displaystyle S_{j}} $S_j$ $S_j$ Défini par ∑ x ∈ S j ( x − μ j ) 2 {displaystyle sum _{xin S_{j}}(x-mu _{j})^{2}} ${displaystyle sum _{xin S_{j}}(x-mu _{j})^{2}}$ ${displaystyle sum _{xin S_{j}}(x-mu _{j})^{2}}$ , avec μ j {displaystylemu _{j}} $mu _{j}$ $mu _{j}$ le centre du cluster.

Étape d’affectation : la méthode de Hartigan et Wong commence par partitionner les points en grappes aléatoires { S j } j ∈ { 1 , ⋯ k } {displaystyle {S_{j}}_{jin {1,cdots k}}} ${displaystyle {S_{j}}_{jin {1,cdots k}}}$ ${displaystyle {S_{j}}_{jin {1,cdots k}}}$ .

Étape de mise à jour : Ensuite, il détermine le n , m ∈ { 1 , … , k } {displaystyle n,min {1,ldots ,k}} ${displaystyle n,min {1,ldots ,k}}$ ${displaystyle n,min {1,ldots ,k}}$ et x ∈ S n {displaystyle xin S_{n}} ${displaystyle xin S_{n}}$ ${displaystyle xin S_{n}}$ pour lequel la fonction suivante atteint un maximum

Δ ( m , n , x ) = φ ( S n ) + φ ( S m ) − φ ( S n ∖ { x } ) − φ ( S m ∪ { x } ) . {displaystyle Delta (m,n,x)=varphi (S_{n})+varphi (S_{m})-varphi (S_{n}smallsetminus {x})-varphi ( S_{m}tasse {x}).} ${displaystyle Delta (m,n,x)=varphi (S_{n})+varphi (S_{m})-varphi (S_{n}smallsetminus {x})-varphi (S_{m}cup {x}).}$ ${displaystyle Delta (m,n,x)=varphi (S_{n})+varphi (S_{m})-varphi (S_{n}smallsetminus {x})-varphi (S_{m}cup {x}).}$

Pour le x , n , m {displaystyle x,n,m} ${displaystyle x,n,m}$ ${displaystyle x,n,m}$ qui atteignent ce maximum, x {style d’affichage x} $x$ $x$ se déplace du cluster S n {displaystyle S_{n}} $S_{n}$ $S_{n}$ au cluster S m {displaystyle S_{m}} $S_m$ $S_m$ .

Terminaison : L’algorithme se termine une fois Δ ( m , n , x ) {displaystyle Delta (m,n,x)} ${displaystyle Delta (m,n,x)}$ ${displaystyle Delta (m,n,x)}$ est inférieur à zéro pour tout x , n , m {displaystyle x,n,m} ${displaystyle x,n,m}$ ${displaystyle x,n,m}$ .

Différentes stratégies d’acceptation de mouvement peuvent être utilisées. Dans une stratégie de première amélioration , toute relocalisation améliorante peut être appliquée, alors 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 privilégie la vitesse, alors que la seconde approche privilégie généralement la qualité de la solution au détriment du temps de calcul supplémentaire. La fonction Δ {displaystyle Delta} $Delta$ $Delta$ utilisé pour calculer le résultat d’une relocalisation peut également être évalué efficacement en utilisant l’égalité ^[35]

Δ ( x , n , m ) = ∣ S n ∣ ∣ S n ∣ − 1 ⋅ ‖ μ n − x ‖ 2 − ∣ S m ∣ ∣ S m ∣ + 1 ⋅ ‖ μ m − x ‖ 2 . {displaystyle Delta (x,n,m)={frac {mid S_{n}mid }{mid S_{n}mid -1}}cdot lVert mu _{n}- xrVert ^{2}-{frac {mid S_{m}mid }{mid S_{m}mid +1}}cdot lVert mu _{m}-xrVert ^{ 2}.} ${displaystyle Delta (x,n,m)={frac {mid S_{n}mid }{mid S_{n}mid -1}}cdot lVert mu _{n}-xrVert ^{2}-{frac {mid S_{m}mid }{mid S_{m}mid +1}}cdot lVert mu _{m}-xrVert ^{2}.}$ ${displaystyle Delta (x,n,m)={frac {mid S_{n}mid }{mid S_{n}mid -1}}cdot lVert mu _{n}-xrVert ^{2}-{frac {mid S_{m}mid }{mid S_{m}mid +1}}cdot lVert mu _{m}-xrVert ^{2}.}$

Optimisation globale et Métaheuristiques

L’algorithme classique des k-moyennes et ses variations sont connus pour ne converger que vers les minima locaux du problème de regroupement de la somme minimale des carrés défini comme

a r g m i n S ∑ i = 1 k ∑ x ∈ S i ‖ x − μ i ‖ 2 . {displaystyle {underset {mathbf {S} }{operatorname {arg,min} }}sum _{i=1}^{k}sum _{mathbf {x} in S_{i }}left|mathbf {x} -{boldsymbol {mu }}_{i}right|^{2}.} ${displaystyle {underset {mathbf {S} }{operatorname {arg,min} }}sum _{i=1}^{k}sum _{mathbf {x} in S_{i}}left|mathbf {x} -{boldsymbol {mu }}_{i}right|^{2}.}$ ${displaystyle {underset {mathbf {S} }{operatorname {arg,min} }}sum _{i=1}^{k}sum _{mathbf {x} in S_{i}}left|mathbf {x} -{boldsymbol {mu }}_{i}right|^{2}.}$

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 du 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, des 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. ^[36] Comme prévu, en raison de la dureté NPdu 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 précieuses en tant qu’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 garantie d’optimalité, d’autres travaux ont exploré des Métaheuristiques et d’autres techniques d’optimisation globale , par exemple, basées sur des approches incrémentales et une optimisation convexe, ^[37] des swaps aléatoires ^[38] (c’est-à-dire des recherche locale ), recherche de voisinage variable ^[39] et Algorithmes génétiques . ^[40][41] Il est en effet connu que trouver de meilleurs minima locaux du problème de regroupement de la 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. ^[41]

Discussion

Un exemple typique de convergence des k -means vers un minimum local. Dans cet exemple, le résultat de k -means clustering (la figure de droite) contredit la structure de cluster évidente de l’ensemble de données. Les petits cercles sont les points de données, les étoiles à quatre rayons sont les Centroïdes (moyennes). La configuration initiale est sur la figure de gauche. L’algorithme converge après cinq itérations présentées sur les figures, de gauche à droite. L’illustration a été préparée avec l’applet Mirkes Java. ^[42] k – signifie le résultat de regroupement pour l’ ensemble de données sur les fleurs d’Iris et les espèces réelles visualisées à l’aide d’ ELKI . Les moyennes de cluster sont marquées à l’aide de symboles plus grands et semi-transparents. k -means clustering vs. EM clustering sur un ensemble de données artificiel (“souris”). La tendance des k -means à produire des clusters de taille égale conduit ici à de mauvais résultats, tandis que EM bénéficie des distributions gaussiennes avec différents rayons présents dans l’ensemble de données.

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

La distance euclidienne est utilisée comme métrique et la variance est utilisée comme mesure de la dispersion des grappes.
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 vérifications 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 exemple sur 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. On s’attend à ce que les clusters soient de taille similaire, de sorte que l’affectation au centre de cluster le plus proche soit l’affectation correcte. Lorsque par exemple l’application de k -means avec une valeur de k = 3 {displaystyle k=3} $k=3$ $k=3$ sur l’ ensemble de données de fleurs d’Iris bien connu , le résultat ne parvient souvent pas à séparer les trois espèces d’ Iris contenues dans l’ensemble de données. Avec k = 2 {displaystyle k=2} $k=2$ $k=2$ , les deux amas visibles (l’un contenant deux espèces) seront découverts, alors qu’avec k = 3 {displaystyle k=3} $k=3$ $k=3$ l’un des deux groupes sera divisé en deux parties paires. En réalité, k = 2 {displaystyle k=2} $k=2$ $k=2$ est plus approprié pour cet ensemble de données, malgré le fait que l’ensemble de données contient 3 classes . Comme avec tout autre algorithme de clustering, le résultat k -means suppose que les données satisfont à certains critères. Cela fonctionne bien sur certains ensembles de données et échoue sur d’autres.

Le résultat des k -moyennes peut être vu comme les cellules de Voronoi des moyennes du 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 de maximisation des attentes (sans doute une généralisation des k -moyennes) sont plus flexibles en ayant à la fois des variances et des covariances. Le résultat EM est donc capable d’accueillir des clusters de taille variable bien mieux que k -means ainsi que des clusters corrélés (pas dans cet exemple). En contrepartie, l’EM nécessite l’optimisation d’un plus grand nombre de paramètres libres et pose des problèmes méthodologiques dus à des clusters évanescents ou à des matrices de covariance mal conditionnées. K-means est étroitement lié à la modélisation bayésienne non paramétrique . ^[43]

Applications

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

Quantification vectorielle

Image couleur à deux canaux (à des fins d’illustration — canaux rouge et vert uniquement). Quantification vectorielle des couleurs présentes dans l’image ci-dessus dans les cellules de Voronoi à l’aide de k -means.

k -means provient du traitement du signal et trouve toujours une utilisation dans ce domaine. Par exemple, en infographie , la quantification des couleurs consiste à réduire la palette de couleurs d’une image à un nombre fixe de couleurs k . L’ algorithme k -means peut facilement être utilisé pour cette tâche et produit des résultats compétitifs. Un cas d’utilisation de cette approche est la segmentation d’image . D’autres utilisations de la quantification vectorielle incluent l’échantillonnage non aléatoire , car k -means peut facilement être utilisé pour choisir k objets différents mais prototypiques à partir d’un grand ensemble de données pour une analyse plus approfondie.

L’analyse par grappes

Dans l’analyse de cluster, l’ algorithme k -means peut être utilisé pour partitionner l’ensemble de données d’entrée en k partitions (clusters).

Cependant, l’ algorithme k -means pur n’est pas très flexible et, en tant que tel, son utilisation 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 discuté 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.

Apprentissage des fonctionnalités

Le clustering k -means a été utilisé comme une étape d’apprentissage de caractéristiques (ou d’apprentissage de dictionnaire ), soit dans un apprentissage ( semi- ) supervisé , soit dans un apprentissage non supervisé . ^[44] L’approche de base consiste d’abord à former une représentation de clustering k -means, en utilisant les données de formation 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 entre la donnée et chaque centroïde, ou simplement une fonction d’indicateur pour le centroïde le plus proche, ^{[44] [45]}ou une transformation douce de la distance. ^[46] Alternativement, en transformant la distance échantillon-grappe à travers un RBF gaussien , on obtient la couche cachée d’un réseau de fonction de base radiale . ^[47]

Cette utilisation des k -moyennes a été combinée avec succès avec des classificateurs simples et linéaires pour l’apprentissage semi-supervisé en PNL (spécifiquement pour la reconnaissance d’entités nommées ) ^[48] et en vision par ordinateur . Sur une tâche de reconnaissance d’objets, il s’est avéré qu’il présentait des performances comparables avec des approches d’apprentissage de fonctionnalités plus sophistiquées telles que les auto- encodeurs et les machines Boltzmann restreintes . ^[46] Cependant, il nécessite généralement plus de données, pour des performances équivalentes, car chaque point de données ne contribue qu’à une seule “fonctionnalité”. ^[44]

Relation avec d’autres algorithmes

Modèle de mélange gaussien

“L’algorithme standard” lent pour le clustering k -means, et son Algorithme de maximisation des attentes associé , est un cas particulier d’un Modèle de mélange gaussien, en particulier le cas limite lors de la fixation de toutes les covariances pour qu’elles soient diagonales, égales et aient une petite variance infinitésimale. ^{[49] : 850} Au lieu de petites variances, une affectation de cluster dur peut également être utilisée pour montrer une autre équivalence de k -means clustering à un cas particulier de modélisation de mélange gaussien “dur”. ^{[50] : 354, 11.4.2.5} Cela ne signifie pas qu’il est efficace d’utiliser la modélisation de mélange gaussien pour calculer k-means, mais juste qu’il existe une relation théorique, et que la modélisation du mélange gaussien peut être interprétée comme une généralisation de k -means ; au contraire, il a été suggéré d’utiliser le clustering k-means pour trouver des points de départ pour la modélisation du mélange gaussien sur des données difficiles. ^{[49] : 849}

K-SVD

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 codebook, avec un poids de 1. ^[51]

Analyse des composants principaux

La solution relâchée de k -means clustering, spécifiée par les indicateurs de cluster, est donnée par l’analyse en composantes principales (ACP). ^{[52] [53]} L’intuition est que k-signifie décrire des grappes 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 PCA. 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 PCA. Les clusters bien séparés sont efficacement modélisés par des clusters en forme de boule et donc découverts par k -means. Les grappes non sphériques sont difficiles à séparer lorsqu’elles sont proches. Par exemple, deux amas 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 PCA.k -means ne devrait pas s’attendre à bien faire sur ces données. ^[54] 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. ^[55]

Regroupement des décalages moyens

Les algorithmes de clustering par décalage moyen de base maintiennent 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. Ensuite, cet ensemble est remplacé itérativement par la moyenne des points de l’ensemble qui se trouvent à une distance donnée de ce point. En revanche, k -means limite cet ensemble mis à jour à k points généralement beaucoup moins que le nombre de points dans l’ensemble de données d’entrée, et remplace chaque point de cet ensemble par la moyenne de tous les points de l’ ensemble d’entrée qui sont plus proches de ce point que tout autre (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 subissant le 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. ^[56] L’un des avantages du décalage moyen par rapport aux k -moyennes est que le nombre de clusters n’est pas pré-spécifié, car le décalage moyen est susceptible de ne trouver que quelques clusters s’il n’en existe qu’un petit nombre. Cependant, 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. Le décalage moyen a des variantes douces.

Analyse indépendante des composants

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 en composantes indépendantes linéaires (ICA). Cela aide à expliquer l’application réussie de k -means à l’apprentissage des fonctionnalités . ^[57]

Filtrage bilatéral

k -means suppose implicitement que l’ordre de l’ensemble de données d’entrée n’a pas d’importance. Le filtre bilatéral est similaire aux k -moyennes et au décalage moyen en ce sens qu’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 limite le calcul de la moyenne (pondérée par le noyau) pour n’inclure que les points proches dans l’ordre des données d’entrée. ^[56] Cela le rend applicable à des problèmes tels que le débruitage d’image, où la disposition spatiale des pixels dans une image est d’une importance critique.

Problèmes similaires

L’ensemble des fonctions de cluster minimisant l’erreur au carré comprend également l’ algorithme k – medoids , 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 .

Implémentations logicielles

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). ^[1] 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.

Logiciel libre/Open Source

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 JuliaStats Clustering.
KNIME contient des nœuds pour k -means et k -medoids.
Mahout contient un k -means basé sur MapReduce .
mlpack contient une implémentation C++ de k -means.
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 score de silhouette de cluster.
PSPP contient k -means, La commande QUICK CLUSTER effectue un clustering k -means sur l’ensemble de données.
R contient trois variations de k -moyennes.
SciPy et scikit-learn contiennent plusieurs implémentations k -means.
Spark MLlib implémente un algorithme distribué k -means.
Torch contient un package unsup qui fournit un clustering k -means.
Weka contient k -means et x -means.

Propriétaire

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

Ayasdi
Mathématique
MATLAB
OriginePro
RapidMiner
SAP HANA
SAS
SPSS
État

Voir également

Algorithme BFR
Tessellation centroïdale de Voronoi
Coups de tête/queue
k q-bémols
K-signifie++
Algorithme de Linde – Buzo – Gray
Carte auto-organisée

Références

^ ^un ^b Kriegel, Hans-Peter ; Schubert, Erich; Zimek, Arthur (2016). “L’art (noir) de l’évaluation d’exécution : comparons-nous des algorithmes ou des implémentations ?”. Connaissances et systèmes d’information . 52 (2): 341–378. doi : 10.1007/s10115-016-1004-2 . ISSN 0219-1377 . S2CID 40772241 .
^ MacQueen, JB (1967). Quelques méthodes de classification et d’analyse d’observations multivariées . Actes du 5e Symposium de Berkeley sur les statistiques mathématiques et les probabilités. Vol. 1. Presse de l’Université de Californie. p. 281–297. MR 0214227 . Zbl 0214.46201 . Récupéré le 07/04/2009 .
^ Steinhaus, Hugo (1957). “Sur la division des corps matériels en parties”. Taureau. Acad. Polonais. Sci. (en français). 4 (12): 801–804. MR 0090073 . Zbl 0079.16403 .
^ Lloyd, Stuart P. (1957). “Quantification des moindres carrés en PCM”. Document des laboratoires téléphoniques Bell . Publié dans une revue bien plus tard : Lloyd, Stuart P. (1982). “Quantification des moindres carrés en PCM” (PDF) . Transactions IEEE sur la théorie de l’information . 28 (2): 129–137. CiteSeerX 10.1.1.131.1338 . doi : 10.1109/TIT.1982.1056489 . Récupéré le 15/04/2009 .
^ Forgy, Edward W. (1965). “Analyse de cluster de données multivariées: efficacité versus interprétabilité des classifications”. Biométrie . 21 (3): 768–769. JSTOR 2528559 .
^ Pelleg, Dan; Moore, Andrew (1999). “Accélérer les algorithmes exacts de k -means avec un raisonnement géométrique” . Actes de la cinquième conférence internationale ACM SIGKDD sur la découverte des connaissances et l’exploration de données – KDD ’99 . San Diego, Californie, États-Unis : ACM Press : 277–281. doi : 10.1145/312129.312248 . ISBN 9781581131437. S2CID 13907420 .
^ MacKay, David (2003). “Chapitre 20. Un exemple de tâche d’inférence : clustering” (PDF) . Théorie de l’information, inférence et algorithmes d’apprentissage . La presse de l’Universite de Cambridge. p. 284–292. ISBN 978-0-521-64298-9. MR 2012999 .
^ Étant donné que la racine carrée est une fonction monotone, il s’agit également de l’affectation de distance euclidienne minimale.
^ ^un ^bcde ^Hartigan ^,^JA ; Wong, MA (1979). “Algorithme AS 136: Ak -Means Algorithme de Clustering”. Journal de la Royal Statistical Society, série C . 28 (1): 100–108. JSTOR 2346830 .
^ ^un ^b Hamerly, Greg; Elkan, Charles (2002). “Alternatives à l’ algorithme k -means qui trouvent de meilleurs regroupements” (PDF) . Actes de la onzième conférence internationale sur la gestion de l’information et des connaissances (CIKM) .
^ Celebi, moi; Kingravi, HA; Vela, Pennsylvanie (2013). “Une étude comparative des méthodes d’initialisation efficaces pour l’ algorithme de clustering k -means”. Systèmes experts avec applications . 40 (1): 200–210. arXiv : 1209.1960 . doi : 10.1016/j.eswa.2012.07.021 . S2CID 6954668 .
^ Bradley, Paul S.; Fayyad, Usama M. (1998). “Affinage des points initiaux pour k -Means Clustering”. Actes de la quinzième conférence internationale sur l’apprentissage automatique .
^ Vattani, A. (2011). “k-means nécessite un nombre exponentiel d’itérations même dans le plan” (PDF) . Géométrie discrète et computationnelle . 45 (4): 596–616. doi : 10.1007/s00454-011-9340-1 . S2CID 42683406 .
^ ^{un Arthur} ^b , David; Manthey, B.; En ligneRoeglin, H. (2009). “k-means a une complexité polynomiale lissée”. Actes du 50e Symposium sur les fondements de l’informatique (FOCS) . arXiv : 0904.1113 .
^ Aloise, D.; Deshpande, A.; Hansen, P.; En lignePopat, P. (2009). “NP-dureté du regroupement euclidien de la somme des carrés” . Apprentissage automatique . 75 (2): 245–249. doi : 10.1007/s10994-009-5103-0 .
^ Dasgupta, S.; Freund, Y. (juillet 2009). “Arbres de projection aléatoires pour la quantification vectorielle”. Transactions IEEE sur la théorie de l’information . 55 (7): 3229–3242. arXiv : 0805.1390 . doi : 10.1109/TIT.2009.2021326 . S2CID 666114 .
^ Mahajan, Meena; Nimbhorkar, Prajakta ; Varadarajan, Kasturi (2009). Le problème Planar k -Means est NP-Hard . Notes de cours en informatique. Vol. 5431. pp. 274–285. CiteSeerX 10.1.1.331.1306 . doi : 10.1007/978-3-642-00202-1_24 . ISBN 978-3-642-00201-4.
^ Inaba, M.; Katoh, N.; En ligneImai, H. (1994). Applications des diagrammes de Voronoi pondérés et de la randomisation au k – clustering basé sur la variance . Actes du 10e Symposium ACM sur la géométrie computationnelle . p. 332–339. doi : 10.1145/177424.178042 .
^ Manning, Christopher D.; Raghavan, Prabhakar ; Schütze, Hinrich (2008). Introduction à la recherche d’informations . New York : Cambridge University Press. ISBN 978-0521865715. OCLC 190786122 .
^ ^{un Arthur} ^b , David; Vassilvitskii, Sergei (2006-01-01). Quelle est la lenteur de la méthode k -means ? . Actes du vingt-deuxième symposium annuel sur la géométrie computationnelle . SCG ’06. New York, NY, États-Unis : ACM. p. 144–153. doi : 10.1145/1137856.1137880 . ISBN 978-1595933409. S2CID 3084311 .
^ Bhowmick, Abishek (2009). “Une analyse théorique de l’algorithme de Lloyd pour k -means clustering” (PDF) . Archivé de l’original (PDF) le 2015-12-08. {{cite journal}}: Cite journal requires |journal= (help)Voir aussi ici .
^ ^un ^b Phillips, Steven J. (2002-01-04). “Accélération de K-Means et algorithmes de clustering associés”. Dans Mount, David M.; Stein, Clifford (éd.). Accélération de k -Means et algorithmes de clustering associés . Notes de cours en informatique. Vol. 2409. Springer Berlin Heidelberg. p. 166–177. doi : 10.1007/3-540-45643-0_13 . ISBN 978-3-540-43977-6.
^ ^un ^b Elkan, Charles (2003). “Utilisation de l’inégalité triangulaire pour accélérer k -means” (PDF) . Actes de la vingtième conférence internationale sur l’apprentissage automatique (ICML) .
^ ^un ^b Hamerly, Greg. “Faire k -signifie encore plus vite”. CiteSeerX 10.1.1.187.3017 .
^ ^un ^b Hamerly, Greg; Drake, Jonathan (2015). Accélération de l’algorithme de Lloyd pour le clustering k -means . Algorithmes de clustering partitionnel . p. 41–78. doi : 10.1007/978-3-319-09259-1_2 . ISBN 978-3-319-09258-4.
^ Kanungo, Tapas; Mont, David M. ; Netanyahou, Nathan S. ; Piatko, Christine D. ; Silverman, Ruth; Wu, Angela Y. (2002). “Un algorithme de clustering k -means efficace: analyse et implémentation” (PDF) . Transactions IEEE sur l’analyse de modèles et l’intelligence artificielle . 24 (7): 881–892. doi : 10.1109/TPAMI.2002.1017616 . Récupéré le 24/04/2009 .
^ Drake, Jonathan (2012). ” K -means accéléré avec des limites de distance adaptatives” (PDF) . Le 5e atelier NIPS sur l’optimisation pour l’apprentissage automatique, OPT2012 .
^ Dhillon, EST; Modha, DM (2001). “Décompositions de concepts pour de grandes données textuelles clairsemées utilisant le clustering” . Apprentissage automatique . 42 (1): 143–175. doi : 10.1023/a:1007612920971 .
^ Steinbach, M.; Karypis, G.; En ligneKumar, V. (2000). ” “Une comparaison des techniques de regroupement de documents”. Dans “. Atelier KDD sur l’exploration de texte . 400 (1): 525–526.
^ Pelleg, D.; & Moore, AW (2000, juin). « X-means : extension de k -means avec une estimation efficace du nombre de clusters ». Dans ICML , Vol. 1
^ Hamerly, Greg; Elkan, Charles (2004). “Apprendre le k dans k-means” (PDF) . Progrès dans les systèmes de traitement de l’information neuronale . 16 : 281.
^ Amorim, RC; Mirkin, B. (2012). “Métrique de Minkowski, pondération des caractéristiques et initialisation de cluster anormale dans le clustering k -Means”. Reconnaissance de formes . 45 (3): 1061-1075. doi : 10.1016/j.patcog.2011.08.012 .
^ Amorim, RC; En ligneHennig, C. (2015). “Récupération du nombre de clusters dans des ensembles de données avec des caractéristiques de bruit à l’aide de facteurs de mise à l’échelle des caractéristiques”. Sciences de l’information . 324 : 126–145. arXiv : 1602.06989 . doi : 10.1016/j.ins.2015.06.039 . S2CID 315803 .
^ Sculley, David (2010). ” K – means clustering à l’échelle du Web” . Actes de la 19e conférence internationale sur le World Wide Web . ACM. pp. 1177–1178 . Récupéré le 21/12/2016 .
^ Telgarsky, Matus. “Méthode de Hartigan: k -means Clustering sans Voronoi” (PDF) .
^ Piccialli, Véronique; Sudoso, Antonio M.; Wiegele, Angelika (2022-03-28). “SOS-SDP : un solveur exact pour le clustering de la somme minimale des carrés” . INFORMS Journal on Computing : ijoc.2022.1166. doi : 10.1287/ijoc.2022.1166 . ISSN 1091-9856 .
^ Bagirov, AM; Taheri, S.; En ligneUgon, J. (2016). “Approche de programmation DC non lisse aux problèmes de clustering de somme des carrés minimum”. Reconnaissance de formes . 53 : 12–24. Bibcode : 2016PatRe..53…12B . doi : 10.1016/j.patcog.2015.11.011 .
^ Fränti, Pasi (2018). “Efficacité du clustering d’échange aléatoire” . Journal des mégadonnées . 5 (1): 1–21. doi : 10.1186/s40537-018-0122-y .
^ Hansen, P.; En ligneMladenovic, N. (2001). “J-Means: Une nouvelle heuristique de recherche locale pour la somme minimale des carrés de regroupement”. Reconnaissance de formes . 34 (2): 405–413. Bibcode : 2001PatRe..34..405H . doi : 10.1016/S0031-3203(99)00216-2 .
^ Krishna, K.; Murty, MN (1999). “Algorithme génétique des k-moyennes” . Transactions IEEE sur les systèmes, l’homme et la cybernétique, partie B : Cybernétique . 29 (3): 433–439. doi : 10.1109/3477.764879 . PMID 18252317 .
^ ^un ^b Gribel, Daniel; Vidal, Thibault (2019). “HG-means: Une métaheuristique hybride évolutive pour le regroupement minimum de la somme des carrés”. Reconnaissance de formes . 88 : 569–583. arXiv : 1804.09813 . doi : 10.1016/j.patcog.2018.12.022 . S2CID 13746584 .
^ Mirkes, EM “Applet K-means et k – medoids” . Récupéré le 2 janvier 2016 .
^ Kulis, Brian; Jordan, Michael I. (2012-06-26). Revisiting k -means: new algorithms via Bayesian nonparametrics (PDF) . ICML . pages 1131–1138. ISBN 9781450312851.
^ ^un ^{bcCoates ,} ^Adam ; En ligne, Andrew Y. (2012). “Apprentissage des représentations de caractéristiques avec k -means” (PDF) . À Montavon, G.; Orr, GB ; Müller, K.-R. (éd.). Réseaux de neurones : trucs du métier . Springer.
^ Csurka, Gabriella; Danse, Christopher C. ; Ventilateur, Lixin ; Willamowski, Jutta; Bray, Cédric (2004). Catégorisation visuelle avec sacs de points clés (PDF) . Atelier ECCV sur l’apprentissage statistique en vision par ordinateur.
^ ^un ^b Coates, Adam; Lee, Honglak ; En ligne, Andrew Y. (2011). Une analyse des réseaux à une seule couche dans l’apprentissage non supervisé des fonctionnalités (PDF) . Conférence internationale sur l’intelligence artificielle et les statistiques (AISTATS). Archivé de l’original (PDF) le 10/05/2013.
^ Schwenker, Friedhelm; Kestler, Hans A.; Palmier, Günther (2001). “Trois phases d’apprentissage pour les réseaux à fonction de base radiale”. Réseaux de neurones . 14 (4–5): 439–458. CiteSeerX 10.1.1.109.312 . doi : 10.1016/s0893-6080(01)00027-2 . PMID 11411631 .
^ Lin, Dekang; Wu, Xiaoyun (2009). Regroupement de phrases pour l’apprentissage discriminatif (PDF) . Réunion annuelle de l’ ACL et de l’IJCNLP. pp. 1030–1038.
^ ^{une presse} ^b , WH; Teukolsky, SA; Vetterling, WT ; Flannery, BP (2007). “Section 16.1. Modèles de mélange gaussien et regroupement de k – moyennes” . Recettes numériques: L’art du calcul scientifique (3e éd.). New York (NY) : Cambridge University Press. ISBN 978-0-521-88068-8.
^ Kevin P. Murphy (2012). Apprentissage automatique : une perspective probabiliste . Cambridge, Mass. : MIT Press. ISBN 978-0-262-30524-2. OCLC 810414751 .
^ Aharon, Michal ; Elad, Michael ; Bruckstein, Alfred (2006). “K-SVD: Un algorithme pour la conception de dictionnaires surcomplets pour une représentation clairsemée” (PDF) . Transactions IEEE sur le traitement du signal . 54 (11): 4311. Bibcode : 2006ITSP…54.4311A . doi : 10.1109/TSP.2006.881199 . S2CID 7477309 .
^ Zha, Hongyuan; Ding, Chris ; Gu, Ming ; Lui, Xiaofeng; Simon, Horst D. (décembre 2001). “Relaxation spectrale pour k -means Clustering” (PDF) . Systèmes de traitement de l’information neuronale Vol.14 (NIPS 2001) : 1057–1064.
^ Ding, Chris; Lui, Xiaofeng (juillet 2004). “K-means Clustering via l’analyse en composantes principales” (PDF) . Actes de la conférence internationale sur l’apprentissage automatique (ICML 2004) : 225–232.
^ Drineas, Petros; Frieze, Alan M.; Kannan, Ravi ; Vempala, Santosh ; Vinay, Vishwanathan (2004). “Regroupement de grands graphiques via la décomposition en valeurs singulières” (PDF) . Apprentissage automatique . 56 (1–3): 9–33. doi : 10.1023/b:mach.0000033113.59016.96 . S2CID 5892850 . Récupéré le 02/08/2012 .
^ Cohen, Michael B.; Aîné, Sam ; Musco, Cameron; Musco, Christophe; Persu, Madalina (2014). “Réduction de dimensionnalité pour k -means regroupement et approximation de rang bas (annexe B)”. arXiv : 1410.6801 [ cs.DS ].
^ ^un petit ^{b , Max A.;}En ligneJones, Nick S. (2011). “Méthodes généralisées et solveurs pour les signaux constants par morceaux: partie I” (PDF) . Actes de la Royal Society A . 467 (2135): 3088–3114. Bibcode : 2011RSPSA.467.3088L . doi : 10.1098/rspa.2010.0671 . PMC 3191861 . PMID 22003312 .
^ Vinnikov, Alon; Shalev-Shwartz, Shai (2014). “K-means récupère les filtres ICA lorsque les composants indépendants sont clairsemés” (PDF) . Actes de la conférence internationale sur l’apprentissage automatique (ICML 2014) .