Agrupamento hierárquico

método de análise de agrupamento que busca construir uma hierarquia de grupos

Em mineração de dados e estatística, o agrupamento hierárquico (também chamado de análise de agrupamento hierárquico ou HCA) é um método de análise de agrupamento que busca construir uma hierarquia de agrupamentos. As estratégias para o agrupamento hierárquico geralmente se dividem em duas categorias:

  • Aglomerativo: Esta é uma abordagem "de baixo para cima": cada observação começa em seu próprio agrupamento, e pares de agrupamentos são fundidos à medida que se sobe na hierarquia.
  • Divisivo: Esta é uma abordagem "de cima para baixo": todas as observações começam em um único agrupamento, e divisões são realizadas de forma recursiva à medida que se desce na hierarquia.

Em geral, as fusões e divisões são determinadas de maneira gulosa. Os resultados do agrupamento hierárquico[1] são geralmente apresentados em um dendrograma.

O agrupamento hierárquico tem a vantagem distinta de que qualquer medida válida de distância pode ser usada. Na verdade, as próprias observações não são necessárias: tudo o que é usado é uma matriz de distâncias (formalmente uma matriz de dissimilaridade). Por outro lado, exceto pelo caso especial da distância de ligação única, nenhum dos algoritmos (exceto a busca exaustiva em ) pode garantir encontrar a solução ótima.

Complexidade

editar

O algoritmo padrão para agrupamento aglomerativo hierárquico (AAH) tem uma complexidade de tempo de   e requer   de memória, o que o torna muito lento para conjuntos de dados de tamanho médio. No entanto, para alguns casos especiais, são conhecidos métodos aglomerativos eficientes ótimos (de complexidade  ): SLINK[2] para agrupamento por ligação única e CLINK[3] para agrupamento por ligação completa. Com um heap, o tempo de execução do caso geral pode ser reduzido para  , uma melhoria em relação ao limite mencionado de  , ao custo de aumentar ainda mais os requisitos de memória. Em muitos casos, a sobrecarga de memória dessa abordagem é grande demais para ser praticamente utilizável.

O agrupamento divisivo com uma busca exaustiva é  , mas é comum usar heurísticas mais rápidas para escolher divisões, como k-means.

Ligação entre Agrupamentos

editar

Para decidir quais agrupamentos devem ser combinados (para aglomerativo), ou onde um agrupamento deve ser dividido (para divisivo), é necessária uma medida de dissimilaridade entre conjuntos de observações. Na maioria dos métodos de agrupamento hierárquico, isso é alcançado pelo uso de uma distância apropriada d, como a distância euclidiana, entre observações individuais do conjunto de dados, e um critério de ligação, que especifica a dissimilaridade de conjuntos como uma função das distâncias entre pares de observações nos conjuntos. A escolha da métrica e da ligação pode ter um grande impacto no resultado do agrupamento, onde a métrica de nível inferior determina quais objetos são mais similares, enquanto o critério de ligação influencia a forma dos agrupamentos. Por exemplo, a ligação completa tende a produzir agrupamentos mais esféricos do que a ligação única.

O critério de ligação determina a distância entre conjuntos de observações como uma função das distâncias entre pares de observações.

Alguns critérios de ligação comumente usados entre dois conjuntos de observações A e B e uma distância d são:[4][5]

Nomes Fórmula
Máximo ou agrupamento por ligação completa  
Mínimo ou agrupamento por ligação única  
Ligação média não ponderada (ou UPGMA)  
Ligação média ponderada (ou WPGMA)  
Ligação de centróide, ou UPGMC   onde   e   são os centróides de A resp. B.
Ligação mediana, ou WPGMC   onde  
Ligação versátil[6]  
Ligação de Ward,[7] Aumento Mínimo da Soma dos Quadrados (MISSQ)[8]  
Soma Mínima de Erro dos Quadrados (MNSSQ)[8]  
Aumento Mínimo na Variância (MIVAR)[8]   
Variância Mínima (MNVAR)[8]  
Ligação Mini-Max[9]  
Ligação de Hausdorff[10]  
Ligação de Medoid de Soma Mínima[11]   tal que m é o medoid do agrupamento resultante
Ligação de Aumento de Soma Mínima de Medoid[11]  
Ligação de Medoid[12][13]   onde  ,   são os medoids dos agrupamentos anteriores
Agrupamento de energia mínima  

Alguns desses só podem ser recalculados recursivamente (WPGMA, WPGMC), para muitos um cálculo recursivo com equações de Lance-Williams é mais eficiente, enquanto para outros (Mini-Max, Hausdorff, Medoid) as distâncias têm que ser calculadas com a fórmula completa mais lenta. Outros critérios de ligação incluem:

  • A probabilidade de que os agrupamentos candidatos se originem da mesma função de distribuição (ligação V).
  • O produto do grau de entrada e saída em um gráfico k-vizinhos mais próximos (ligação de grau de gráfico).[14]
  • O incremento de algum descritor de agrupamento (ou seja, uma quantidade definida para medir a qualidade de um agrupamento) após a fusão de dois agrupamentos.[15][16][17]

Exemplo de Agrupamento Aglomerativo

editar
 
Dados brutos

Por exemplo, suponha que esses dados devam ser agrupados e que a distância Euclidiana seja a métrica de distância utilizada.

O dendrograma do agrupamento hierárquico seria:

 
Representação tradicional

Cortar a árvore em uma determinada altura resultará em um agrupamento particionado com uma precisão selecionada. Neste exemplo, cortar após a segunda linha (de cima para baixo) do dendrograma resultará nos agrupamentos {a} {b c} {d e} {f}. Cortar após a terceira linha resultará nos agrupamentos {a} {b c} {d e f}, que é um agrupamento mais grosseiro, com um número menor, mas com agrupamentos maiores.

Este método constrói a hierarquia a partir dos elementos individuais, fundindo progressivamente os agrupamentos. Em nosso exemplo, temos seis elementos {a} {b} {c} {d} {e} e {f}. O primeiro passo é determinar quais elementos devem ser fundidos em um agrupamento. Geralmente, queremos pegar os dois elementos mais próximos, de acordo com a distância escolhida.

Opcionalmente, também é possível construir uma matriz de distâncias nesta etapa, onde o número na i-ésima linha e j-ésima coluna é a distância entre o i-ésimo e o j-ésimo elementos. Então, à medida que o agrupamento progride, linhas e colunas são fundidas à medida que os agrupamentos são fundidos e as distâncias atualizadas. Esta é uma maneira comum de implementar esse tipo de agrupamento e tem a vantagem de armazenar em cache as distâncias entre os agrupamentos. Um algoritmo simples de agrupamento aglomerativo é descrito na página de agrupamento por ligação simples; ele pode ser facilmente adaptado para diferentes tipos de ligação (veja abaixo).

Suponha que tenhamos fundido os dois elementos mais próximos, b e c, agora temos os seguintes agrupamentos {a}, {b, c}, {d}, {e} e {f}, e queremos fundi-los ainda mais. Para fazer isso, precisamos pegar a distância entre {a} e {b c} e, portanto, definir a distância entre dois agrupamentos. Geralmente, a distância entre dois agrupamentos A e B é uma das seguintes:

  • A distância máxima entre elementos de cada agrupamento (também chamado de agrupamento por ligação completa):
 
  • A distância mínima entre elementos de cada agrupamento (também chamado de agrupamento por ligação simples):
 
  • A distância média entre elementos de cada agrupamento (também chamado de agrupamento por ligação média, usado por exemplo no UPGMA):
 
  • A soma de toda a variância intra-agrupamento.
  • O aumento na variância para o agrupamento que está sendo fundido (método de Ward[7])
  • A probabilidade de que agrupamentos candidatos se originem da mesma função de distribuição (V-ligação).

Em caso de distâncias mínimas empatadas, um par é escolhido aleatoriamente, permitindo assim gerar vários dendrogramas estruturalmente diferentes. Alternativamente, todos os pares empatados podem ser unidos ao mesmo tempo, gerando um dendrograma único.[18]

Sempre é possível decidir parar o agrupamento quando há um número suficientemente pequeno de agrupamentos (critério de número). Algumas ligações também podem garantir que a aglomeração ocorra a uma distância maior entre os agrupamentos do que a aglomeração anterior, e então pode-se parar o agrupamento quando os agrupamentos estão muito distantes para serem fundidos (critério de distância). No entanto, isso não é o caso de, por exemplo, a ligação do centróide onde as chamadas reversões[19] (inversões, desvios da ultrametricidade) podem ocorrer.

Agrupamento Divisivo

editar

O princípio básico do agrupamento divisivo foi publicado como o algoritmo DIANA (Análise Divisiva de Agrupamento).[20] Inicialmente, todos os dados estão no mesmo agrupamento e o maior agrupamento é dividido até que cada objeto esteja separado. Como existem   maneiras de dividir cada agrupamento, heurísticas são necessárias. DIANA escolhe o objeto com a dissimilaridade média máxima e, em seguida, move todos os objetos para este agrupamento que são mais semelhantes ao novo agrupamento do que ao restante.

Informalmente, DIANA não é tanto um processo de "dividir", mas sim de "esvaziar": a cada iteração, um agrupamento existente (por exemplo, o agrupamento inicial de todo o conjunto de dados) é escolhido para formar um novo agrupamento dentro dele. Objetos se movem progressivamente para este agrupamento aninhado, esvaziando o agrupamento existente. Eventualmente, tudo o que resta dentro de um agrupamento são agrupamentos aninhados que cresceram lá, sem possuir nenhum objeto solto por si só.

Formalmente, DIANA opera nas seguintes etapas:

  1. Deixe   ser o conjunto de todos os   índices de objetos e   o conjunto de todos os agrupamentos formados até agora.
  2. Itere o seguinte até que  :
    1. Encontre o agrupamento atual com 2 ou mais objetos que tenha o maior diâmetro:  
    2. Encontre o objeto neste agrupamento com a maior dissimilaridade em relação ao restante do agrupamento:  
    3. Retire   do seu antigo agrupamento   e coloque-o em um novo grupo fragmentado  .
    4. Enquanto   não estiver vazio, continue migrando objetos de   para adicioná-los a  . Para escolher quais objetos migrar, não considere apenas a dissimilaridade com  , mas também ajuste pela dissimilaridade com o grupo fragmentado: defina   onde definimos  , então ou pare de iterar quando  , ou migre  .
    5. Adicione   a  .

Intuitivamente,   acima mede o quanto um objeto deseja deixar seu agrupamento atual, mas é atenuado quando o objeto também não se encaixaria no grupo fragmentado. Tais objetos provavelmente iniciarão seu próprio grupo fragmentado eventualmente.

O dendrograma de DIANA pode ser construído permitindo que o grupo fragmentado   seja um filho do agrupamento esvaziado   a cada vez. Isso constrói uma árvore com   como sua raiz e   agrupamentos únicos de um único objeto como suas folhas.

Software

editar

Implementações de código aberto

editar
 
Dendrograma de agrupamento hierárquico do conjunto de dados da flor Iris (usando R). Fonte
 
Visualização interativa de dendrograma e agrupamento hierárquico na suíte de mineração de dados Orange.
  • ALGLIB implementa vários algoritmos de agrupamento hierárquico (ligação simples, ligação completa, Ward) em C++ e C# com memória O(n²) e tempo de execução O(n³).
  • ELKI inclui múltiplos algoritmos de agrupamento hierárquico, várias estratégias de ligação e também inclui os algoritmos eficientes SLINK,[2] CLINK[3] e Anderberg, extração flexível de agrupamentos de dendrogramas e vários outros algoritmos de análise de agrupamento.
  • Julia tem uma implementação dentro do pacote Clustering.jl.[21]
  • Octave, o análogo do GNU para MATLAB implementa agrupamento hierárquico na função "linkage".
  • Orange, uma suíte de software de mineração de dados, inclui agrupamento hierárquico com visualização interativa de dendrograma.
  • R possui funções internas[22] e pacotes que fornecem funções para agrupamento hierárquico.[23][24][25]
  • SciPy implementa agrupamento hierárquico em Python, incluindo o algoritmo SLINK eficiente.
  • Scikit-learn também implementa agrupamento hierárquico em Python.
  • Weka inclui análise de agrupamento hierárquico.

Implementações comerciais

editar
  • MATLAB inclui análise de agrupamento hierárquico.
  • SAS inclui análise de agrupamento hierárquico no PROC CLUSTER.
  • Mathematica inclui um Pacote de Agrupamento Hierárquico.
  • NCSS inclui análise de agrupamento hierárquico.
  • SPSS inclui análise de agrupamento hierárquico.
  • Qlucore Omics Explorer inclui análise de agrupamento hierárquico.
  • Stata inclui análise de agrupamento hierárquico.
  • CrimeStat inclui um algoritmo de agrupamento hierárquico de vizinho mais próximo com uma saída gráfica para um Sistema de Informação Geográfica.

Veja também

editar

Referências

editar
  1. Nielsen, Frank (2016). «8. Hierarchical Clustering». Introduction to HPC with MPI for Data Science. [S.l.]: Springer. pp. 195–211. ISBN 978-3-319-21903-5 
  2. «The CLUSTER Procedure: Clustering Methods». SAS/STAT 9.2 Users Guide. SAS Institute. Consultado em 26 de abril de 2009 
  3. Székely, G. J.; Rizzo, M. L. (2005). «Hierarchical clustering via Joint Between-Within Distances: Extending Ward's Minimum Variance Method». Journal of Classification. 22 (2): 151–183. doi:10.1007/s00357-005-0012-9 
  4. Fernández, Alberto; Gómez, Sergio (2020). «Versatile linkage: a family of space-conserving strategies for agglomerative hierarchical clustering». Journal of Classification. 37 (3): 584–597. arXiv:1906.09222 . doi:10.1007/s00357-019-09339-z 
  5. a b Ward, Joe H. (1963). «Hierarchical Grouping to Optimize an Objective Function». Journal of the American Statistical Association. 58 (301): 236–244. JSTOR 2282967. MR 0148188. doi:10.2307/2282967 
  6. a b c d Podani, János (1989), Mucina, L.; Dale, M. B., eds., «New combinatorial clustering methods», ISBN 978-94-009-2432-1, Dordrecht: Springer Netherlands, Numerical syntaxonomy (em inglês), pp. 61–77, doi:10.1007/978-94-009-2432-1_5, consultado em 4 de novembro de 2022 
  7. Ao, S. I.; Yip, K.; Ng, M.; Cheung, D.; Fong, P.-Y.; Melhado, I.; Sham, P. C. (7 de dezembro de 2004). «CLUSTAG: hierarchical clustering and graph methods for selecting tag SNPs». Bioinformatics. 21 (8): 1735–1736. ISSN 1367-4803. PMID 15585525. doi:10.1093/bioinformatics/bti201  
  8. Basalto, Nicolas; Bellotti, Roberto; De Carlo, Francesco; Facchi, Paolo; Pantaleo, Ester; Pascazio, Saverio (15 de junho de 2007). «Hausdorff clustering of financial time series». Physica A: Statistical Mechanics and Its Applications (em inglês). 379 (2): 635–644. Bibcode:2007PhyA..379..635B. ISSN 0378-4371. arXiv:physics/0504014 . doi:10.1016/j.physa.2007.01.011 
  9. a b Schubert, Erich (2021). HACAM: Hierarchical Agglomerative Clustering Around Medoids – and its Limitations (PDF). LWDA’21: Lernen, Wissen, Daten, Analysen September 01–03, 2021, Munich, Germany. pp. 191–204 – via CEUR-WS 
  10. Miyamoto, Sadaaki; Kaizu, Yousuke; Endo, Yasunori (2016). Hierarchical and Non-Hierarchical Medoid Clustering Using Asymmetric Similarity Measures. 2016 Joint 8th International Conference on Soft Computing and Intelligent Systems (SCIS) and 17th International Symposium on Advanced Intelligent Systems (ISIS). pp. 400–403. doi:10.1109/SCIS-ISIS.2016.0091 
  11. Herr, Dominik; Han, Qi; Lohmann, Steffen; Ertl, Thomas (2016). Visual Clutter Reduction through Hierarchy-based Projection of High-dimensional Labeled Data (PDF). Graphics Interface. Graphics Interface (em inglês). doi:10.20380/gi2016.14. Consultado em 4 de novembro de 2022 
  12. Zhang, Wei; Wang, Xiaogang; Zhao, Deli; Tang, Xiaoou (2012). «Graph Degree Linkage: Agglomerative Clustering on a Directed Graph». In: Fitzgibbon, Andrew; Lazebnik, Svetlana; Perona, Pietro; Sato, Yoichi; Schmid, Cordelia. Computer Vision – ECCV 2012. Col: Lecture Notes in Computer Science (em inglês). 7572. [S.l.]: Springer Berlin Heidelberg. pp. 428–441. Bibcode:2012arXiv1208.5092Z. ISBN 9783642337185. arXiv:1208.5092 . doi:10.1007/978-3-642-33718-5_31  Veja também: https://github.com/waynezhanghk/gacluster
  13. Zhang, W.; Zhao, D.; Wang, X. (2013). «Agglomerative clustering via maximum incremental path integral». Pattern Recognition. 46 (11): 3056–65. Bibcode:2013PatRe..46.3056Z. CiteSeerX 10.1.1.719.5355 . doi:10.1016/j.patcog.2013.04.013 
  14. Zhao, D.; Tang, X. (2008). «Cyclizing clusters via zeta function of a graph». NIPS'08: Proceedings of the 21st International Conference on Neural Information Processing Systems. [S.l.]: Curran. pp. 1953–60. CiteSeerX 10.1.1.945.1649 . ISBN 9781605609492 
  15. Ma, Y.; Derksen, H.; Hong, W.; Wright, J. (2007). «Segmentation of Multivariate Mixed Data via Lossy Data Coding and Compression». IEEE Transactions on Pattern Analysis and Machine Intelligence. 29 (9): 1546–62. PMID 17627043. doi:10.1109/TPAMI.2007.1085. hdl:2142/99597  
  16. Fernández, Alberto; Gómez, Sergio (2008). «Resolvendo a Não-unicidade no Agrupamento Hierárquico Aglomerativo Usando Multidendrogramas». Journal of Classification. 25 (1): 43–65. arXiv:cs/0608049 . doi:10.1007/s00357-008-9004-x 
  17. Legendre, P.; Legendre, L.F.J. (2012). «Análise de Agrupamento §8.6 Reversões». Ecologia Numérica. Col: Desenvolvimento em Modelagem Ambiental. 24 3rd ed. [S.l.]: Elsevier. pp. 376–7. ISBN 978-0-444-53868-0 
  18. Kaufman, L.; Rousseeuw, P.J. (2009) [1990]. «6. Análise Divisiva (Programa DIANA)». Encontrando Grupos em Dados: Uma Introdução à Análise de Agrupamento. [S.l.]: Wiley. pp. 253–279. ISBN 978-0-470-31748-8 
  19. «Agrupamento Hierárquico · Clustering.jl». juliastats.org (em inglês). Consultado em 28 de fevereiro de 2022 
  20. «função hclust - RDocumentation». www.rdocumentation.org (em inglês). Consultado em 7 de junho de 2022 
  21. Galili, Tal; Benjamini, Yoav; Simpson, Gavin; Jefferis, Gregory (28 de outubro de 2021), dendextend: Extendendo a Funcionalidade de 'dendrograma' no R, consultado em 7 de junho de 2022 
  22. Paradis, Emmanuel; et al. «ape: Análises de Filogenética e Evolução». Consultado em 28 de dezembro de 2022 
  23. Fernández, Alberto; Gómez, Sergio (12 de setembro de 2021). «mdendro: Aglomeração Hierárquica Estendida». Consultado em 28 de dezembro de 2022