Clusterização em machine learning: 5 algoritmos essenciais de clusterização

Clusterização não é um algoritmo específico, e sim uma tarefa geral a ser resolvida. Você pode alcançá-la com diferentes algoritmos, que variam bastante na definição do que é um cluster e em como encontrá-los com eficiência. 

Construindo a intuição por trás da clusterização

Antes de entrar nos detalhes dos algoritmos, vamos criar uma intuição usando um exemplo simples com frutas. Suponha que temos um grande conjunto de imagens contendo três frutas: (i) morangos, (ii) peras e (iii) maçãs. 

No dataset, todas as imagens estão misturadas, e seu objetivo é agrupar frutas semelhantes, ou seja, criar três grupos, cada um contendo um tipo de fruta. É exatamente isso que um algoritmo de clusterização faz. 

Critérios de sucesso para uma boa análise de clusterização

Diferente de casos de uso supervisionados, como classificação ou regressão, a clusterização não pode ser totalmente automatizada de ponta a ponta. Em vez disso, é um processo iterativo de descoberta, que exige conhecimento de domínio e julgamento humano para ajustar dados e parâmetros do modelo até chegar ao resultado desejado. 

Mais importante: por ser aprendizado não supervisionado e não usar dados rotulados, não podemos calcular métricas como acurácia, AUC, RMSE etc. para comparar algoritmos ou técnicas de pré-processamento. Isso torna a avaliação de desempenho de modelos de clusterização mais desafiadora e subjetiva. 

Os critérios de sucesso em modelos de clusterização giram em torno de:

• É interpretável?
• O resultado é útil para o negócio?
• Você aprendeu algo novo ou descobriu padrões que não conhecia antes da clusterização?

Medição da qualidade dos clusters

Sem dados rotulados, você não calcula acurácia ou AUC. Duas métricas ajudam a quantificar o quão bem seus clusters estão separados. As mais comuns:

• O Silhouette Score mede o quão semelhante um ponto é ao seu próprio cluster em comparação com o cluster vizinho mais próximo. Varia de -1 a 1; valores acima de 0,5 sugerem clusters bem separados.
• O Davies-Bouldin Index mede a similaridade média entre cada cluster e seu cluster mais semelhante — quanto menor, melhor.

Ambas estão disponíveis no scikit-learn: sklearn.metrics.silhouette_score(X, labels) e sklearn.metrics.davies_bouldin_score(X, labels).

1. K-Means

O K-Means é o algoritmo mais utilizado em tarefas de clusterização, em grande parte porque seus passos são fáceis de entender e a implementação no scikit-learn é direta. Ele é baseado em centróides e requer que você defina o número de clusters que deseja criar. 

Esse número normalmente vem do caso de uso ou de testes com diferentes valores e avaliação do resultado. 

O K-Means é um algoritmo iterativo que cria clusters não sobrepostos, ou seja, cada instância no seu dataset pertence a apenas um cluster. A forma mais simples de construir a intuição do K-Means é acompanhar seus passos junto com o diagrama abaixo. Você também encontra uma descrição detalhada em nossos tutoriais K-Means Clustering in Python e K-Means Clustering in R. 

1. Você especifica o número de clusters.
2. Inicializa centróides aleatoriamente com base nesse número. No diagrama, na Iteration 1, três centróides são inicializados aleatoriamente nas cores azul, vermelho e verde.
3. Calcula a distância entre cada ponto e cada centróide e atribui cada ponto ao centróide mais próximo.
4. Recalcula a média (centro) com base nos pontos atribuídos, mudando a posição do centróide, como nas Iterations 2–9, até convergir.
5. As iterações continuam até não haver mudança no centróide ou até atingir o parâmetro max_iter (número máximo de iterações). No scikit-learn, o padrão de max_iter é 300.

Fonte da imagem: Learnbymarketing.com

2. MeanShift

Diferente do K-Means, o MeanShift não exige especificar o número de clusters. O próprio algoritmo determina quantos clusters existem, o que é uma vantagem quando você não sabe esse número de antemão. 

O MeanShift também é baseado em centróides e atribui pontos iterativamente aos clusters. Seu uso mais comum é em tarefas de segmentação de imagens.

O MeanShift se baseia em estimação de densidade por kernel. Assim como no K-Means, os pontos são movidos iterativamente em direção ao centróide mais próximo, inicializados aleatoriamente, e cada ponto é deslocado no espaço em direção à região com mais pontos, isto é, a Moda (maior densidade de pontos na região, no contexto do MeanShift). 

Por isso, o MeanShift também é conhecido como algoritmo “busca da moda”. Os passos são:

• Escolha um ponto aleatório e crie uma janela ao seu redor.
• Calcule a média de todos os pontos dentro dessa janela.
• Desloque a janela seguindo a direção da moda. 
• Repita até a convergência.

Fonte da imagem: ResearchGate

Para um passo a passo do MeanShift na prática, veja nosso tutorial de Mean Shift Clustering.

3. DBSCAN

DBSCAN, de Density-Based Spatial Clustering of Applications with Noise, é um algoritmo de clusterização não supervisionado que parte da premissa de que clusters são regiões densas separadas por regiões de menor densidade. 

Sua maior vantagem sobre K-Means e MeanShift é ser robusto a outliers, ou seja, não inclui pontos discrepantes em nenhum cluster. 

O DBSCAN requer apenas dois parâmetros: 

• O raio do círculo criado ao redor de cada ponto, conhecido como epsilon

• minPoints, que define o número mínimo de pontos dentro desse círculo para que o ponto seja classificado como núcleo (Core).

Cada ponto é cercado por um círculo de raio epsilon, e o DBSCAN os classifica como ponto de núcleo (Core), de borda (Border) ou ruído (Noise). Um ponto é Core se o círculo ao seu redor contém pelo menos minPoints. 

É Border se tiver menos que o mínimo exigido e é Noise se não houver pontos adicionais dentro do raio epsilon de qualquer ponto. Pontos Noise não são atribuídos a nenhum cluster (são outliers).

Alguns usos comuns do DBSCAN:

• Separa muito bem regiões de alta e baixa densidade;
• Funciona bem em dados não lineares; e
• Pode ser usado em detecção de anomalias, pois isola pontos de ruído sem atribuí-los a clusters.

DBSCAN vs. K-Means

Comparando DBSCAN e K-Means, as diferenças mais comuns são: 

• K-Means atribui todos os registros a algum cluster; o DBSCAN não atribui pontos de ruído (outliers) a nenhum cluster
• K-Means tem dificuldade com clusters não globulares; o DBSCAN lida bem com isso
• K-Means assume que os dados seguem distribuição aproximadamente Gaussiana; o DBSCAN não faz suposições sobre a distribuição dos dados.

Saiba mais no nosso guia do algoritmo DBSCAN, com ajuste de parâmetros e exemplos práticos. 

Fonte da imagem: Medium

4. Clusterização hierárquica

A clusterização hierárquica constrói uma hierarquia de clusters. Existem dois tipos. 

• Aglomerativa: abordagem bottom-up, em que cada observação começa como seu próprio cluster e, de baixo para cima, observações se juntam em pares e pares formam clusters. 
• Divisiva: abordagem top-down: todas as observações começam em um único cluster, e as divisões são feitas recursivamente de cima para baixo.

Para analisar dados de redes sociais, a clusterização hierárquica é a mais comum e popular. Os nós (ramos) do grafo são comparados de acordo com seu grau de similaridade. Ao conectar pequenos grupos de nós relacionados, formam-se agrupamentos maiores.

Seu maior benefício é ser fácil de entender e implementar. O resultado costuma ser analisado em uma imagem chamada dendrograma.

Saiba mais no nosso tutorial de clusterização hierárquica, que mostra como construir e ler dendrogramas em Python. 

Fonte da imagem: ResearchGate

5. BIRCH

BIRCH significa Balanced Iterative Hierarchical Based Clustering. Ele é usado em datasets muito grandes, onde o K-Means não escala bem. O BIRCH divide grandes volumes em pequenos clusters e tenta reter o máximo de informação possível. Em vez de agrupar todo o dataset de uma vez, primeiro cria grupos menores e depois os reagrupa no resultado final. 

O BIRCH costuma complementar outros algoritmos de clusterização, gerando um sumário de informações que pode ser utilizado por eles. Assim como no K-Means, é necessário definir o número de clusters para treinar o BIRCH.

Um dos benefícios do BIRCH é conseguir agrupar progressiva e dinamicamente pontos multidimensionais, buscando formar clusters da melhor qualidade possível dentro de limites de memória e tempo. Na maioria dos casos, o BIRCH precisa apenas de uma varredura pelo banco de dados, o que o torna escalável. 

O uso mais comum do BIRCH é como alternativa eficiente em memória ao K-Means, para agrupar datasets muito grandes que não cabem em memória ou exigem computação além do viável para o K-Means.

Aplicações de negócio da clusterização

A clusterização tem aplicações amplas em mídia, saúde, manufatura, varejo — em qualquer lugar com grandes volumes de dados não rotulados. Veja alguns exemplos práticos.

Segmentação de clientes

Clientes são categorizados por meio de algoritmos de clusterização de acordo com comportamento de compra ou interesses, para criar campanhas de marketing direcionadas. 

Imagine que você tem 10 milhões de clientes e quer criar campanhas personalizadas. É inviável fazer 10 milhões de campanhas; o que fazer? Podemos usar clusterização para agrupar os 10 milhões em, por exemplo, 25 clusters e então criar 25 campanhas em vez de 10 milhões.

Fonte da imagem: Medium

Clusterização no varejo

Há muitas oportunidades no varejo. Por exemplo, você pode coletar dados de cada loja e agrupar no nível de loja para identificar quais localizações são semelhantes com base em atributos como fluxo de pessoas, ticket médio, número de SKUs etc. 

Outro exemplo é agrupar no nível de categoria. No diagrama abaixo, temos oito lojas. Cores diferentes representam clusters diferentes. Há quatro clusters neste exemplo. 

Note que a categoria desodorantes na Loja 1 está no cluster vermelho, enquanto na Loja 2 está no azul. Isso indica que as duas lojas têm públicos-alvo bem distintos para desodorantes.

Fonte da imagem: dotactiv.com

Clusterização em cuidados clínicos / gestão de doenças

A saúde e as ciências clínicas oferecem aplicações particularmente fortes. Um exemplo é a pesquisa de Komaru & Yoshida et al. 2020, que coletou dados demográficos e laboratoriais de 101 pacientes e os segmentou em 3 clusters. 

Cada cluster representou condições diferentes. Por exemplo, o cluster 1 tem pacientes com WBC e CRP baixos. O cluster 2 tem pacientes com BMP e soro altos, e o cluster 3 tem pacientes com soro baixo. Cada cluster indica uma trajetória de sobrevivência distinta considerando a mortalidade em 1 ano após hemodiálise.

Fonte da imagem: elsevierhealth.com

Segmentação de imagens

Segmentação de imagens é classificar uma imagem em grupos. Há muita pesquisa sobre segmentação usando clusterização. Esse tipo é útil quando você quer isolar objetos em uma imagem para analisá-los individualmente. 

No exemplo abaixo, a imagem da esquerda é a original, e a da direita é o resultado da clusterização. Dá para ver claramente 4 clusters, que são 4 objetos diferentes na imagem determinados pelos pixels (tigre, grama, água e areia).

Comparando algoritmos de clusterização

Existem 10 algoritmos de clusterização não supervisionada implementados no scikit-learn, uma biblioteca popular de machine learning em Python. Há diferenças fundamentais na forma como cada algoritmo encontra e atribui clusters no dataset. 

Essas diferenças matemáticas podem ser comparadas em quatro aspectos:

• Parâmetros exigidos pelo modelo 
• Escalabilidade 
• Casos de uso 
• Geometria, isto é, a métrica usada para calcular distâncias. 

No diagrama abaixo, cada coluna representa a saída de um algoritmo diferente, como K-Means, Affinity Propagation, MeanShift etc. São 10 algoritmos treinados no mesmo dataset.

Alguns geraram o mesmo resultado. Note que Agglomerative Clustering, DBSCAN, OPTICS e Spectral Clustering produziram os mesmos clusters. 

Por outro lado, K-Means e MeanShift deram resultados distintos. No K-Means, há apenas dois grupos (azul e laranja), enquanto no MeanShift há três (azul, verde e laranja). 

Fonte da imagem: scikit-learn

Infelizmente (ou felizmente), não há resposta certa ou errada em clusterização. Seria simples afirmar “o algoritmo X é o melhor aqui”. 

Isso não é possível — e é por isso que clusterização é uma tarefa desafiadora. 

No fim, qual algoritmo funciona melhor não depende de uma métrica facilmente mensurável, mas da interpretação e da utilidade do resultado para o caso de uso.

Como escolher o algoritmo de clusterização certo

Cada algoritmo se adapta melhor a condições de dados diferentes. Use esta tabela como ponto de partida e teste pelo menos dois nos seus dados antes de decidir.

Um começo prático: teste K-Means primeiro pela velocidade, troque para DBSCAN se seus dados tiverem formas irregulares ou muitos outliers e use o hierárquico quando quiser explorar a estrutura dos clusters visualmente via dendrograma antes de escolher k.

Considerações finais

Clusterização é mais difícil de aplicar do que técnicas supervisionadas como classificação e regressão por dois motivos: você não mede desempenho contra alvos rotulados e parâmetros como o número de clusters exigem julgamento de domínio, não seleção algorítmica. 

Mesmo assim, é uma habilidade valiosa em várias funções: data scientists, engenheiros de ML e analistas se deparam com problemas que a clusterização resolve. 

Se quiser se aprofundar em clusterização e aprendizado não supervisionado e aprender a implementar em Python e R, os cursos abaixo vão ajudar você a evoluir: 

• Cluster Analysis in Python
• Cluster Analysis in R
• Unsupervised Learning in Python
• Unsupervised Learning in R