O que é agrupamento hierárquico?

O clustering é uma técnica de aprendizado de máquina não supervisionado utilizada na análise de conjuntos de dados para detectar e agrupar objetos semelhantes. A análise de cluster hierárquico (HCA), ou agrupamento hierárquico, agrupa objetos em uma hierarquia de cluster 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 detectar 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 agrupamentos em grupos maiores até surgir um único agrupamento.

- 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 de 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 clustering divisivos e aglomerativos são "greedy", o que significa que o algoritmo decide quais clusters mesclam ou dividem, fazendo a escolha localmente ótima 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 em forma de árvore chamado dendrograma³ é frequentemente utilizado para visualizar a hierarquia dos clusters. Ele exibe a ordem em que os clusters foram mesclados ou divididos e mostra a semelhança ou a distância entre os pontos de dados. Os dendrogramas 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 de ligação de distância euclidianos mais comuns. Exemplos de outras métricas de distância que podem ser utilizadas são Minkowski, Hamming, Mahalanobis, Hausdorf e distância de Manhattan. Observe que cada método de vinculação gera clusters diferentes 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 que estão sendo agrupados, a densidade de 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 agrupamentos e, em seguida, utiliza a distância mínima entre os agrupamentos. O método min lida bem com formas de cluster não elípticas, mas será afetado por ruídos e valores discrepantes. 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 and B são dois conjuntos de observações d é uma função da distância.

As distâncias de cluster 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. 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, introduzidos por Sokal e Michener⁷ , definem a distância entre agrupamentos como a distância média entre pares em todos os pares de pontos nos agrupamentos. O algoritmo pode ser o método do grupo de pares não ponderado com média aritmética (UPGMA) ou o método do grupo 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 que estão sendo combinados em cada etapa para formar um novo cluster da união de i e j. Podemos então calcular a distância de 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 de agrupamento ou centroides. A distância entre centroides é calculada usando uma função de distância:

∥μA-μB∥2

onde μ_A é o centróide de A e μ_B é o centróide de B.

Joe H. Ward introduziu 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 e, em seguida, aumenta à medida que mesclamos clusters. O método de Ward minimiza a soma das distâncias quadradas dos pontos dos centros do cluster à medida que são mesclados. O método de Ward é uma boa escolha para variáveis quantitativas⁹ e é menos afetado por ruído 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 cluster e encontrar o par de cluster 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 agrupamento. O algoritmo utiliza um critério de agrupamento de ligação selecionado com base em uma matriz de disparidade para decidir qual par de agrupamentos se 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: 10

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

2. Atribua cada ponto de dados a um cluster.

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

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 por Kaufman e Rousseeuw com seu algoritmo DIANA (Agrupamento de Análise Divisiva)¹² em 1990. O agrupamento divisivo utiliza a abordagem oposta ao 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 agrupamentos¹³ e podem ser mais precisos do que os métodos aglomerativos porque o algoritmo considera todo o conjunto de dados desde o início do processo.

Para melhorar a eficiência, os métodos de divisão utilizam algoritmos de agrupamento plano, como k-means, para dividir o conjunto de dados em clusters. O número de clusters deve ser especificado antecipadamente. O algoritmo k-means divide os agrupamentos minimizando a soma dos quadrados dentro do agrupamento entre os pontos centroides. Isso é conhecido como critério de inércia ¹⁴. As etapas de 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 coesivo 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 do cluster são normalmente apresentados em um dendograma (estrutura de árvore binária). O eixo x no dendograma representa os pontos de dados e oeixo y, ou a altura das linhas, mostra a que distância os agrupamentos estavam quando foram mesclados.

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

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 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 clustering. No exemplo abaixo, a linha horizontal H2 seleciona quatro clusters. H2 não pode se migrar para cima e para baixo até H1 sem cortar outras linhas horizontais. Esse cenário mostra que a escolha de dois clusters( H1) provavelmente é mais apropriada para seu modelo de clustering.

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

- 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 mídias sociais.

As coortes 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²⁰ utilizando, por exemplo, critérios diagnósticos, respostas fisiológicas ou mutações no DNA. Também pode ser aplicado para agrupar espécies por características biológicas para entender o desenvolvimento evolutivo.

O agrupamento hierárquico é utilizado em aplicações de reconhecimento de texto baseadas em imagem 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 oferece a função AgglomerativeCluster²¹ (consulte também exemplos de agrupamento agregativo²² no sklearn) e o SciPy oferece 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 ver uma experiência prática, confira nossos tutoriais passo a passo: como implementar agrupamento hierárquico em Python e como implementar agrupamento hierárquico em R.