Introdução a técnica de clusterização 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.
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 algo assim. Esse algoritmo segue 5 passos básicos:
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.
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.
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.
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. 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.
Encontrar a solução global ótima é um problema de difícil solução.
Precisaremos de técnicas mais robustas e ajustes para isso.
Nos acompanha em @aprendadatascience para mais informações sobre Machine Learning e Data Science.
