O que é Agrupamento K-Means?

O agrupamento K-means é um algoritmo de aprendizado não supervisionado, e dentre todos os algoritmos de aprendizado não supervisionado, o agrupamento K-means pode ser o mais amplamente utilizado, graças à sua potência e simplicidade. Como funciona exatamente o agrupamento K-means?

A resposta curta é que o agrupamento K-means funciona criando um ponto de referência (um centroid) para um número desejado de classes, e então atribuindo pontos de dados a clusters de classes com base em qual ponto de referência é o mais próximo. Embora essa seja uma definição rápida para o agrupamento K-means, vamos dedicar algum tempo para mergulhar mais fundo no agrupamento K-means e obter uma melhor intuição de como ele opera.

Definindo Agrupamento

Antes de examinarmos os algoritmos exatos usados para realizar o agrupamento K-means, vamos dedicar um pouco de tempo para definir o agrupamento em geral.

Os clusters são apenas grupos de itens, e o agrupamento é apenas colocar itens nesses grupos. No sentido da ciência de dados, algoritmos de agrupamento visam fazer duas coisas:

• Garantir que todos os pontos de dados em um cluster sejam tão semelhantes entre si quanto possível.
• Garantir que todos os pontos de dados em clusters diferentes sejam tão dissimilares entre si quanto possível.

Algoritmos de agrupamento agrupam itens com base em alguma métrica de semelhança. Isso é frequentemente feito encontrando o “centroide” dos diferentes grupos possíveis no conjunto de dados, embora não exclusivamente. Existem várias algoritmos de agrupamento diferentes, mas o objetivo de todos os algoritmos de agrupamento é o mesmo, determinar os grupos intrínsecos a um conjunto de dados.

Agrupamento K-Means

O agrupamento K-means é um dos tipos mais antigos e comuns de algoritmos de agrupamento, e opera com base na quantização de vetores. Há um ponto no espaço escolhido como origem, e então vetores são desenhados da origem para todos os pontos de dados no conjunto de dados.

Em geral, o agrupamento K-means pode ser dividido em cinco etapas diferentes:

• Coloque todas as instâncias em subconjuntos, onde o número de subconjuntos é igual a K.
• Encontre o ponto médio/centroide das partições de cluster recém-criadas.
• Com base nesses centroides, atribua cada ponto a um cluster específico.
• Calcule as distâncias de cada ponto para os centroides e atribua pontos aos clusters onde a distância do centroide é mínima.
• Depois que os pontos forem atribuídos aos clusters, encontre o novo centroide dos clusters.

As etapas acima são repetidas até que o processo de treinamento seja concluído.

Na fase inicial, os centroides são colocados em algum lugar entre os pontos de dados.
Foto: Weston.pace via wikimedia commons, GNU Free Documentation License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Alternativamente, após os centroides terem sido colocados, podemos conceber o agrupamento K-means como alternando entre duas fases diferentes: rotulando pontos de dados e atualizando centroides.

Na segunda etapa, uma métrica de distância como a distância euclidiana é usada para calcular qual centroide um determinado ponto está mais próximo, e então os pontos são atribuídos à classe desse centroide. Foto: Weston.pace via Wikimedia Commons, GNU Free Doc License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

Na fase de rotulagem dos pontos de dados, cada ponto de dados é atribuído um rótulo que o coloca no cluster pertencente ao centroide mais próximo. O centroide mais próximo é normalmente determinado usando a distância euclidiana ao quadrado, embora outras métricas de distância, como a distância de Manhattan, Cosine e Jaccard, possam ser usadas, dependendo do tipo de dados alimentados no algoritmo de agrupamento.

Na terceira etapa, os centroides são movidos para a média de todos os pontos de dados. As classes são então reatribuídas. Foto: Weston.pace via Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

Na etapa de atualização do centroide, os centroides são calculados encontrando a média da distância entre todos os pontos de dados atualmente contidos em um cluster.

Como Escolher o Valor Certo para “K”

Considerando que o agrupamento K-means é um algoritmo não supervisionado e o número de classes não é conhecido antecipadamente, como você decide sobre o número apropriado de classes/o valor correto para K?

Uma técnica para selecionar o valor correto de K é chamada de “técnica do cotovelo”. A técnica do cotovelo consiste em executar um algoritmo de agrupamento K-means para uma faixa de diferentes valores de K e usar uma métrica de precisão, normalmente a Soma dos Erros Quadrados, para determinar quais valores de K dão os melhores resultados. A Soma dos Erros Quadrados é determinada calculando a média da distância entre o centroide de um cluster e os pontos de dados nesse cluster.

O termo “técnica do cotovelo” vem do fato de que, quando você plotar a SSE em relação aos diferentes valores de K, o gráfico resultante terá frequentemente uma forma de “cotovelo”, onde a SSE diminui rapidamente para os primeiros valores de K, mas então se estabiliza. Nesses casos, o valor de K localizado no cotovelo é o melhor valor para K, pois há retornos rapidamente decrescentes após esse valor.

Agrupamento K-Means em Lotes

À medida que os conjuntos de dados crescem, o tempo de computação também cresce. O agrupamento K-means básico pode levar muito tempo para ser concluído quando executado em conjuntos de dados maciços, e, como resultado, ajustes no agrupamento K-means foram feitos para permitir reduzir os custos espaciais e temporais do algoritmo.

O agrupamento K-means em lotes é uma variante do agrupamento K-means onde o tamanho do conjunto de dados considerado é limitado. O agrupamento K-means normal opera no conjunto de dados inteiro/batch de uma vez, enquanto o agrupamento K-means em lotes divide o conjunto de dados em subconjuntos. Os lotes são amostrados aleatoriamente do conjunto de dados inteiro e, para cada nova iteração, uma nova amostra aleatória é selecionada e utilizada para atualizar a posição dos centroides.

No agrupamento K-means em lotes, os clusters são atualizados com uma combinação dos valores do lote e uma taxa de aprendizado. A taxa de aprendizado diminui ao longo das iterações, e é o inverso do número de pontos de dados colocados em um cluster específico. O efeito de reduzir a taxa de aprendizado é que o impacto de novos dados é reduzido e a convergência é alcançada quando, após várias iterações, não há mudanças nos clusters.

Os resultados de estudos sobre a eficácia do agrupamento K-means em lotes sugerem que ele pode reduzir com sucesso o tempo de computação com um ligeiro compromisso na qualidade do cluster.

Aplicações do Agrupamento K-Means

O agrupamento K-means pode ser usado com segurança em qualquer situação onde os pontos de dados possam ser segmentados em grupos/distintos. Aqui estão alguns exemplos de casos de uso comuns para o agrupamento K-means.

O agrupamento K-means pode ser aplicado à classificação de documentos, agrupando documentos com base em recursos como tópicos, tags, uso de palavras, metadados e outros recursos de documentos. Ele também pode ser usado para classificar usuários como bots ou não bots com base em padrões de atividade, como posts e comentários. O agrupamento K-means também pode ser usado para colocar pessoas em grupos com base em níveis de preocupação ao monitorar sua saúde, com base em recursos como comorbidades, idade, histórico do paciente, etc.

O agrupamento K-means também pode ser usado para tarefas mais abertas, como criar sistemas de recomendação. Os usuários de um sistema como o Netflix podem ser agrupados com base em padrões de visualização e recomendados conteúdos semelhantes. O agrupamento K-means pode ser usado para tarefas de detecção de anomalias, destacando instâncias potenciais de fraude ou itens defeituosos.