Suivez nous sur
Classe de maître IA :

AI 101

Qu'est-ce que le clustering K-Means ?

mm
Le kit de préparation mis à jour on

Le clustering K-means est un apprentissage non supervisé algorithme, et parmi tous les algorithmes d'apprentissage non supervisés, le clustering K-means pourrait être le plus largement utilisé, grâce à sa puissance et sa simplicité. Comment fonctionne exactement le clustering K-means ?

La réponse courte est que le clustering K-means fonctionne en création d'un point de référence (un centroïde) pour un nombre de classes souhaité, puis attribution de points de données à des clusters de classes en fonction du point de référence le plus proche. Bien qu'il s'agisse d'une définition rapide du clustering K-means, prenons un peu de temps pour approfondir le clustering K-means et avoir une meilleure intuition de son fonctionnement.

Définir le clustering

Avant d'examiner les algorithmes exacts utilisés pour effectuer le clustering K-means, prenons un peu de temps pour définir le clustering en général.

Les clusters ne sont que des groupes d'éléments, et le clustering consiste simplement à placer des éléments dans ces groupes. Au sens de la science des données, algorithmes de clustering viser à faire deux choses :

  • Assurez-vous que tous les points de données d'un cluster sont aussi similaires que possible.
  • Assurez-vous que tous les points de données des différents clusters sont aussi différents que possible les uns des autres.

Les algorithmes de clustering regroupent les éléments en fonction d'une métrique de similarité. Cela se fait souvent en trouvant le "centre de gravité" des différents groupes possibles dans l'ensemble de données, mais pas exclusivement. Il existe une variété d'algorithmes de clustering différents, mais l'objectif de tous les algorithmes de clustering est le même, déterminer les groupes intrinsèques à un ensemble de données.

K-Means Clustering

K-Means Clustering est l'un des types d'algorithmes de clustering les plus anciens et les plus couramment utilisés, et il fonctionne sur la base de quantification vectorielle. Il y a un point dans l'espace choisi comme origine, puis des vecteurs sont dessinés de l'origine à tous les points de données du jeu de données.

En général, le clustering K-means peut être décomposé en cinq étapes différentes :

  • Placez toutes les instances dans des sous-ensembles, où le nombre de sous-ensembles est égal à K.
  • Trouvez le point moyen/centre de gravité des partitions de cluster nouvellement créées.
  • Sur la base de ces centroïdes, attribuez chaque point à un cluster spécifique.
  • Calculez les distances de chaque point aux centres de gravité et attribuez des points aux grappes où la distance du centre de gravité est minimale.
  • Une fois les points attribués aux clusters, recherchez le nouveau centroïde des clusters.

Les étapes ci-dessus sont répétées jusqu'à ce que le processus de formation soit terminé.

Dans la phase initiale, les centroïdes sont placés quelque part parmi les points de données.
Photo : Weston.pace via wikimedia commons, licence de documentation gratuite GNU (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Alternativement, une fois les centroïdes placés, nous pouvons concevoir le clustering K-means comme un va-et-vient entre deux phases différentes : l'étiquetage des points de données et la mise à jour des centroïdes.

Dans la deuxième étape, une métrique de distance telle que la distance euclidienne est utilisée pour calculer de quel centre de gravité un point donné est le plus proche, puis les points sont attribués à la classe de ce centre de gravité. Photo : Weston.pace via Wikimedia Commons, licence GNU Free Doc (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

Dans la phase d'étiquetage des points de données, chaque point de données se voit attribuer une étiquette qui le place dans le cluster appartenant au centroïde le plus proche. Le centroïde le plus proche est généralement déterminé à l'aide de la distance euclidienne au carré, bien que d'autres mesures de distance telles que la distance Manhattan, le cosinus et la distance Jaccard puissent être utilisées en fonction du type de données introduites dans l'algorithme de clustering.

Dans la troisième étape, les centroïdes sont déplacés vers la moyenne de tous les points de données. Les classes sont alors réaffectées. Photo : Weston.pace via Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

Dans l'étape de mise à jour du centroïde, les centroïdes sont calculés en trouvant la distance moyenne entre tous les points de données actuellement contenus dans un cluster.

Comment choisir la bonne valeur pour "K"

Considérant que le clustering K-means est un algorithme non supervisé et que le nombre de classes n'est pas connu à l'avance, comment décidez-vous du nombre approprié de classes/de la bonne valeur pour K ?

Une technique pour sélectionner la bonne valeur K est appelée la «la technique du coude”. La technique du coude consiste à exécuter un algorithme de clustering K-means pour une plage de valeurs K différentes et à utiliser une métrique de précision, généralement la somme de l'erreur quadratique, pour déterminer quelles valeurs de K donnent les meilleurs résultats. La somme de l'erreur quadratique est déterminée en calculant la distance moyenne entre le centroïde d'un cluster et les points de données de ce cluster.

Le terme "technique du coude" vient du fait que lorsque vous tracez le SSE par rapport aux différentes valeurs de K, le tracé linéaire résultant aura souvent une forme de "coude", où le SSE diminue rapidement pour les premières valeurs de K, mais ensuite se stabilise. Dans de telles conditions, la valeur de K située au coude est la meilleure valeur pour K, car il y a des rendements rapidement décroissants après cette valeur.

Clustering K-Means en mini-lots

À mesure que les ensembles de données grandissent, le temps de calcul augmente également. Le clustering K-means de base peut prendre beaucoup de temps lorsqu'il est exécuté sur des ensembles de données massifs, et par conséquent, des ajustements au clustering K-means ont été apportés pour permettre de réduire les coûts spatiaux et temporels de l'algorithme.

Regroupement de mini-lots K-means est une variante du clustering K-means où la taille de l'ensemble de données considéré est plafonnée. Le clustering K-means normal fonctionne sur l'ensemble de données/lot à la fois, tandis que le clustering K-means Mini-batch décompose l'ensemble de données en sous-ensembles. Les mini-lots sont échantillonnés au hasard à partir de l'ensemble de données et pour chaque nouvelle itération, un nouvel échantillon aléatoire est sélectionné et utilisé pour mettre à jour la position des centroïdes.

Dans le clustering Mini-Batch K-Means, les clusters sont mis à jour avec une combinaison des valeurs du mini-lot et un taux d'apprentissage. Le taux d'apprentissage diminue au fil des itérations, et c'est l'inverse du nombre de points de données placés dans un cluster spécifique. L'effet de la réduction du taux d'apprentissage est que l'impact des nouvelles données est réduit et la convergence est atteinte lorsque, après plusieurs itérations, il n'y a pas de changement dans les clusters.

Les résultats des études sur l'efficacité du clustering Mini-batch K-means suggèrent qu'il peut réduire avec succès le temps de calcul avec un léger compromis sur la qualité du cluster.

Applications du clustering K-Means

Le clustering K-means peut être utilisé en toute sécurité dans toutes les situations où les points de données peuvent être segmentés en groupes/classes distincts. Voici quelques exemples de cas d'utilisation courants pour le clustering K-mean.

Le clustering K-means pourrait être appliqué à la classification des documents, en regroupant les documents en fonction de fonctionnalités telles que les sujets, les balises, l'utilisation des mots, les métadonnées et d'autres fonctionnalités du document. Il pourrait également être utilisé pour classer les utilisateurs en tant que robots ou non en fonction de modèles d'activité tels que les publications et les commentaires. Le regroupement K-means peut également être utilisé pour regrouper les personnes en fonction des niveaux de préoccupation lors de la surveillance de leur santé, en fonction de caractéristiques telles que les comorbidités, l'âge, les antécédents du patient, etc.

Le clustering K-means peut également être utilisé pour des tâches plus ouvertes telles que la création de systèmes de recommandation. Les utilisateurs d'un système comme Netflix peuvent être regroupés en fonction des habitudes de visionnage et du contenu similaire recommandé. Le clustering K-means pourrait être utilisé pour les tâches de détection d'anomalies, mettant en évidence les cas potentiels de fraude ou d'articles défectueux.