Qu'est-ce que le clustering en k-moyennes ?

Comme indiqué précédemment, de nombreux algorithmes de clustering ne sont pas adaptés aux ensembles de données utilisés dans le machine learning, qui comptent souvent des millions d'exemples. Par exemple, les algorithmes de clustering hiérarchiques agrégatifs ou divisifs examinent toutes les paires de points et ont une complexité de $O(n^2 log(n))$ et $O(n^2)$, respectivement.

Ce cours se concentre sur k-means, car il évolue comme $O(nk)$, où $k$est le nombre de clusters choisis par l'utilisateur. Cet algorithme regroupe les points en$k$ clusters en minimisant les distances entre chaque point et le centroïde de son cluster (voir figure 1).

Par conséquent, k-means traite les données comme composées d'un certain nombre de distributions approximativement circulaires et tente de trouver des clusters correspondant à ces distributions. Toutefois, les données réelles contiennent des valeurs aberrantes et des groupes basés sur la densité, et peuvent ne pas correspondre aux hypothèses sous-jacentes à k-means.

Algorithme de clustering en k-moyennes

L'algorithme suit les étapes suivantes:

1. Fournissez une estimation initiale pour $k$, qui pourra être révisée ultérieurement. Pour cet exemple, nous choisissons $k = 3$.

2. Choisissez de manière aléatoire $k$  centroïdes.

   

   Figure 1: k-moyennes à l'initialisation.

3. Attribuez chaque point au centroïde le plus proche pour obtenir les $k$ clusters initiaux.

   

   Figure 2: Clusters initiaux

4. Pour chaque cluster, calculez un nouveau centroid en prenant la position moyenne de tous les points du cluster. Les flèches de la figure 4 montrent l'évolution des positions des centres de gravité.

   

   Figure 3: Centroïdes recalculés.

5. Réattribuez chaque point au nouveau centroïde le plus proche.

   

   Figure 4: Regroupements après réaffectation.

6. Répétez les étapes 4 et 5, en recalculant les centroids et l'appartenance aux clusters, jusqu'à ce que les points ne changent plus de cluster. Dans le cas d'ensembles de données volumineux, vous pouvez arrêter l'algorithme avant la convergence en fonction d'autres critères.

Étant donné que les positions des centres de gravité sont initialement choisies de manière aléatoire, k-means peut renvoyer des résultats très différents lors d'exécutions successives. Pour résoudre ce problème, exécutez k-means plusieurs fois et choisissez le résultat avec les meilleures métriques de qualité. (Nous décrirons les métriques de qualité plus loin dans ce cours.) Vous aurez besoin d'une version avancée de k-means pour choisir de meilleures positions initiales des centroids.

Bien qu'une compréhension approfondie des mathématiques ne soit pas nécessaire, pour les curieux, k-means est un cas particulier de l'algorithme d'espérance-maximisation. Consultez les notes de cours sur le sujet de l'université de Pennsylvanie.