clustering k-meansIl s’agit d’une méthode de quantification vectorielle qui a été utilisée dans le traitement du signal à ses débuts. Il est actuellement principalement utilisé comme méthode d’analyse de clustering dans le domaine de l’exploration de données.

Le but du clustering k-means est de diviser n points en k clusters de sorte que chaque point appartienne au cluster correspondant à la moyenne la plus proche, et d'utiliser cela comme critère de clustering. Ce type de problème peut être compris comme le problème de division d'un espace de données en cellules de Voronoi, qui est principalement utilisé pour regrouper des points de données bidimensionnels.

Principales étapes

1. Sélectionnez k points comme points de masse initiaux ;

2. Répétez les étapes :

• Affectez chaque point au centroïde le plus proche pour former k clusters ;
• Recalculer le centroïde de chaque cluster ;

3. Jusqu'à ce que le cluster ne change pas ou que le nombre maximal d'itérations soit atteint.

Mesures de distance et fonctions objectives

Considérez la fonction de distance euclidienne et utilisez la somme des erreurs au carré comme fonction objective du clustering.

Avantages et inconvénients

Avantages : L'algorithme k-means est un algorithme classique pour les problèmes de clustering. L'algorithme est simple et rapide, et présente une efficacité d'algorithme relativement élevée pour de grandes quantités de données. Sa grande évolutivité est généralement utilisée comme algorithme de fin optimale locale. L'effet de regroupement est meilleur lorsque les grappes sont denses, rondes et groupées, et que les différences entre les grappes sont évidentes.

Inconvénients : L'utilisateur doit donner à l'avance le nombre k de clusters à générer ; l'algorithme est sensible à la valeur initiale, et différentes valeurs initiales conduiront à des résultats de clustering différents ; il est sensible aux données de bruit et aux données ponctuelles isolées, et une petite quantité de données aura un impact énorme sur la valeur moyenne.

Références

【1】Algorithme des k-moyennes — Wikipédia

【2】http://hometown.group/wp-content/uploads/2018/07/%E8%81%9A%E7%B1%BB.pdf