K-means est utile et efficace dans de nombreux contextes de machine learning, mais présente quelques faiblesses distinctes.
Avantages de la méthode k-moyennes
Relativement simple à mettre en œuvre.
Évolut avec les grands ensembles de données.
Elle converge toujours.
Permet de préchauffer les positions des centroïdes.
S'adapte facilement aux nouveaux exemples.
Peut être généralisé aux clusters de différentes formes et tailles, tels que les clusters elliptiques.
Généraliser k-moyennes
Une implémentation simple de k-moyennes peut rencontrer des difficultés avec des clusters de différentes densités et tailles. La partie gauche de la figure 1 montre les clusters que nous devrions voir, tandis que la partie droite montre les clusters proposés par k-means.
Pour améliorer les performances sur des clusters déséquilibrés comme ceux illustrés à la figure 1, vous pouvez généraliser, c'est-à-dire adapter, k-means. La figure 2 montre trois ensembles de données différents regroupés en deux généralisations différentes. Le premier ensemble de données montre k-means sans généralisation, tandis que le deuxième et le troisième permettent aux clusters de varier en largeur.
Ce cours n'explique pas comment généraliser k-means, mais les personnes intéressées peuvent consulter Clustering – k-means Gaussian mixture models (Clustering : modèles de mélange gaussien k-means) de Carlos Guestrin de l'université Carnegie-Mellon.
Inconvénients de la méthode k-moyennes
doit être choisi manuellement.
Les résultats dépendent des valeurs initiales.
Pour les valeurs faibles, vous pouvez atténuer cette dépendance en exécutant k-means plusieurs fois avec différentes valeurs initiales et en sélectionnant le meilleur résultat. À mesure que augmente, vous avez besoin d'un ensemencement k-moyennes pour choisir de meilleurs centroides initiaux. Pour en savoir plus sur l'ensemencement k-moyennes, consultez "A Comparative Study of Efficient Initialization Methods for the K-means Clustering Algorithm" (Étude comparative des méthodes d'initialisation efficaces pour l'algorithme de clustering k-moyennes) par M. Emre Celebi, Hassan A. Kingravi, et Patricio A. Vela.
Difficulté à regrouper des données de différentes tailles et densités sans généralisation.
Difficulté à regrouper les valeurs aberrantes
Les centroïdes peuvent être entraînés par des valeurs aberrantes, ou les valeurs aberrantes peuvent avoir leur propre cluster au lieu d'être ignorées. Envisagez de supprimer ou de couper les valeurs aberrantes avant de créer des groupes.
Difficulté croissante avec le nombre de dimensions.
À mesure que le nombre de dimensions dans les données augmente, une mesure de similarité basée sur la distance converge vers une valeur constante entre les exemples donnés. Réduisez la dimensionnalité en utilisant la PCA sur les données d'éléments géographiques ou le clustering spectral pour modifier l'algorithme de clustering.
Malédiction de la dimensionnalité et clustering spectral
Dans ces trois graphiques, notez que, à mesure que le nombre de dimensions augmente, l'écart type de la distance entre les exemples diminue par rapport à la distance moyenne entre les exemples. Cette convergence signifie que k-means devient moins efficace pour distinguer les exemples à mesure que la dimensionnalité des données augmente. C'est ce qu'on appelle la malédiction de la dimensionnalité.
Vous pouvez éviter cette diminution des performances avec le clustering spectral, qui ajoute des étapes de pré-clustering à l'algorithme. Pour effectuer un clustering spectral:
- Réduire la dimensionnalité des données de fonctionnalités à l'aide de l'ACP
- Projetez tous les points de données dans le sous-espace à dimension inférieure.
- Regroupez les données de ce sous-espace à l'aide de l'algorithme de votre choix.
Pour en savoir plus sur le clustering spectral, consultez A Tutorial on Spectral Clustering (Un tutoriel sur le clustering spectral) d'Ulrike von Luxburg.