Avantages des k-moyennes
L'implémentation est relativement simple.
Adaptation à de grands ensembles de données.
Convergence des garanties.
Peut démarrer les positions des centroïdes à chaud.
S'adapte facilement à de nouveaux exemples.
Généralisation en clusters de différentes formes et tailles, tels que des clusters elliptiques.
Généralisation en k-moyennes
Que se passe-t-il lorsque les clusters sont de densités et de tailles différentes ? Consultez la figure 1. Comparez les clusters intuitifs de gauche et ceux réellement identifiés par les k-moyennes sur la droite. La comparaison montre comment les k-moyennes peuvent tomber sur certains ensembles de données.
Pour mettre en cluster des clusters naturellement déséquilibrés tels que ceux illustrés dans la figure 1, vous pouvez adapter (généraliser) des k-moyennes. Dans la figure 2, les lignes montrent les limites du cluster après la généralisation des k-moyennes comme suit:
- Graphique de gauche: aucune généralisation entraînant une limite non intuitive du cluster.
- Graphique au centre: autorisez différentes largeurs de cluster, ce qui génère des clusters plus intuitifs de différentes tailles.
- Tracé droit: en plus des largeurs de cluster différentes, autorisez différentes largeurs par dimension, ce qui permet d'obtenir des clusters elliptiques plutôt que sphériques, ce qui améliore le résultat.
Bien que ce cours ne traite pas de la généralisation des k-moyennes, n'oubliez pas que la facilité de modification des k-moyennes est une autre des raisons de sa puissance. Pour en savoir plus sur la généralisation des k-moyennes, consultez la page Clustering – K-moyennes des mélanges gaussiens de Carlos Guestrin, de l'université Carnegie-Mellon.
Inconvénients de l'algorithme k-moyennes
Sélection \(k\) manuelle.
Utilisez le graphique "Perte ou clusters" pour déterminer la valeur optimale (k), comme indiqué dans la section Interpréter les résultats.
Dépend des valeurs initiales.
Pour une valeur faible ( \(k\)), vous pouvez atténuer cette dépendance en exécutant plusieurs k-moyennes avec différentes valeurs initiales et en choisissant le meilleur résultat. À mesure que \(k\)augmente, vous avez besoin de versions avancées de k-moyennes afin de recueillir de meilleures valeurs pour les centroïdes initiaux (appelés ensemencements de k-moyennes). Pour une présentation complète de k-moyennes, consultez la page A Comparative Study of Effective Initialization Methods for the K-Means Clustering Clusters (Étude comparative des méthodes d'initialisation efficaces pour l'algorithme de clustering en k-moyennes) de M. Emre Celebi, Hassan A. Kingravi, Patricio A. Vela.
Clustering de données de tailles et de densités différentes.
L'algorithme k-moyennes rencontre des difficultés pour regrouper les données lorsque les clusters sont de tailles et de densités différentes. Pour mettre en cluster ces données, vous devez généraliser les k-moyennes comme décrit dans la section Avantages.
Clusterer les anomalies.
Les centroïdes peuvent être repoussés par des anomalies, ou les anomalies peuvent se voir attribuer leur propre cluster au lieu d'être ignorées. Envisagez de supprimer ou de supprimer les anomalies avant de procéder au clustering.
Scaling avec nombre de dimensions.
À mesure que le nombre de dimensions augmente, une mesure de similarité basée sur la distance converge vers une valeur constante entre des exemples donnés. Réduisez la dimensionnalité soit en utilisant ACP sur les données de caractéristiques, soit en utilisant le "clustering spectral" pour modifier l'algorithme de clustering, comme expliqué ci-dessous.
jure de la dimensionnalité et du clustering spectral ;
Ces graphiques montrent comment le ratio de l'écart type par rapport à la distance entre les exemples diminue à mesure que le nombre de dimensions augmente. Cette convergence signifie que les k-moyennes deviennent moins efficaces pour distinguer les exemples. Cette conséquence négative des données à grande dimension est appelée la malédiction de la dimensionnalité.
Le clustering spectral permet d'éviter la malédiction des dimensions en ajoutant une étape de pré-clustering à votre algorithme:
- Réduire la dimensionnalité des données de caractéristiques à l'aide de l'ACP.
- Projetez 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.
Par conséquent, le clustering spectral n'est pas un algorithme de clustering distinct, mais une étape de pré-clustering que vous pouvez utiliser avec n'importe quel algorithme de clustering. Les détails du clustering spectral sont complexes. Consultez le tutoriel sur le clustering spectral d'Ulrike von Luxburg.