Introdução ao K-Means

Essa é uma das técnicas mais populares de aprendizado não-supervisionado

Clusterização de dados é um método de aprendizado não-supervisionado, onde os dados são separados em grupos de dados ou clusters baseados em uma ou mais medidas/características similares.

K-means é um dos exemplos mais comuns dessas técnicas.

Para entendermos melhor, vamos imaginar um exemplo de 1 dimensão, com dados de renda de pessoas. Tentaremos descobrir algum padrão nesses dados.

Exemplo Renda Anual de 10 Pessoas

A imagem ao lado representa a renda anual em Libras de 10 pessoas.

Utilizando técnicas tradicionais de estatística poderíamos deduzir que a média de renda anual está em torno de 30–50 mil libras por ano. Mas somente essa informação não é suficiente para dividirmos as pessoas em grupos. Será que existem grupos de pessoas nessa lista?
Ricos e Classe Média?

O algoritmo K-means é muito bom em encontrar esses padrões, mesmo sem a nossa ajuda de indicar as médias ou ou qualquer informação adicional.

Esse algoritmo segue 5 passos básicos, que iremos detalha-los a seguir.

Primeiro, selecionamos o número de clusters que desejamos encontrar. Esse é o significado do k em k-means. Para o exemplo acima, precisaríamos escolher k igual a dois. O algoritmo então seleciona aleatoriamente k pontos no eixo dos nossos dados. Esses pontos não precisam ser necessariamente pontos existentes nos dados. Eles serão utilizados para calcular os chamados centróides.

Os dois pontos escolhidos aleatoriamente (azul e laranja) serão a referência/centróide.

Calcularemos a distância entre os demais pontos e esses centróides na segunda etapa.

Na segunda etapa, é calculada a distância entre cada ponto e cada centróide. Para o problema de uma dimensão, a distância é a diferença simples entre os valores do eixo x.

Na terceira etapa, os clusters são formados com a atribuição de cada ponto para um centróide, escolhendo o centróide de acordo com a menor distância entre os pontos.

Na quarta etapa, é quando ocorre a atualização dos clusters. A média entre os membros é calculada e esse valor torna-se o novo centróide(azul e laranja mais escuro).

O centróide anterior é então ignorado.

Quinta e última etapa, aqui são executadas novamente as etapas 2 a 4 recursivamente até que as posições dos centróides não sejam alteradas.

Quando os centróides permancerem estáveis, dizemos que o algoritmo convergiu.

Nesse exemplo, descobrimos apenas 2 clusters, mas caso utilizássemos um número maior para K, poderíamos encontrar outros padrões nos dados.

A maioria dos exemplos práticos envolvem o uso de mais de uma dimensão de características ou atributos. Os mesmos princípios explicados aqui seriam utilizados para duas ou mais dimensões. A distância entre os pontos continuaria sendo uma distância euclidiana simples. Podemos utilizar um valor qualquer para K, desde que existam dados suficientes para realizar o treinamento.

K-means converge para o chamado mínimo local, basicamente significa que apesar de conseguir agrupar os dados, podem existir soluções melhores caso o algoritmo seja iniciado novamente com novas posições para os centróides.