« K-moyennes » : différence entre les versions
Contenu supprimé Contenu ajouté
→Initialisation : assigner dans cet usage est un anglicisme. À éviter. |
Modifications (non achevées) d'une partie sur les algorithmes d'approximation. Sera prochainement complétée. |
||
Ligne 143 :
| lire en ligne=https://www.cs.umd.edu/users/mount/Papers/kmlocal-cgta-final.pdf}}</ref>.
== Algorithmes d'approximation ==
Dans le cadre euclidien, il existe des algorithmes (1+ε)-approchés<ref>{{Article |prénom1=J. |nom1=Matoušek |titre=On Approximate Geometric k -Clustering |périodique=Discrete & Computational Geometry |volume=24 |numéro=1 |date=2000-01 |issn=0179-5376 |issn2=1432-0444 |doi=10.1007/s004540010019 |lire en ligne=http://dx.doi.org/10.1007/s004540010019 |consulté le=2019-12-09 |pages=61–84 }}</ref>. Mais le temps de calcul rend ces algorithmes inutilisables en pratique. Dans leur article «A local search approximation algorithm for k-means clustering », Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman et Angela Y. Wu donnent un (9+ε)-approché qui, combiné à la méthode des k-moyennes, donne de meilleurs résultats en pratique que la méthode des k-moyennes seules (meilleur optimisation et temps de calcul plus faible).
Il s'agit d'une méthode par recherche locale.
=== Description du problème ===
Soient '''P''' un ensemble de <math>n</math> points de <math>\R^{d}</math> et <math>k\in \N</math>. On note d la distance euclidienne dans <math>\R^{d}</math>.
But : Trouver un ensemble S de k points de <math>\R^{d}</math>, appelés centres, tels que si on note s(x)
=== Principe de l'algorithme ===
Pour commencer il faut déterminer un ensemble C de centres potentiels contenant au moins un sous-ensemble de k centres solutions.
<br />
== Applications ==
=== Avantages et inconvénients pour l'apprentissage ===
| |||