Introdução ao clustering hierárquico em Python

Motivação

Imagine que você é um cientista de dados em uma empresa de varejo. Sua liderança pediu para segmentar os clientes nos seguintes grupos: clientes de baixo gasto, médios, altos ou platinum, com base no comportamento de consumo, para campanhas de marketing segmentadas e recomendações de produtos.

Sabendo que não existem rótulos históricos associados a esses clientes, como categorizá-los?

É aqui que o clustering ajuda. Trata-se de uma técnica de machine learning não supervisionada usada para agrupar dados sem rótulos em categorias semelhantes.

Este tutorial foca na abordagem de clustering hierárquico, uma entre várias técnicas de aprendizado não supervisionado. Vamos começar com uma visão geral do que é clustering hierárquico e depois compará-lo com outras técnicas conhecidas.

Em seguida, vamos guiar você por uma implementação passo a passo em Python usando a popular biblioteca Scipy.

Definição de clustering hierárquico

O clustering hierárquico é baseado na determinação de agrupamentos sucessivos a partir de clusters previamente formados. É uma técnica voltada para organizar os dados em uma árvore de clusters, chamada de dendrograma, que representa graficamente a relação hierárquica entre os agrupamentos.

Comparação do clustering hierárquico com outras técnicas de clustering

Clustering hierárquico é um algoritmo poderoso, mas não é o único, e cada tipo de clustering tem seus prós e contras.

Vamos entender como ele se compara a outros tipos, como K-means e o clustering baseado em modelos. Existem muitas outras técnicas, mas essas duas, além do clustering hierárquico, são amplamente usadas e ajudam a criar um referencial para entender as demais.

Você pode saber mais sobre clustering em machine learning neste artigo separado, que cobre cinco algoritmos essenciais.

Clustering hierárquico vs. K-means

Diferentemente do clustering hierárquico, o K-means busca particionar os dados originais em “K” grupos ou clusters, em que o usuário define “K” antecipadamente.

A ideia geral é encontrar clusters que minimizem a distância euclidiana quadrática de todos os pontos aos respectivos centros, considerando todos os atributos (variáveis ou features), e mesclar os indivíduos de forma iterativa.

Nosso tutorial K-means clustering em Python com Scikit-learn vai ajudar você a entender o funcionamento interno do K-means com um estudo de caso interessante.

Vantagens

• É computacionalmente mais eficiente que o clustering hierárquico e pode ser usado para analisar grandes conjuntos de dados.
• K-means é mais simples de entender e implementar.

Desvantagens

• É menos flexível que o clustering hierárquico porque exige que o usuário defina o número de clusters antes, o que pode não ser óbvio em alguns cenários.
• O resultado não é estável e pode mudar de uma iteração para outra com o mesmo conjunto de dados.
• É mais sensível a outliers, pois a presença de outliers afeta a média do cluster.
• Tanto k-means quanto o clustering hierárquico não lidam diretamente com dados categóricos e podem não funcionar bem com dados não contínuos ou com variância muito alta.

Apesar das limitações, o K-means continua popular pela facilidade de uso e eficiência computacional. Ele é frequentemente usado como referência para comparar o desempenho de outras técnicas de clustering.

Clustering baseado em modelos

Tanto K-means quanto o clustering hierárquico usam uma matriz de distâncias para representar as distâncias entre todos os pontos do dataset. Já o clustering baseado em modelos aplica técnicas estatísticas para identificar clusters nos dados. O processo geral é:

• Definir o modelo estatístico a ser usado e escolher o número de clusters.
• Ajustar o modelo aos dados.
• Identificar os clusters com base nos parâmetros do modelo.

Vantagens

• É mais flexível que o clustering hierárquico, pois permite usar diferentes modelos para identificar diferentes tipos de clusters.
• Funciona melhor com dados que têm formas ou estruturas complexas.

Desvantagens

• É computacionalmente mais caro que o clustering hierárquico, especialmente em grandes volumes de dados.
• Exige maior conhecimento de modelagem estatística, já que a escolha do modelo pode afetar o resultado final.
• Assim como o K-means, requer a especificação prévia do número de clusters.

Aplicações do clustering hierárquico

O clustering hierárquico tem diversas aplicações no dia a dia, incluindo (mas não se limitando a) biologia, processamento de imagens, marketing, economia e análise de redes sociais.

Biologia

O agrupamento de sequências de DNA é um dos maiores desafios em bioinformática.

Biólogos podem usar clustering hierárquico para estudar relações genéticas entre organismos e classificá-los em grupos taxonômicos. Isso facilita a análise rápida e a visualização dos relacionamentos subjacentes.

Processamento de imagens

No processamento de imagens, o clustering hierárquico pode agrupar regiões ou pixels semelhantes em termos de cor, intensidade ou outras características. Isso é útil para tarefas como segmentação de imagens, classificação de imagens e reconhecimento de objetos.

Marketing

Profissionais de marketing podem usar clustering hierárquico para estabelecer uma hierarquia entre diferentes tipos de clientes com base em seus hábitos de compra, permitindo estratégias de marketing mais assertivas e melhores recomendações de produtos. Por exemplo, diferentes produtos no varejo podem ser recomendados conforme clientes gastem pouco, médio ou muito.

Análise de redes sociais

Redes sociais são uma grande fonte de informação valiosa quando bem exploradas. O clustering hierárquico pode ser usado para identificar grupos ou comunidades, entender suas relações e a estrutura da rede como um todo.

O algoritmo de clustering hierárquico

Nesta seção, veremos três conceitos principais: as etapas do algoritmo hierárquico, os dois tipos de clustering hierárquico (aglomerativo e divisivo) e, por fim, algumas técnicas para escolher a melhor medida de distância.

Etapas envolvidas no algoritmo

O algoritmo de clustering hierárquico usa medidas de distância para gerar clusters. Esse processo envolve as etapas principais abaixo:

Pré-processe os dados removendo valores ausentes e aplicando tarefas adicionais para deixá-los o mais limpos possível. Essa etapa é geral para a maioria das tarefas de machine learning.

1. Calcule a matriz de distâncias contendo a distância entre cada par de pontos, usando uma métrica específica como distância euclidiana, Manhattan ou similaridade do cosseno. A métrica padrão costuma ser a euclidiana.

2. Una os dois clusters mais próximos.

3. Atualize a matriz de distâncias considerando os novos clusters.

4. Repita os passos 1, 2 e 3 até que todos os clusters sejam mesclados em um único cluster.

Exemplos de clustering hierárquico

Podemos considerar os métodos aglomerativo e divisivo como espelhos um do outro. Vamos ver como cada um opera, com exemplo e visualização.

Clustering hierárquico aglomerativo

Este primeiro cenário corresponde à abordagem explicada acima. Começa tratando cada observação como um cluster unitário (apenas um ponto). Em seguida, mescla os clusters iterativamente até restar apenas um. Esse processo também é chamado de abordagem bottom-up.

Como mostrado na ilustração abaixo:

• Começamos tratando cada animal como seu próprio cluster.
• Depois geramos três clusters diferentes a partir desses animais, com base em suas semelhanças:
• Aves: águia e pavão
• Mamíferos: leão e urso
• Animais com mais de três pernas: aranha e escorpião.
• Repetimos o processo de mesclagem para criar o cluster Vertebrados combinando os dois clusters mais semelhantes: Aves e Mamíferos.
• Depois disso, os dois clusters restantes, Vertebrados e Mais de três pernas, são unidos para formar um único cluster Animais.

Dendrograma da abordagem aglomerativa

Clustering divisivo

Já o clustering divisivo é top-down, pois começa considerando todos os pontos como um único cluster, e então os separa até que todos os pontos fiquem isolados.

Na ilustração do método divisivo:

• Percebemos que o conjunto de animais é considerado como um único bloco.
• Depois, dividimos esse bloco em dois clusters: Vertebrados e Mais de 3 pernas.
• A divisão é aplicada iterativamente aos clusters criados até chegarmos aos animais individuais.

Dendrograma da abordagem divisiva

Escolhendo a medida de distância certa

A escolha da medida de distância é crítica no clustering e depende do problema que você quer resolver. Considerando o cenário a seguir, poderíamos agrupar alunos com base em qualquer uma das abordagens, como:

• País de origem
• Gênero
• Formação acadêmica anterior

Todas são formas válidas de agrupar, mas com significados diferentes.

Embora a distância euclidiana seja a mais comum na maioria dos softwares de clustering, outras medidas existem, como Manhattan, Canberra, correlação de Pearson ou Spearman e Minkowski.

Como medir os clusters antes de uni-los

As distâncias mencionadas acima se referem a itens. Aqui, cobrimos três formas padrão (não exaustivas) de medir o par de clusters mais próximo antes de mesclá-los: (1) single linkage, (2) complete linkage e (3) average linkage.

Single linkage

Entre todas as distâncias par-a-par entre os itens dos clusters C1 e C2, o single linkage considera como distância entre os clusters a menor distância.

Distância (C1, C2) = Min { d(i, j), em que o item i está em C1 e o item j está em C2}

Entre todos os pares de itens dos dois clusters, os destacados em verde têm a menor distância.

Ilustração de single linkage

Complete linkage

Entre todas as distâncias par-a-par entre os itens dos clusters C1 e C2, o complete linkage considera como distância entre os clusters a maior distância.

Distância (C1, C2) = Max { d(i, j), em que o item i está em C1 e o item j está em C2}

Entre todos os pares de itens dos dois clusters, os destacados em verde têm a maior distância.

Ilustração de complete linkage

Average linkage

No average linkage, a distância entre dois clusters C1 e C2 corresponde à média das distâncias entre todos os pares de itens dos dois clusters.

Distância (C1, C2) = Soma{ d(i, j) } / número total de distâncias

Ilustração de average linkage

Então, o average linkage é calculado assim

d(a,j) + d(a,h) + d(a,n) + d(d,j) + d(d,h) + d(d,n)

—-----------------------------------------------------------, onde o número total de distâncias = 6

número total de distâncias

Implementando clustering hierárquico em Python

Agora que você entendeu como o clustering hierárquico funciona, nesta seção vamos para a implementação técnica em Python.

Se você prefere implementar em R, nosso tutorial Hierarchical clustering em R é o ponto de partida.

Preparando o ambiente

Para começar, você precisa ter o Python instalado no computador, além das seguintes bibliotecas:

• Pandas para carregar o data frame.
• Scikit-learn para normalização dos dados.
• Seaborn e matplotlib para visualização.
• Scipy para aplicar o clustering.

Você pode instalar essas bibliotecas com o pip, o gerenciador de pacotes do Python, assim:

pip install scikit-learn
pip install pandas

pip install matplotlib seaborn

pip install scipy

Em seguida, vamos importar os módulos necessários e carregar o conjunto de dados. Usaremos o dataset Iris embutido no scikit-learn, que contém informações sobre diferentes tipos de flores iris.

Para ilustrar melhor o caso, vamos usar o Loan Data disponível no DataLab. Todo o código deste tutorial está nesta workbook do DataLab; você pode criar uma cópia e executar o código no navegador, sem instalar nada no seu computador.

Entendendo os dados

O conjunto possui 9.500 empréstimos com informações sobre a estrutura do empréstimo, o tomador e se o empréstimo foi quitado integralmente. Vamos remover a coluna alvo not.fully.paid para manter o caráter não supervisionado.

import pandas as pd
loan_data = pd.read_csv("loan_data.csv")
loan_data.head()

Primeiras cinco linhas dos dados

A instrução a seguir mostra que os dados têm 9.578 linhas e 14 colunas de tipos numéricos, exceto purpose, que é um objeto e traz a descrição textual do propósito do empréstimo.

loan_data.info()

Informações sobre os dados

Pré-processamento dos dados

Antes de aplicar o clustering, os dados precisam ser pré-processados para lidar com ausências, normalizar valores de colunas e remover colunas irrelevantes.

Tratando valores ausentes

Pelo resultado abaixo, notamos que não há valores ausentes nos dados.

percent_missing =round(100*(loan_data.isnull().sum())/len(loan_data),2)
percent_missing

Percentual de valores ausentes

Remover colunas indesejadas

Vamos analisar os dados do empréstimo usando todas as colunas, exceto:

• purpose
• not.fully.paid, pois é o rótulo que indica se o tomador quitou totalmente ou não.

cleaned_data corresponde aos dados sem as colunas acima.

cleaned_data = loan_data.drop(['purpose', 'not.fully.paid'], axis=1)
cleaned_data.info()

A imagem abaixo mostra as informações do novo conjunto.

Novos dados sem as colunas indesejadas

Análise de outliers

Uma das fraquezas do clustering hierárquico é a sensibilidade a outliers. A distribuição de cada variável pode ser vista no boxplot.

def show_boxplot(df):
plt.rcParams['figure.figsize'] = [14,6]
sns.boxplot(data = df, orient="v")
plt.title("Outliers Distribution", fontsize = 16)
plt.ylabel("Range", fontweight = 'bold')
plt.xlabel("Attributes", fontweight = 'bold')
   
show_boxplot(cleaned_data)

Boxplot de todas as variáveis

O saldo rotativo do tomador (revol_bal) é o único atributo com pontos bem afastados do restante.

Usando a abordagem do intervalo interquartílico (IQR), podemos remover os pontos fora do intervalo definido por quartis +/- 1,5 * IQR, em que IQR é o intervalo interquartílico.

Isso é feito com a função auxiliar abaixo.

def remove_outliers(data):
   
df = data.copy()
   
for col in list(df.columns):
 
      Q1 = df[str(col)].quantile(0.05)
      Q3 = df[str(col)].quantile(0.95)
      IQR = Q3 - Q1
      lower_bound = Q1 - 1.5*IQR
      upper_bound = Q3 + 1.5*IQR
 
      df = df[(df[str(col)] >= lower_bound) & 

        (df[str(col)] <= upper_bound)]
   
return df

Depois, aplicamos a função ao conjunto de dados.

without_outliers = remove_outliers(cleaned_data)

Agora podemos verificar o novo boxplot e comparar com o anterior à remoção dos outliers.

show_boxplot(without_outliers)

Não há mais pontos fora do intervalo interquartílico.

without_outliers.shape

O shape agora é 9.319 linhas e 12 colunas. Isso significa que 259 observações eram outliers e foram removidas.

Reescalar os dados

Como o clustering hierárquico usa distância euclidiana, que é muito sensível a variáveis em escalas diferentes, é recomendável reescalar todas as variáveis antes de calcular distâncias.

Usaremos a classe StandardScaler do sklearn.

from sklearn.preprocessing import StandardScaler

data_scaler = StandardScaler()

scaled_data = data_scaler.fit_transform(without_outliers)
scaled_data.shape

O shape permanece o mesmo (9.319 linhas, 12 colunas) porque a normalização não altera as dimensões.

Aplicando o algoritmo de clustering hierárquico

Com os pré-requisitos atendidos, vamos à implementação do algoritmo.

Neste ponto, podemos escolher qual método de linkage adotar no atributo method da função linkage(). Aqui vamos cobrir as três técnicas usando distância euclidiana.

Isso é feito com o código abaixo, após importar as bibliotecas relevantes.

from scipy.cluster.hierarchy import linkage, dendrogram

complete_clustering = linkage(scaled_data, method="complete", metric="euclidean")
average_clustering = linkage(scaled_data, method="average", metric="euclidean")
single_clustering = linkage(scaled_data, method="single", metric="euclidean")

Depois de calcular os três agrupamentos, os dendrogramas correspondentes são mostrados a seguir, começando pelo complete linkage

dendrogram(complete_clustering)
plt.show()

Dendrograma do método complete linkage

dendrogram(average_clustering)
plt.show()

Dendrograma do método average linkage

dendrogram(single_clustering)
plt.show()

Dendrograma do método single linkage

Interpretando os resultados (visualizando o dendrograma, determinando o número de clusters)

Para cada método de linkage, o dendrograma mostra como é construída a hierarquia até que todos os pontos pertençam a um único cluster.

• O eixo x do dendrograma representa as amostras.
• O eixo y representa a distância entre essas amostras. Quanto mais alta a linha, maior a dissimilaridade entre amostras/clusters.
• Obtemos o número adequado de clusters traçando uma linha horizontal ao longo da maior linha vertical; o número de interseções corresponde ao número de clusters.

O número ideal de clusters é obtido identificando a maior linha vertical que não cruza nenhuma outra (linha horizontal). Essa linha está destacada abaixo com um círculo vermelho e um check verde.

• Para complete linkage, é a linha azul à direita, gerando três clusters.

Número ideal de clusters pela maior distância sem interseção (complete linkage)

• Para average linkage, é a primeira linha vertical azul, gerando dois clusters.

Número ideal de clusters pela maior distância sem interseção (average linkage)

• Para single linkage, é a primeira linha vertical, gerando apenas um cluster.

Número ideal de clusters pela maior distância sem interseção (single linkage)

Pelas observações acima, o average linkage parece oferecer o melhor agrupamento, ao contrário do single e do complete linkage, que sugerem, respectivamente, um e três clusters. Além disso, o número ideal de dois clusters corresponde ao nosso conhecimento prévio do dataset, ou seja, dois tipos de tomadores.

Agora que encontramos o número ideal de clusters, vamos ver o que eles significam com base no score de crédito (fico) dos tomadores.

cluster_labels = cut_tree(average_clustering, n_clusters=2).reshape(-1, )
without_outliers["Cluster"] = cluster_labels

sns.boxplot(x='Cluster', y='fico', data=without_outliers)

No boxplot acima, observamos que:

• Tomadores do cluster 0 têm scores de crédito mais altos.
• Já os do cluster 1 têm scores mais baixos.

Cluster Analysis in Python pode ser um ótimo próximo passo para se aprofundar em K-means e clustering hierárquico com a biblioteca Scipy.

Conclusão

Este artigo abordou o que é clustering hierárquico, seus pontos fortes e fracos, e como ele se compara ao K-means e ao clustering baseado em modelos.

Esperamos que o conteúdo ajude você a desenvolver as competências necessárias para agrupar seus dados sem rótulos de forma eficiente e tomar decisões acionáveis.