L'algorithme k-moyennes est utile et efficace dans de nombreux contextes de machine learning, quelques points faibles distincts.
Avantages des k-moyennes
L'implémentation est relativement simple.
Évolutivité à l'échelle de grands ensembles de données :
La convergence est systématique.
Permet de démarrer à chaud la position des centroïdes.
S'adapte de manière fluide aux nouveaux exemples.
Peut être généralisée à des clusters de différentes des formes et des tailles, par exemple des groupes elliptiques.
Généraliser des k-moyennes
Une implémentation simple de k-moyennes peut avoir des difficultés avec les groupes de différentes densités et tailles. La partie gauche de la figure 1 montre les clusters que nous nous attendons à voir, tandis que le côté droit montre les clusters proposés par k-moyennes.
Pour optimiser les performances sur les clusters déséquilibrés comme ceux illustrés dans la figure 1, vous pouvez généraliser, c'est-à-dire adapter, les k-moyennes. La figure 2 illustre trois des ensembles de données regroupés avec deux généralisations différentes. Le premier jeu de données montre k-moyennes sans généralisation, tandis que les deuxième et troisième permettent aux clusters en largeur variable.
Ce cours n'aborde pas la généralisation des k-moyennes, mais les personnes intéressées vous devriez voir la section Clustering – Mélange gaussien en k-moyennes modèles de ML par Carlos Guestrin de l'Université Carnegie Mellon.
Inconvénients de l'algorithme k-moyennes
Vous devez choisir\(k\) manuellement.
Les résultats dépendent des valeurs initiales.
Pour une \(k\)faible, vous pouvez atténuer cette dépendance en exécutant plusieurs avec des valeurs initiales différentes et choisir le meilleur résultat. En tant que \(k\) augmente, vous avez besoin d'une semence de k-moyennes pour choisir une meilleure centroïdes Pour une discussion complète sur l'ensemencement des k-moyennes, voir "Une étude comparative Étude des méthodes d'initialisation efficaces pour le clustering en k-moyennes Algorithme, par M. Emre Celebi, Hassan A. Kingravi et Patricio A. Vela.
Difficultés pour regrouper des données de tailles et sans généralisation.
Difficulté à regrouper les valeurs aberrantes.
Les centroïdes peuvent être déplacés par des valeurs aberrantes, ou les valeurs aberrantes peuvent avoir leur propre groupe au lieu d'être ignorés. Envisagez de supprimer ou de rogner les valeurs aberrantes avant le clustering.
Difficultés pour effectuer le scaling en fonction du nombre de dimensions.
À mesure que le nombre de dimensions dans les données augmente, une similarité basée sur la distance converge vers une valeur constante entre des exemples donnés. Réduire de la dimensionnalité, soit en utilisant PCA sur les données de caractéristiques ou en utilisant le clustering spectral pour le modifier algorithme.
La malédiction de la dimensionnalité et du clustering spectral
Dans ces trois graphiques, notez comment, à mesure que les dimensions augmentent, l'écart type la distance entre les exemples diminue par rapport à la distance moyenne entre exemples. Ce la convergence signifie que l'algorithme k-moyennes est moins efficace pour faire la distinction à mesure que la dimensionnalité des données augmente. C'est ce que l'on appelle la malédiction de la dimensionnalité.
Vous pouvez éviter cette baisse des performances grâce au clustering spectral, ce qui ajoute des étapes de préclustering à l'algorithme. Pour exécuter des requêtes clustering:
- Réduisez la dimensionnalité des données de caractéristiques à l'aide de l'APC.
- Projeter tous les points de données dans le sous-espace de dimension inférieure.
- Regroupez les données de ce sous-espace à l'aide de l'algorithme de votre choix.
Voir le tutoriel sur l'API Spectral Clustering, par Ulrike von Luxbourg, pour en savoir plus sur le spectral le clustering.