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 centróide) 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 em grupos. No sentido de 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.

Os algoritmos de agrupamento agrupam itens com base em alguma métrica de similaridade. Isso é frequentemente feito encontrando o “centróide” 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 inerentes a um conjunto de dados.

Agrupamento K-Means

O agrupamento K-means é um dos algoritmos de agrupamento mais antigos e mais comumente usados, e ele 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/centróide das partições de cluster recém-criadas.
• Com base nesses centróides, atribua cada ponto a um cluster específico.
• Calcule as distâncias de cada ponto para os centróides e atribua pontos aos clusters onde a distância do centróide é mínima.
• Depois que os pontos forem atribuídos aos clusters, encontre o novo centróide dos clusters.

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

Na fase inicial, os centróides 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 centróides terem sido colocados, podemos conceber o agrupamento K-means como alternar entre duas fases diferentes: rotulando pontos de dados e atualizando centróides.

Na segunda etapa, uma métrica de distância como a distância euclidiana é usada para calcular qual centróide um ponto dado está mais próximo, e então os pontos são atribuídos à classe desse centróide. Foto: Weston.pace via Wikimedia Commons, GNU 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 a um rótulo que o coloca no cluster pertencente ao centróide mais próximo. O centróide mais próximo é tipicamente determinado usando a distância euclidiana ao quadrado, embora outras métricas de distância, como a distância de Manhattan, Cosseno e Jaccard, possam ser usadas, dependendo do tipo de dados alimentados no algoritmo de agrupamento.

Na terceira etapa, os centróides 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 centróide, os centróides 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 Correto 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, tipicamente 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 centróide 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.

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/bloco por vez, enquanto o agrupamento K-means em lotes divide o conjunto de dados em subconjuntos. Os mini-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 centróides.

No agrupamento K-means em lotes, os clusters são atualizados com uma combinação dos valores do mini-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 uma ligeira perda na qualidade do cluster.

Aplicações do Agrupamento K-Means

O agrupamento K-means pode ser usado com segurança em qualquer situação em que os pontos de dados possam ser segmentados em grupos/classes 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 (NFLX ) podem ser agrupados com base em padrões de visualização e recomendados conteúdos semelhantes. O agrupamento K-means pode ser usado para detecção de anomalias, destacando instâncias potenciais de fraude ou itens defeituosos.