A clusterização hierárquica, também conhecida como análise de agrupamento hierárquico (HCA), é um método de análise de agrupamento em mineração de dados e estatística que busca construir uma hierarquia de clusters. Diferentemente de métodos particionais como k-means, que exigem que o número de clusters seja especificado antecipadamente, a clusterização hierárquica produz uma estrutura aninhada que pode ser cortada em qualquer nível para gerar diferentes números de clusters. Os resultados são tipicamente apresentados em um dendrograma, um diagrama semelhante a uma árvore que ilustra a sequência de fusões ou divisões. Essa abordagem é amplamente utilizada em campos como biologia, ciências sociais e aprendizado de máquina para análise exploratória de dados.
A principal vantagem da clusterização hierárquica é sua flexibilidade: qualquer medida válida de distância pode ser usada, e as observações em si não são necessárias, apenas uma matriz de distâncias. No entanto, exceto no caso especial da distância de ligação simples, nenhum dos algoritmos pode ser garantido para encontrar a solução ótima sem busca exaustiva, que tem uma complexidade de tempo de O(2^n).
Estratégias Aglomerativas e Divisivas
As estratégias de clusterização hierárquica geralmente se enquadram em duas categorias: aglomerativa e divisiva. A clusterização aglomerativa, frequentemente chamada de abordagem "de baixo para cima", começa com cada ponto de dados como um cluster individual. A cada etapa, o algoritmo funde os dois clusters mais semelhantes com base em uma métrica de distância escolhida (por exemplo, distância euclidiana) e um critério de ligação (por exemplo, ligação simples, ligação completa). Esse processo continua até que todos os pontos de dados sejam combinados em um único cluster ou um critério de parada seja atendido. Os métodos aglomerativos são mais comumente usados devido à sua simplicidade e eficiência computacional para conjuntos de dados de pequeno a médio porte.
A clusterização divisiva, conhecida como abordagem "de cima para baixo", começa com todos os pontos de dados em um único cluster e divide recursivamente o cluster em outros menores. A cada etapa, o algoritmo seleciona um cluster e o divide em dois ou mais subconjuntos, frequentemente usando um critério como maximizar a distância entre os clusters resultantes. Os métodos divisivos são menos comuns, mas podem ser úteis quando o objetivo é identificar primeiro clusters grandes e distintos. Em geral, as fusões e divisões são determinadas de maneira gulosa, o que significa que o algoritmo faz escolhas localmente ótimas a cada etapa sem considerar a estrutura global.
Complexidade e Algoritmos
O algoritmo padrão para clusterização hierárquica aglomerativa (HAC) tem uma complexidade de tempo de O(n^3) e requer Ω(n^2) de memória, o que o torna lento demais até mesmo para conjuntos de dados médios. No entanto, para alguns casos especiais, métodos aglomerativos eficientes ótimos de complexidade O(n^2) são conhecidos: SLINK para ligação simples e CLINK para ligação completa. Com um heap, o tempo de execução do caso geral pode ser reduzido para O(n^2 log n) em vez de O(n^3), ao custo de requisitos adicionais de memória. Em muitos casos, as sobrecargas de memória dessa abordagem são grandes demais para torná-la praticamente utilizável. Existem métodos que usam quadtrees que demonstram tempo total de execução O(n^2) com espaço O(n).
A clusterização divisiva com busca exaustiva é O(2^n), mas é comum usar heurísticas mais rápidas para escolher divisões, como k-means. Essas heurísticas trocam a otimalidade pela viabilidade computacional, permitindo que métodos divisivos sejam aplicados a conjuntos de dados maiores.
Métricas de Distância
Enquanto o critério de ligação determina como a dissimilaridade entre conjuntos de observações é calculada, a métrica de distância subjacente determina como a dissimilaridade entre observações individuais é medida. Como a clusterização hierárquica permite qualquer medida válida de distância, a escolha da métrica é guiada pela natureza dos dados e pode ter um efeito significativo na clusterização resultante.
A distância euclidiana é a métrica mais amplamente usada para dados numéricos contínuos. Ela corresponde à distância em linha reta entre dois pontos no espaço euclidiano e é a escolha padrão na maioria dos softwares estatísticos. A distância de Manhattan (também chamada de distância do quarteirão ou distância L1) soma as diferenças absolutas entre as características. Ela é frequentemente preferida quando as características são medidas em escalas diferentes ou quando os dados contêm outliers, pois é menos sensível a grandes desvios do que a distância euclidiana. A distância de cosseno mede a dissimilaridade angular entre dois vetores não nulos e é comumente usada em análise de texto e outros contextos de alta dimensionalidade.
Critérios de Ligação
O critério de ligação determina como a distância entre dois clusters é calculada a partir das distâncias entre seus membros individuais. A ligação simples (ou vizinho mais próximo) usa a distância mínima entre quaisquer dois pontos nos dois clusters, o que tende a produzir clusters longos e em forma de cadeia. A ligação completa (ou vizinho mais distante) usa a distância máxima, o que tende a produzir clusters compactos e esféricos. A ligação média usa a distância média entre todos os pares de pontos, oferecendo um compromisso entre as duas. O método de Ward minimiza a variância total dentro do cluster, tornando-o popular para dados contínuos. A escolha do critério de ligação pode alterar drasticamente a forma e a interpretação do dendrograma resultante.
Aplicações e Limitações
A clusterização hierárquica é usada em muitos domínios. Em biologia, é usada para construir árvores filogenéticas com base na similaridade genética. Em marketing, ajuda a segmentar clientes em grupos com comportamentos semelhantes. Em análise de imagens, pode agrupar pixels ou características. Em inteligência artificial, a clusterização hierárquica é frequentemente usada como uma técnica de aprendizado não supervisionado para análise exploratória de dados e como uma etapa de pré-processamento para outros algoritmos.
Apesar de suas vantagens, a clusterização hierárquica tem limitações. A natureza gulosa dos algoritmos significa que, uma vez feita uma fusão ou divisão, ela não pode ser desfeita, o que pode levar a resultados subótimos. A complexidade computacional do algoritmo padrão restringe seu uso a conjuntos de dados de tamanho moderado, embora existam implementações otimizadas para critérios de ligação específicos. Além disso, a interpretação de um dendrograma pode ser subjetiva, e a escolha da métrica de distância e do critério de ligação requer conhecimento do domínio.