Comme mentionné précédemment, de nombreux algorithmes de clustering ne s'adaptent pas aux ensembles de données utilisées en machine learning, qui comportent souvent des millions d'exemples. Par exemple, les algorithmes de clustering hiérarchique agglomératif ou divisif examinent toutes les paires de points et présentent des complexités associées aux valeurs suivantes : \(O(n^2 log(n))\) et \(O(n^2)\), respectivement.
Ce cours se concentre sur les k-moyennes, car il s'adapte en \(O(nk)\), où \(k\) correspond au nombre de clusters choisis par l'utilisateur. Cet algorithme regroupe les points dans \(k\) clusters en minimisant la distance entre chaque point et ses du centroïde du cluster (voir la figure 1).
Par conséquent, k-moyennes traite efficacement les données comme étant composées d'un certain nombre circulaires et tente de trouver des clusters correspondant distributions. Mais les données réelles contiennent des anomalies et des clusters basés sur la densité et peuvent ne pas correspondre aux hypothèses sous-jacentes aux k-moyennes.
Algorithme de clustering en k-moyennes
L'algorithme procède comme suit:
Fournissez une estimation initiale pour \(k\), qui peut être modifiée ultérieurement. Pour cette exemple, nous choisissons \(k = 3\).
Choisir au hasard \(k\) centroïdes.
Figure 1: k-moyennes au moment de l'initialisation Attribuez chaque point au centroïde le plus proche pour obtenir \(k\) les clusters initiaux.
Figure 2: Clusters initiaux Pour chaque cluster, calculez un nouveau centroïde en prenant la position moyenne de tous les points du cluster. Les flèches de la figure 4 montrent la variation les positions centroïdes.
Figure 3: centroïdes recalculés Réattribuez chaque point au nouveau centroïde le plus proche.
Figure 4: Clusters après réattribution Répétez les étapes 4 et 5, en recalculant les centroïdes et l'appartenance au cluster, jusqu'à les points d'accès ne changent plus de groupe. Dans le cas d'ensembles de données volumineux, l'algorithme avant la convergence en fonction d'autres critères.
Les positions des centroïdes étant initialement choisies au hasard, les k-moyennes peuvent des résultats très différents lors d'exécutions successives. Pour résoudre ce problème, problème, exécuter k-moyennes plusieurs fois et choisir le résultat offrant la meilleure qualité metrics. (Nous décrirons les métriques de qualité plus loin dans ce cours.) Vous aurez besoin d'un version avancée des k-moyennes pour choisir de meilleures positions initiales des centroïdes.
Bien qu'une compréhension approfondie des mathématiques ne soit pas nécessaire, pour ceux qui sont curieusement, k-moyennes est un cas particulier algorithme de maximisation des attentes. Voir notes de lecture à ce sujet d’UPenn.