Le K-means est une méthode de partitionnement automatique et non supervisée de données. Étant donnés des points et un entier k, le problème est de répartir les points en k groupes, souvent appelés clusters, de façon à minimiser l’inertie intra-classes et maximiser l’inertie inter-classes.

Algorithme classique : K-Means
Il existe un algorithme classique très utilisé en pratique et considéré comme efficace bien que ne garantissant ni l’optimalité, ni un temps de calcul polynomial.

Description :

• Choisir k points qui représentent la position moyenne des partitions initiales ;
• Répéter jusqu’à ce qu’il y ait convergence :
  – assigner chaque observation à la partition la plus proche;
  – mettre à jour la moyenne de chaque cluster.

Initialisation:
L’initialisation est un facteur déterminant dans la qualité des résultats (minimum local). De nombreux travaux traitent ce point. Il existe deux méthodes d’initialisation habituelles :

Forgy qui assigne les k points des moyennes initiales à k données d’entrée choisies aléatoirement.
K-moyennes++ est un algorithme d’initialisation des k points qui propose une initialisation améliorant la probabilité d’obtenir la solution optimale (minimum global). L’intuition derrière cette approche consiste à répartir les k points des moyennes initiales. Le point de moyenne initial du premier cluster est choisi aléatoirement parmi les données. Puis chaque point de moyenne initiale est choisi parmi les points restants, avec une probabilité proportionnelle au carré de la distance entre le point et le cluster le plus proche.

Il y a un nombre fini de partitions possibles à k classes9. De plus, chaque étape de l’algorithme fait strictement diminuer la fonction de coût, positive, et fait découvrir une meilleure partition. Cela permet d’affirmer que l’algorithme converge toujours en temps fini, c’est-à-dire termine.
Le partitionnement final n’est pas toujours optimal. De plus le temps de calcul peut-être exponentiel en le nombre de points, même dans le plan10. Dans la pratique, il est possible d’imposer une limite sur le nombre d’itérations ou un critère sur l’amélioration entre itérations.

Ajout d’une contrainte

Personne à contacter en interne :