O que é agrupamento hierárquico?

Agrupamento é uma técnica de aprendizado de máquina não supervisionado usada na análise de dados para detectar e agrupar objetos similares. A análise de clusters hierárquicos (HCA), ou agrupamento hierárquico, agrupa objetos em uma hierarquia de clusters sem impor uma ordem linear dentro deles. Muitas disciplinas, como biologia, análise de imagens e ciências sociais, utilizam métodos de agrupamento hierárquico para explorar e reconhecer padrões em conjuntos de dados. Os casos de uso incluem categorização de populações em pesquisa clínica, segmentação de clientes e detecção de comunidades de nós em modelos de rede.

Há dois tipos de agrupamento hierárquico:

- Abordagem aglomerativa ou de baixo para cima¹, que mescla repetidamente os clusters em grupos maiores até surgir um único cluster.

- Abordagem divisiva ou de cima para baixo que² começa com todos os dados em um único cluster e continua dividindo clusters sucessivos até que todos os clusters sejam únicos.

A análise do agrupamento hierárquico tem altos custos computacionais. Embora o uso de heap possa reduzir o tempo de computação, os requisitos de memória aumentam. Ambos os tipos de agrupamento divisivo e aglomerativo são "gananciosos", o que significa que o algoritmo decide quais clusters mesclam ou dividem, fazendo a escolha localmente ideal em cada estágio do processo. Também é possível aplicar um critério de parada, em que o algoritmo interrompe a aglomeração ou a divisão de clusters quando atinge um número predeterminado de clusters.

Um diagrama semelhante a uma árvore chamado dendrograma³ é frequentemente utilizado para visualizar a hierarquia de clusters. Ele exibe a ordem na qual os clusters foram mesclados ou divididos e mostra a semelhança ou distância entre os pontos de dados. Dendogramas também podem ser entendidos como uma lista aninhada de listas⁴ com atributos.

Os algoritmos de agrupamento hierárquico utilizam o conceito de uma matriz de dissimilaridade para decidir quais clusters mesclar ou dividir. Dissimilaridade é a distância entre dois pontos de dados, medida por um método de ligação escolhido. Os valores em uma matriz de dissimilaridade expressam:

- A distância⁵, uma distância euclidiana como exemplo, entre pontos únicos de um conjunto

- Um critério de agrupamento de ligação, que especifica a dissimilaridade em função das distâncias de pares de pontos entre conjuntos

Vamos explorar os métodos mais comuns de vinculação de distância euclidiana. Exemplos de outras métricas de distância que podem ser usadas incluem a distância de Minkowski, Hamming, Mahalanobis, Hausdorf e Manhattan. Observe que cada método de vinculação gera diferentes clusters a partir do mesmo conjunto de dados. A seleção do método de agrupamento de ligação apropriado depende de fatores como o tipo de dados sendo agrupados, a densidade dos dados, a forma do cluster e se há valores discrepantes ou ruído no conjunto de dados.

O método de ligação única analisa as distâncias em pares entre os itens em dois clusters e, em seguida, usa a distância mínima entre os clusters. O método min lida bem com formas de clusters não elípticas, mas será afetado por ruídos e valores discrepantes. Ele apresenta uma limitação conhecida como efeito de encadeamento⁶. Alguns pontos que criam uma ponte entre um par de clusters podem resultar na fusão dos dois clusters em um. Os critérios de ligação mínima podem ser representados como:

 mina∈A,b∈Bd(a,b)

onde A e B são dois conjuntos de observações e d é uma função de distância.

As distâncias de clusters também podem ser calculadas com base nos pontos que estão mais distantes uns dos outros. O método max é menos sensível a ruído do que o método min e valores discrepantes, mas sua utilização pode distorcer os resultados quando há clusters globulares ou grandes. O max-linkage frequentemente produz clusters mais esféricos do que min-linkage. O max-linkage pode ser representado na fórmula:

 maxa∈A,b∈Bd(a,b)

onde A e B são dois conjuntos de observações e d é a distância.

Esses métodos, lançados por Sokal e Michener⁷ , definem a distância entre clusters como a distância média entre pares em todos os pares de pontos nos clusters. O algoritmo pode ser o método de grupos de pares não ponderados com média aritmética (UPGMA) ou o método de grupos de pares ponderados com média aritmética (WPGMA). O significado de "não ponderado" aqui é que todas as distâncias contribuem igualmente para cada média.

O UPGMA é representado pela fórmula

 1∣A∣·∣B∣∑a∈A∑b∈Bd(a,b)

onde *A* e *B* são dois conjuntos de observações, e *d* é a distância.

WPGMA é representado pela fórmula

 d(i∪j,k)=d(i,k)+d(j,k)2

onde i e j são os clusters mais próximos sendo combinados em cada etapa para formar um novo cluster da união de i e j. Podemos, então, calcular a distância para outro cluster k, que é a média aritmética das distâncias médias entre os pontos de dados em k e i e k e j.

Aqui, utilizamos a distância entre os centros dos clusters, ou centroides. A distância entre centroides é calculada usando uma função de distância:

∥μA-μB∥2

onde μ_A é o centroide de A e μ_B é o centroide de B.

Joe H. Ward lançou o método de aumento mínimo da soma dos quadrados (Missq)⁸ na década de 1960. Cada ponto de dados começa em seu próprio cluster. Essa abordagem significa que a soma dos quadrados entre os pontos de dados está inicialmente em zero, depois aumenta à medida que mesclamos os clusters. O método de Ward minimiza a soma das distâncias quadradas dos pontos dos centros dos clusters à medida que são mesclados. O método de Ward é uma boa escolha para variáveis quantitativas⁹ e é menos afetado por ruídos ou valores discrepantes. Pode ser representado como:

 ∣A∣·∣B∣A∪B∥μA-μB∥2=∑x∈A∪B∥x-μA∪B∥2-∑x∈A∥x-μA∥2-∑x∈B∥x-μB∥2

onde a média de A e a média de B são os centroides de A e B, respectivamente, e x é um ponto de dados que pertence à união de A e B

O método de variância mínima de Ward pode ser refinado utilizando-se o algoritmo de Lance-Williams. Esses algoritmos utilizam uma fórmula recursiva para atualizar distâncias de clusters e encontrar o par de clusters mais próximo ideal para mesclar.

No agrupamento hierárquico aglomerativo, também conhecido como aninhamento aglomerativo (AGNES), cada ponto de dados começa como um cluster. O algoritmo usa um critério de agrupamento de ligação selecionado com base em uma matriz de disparidade para decidir qual par de clusters unir. O algoritmo sobe na hierarquia e continua emparelhando clusters até que tudo tenha sido vinculado, criando uma série hierárquica de clusters aninhados. Basicamente, as ¹⁰ etapas do agrupamento aglomerativo são:

1. Calcule a matriz de dissimilaridade com uma métrica de distância específica.

2. Atribua cada ponto de dados a um cluster.

3. Mescle os clusters com base em um critério de ligação para a semelhança entre os clusters.

4. Atualize a matriz de distância.

5. Repita as etapas 3 e 4 até que permaneça um único cluster ou qualquer critério de parada seja atendido.

Os princípios por trás do agrupamento hierárquico divisivo foram desenvolvidos por Macnaughton-Smith e outros¹¹ em 1964 e explorados mais profundamente por Kaufman e Rousseeuw com seu algoritmo DIANA (Divisive ANAlysis clustering)¹² em 1990. O agrupamento divisivo usa a abordagem oposta à do agrupamento aglomerativo. Todos os pontos de dados começam em um único cluster, que é dividido repetidamente em mais clusters. A divisão ocorre até que todos os clusters restantes sejam singletons ou que um critério de parada, como um número predefinido de clusters, seja atendido. Os métodos divisivos são melhores na identificação de grandes clusters¹³ e podem ser mais precisos do que os métodos aglomerativos porque o algoritmo considera toda a distribuição do conjunto de dados desde o início do processo.

Para melhorar a eficiência, os métodos divisivos usam algoritmos de agrupamento plano, como o k-means , para dividir o conjunto de dados em clusters. O número de clusters deve ser especificado desde o início. O algoritmo k-means divide clusters minimizando a soma dos quadrados dentro do cluster entre os pontos do centroide. Isso é conhecido como critério de inércia14. As etapas do agrupamento divisivo¹⁵ são:

1. Comece com todos os pontos de dados para um tamanho de conjunto de dados N (d1, d2, d3 ... dN) em um cluster.

2. Divida o cluster em dois clusters diferentes ou heterogêneos com um método de agrupamento plano, como o algoritmo k-means.

3. Repita a etapa 2, escolhendo o melhor cluster para dividir e removendo os valores discrepantes do cluster menos coeso após cada iteração.

4. Pare quando cada exemplo estiver em seu próprio cluster individual; caso contrário, repita a etapa 3.

Os resultados dos clusters são normalmente apresentados em um dendograma (estrutura de árvore binária). O eixo eixo x no dendograma representa os pontos de dados, e o eixo y, ou a altura das linhas, mostra a que distância os clusters estavam quando foram mesclados.

Você pode usar um dendograma para decidir quantos clusters¹⁶ estarão em seu modelo de agrupamento final. Uma estratégia é identificar o ponto de corte natural na árvore onde os galhos diminuem e se tornam mais longos. Ou então, o número de clusters é dado pelo número de linhas verticais cruzadas quando uma linha horizontal corta o dendograma.

Na imagem de exemplo mostrada aqui, a linha horizontal H1 corta duas linhas verticais. Isso mostra que há dois clusters nesse ponto do processo: um cluster com os pontos 5, 8 e 2 e um cluster com os pontos restantes. Quanto mais a linha horizontal puder se mover para cima ou para baixo sem cortar outras linhas horizontais no dendograma, melhor será a seleção desse número de clusters para o seu modelo de agrupamento. No exemplo abaixo, a linha horizontal H2 seleciona quatro clusters. H2 não pode se mover para cima e para baixo até H1 antes de cortar outras linhas horizontais. Esse cenário mostra que a escolha de dois clusters (H1) é provavelmente mais apropriada para o seu modelo de agrupamento.

Um modelo de agrupamento robusto¹⁷ cria clusters com alta similaridade intraclasse e baixa similaridade interclasse. No entanto, pode ser difícil definir a qualidade dos clusters, e a seleção do critério de ligação e dos números dos clusters pode afetar significativamente os resultados. Portanto, ao construir um modelo de agrupamento, experimente diferentes opções e selecione aquelas que melhor o ajudarem a explorar e revelar padrões no conjunto de dados para consideração futura. Os fatores a serem considerados¹⁸ incluem:

- O número de clusters práticos ou lógicos para o conjunto de dados (tamanho do conjunto de dados, formas de cluster, ruído etc.)

- Estatísticas, como os valores médio, máximo e mínimo para cada cluster

- A melhor métrica de disparidade ou critério de ligação a ser aplicado

- O impacto de quaisquer valores discrepantes ou variáveis de resultado

- Qualquer conhecimento específico de domínio ou conjunto de dados

Outros métodos para ajudar a determinar o número ideal de clusters¹⁹ são:

- O método do cotovelo, onde você traça a soma dos quadrados dentro do cluster em relação ao número de clusters e determina o "cotovelo" (o ponto em que o gráfico se nivela)

- Estatística de lacuna, onde você compara a soma real dos quadrados dentro do cluster com a soma esperada dos quadrados dentro do cluster para uma distribuição de referência nula e identifica a maior lacuna.

O agrupamento hierárquico dá aos cientistas de dados insights sobre a estrutura e os relacionamentos nos conjuntos de dados e pode ser aplicado em vários casos de uso.

O agrupamento hierárquico pode ajudar a analisar tendências e segmentar dados de clientes, como agrupamento por escolha de produto, demografia, comportamento de compra, perfil de risco ou interações com redes sociais.

Os grupos de pacientes para pesquisa clínica podem chegar aos milhares. O agrupamento hierárquico ajuda a categorizar populações mistas em grupos mais homogêneos²⁰ usando, por exemplo, critérios de diagnóstico, respostas fisiológicas ou mutações de DNA. Também pode ser aplicado a espécies de grupos por funcionalidades biológicas para entender o desenvolvimento evolutivo.

O agrupamento hierárquico é utilizado em aplicações de reconhecimento de texto baseadas em imagens para agrupar caracteres escritos à mão de acordo com sua forma. Também é utilizado para armazenar e recuperar informações usando determinados critérios ou para categorizar os resultados de pesquisas.

Tanto a linguagem de programação Python quanto a R são amplamente utilizadas em ciência de dados. O Python é flexível e pode lidar com um amplo espectro de tarefas. Por outro lado, o R foi projetado especificamente para computação estatística e oferece opções avançadas para visualizar sua análise de agrupamento hierárquico.

O Python fornece a função AgglomerativeCluster ²¹ (consulte também exemplos de agrupamento aglomerativo²² no sklearn), e o SciPy fornece uma função para plotar dendogramas²³. Pacotes como o dedextend²⁴ aprimoram a funcionalidade do dendograma do R, melhorando a análise de sensibilidade e permitindo comparar e manipular diferentes dendogramas. Para uma experiência prática, confira nossos tutoriais passo a passo: como implementar o agrupamento hierárquico no Python e como implementar o agrupamento hierárquico no R.