Funcionamiento de la agrupación en clústeres de k-means

K-means es una algoritmo que realiza la capacitación de un modelo que agrupa objetos similares. El algoritmo k-means lo logra estableciendo la correspondencia de cada observación en el conjunto de datos de entrada con un punto en el espacio dimensional n (donde n es el número de atributos de la observación). Por ejemplo, sus conjuntos de datos pueden contener observaciones de temperatura y humedad en una ubicación determinada, que se mapea a puntos (t, h) en un espacio bidimensional.

nota

Los algoritmos de agrupación en clústeres no se supervisan. En el aprendizaje no supervisado, no se utilizan las etiquetas que pueden asociarse a los objetos en el conjunto de datos de capacitación. Para obtener más información, consulte Aprendizaje no supervisado.

En la agrupación en clústeres de k-means, cada clúster dispone de un centro. Durante la capacitación de modelos, el algoritmo k-means utiliza la distancia del punto que se corresponde con cada observación en el conjunto de datos en los centros del clúster como base de la agrupación en clústeres. Usted elige el número de clústeres (k) a crear.

Por ejemplo, suponga que desea crear un modelo para reconocer dígitos escritos a mano y que elige el conjunto de datos MNIST para la capacitación. El conjunto de datos proporciona miles de imágenes de dígitos escritos a mano (de 0 a 9). En este ejemplo, puede optar por crear 10 clústeres, uno para cada dígito (0, 1, …, 9). Como parte de la capacitación de modelos, el algoritmo k-means agrupa las imágenes de entrada en 10 clústeres.

Cada imagen del conjunto de datos MNIST es una imagen de 28x28 píxeles, con un total de 784 píxeles. Cada imagen se corresponde con un punto en un espacio de 784 dimensiones, similar a un punto en un espacio bidimensional (x,y). Para buscar un clúster al que pertenece un punto, el algoritmo k-means busca la distancia de ese punto a partir de todos los centros del clúster. A continuación, elige el clúster con el centro más próximo como el clúster al que pertenece la imagen.

nota

Amazon SageMaker utiliza una versión personalizada del algoritmo en la que, en lugar de especificar que el algoritmo cree k clústeres, puede optar por mejorar la precisión del modelo especificando centros de clústeres adicionales (K = k*x). Sin embargo, el algoritmo los reduce en última estancia a k clústeres.

En SageMaker, especificas el número de clústeres al crear un trabajo de formación. Para obtener más información, consulte CreateTrainingJob. En el cuerpo de la solicitud, agregue la asignación de la cadena HyperParameters para especificar las cadenas k y extra_center_factor.

El siguiente es un resumen de cómo funciona k-means para el entrenamiento de modelos en SageMaker:

1. Determina los centros iniciales del clúster K.

   nota

   En los siguientes temas, los clústeres K hacen referencia a k * x, donde especifica k y x cuando se crea un trabajo de capacitación de modelo.

2. Realiza la iteración a través de datos de capacitación de entrada y recalcula los centros de clúster.

3. Reduce los clústeres resultantes a k (si el analista de datos especificó la creación de clústeres k*x en la solicitud).

Las siguientes secciones también explican algunos de los parámetros que un analista de datos puede especificar para configurar un trabajo de capacitación de modelos como parte de la asignación de cadenas HyperParameters.

Paso 1: Determinar los centros iniciales del clúster

Cuando se utilizan las medias k en SageMaker, los centros iniciales de los conglomerados se eligen a partir de las observaciones en un lote pequeño muestreado aleatoriamente. Elija una de las siguientes estrategias para determinar cómo se seleccionan estos centros iniciales del clúster:

• El método aleatorio: elija de forma aleatoria K observaciones en su conjunto de datos de entrada como centros de clústeres. Por ejemplo, puede optar por elegir un centro del clúster que señale a un espacio de 784 dimensiones que se corresponda con cualquiera de las 10 imágenes en el conjunto de datos de capacitación de MNIST.

• El enfoque k-means++, que funciona de la siguiente forma:

  1. Comience por un clúster y determine su centro. Puede seleccionar aleatoriamente una observación desde el conjunto de datos de capacitación y utilizar el punto correspondiente a la observación como el centro del clúster. Por ejemplo, en el conjunto de datos MNIST, elija de forma aleatoria una imagen de dígito escrita a mano. A continuación, elija el punto en el espacio de 784 dimensiones que se corresponde con la imagen como centro del clúster. Este es el centro del clúster 1.

  2. Determine el centro del clúster 2. En las observaciones restantes del conjunto de datos de capacitación, seleccione una observación al azar. Elija una que sea distinta de la seleccionada anteriormente. Esta observación se corresponde con un punto que está alejado del centro del clúster 1. Utilice el conjunto de datos MNIST como ejemplo para realizar el siguiente procedimiento:

     • Para cada imagen restante, busque la distancia del punto correspondiente del centro del clúster 1. Cuadre la distancia y asigne una probabilidad que sea proporcionar al cuadrado de la distancia. De esa forma, una imagen distinta de la que seleccionó anteriormente tiene una mayor probabilidad de que se seleccione como un centro del clúster 2.

     • Elija una de las imágenes de forma aleatoria según las probabilidades asignadas en el paso anterior. El punto que se corresponde con la imagen es el centro del clúster 2.

  3. Repita el paso 2 para buscar el centro del clúster 3. En esta ocasión, busque las distancias de las imágenes restantes desde el centro del clúster 2.

  4. Repita el proceso hasta que tenga los centros del clúster K.

Para adiestrar un modelo SageMaker, debe crear un trabajo de entrenamiento. En la solicitud, proporcione información de configuración especificando los siguientes mapas de cadena HyperParameters:

• Para especificar el número de clústeres que crear, agregue la cadena k.

• Para obtener una mayor precisión, agregue la cadena extra_center_factor opcional.

• Para especificar la estrategia que desee usar para determinar los centros iniciales del clúster, agregue la cadena init_method y establezca su valor en random o k-means++.

Para obtener más información sobre el estimador SageMaker k-means, consulte K-means en la documentación del SDK de Amazon Python SageMaker .

Ahora dispone de un conjunto inicial de los centros del clúster.

Paso 2: Iterar a través de conjuntos de datos de capacitación y calcular los centros del clúster

Los centros del clúster que creó en el paso anterior son principalmente aleatorios, con algunas consideraciones para el conjunto de datos de capacitación. En este paso, utilice el conjunto de datos de capacitación para mover estos centros hacia los verdaderos centros del clúster. El algoritmo realiza la iteración a través del conjunto de datos de capacitación y recalcula los centros del clúster K.

1. Lea un minilote de observaciones (una subred pequeña y elegida aleatoriamente de todos los registros) desde el conjunto de datos de capacitación y realice el siguiente procedimiento.

   nota

   Al crear un trabajo de capacitación de modelos, especifique el tamaño del lote en la cadena mini_batch_size en el mapa de asignación HyperParameters.

   1. Asigne todas las observaciones en el minilote para uno de los clústeres con el centro del clúster más cercano.

   2. Calcule el número de observaciones asignado a cada clúster. A continuación, calcule la proporción de los nuevos puntos asignados por clúster.

      Por ejemplo, tenga en cuenta los siguientes clústeres:

      Clúster c1 = 100 puntos asignados previamente. Ha agregado 25 puntos desde el minilote en este paso.

      Clúster c2 = 150 puntos asignados previamente. Ha agregado 40 puntos desde el minilote en este paso.

      Clúster c3 = 450 puntos asignados previamente. Ha agregado 5 puntos desde el minilote en este paso.

      Calcule la proporción de nuevos puntos asignados a cada uno de los clústeres de la siguiente manera:

      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. Calcule el centro de los nuevos puntos agregados a cada clúster:

      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. Calcule la media ponderada para buscar los centros del clúster actualizados de la siguiente forma:

      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. Lea el próximo minilote y repita el paso 1 para volver a calcular los centros del clúster.

3. Para obtener más información sobre K-Means de minilotes, consulte Web-scale k-means Clustering.

Paso 3: Reducir los clústeres de K a k

Si el algoritmo creó K clústeres —(K = k*x), donde x es mayor que 1—, reduce los K clústeres a k clústeres. (Para obtener más información, consulte extra_center_factor en el tema anterior). Realiza este procedimiento mediante la aplicación del método de Lloyd con la inicialización de kmeans++ en los centros del clúster K. Para obtener más información sobre el método de Lloyd, consulte clustering de k-means.