Fonctionnement du clustering des données à l'aide de l'algorithme de k-moyennes (k-means)

L'algorithme des k-moyennes est un algorithme qui entraîne un modèle regroupant les objets similaires. Il procède en associant chaque observation du jeu de données d'entrée à un point de l'espace à n dimensions (où n est le nombre d'attributs de l'observation). Par exemple, votre ensemble de données peut contenir des observations de température et d'humidité dans une région particulière, qui sont mappées aux points (t, h) d'une espace bidimensionnel.

Note

Les algorithmes de clustering ne sont pas supervisés. Dans l'apprentissage non supervisé, les étiquettes qui pourraient être associées à des objets de l'ensemble de données d'entraînement ne sont pas utilisées. Pour de plus amples informations, veuillez consulter Apprentissage non supervisé.

Dans le cadre du clustering en k-moyennes (k-means), chaque cluster possède un centre. Lors de l'entraînement de modèle, l'algorithme des k-moyennes (k-means) utilise la distance entre le point correspondant à chaque observation dans l'ensemble de données et les centres de cluster comme base pour le clustering. Choisissez le nombre de clusters (k) à créer.

Par exemple, supposons que vous souhaitiez créer un modèle pour identifier les chiffres manuscrits et que vous choisissiez l'ensemble de données MNIST pour l'entraînement. L'ensemble de données fournit des milliers d'images de chiffres manuscrits (0 à 9). Dans cet exemple, vous pouvez choisir de créer 10 clusters, un pour chaque chiffre (0, 1,..., 9). Dans le cadre de l'entraînement de modèle, l'algorithme des k-moyennes regroupe les images en entrée en 10 clusters.

Chaque image de l'ensemble de données MNIST est une image de 28 x 28 pixels, avec un total de 784 pixels. Chaque image correspond à un point dans un espace à 784 dimensions, similaire à un point dans un espace 2D (x, y). Pour rechercher le cluster auquel un point appartient, l'algorithme des k-moyennes détecte la distance entre ce point et tous les centres de cluster. Il choisit ensuite le cluster ayant le centre le plus proche comme cluster auquel l'image appartient.

Note

Amazon SageMaker utilise une version personnalisée de l'algorithme où, au lieu de spécifier que l'algorithme crée k clusters, vous pouvez choisir d'améliorer la précision du modèle en spécifiant des centres de cluster supplémentaires (K = k*x). Cependant, l'algorithme réduit finalement le nombre de clusters à k.

Dans SageMaker, vous spécifiez le nombre de clusters lors de la création d'une tâche d'entraînement. Pour de plus amples informations, veuillez consulter CreateTrainingJob. Dans le corps de la demande, vous ajoutez le mappage de chaîne HyperParameters pour indiquer les chaînes k et extra_center_factor.

Voici un résumé de la façon dont l'algorithme des k-moyennes (k-means) fonctionne pour l'entraînement de modèle dans SageMaker :

1. Il détermine les K centres de cluster initiaux.

   Note

   Dans les rubriques suivantes, K clusters fait référence à k * x, où vous spécifiez k et x lors de la création d'une tâche d'entraînement du modèle.

2. Il répète les données d'entraînement en entrée et recalcule les centres de cluster.

3. Il réduit les clusters obtenus au nombre de k (si le spécialiste des données a spécifié la création de k*x clusters dans la demande).

Les sections suivantes expliquent également certains des paramètres qui peuvent être spécifiés par un spécialiste des données pour configurer une tâche d'entraînement de modèle dans le cadre du mappage de chaîne HyperParameters.

Étape 1 : Déterminer les centres de cluster initiaux

Lorsque vous utilisez l'algorithme des k-moyennes (k-means) dans SageMaker, les centres de cluster initiaux sont choisis à partir des observations dans un petit lot échantillonné de façon aléatoire. Choisissez l'une des stratégies suivantes pour déterminer la façon dont ces centres de cluster initiaux sont sélectionnés :

• L'approche aléatoire—Choisissez aléatoirement K observations dans votre jeu de données d'entrée en tant que centres de cluster. Par exemple, vous pouvez choisir un centre de cluster qui pointe vers l'espace à 784 dimensions correspondant à 10 images (quelconques) dans l'ensemble de données d'entraînement MNIST.

• L'approche de type k-moyennes++ (k-means++), qui fonctionne comme suit :

  1. Démarrez avec un cluster et déterminez son centre. Vous sélectionnez de façon aléatoire une observation à partir de votre ensemble de données d'entraînement et vous utilisez le point correspondant à l'observation comme centre de cluster. Par exemple, dans l'ensemble de données MNIST, choisissez de façon aléatoire une image de chiffre manuscrit. Choisissez ensuite le point dans l'espace à 784 dimensions qui correspond à l'image choisie comme centre de cluster. Il s'agit du centre de cluster 1.

  2. Déterminez le centre du cluster 2. Choisissez de façon aléatoire une observation dans les observations restantes de l'ensemble de données d'entraînement. Choisissez-en une qui est différente de celle que vous avez sélectionnée précédemment. Cette observation correspond à un point qui est éloigné du centre de cluster 1. En utilisant l'ensemble de données MNIST comme exemple, vous effectuez les opérations suivantes :

     • Pour chacune des images restantes, recherchez la distance entre le point correspondant et le centre de cluster 1. Mettez au carré la distance et attribuez une probabilité proportionnelle au carré de la distance. Ainsi, une image qui est différente de celle que vous avez sélectionnée précédemment possède une plus forte probabilité d'être sélectionnée comme centre de cluster 2.

     • Choisissez l'une des images de façon aléatoire, en fonction des probabilités attribuées à l'étape précédente. Le point qui correspond à l'image est le centre de cluster 2.

  3. Répétez l'étape 2 pour trouver le centre de cluster 3. Cette fois, trouvez les distances entre les images restantes et le centre de cluster 2.

  4. Répétez l'opération jusqu'à ce que vous ayez les centres de clusters K.

Pour entraîner un modèle dans SageMaker, vous créez une tâche d'entraînement. Dans la demande, vous fournissez les informations de configuration en spécifiant les mappages de chaîne HyperParameters suivants :

• Pour spécifier le nombre de clusters à créer, ajoutez la chaîne k.

• Pour une plus grande précision, ajoutez la chaîne facultative extra_center_factor.

• Pour spécifier la stratégie à utiliser pour déterminer les centres de cluster initiaux, ajoutez la chaîne init_method et définissez sa valeur sur random ou k-means++.

Pour plus d'informations sur l'estimateur k-means de SageMaker, consultez K-means dans la documentation du kit SDK Amazon SageMaker.

Vous disposez maintenant d'un ensemble initial de centres de cluster.

Étape 2 : Répéter le jeu de données d'entraînement et calculer les centres de cluster

Les centres de cluster que vous avez créés à l'étape précédente sont principalement aléatoires, mais l'ensemble de données d'entraînement rentre partiellement en compte. Au cours de cette étape, vous utilisez l'ensemble de données d'entraînement pour déplacer ces centres vers les centres de cluster réels. L'algorithme itère sur l'ensemble des données d'entraînement et recalcule les K centres de cluster.

1. Lisez un mini-lot d'observations (un petit sous-ensemble de tous les enregistrements choisi de façon aléatoire) à partir de l'ensemble de données d'entraînement et effectuez les opérations ci-après.

   Note

   Lors de la création d'une tâche d'entraînement de modèle, vous spécifiez la taille du lot dans la chaîne mini_batch_size dans le mappage de chaîne HyperParameters.

   1. Attribuez toutes les observations du mini-lot à l'un des clusters ayant le centre de cluster le plus proche.

   2. Calculez le nombre d'observations attribuées à chaque cluster. Calculez ensuite la proportion de nouveaux points attribués par cluster.

      Prenons l'exemple des clusters suivants :

      Cluster c1 = 100 points précédemment attribués. Vous avez ajouté 25 points provenant du mini-lot au cours de cette étape.

      Cluster c2 = 150 points précédemment attribués. Vous avez ajouté 40 points provenant du mini-lot au cours de cette étape.

      Cluster c3 = 450 points précédemment attribués. Vous avez ajouté 5 points provenant du mini-lot au cours de cette étape.

      Calculez la proportion de nouveaux points attribués à chacun des clusters comme suit :

      p1 = proportion of points assigned to c1 = 25/(100+25)
      p2 = proportion of points assigned to c2 = 40/(150+40)
      p3 = proportion of points assigned to c3 = 5/(450+5)

   3. Calculez le centre des nouveaux points ajoutés à chaque cluster :

      d1 = center of the new points added to cluster 1
      d2 = center of the new points added to cluster 2
      d3 = center of the new points added to cluster 3

   4. Calculez la moyenne pondérée pour trouver les centres de cluster mis à jour comme suit :

      Center of cluster 1 = ((1 - p1) * center of cluster 1) + (p1 * d1)
      Center of cluster 2 = ((1 - p2) * center of cluster 2) + (p2 * d2)
      Center of cluster 3 = ((1 - p3) * center of cluster 3) + (p3 * d3)

2. Lisez le mini-lot suivant et répétez l'étape 1 pour recalculer les centres de cluster.

3. Pour plus d'informations sur l'algorithme des k-moyennes par mini-lot, consultez Clustering en k-moyennes (k-means) à l'échelle du Web (langue française non garantie).

Étape 3 : Réduire le nombre de clusters de K à k

Si l'algorithme a créé K clusters—(K = k*x) où x est supérieur à 1—, il réduit le nombre de clusters de K à k. (Pour plus d'informations, consultez extra_center_factor dans la discussion précédente.) Il procède en appliquant la méthode de Lloyd avec initialisation par kmeans++ des K centres de cluster. Pour plus d'informations sur la méthode de Lloyd, consultez l'article sur le clustering en k-moyennes.