Como funciona o clustering do k-means

O k-means é um algoritmo que treina um modelo para agrupar objetos semelhantes. Para isso, ele mapeia cada observação no conjunto de dados de entrada para um ponto no espaço de n dimensões (em que n é o número de atributos da observação). Por exemplo, o conjunto de dados pode conter observações de temperatura e umidade de um determinado local, que são mapeados para os pontos t, u em um espaço de 2 dimensões (bidimensional).

nota

Algoritmos de clustering não são supervisionados. Na aprendizagem não supervisionada, os rótulos que podem ser associados aos objetos do conjunto de dados de treinamento não são usados. Para ter mais informações, consulte Aprendizado não supervisionado.

No clustering de k-means, cada cluster tem um centro. Durante o treinamento de modelo, o algoritmo k-means usa a distância do ponto correspondente a cada observação no conjunto de dados até os centros dos clusters como base para o agrupamento. Você escolhe o número de clusters (k) a ser criado.

Por exemplo, digamos que você queira criar um modelo para reconhecer dígitos manuscritos e escolhe o conjunto de dados do MNIST para treinamento. O conjunto de dados fornece milhares de imagens de dígitos manuscritos (de 0 a 9). Neste exemplo, você pode optar por criar 10 clusters, um para cada dígito (0, 1,..., 9). Como parte do treinamento de modelo, o algoritmo k-means agrupa as imagens de entrada em 10 clusters.

O tamanho em pixels de cada imagem no conjunto de dados do MNIST é 28 x 28, totalizando 784 pixels. Cada imagem corresponde a um ponto em um espaço de 784 dimensões, semelhante a um ponto em um espaço de 2 dimensões 2 (x, y). Para localizar um cluster ao qual um ponto pertence, o algoritmo k-means localiza a distância desse ponto a partir de todos os centros dos clusters. Em seguida, ele escolhe o cluster com o centro mais próximo como aquele ao qual a imagem pertence.

nota

A Amazon SageMaker usa uma versão personalizada do algoritmo em que, em vez de especificar que o algoritmo cria k clusters, você pode optar por melhorar a precisão do modelo especificando centros de cluster extras (K = k*x). No entanto, o algoritmo, em última análise, reduz tais centros para clusters k.

Em SageMaker, você especifica o número de clusters ao criar um trabalho de treinamento. Para ter mais informações, consulte CreateTrainingJob. No corpo da solicitação, adicione o mapa de strings HyperParameters para especificar as strings k e extra_center_factor.

A seguir está um resumo de como o k-means funciona para o treinamento de modelos em SageMaker:

1. Ele determina os centros de clusters K iniciais.

   nota

   Nos tópicos a seguir, os clusters K referem-se a k* x, em que você especifica k e x ao criar um trabalho de treinamento de modelo.

2. Ele faz a iteração dos dados de treinamento de entrada e recalcula os centros de clusters.

3. Ele reduz os clusters resultantes para k (se o cientista de dados tiver especificado a criação de clusters k* x na solicitação).

As seguintes seções também explicam alguns dos parâmetros que um cientista de dados pode especificar para configurar um trabalho de treinamento de modelo como parte do mapa de strings HyperParameters.

Etapa 1: Determinação dos centros de clusters iniciais

Ao usar k-means in SageMaker, os centros de agrupamento iniciais são escolhidos a partir das observações em um pequeno lote amostrado aleatoriamente. Escolha uma das seguintes estratégias para determinar como esses centros de clusters iniciais serão selecionados:

• A abordagem aleatória—Escolha aleatoriamente K observações em seu conjunto de dados de entrada como centros de clusters. Por exemplo, você pode escolher um centro de cluster que aponte para o espaço de 784 dimensões que, por sua vez, corresponde a quaisquer 10 imagens do conjunto de dados de treinamento do MNIST.

• A abordagem k-means++, que funciona da seguinte forma:

  1. Comece com um cluster e determine seu centro. Selecione aleatoriamente uma observação do seu conjunto de dados de treinamento e use o ponto correspondente à observação como centro do cluster. Por exemplo, no conjunto de dados do MNIST, escolha aleatoriamente uma imagem de dígito manuscrito. Em seguida, escolha o ponto no espaço de 784 dimensões que corresponde à imagem como centro do cluster. Esse é o centro do cluster 1.

  2. Determine o centro do cluster 2. Dentre as demais observações do conjunto de dados de treinamento, escolha uma aleatoriamente. Escolha uma que seja diferente da selecionada anteriormente. Essa observação corresponde a um ponto que está distante do centro do cluster 1. Usando o conjunto de dados do MNIST como exemplo, faça o seguinte:

     • Para cada uma das imagens restantes, encontre a distância do ponto correspondente a partir do centro do cluster 1. Eleve a distância ao quadrado e atribua uma probabilidade que seja proporcional a esse resultado. Dessa forma, uma imagem diferente da que você selecionou anteriormente terá mais probabilidade de ser selecionada como centro do cluster 2.

     • Escolha uma das imagens aleatoriamente, com base nas probabilidades atribuídas na etapa anterior. O ponto que corresponde à imagem é o centro do cluster 2.

  3. Repita a etapa 2 para encontrar o centro do cluster 3. Dessa vez, encontre as distâncias das imagens restantes a partir do centro do cluster 2.

  4. Repita o processo até que você tenha os centros de clusters K.

Para treinar um modelo SageMaker, você cria um trabalho de treinamento. Na solicitação, forneça as informações de configuração especificando os seguintes mapas de strings HyperParameters:

• Para especificar o número de clusters a ser criado, adicione a string k.

• Para mais precisão, adicione a string opcional extra_center_factor.

• Para especificar a estratégia a ser usada para determinar os centros de clusters iniciais, adicione a string init_method e defina seu valor como random ou k-means++.

Para obter mais informações sobre o estimador SageMaker k-means, consulte K-means na documentação do SDK do Amazon Python SageMaker .

Agora, você tem um conjunto inicial de centros de clusters.

Etapa 2: Iteração do conjunto de dados de treinamento e cálculo dos centros de clusters

Os centros de clusters que você criou na etapa anterior são, em sua maioria, aleatórios, com algumas considerações para o conjunto de dados de treinamento. Nesta etapa, use o conjunto de dados de treinamento para mover esses centros para os centros de clusters reais. O algoritmo itera o conjunto de dados de treinamento e recalcula os centros de clusters K.

1. Leia um minilote de observações (um pequeno subconjunto de todos os registros, escolhido aleatoriamente) a partir do conjunto de dados de treinamento e faça o seguinte.

   nota

   Ao criar um trabalho de treinamento de modelo, especifique o tamanho do lote na string mini_batch_size do mapa de strings HyperParameters.

   1. Atribua todas as observações do minilote a um dos clusters que tiver o centro mais próximo.

   2. Calcule o número de observações atribuído a cada cluster. Em seguida, calcule a proporção dos novos pontos atribuídos por cluster.

      Por exemplo, considere os seguintes clusters:

      Cluster c1 = 100 pontos atribuídos anteriormente. You adicionou 25 pontos do minilote nesta etapa.

      Cluster c2 = 150 pontos atribuídos anteriormente. You adicionou 40 pontos do minilote nesta etapa.

      Cluster c3 = 450 pontos atribuídos anteriormente. You adicionou 5 pontos do minilote nesta etapa.

      Calcule a proporção dos novos pontos atribuídos a cada um dos clusters da seguinte forma:

      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. Compute o centro dos novos pontos adicionados a cada 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. Compute a média ponderada para encontrar os centros de clusters atualizados da seguinte 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. Leia o próximo minilote e repita a etapa 1 para recalcular os centros de clusters.

3. Para obter mais informações sobre o k-means de minilotes, consulte Clustering de k-means na escala da web.

Etapa 3: Redução dos clusters de K para k

Se o algoritmo tiver criado clusters K—(K = k*x), em que x é maior que 1—então ele reduzirá os clusters K para clusters k. (Para obter mais informações, consulte extra_center_factor na discussão anterior.) Para fazer isso, ele aplica o método de Lloyd com inicialização kmeans++ aos centros de clusters K. Para obter mais informações sobre o método de Lloyd, consulte o artigo sobre clustering de k-means.