Qu’est-ce que le regroupement K-Means ?

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

La réponse courte est que le regroupement K-Means fonctionne en créant un point de référence (un centroïde) pour un nombre désiré de classes, puis en affectant les points de données aux clusters de classes en fonction du point de référence le plus proche. Même si c’est une définition rapide du regroupement K-Means, plongeons plus profondément dans le regroupement K-Means pour mieux comprendre son fonctionnement.

Définition du regroupement

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

Les clusters sont simplement des groupes d’éléments, et le regroupement consiste à mettre les éléments dans ces groupes. Dans le sens de la science des données, les algorithmes de regroupement visent à faire deux choses :

• Assurer que tous les points de données dans un cluster soient aussi similaires les uns aux autres que possible.
• Assurer que tous les points de données dans des clusters différents soient aussi dissemblables les uns aux autres que possible.

Les algorithmes de regroupement regroupent les éléments en fonction d’une mesure de similarité. Cela est souvent fait en trouvant le « centroïde » des différents groupes possibles dans le jeu de données, bien que ce ne soit pas exclusif. Il existe une variété d’algorithmes de regroupement différents, mais l’objectif de tous les algorithmes de regroupement est le même, à savoir déterminer les groupes intrinsèques à un jeu de données.

Regroupement K-Means

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

En général, le regroupement 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/centroïde des partitions de cluster nouvellement créées.
• En fonction de ces centroïdes, affectez chaque point à un cluster spécifique.
• Calculez les distances de chaque point aux centroïdes et affectez les points aux clusters où la distance au centroïde est minimale.
• Une fois les points affectés aux clusters, trouvez le nouveau centroïde des clusters.

Les étapes ci-dessus sont répétées jusqu’à la fin du processus de formation.

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

Alternativement, après que les centroïdes aient été placés, nous pouvons concevoir le regroupement 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 à quel centroïde un point donné est le plus proche, puis les points sont affectés à la classe de ce centroïde. Photo: Weston.pace via Wikimedia Commons, GNU Free Doc License (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 est affecté 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é en utilisant la distance euclidienne au carré, bien que d’autres métriques de distance telles que la distance de Manhattan, la cosinus et la distance de Jaccard puissent être utilisées en fonction du type de données alimentées dans l’algorithme de regroupement.

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 la phase de mise à jour des centroïdes, les centroïdes sont calculés en trouvant la moyenne de la distance entre tous les points de données actuellement contenus dans un cluster.

Comment choisir la bonne valeur pour « K »

Étant donné que le regroupement 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/la bonne valeur pour K ?

Une technique pour sélectionner la bonne valeur de K consiste à utiliser la technique du « coude ». La technique du coude consiste à exécuter un algorithme de regroupement K-Means pour une gamme de valeurs de K différentes et à utiliser une métrique de précision, généralement la somme des erreurs au carré, pour déterminer quelles valeurs de K donnent les meilleurs résultats. La somme des erreurs au carré est déterminée en calculant la moyenne de la distance entre le centroïde d’un cluster et les points de données dans ce cluster.

Le terme « technique du coude » vient du fait que lorsque vous tracez la somme des erreurs au carré en fonction des différentes valeurs de K, le graphique résultant aura souvent une forme de « coude », où la somme des erreurs au carré diminue rapidement pour les premières valeurs de K, mais se stabilise ensuite. Dans de telles conditions, la valeur de K située au niveau du coude est la meilleure valeur pour K, car il y a des rendements rapidement décroissants après cette valeur.

Regroupement K-Means par lots

À mesure que les jeux de données grandissent, le temps de calcul augmente également. Le regroupement K-Means de base peut prendre beaucoup de temps pour se terminer lorsqu’il est exécuté sur des jeux de données massifs, et en conséquence, des modifications ont été apportées au regroupement K-Means pour permettre de réduire les coûts spatiaux et temporels de l’algorithme.

Le regroupement K-Means par lots est une variante du regroupement K-Means où la taille du jeu de données considéré est limitée. Le regroupement K-Means standard opère sur l’ensemble du jeu de données/lot à la fois, tandis que le regroupement K-Means par lots divise le jeu de données en sous-ensembles. Les lots sont échantillonnés aléatoirement à partir de l’ensemble du jeu de données et pour chaque nouvelle itération, un nouveau échantillon aléatoire est sélectionné et utilisé pour mettre à jour la position des centroïdes.

Dans le regroupement K-Means par lots, les clusters sont mis à jour avec une combinaison des valeurs de lots et d’un taux d’apprentissage. Le taux d’apprentissage diminue au fil des itérations, et il 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 changements dans les clusters.

Les résultats des études sur l’efficacité du regroupement K-Means par lots suggèrent qu’il peut réduire avec succès le temps de calcul avec un léger compromis sur la qualité des clusters.

Applications du regroupement K-Means

Le regroupement K-Means peut être utilisé en toute sécurité dans toute situation où les points de données peuvent être segmentés en groupes/classe distincts. Voici quelques exemples d’utilisation courante du regroupement K-Means.

Le regroupement K-Means pourrait être appliqué à la classification de documents, en regroupant les documents en fonction de caractéristiques telles que les sujets, les balises, l’utilisation de mots, les métadonnées et d’autres caractéristiques de documents. Il pourrait également être utilisé pour classer les utilisateurs en 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 mettre les personnes dans des groupes 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, l’historique des patients, etc.

Le regroupement K-Means peut également être utilisé pour des tâches plus ouvertes comme la création de systèmes de recommandation. Les utilisateurs d’un système comme Netflix peuvent être regroupés en fonction de leurs habitudes de visualisation et des contenus similaires leur sont recommandés. Le regroupement K-Means pourrait être utilisé pour la détection d’anomalies, en mettant en évidence les instances potentielles de fraude ou d’éléments défectueux.