Mostrar código-fonte de Agrupamento hierárquico

{{Descrição curta|Método estatístico de análise que busca construir uma hierarquia de agrupamentos}}{{Barra de aprendizagem de máquina}}
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 [[:en:Cluster_analysis|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 [[algoritmo guloso|gulosa]]. Os resultados do agrupamento hierárquico<ref>{{citar livro|primeiro=Frank |último=Nielsen |título=Introduction to HPC with MPI for Data Science |ano=2016 |publicado=Springer |isbn=978-3-319-21903-5 |páginas=195–211
|capítulo=8. Hierarchical Clustering | url=https://www.springer.com/gp/book/9783319219028 |capítulourl=https://www.researchgate.net/publication/314700681 }}</ref> 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 <math>\mathcal{O}(2^n)</math>) pode garantir encontrar a solução ótima.

== Complexidade ==
O algoritmo padrão para '''agrupamento aglomerativo hierárquico''' (AAH) tem uma [[complexidade de tempo]] de <math>\mathcal{O}(n^3)</math> e requer <math>\Omega(n^2)</math> 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 <math>\mathcal{O}(n^2)</math>): '''SLINK'''<!--negrito conforme WP:R#PLA--><ref name="SLINK">{{citar periódico|autor=R. Sibson |título=SLINK: an optimally efficient algorithm for the single-link cluster method |periódico=The Computer Journal | volume=16 |número=1 |páginas=30–34 |ano=1973 |publicado=British Computer Society | url=http://www.cs.gsu.edu/~wkim/index_files/papers/sibson.pdf | doi=10.1093/comjnl/16.1.30| doi-access=free }}</ref> para [[:en:Single-linkage_clustering|agrupamento por ligação única]] e CLINK<ref name="CLINK">{{citar periódico|autor=D. Defays |título=An efficient algorithm for a complete-link method |periódico=The Computer Journal | volume=20 |número=4 |páginas=364–6 |ano=1977 |publicado=British Computer Society | doi=10.1093/comjnl/20.4.364| doi-access= }}</ref> para [[:en:Complete-linkage_clustering|agrupamento por ligação completa]]. Com um [[heap]], o tempo de execução do caso geral pode ser reduzido para <math>\mathcal{O}(n^2 \log n)</math>, uma melhoria em relação ao limite mencionado de <math>\mathcal{O}(n^3)</math>, 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 é <math>\mathcal{O}(2^n)</math>, mas é comum usar heurísticas mais rápidas para escolher divisões, como [[agrupamento k-means|''k''-means]].

== Ligação entre Agrupamentos ==
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:<ref>{{citar web|título=The CLUSTER Procedure: Clustering Methods | url=https://support.sas.com/documentation/cdl/en/statug/63033/HTML/default/statug_cluster_sect012.htm |obra=SAS/STAT 9.2 Users Guide |publicado= [[SAS Institute]] |acessodata=2009-04-26}}</ref><ref>{{citar periódico|último1=Székely |primeiro1=G. J. |último2=Rizzo |primeiro2=M. L. |ano=2005 |título=Hierarchical clustering via Joint Between-Within Distances: Extending Ward's Minimum Variance Method |periódico=Journal of Classification |volume=22 |número=2 |páginas=151–183 |doi=10.1007/s00357-005-0012-9 |s2cid=206960007 }}</ref>
{|class="wikitable"
! Nomes
! Fórmula
|-
| Máximo ou [[:en:Complete-linkage_clustering|agrupamento por ligação completa]]
| <math> \max_{a\in A,\, b\in B} d(a,b) </math>
|-
| Mínimo ou [[:en:Single-linkage_clustering|agrupamento por ligação única]]
| <math> \min_{a\in A,\, b\in B} d(a,b) </math>
|-
| Ligação média não ponderada (ou [[:en:UPGMA|UPGMA]])
| <math> \frac{1}{|A|\cdot|B|} \sum_{a \in A }\sum_{ b \in B} d(a,b). </math>
|-
| Ligação média ponderada (ou [[:en:WPGMA|WPGMA]])
| <math> d(i \cup j, k) = \frac{d(i, k) + d(j, k)}{2}. </math>
|-
| Ligação de centróide, ou UPGMC
| <math>\lVert \mu_A-\mu_B\rVert^2</math> onde <math>\mu_A</math> e <math>\mu_B</math> são os centróides de ''A'' resp. ''B''.
|-
|Ligação mediana, ou WPGMC
|<math>d(i\cup j, k) = d(m_{i\cup j}, m_k)</math> onde <math>m_{i\cup j} = \tfrac12\left(m_i + m_j\right)</math>
|-
|Ligação versátil<ref>{{citar periódico| doi=10.1007/s00357-019-09339-z |último1=Fernández |primeiro1=Alberto |último2=Gómez |primeiro2=Sergio |título=Versatile linkage: a family of space-conserving strategies for agglomerative hierarchical clustering |periódico=Journal of Classification | volume=37 |ano=2020 |número=3 |páginas=584–597| arxiv=1906.09222 | s2cid=195317052 }}</ref>
| <math>\sqrt[p]{\frac{1}{|A|\cdot|B|} \sum_{a \in A }\sum_{ b \in B} d(a,b)^p}, p\neq 0</math>
|-
|[[:en:Ward's_method|Ligação de Ward]],<ref name="wards method">{{citar periódico|último=Ward |primeiro=Joe H. |ano=1963 |título=Hierarchical Grouping to Optimize an Objective Function |periódico=Journal of the American Statistical Association |volume=58 |número=301 |páginas=236–244 |doi=10.2307/2282967 |jstor=2282967 |mr=0148188}}</ref> Aumento Mínimo da Soma dos Quadrados (MISSQ)<ref name=":0">{{Citation |último=Podani |primeiro=János |título=New combinatorial clustering methods |data=1989 |url=https://doi.org/10.1007/978-94-009-2432-1_5 |obra=Numerical syntaxonomy |páginas=61–77 |editor-sobrenome=Mucina |editor-nome=L. |local=Dordrecht |publicado=Springer Netherlands |língua=en |doi=10.1007/978-94-009-2432-1_5 |isbn=978-94-009-2432-1 |acessodata=2022-11-04 |editor-sobrenome2=Dale |editor-nome2=M. B.}}</ref>
|<math>\frac{|A|\cdot|B|}{|A\cup B|} \lVert \mu_A - \mu_B \rVert ^2
= \sum_{x\in A\cup B} \lVert x - \mu_{A\cup B} \rVert^2
- \sum_{x\in A} \lVert x - \mu_{A} \rVert^2
- \sum_{x\in B} \lVert x - \mu_{B} \rVert^2</math>
|-
|Soma Mínima de Erro dos Quadrados (MNSSQ)<ref name=":0" />
|<math>\sum_{x\in A\cup B} \lVert x - \mu_{A\cup B} \rVert^2</math>
|-
|Aumento Mínimo na Variância (MIVAR)<ref name=":0" />
|<math>\frac{1}{|A\cup B|}\sum_{x\in A\cup B} \lVert x - \mu_{A\cup B} \rVert^2
- \frac{1}{|A|}\sum_{x\in A} \lVert x - \mu_{A} \rVert^2
- \frac{1}{|B|}\sum_{x\in B} \lVert x - \mu_{B} \rVert^2</math><math>= \text{Var}(A\cup B) - \text{Var}(A) - \text{Var}(B)</math>
|-
|Variância Mínima (MNVAR)<ref name=":0" />
|<math>\frac{1}{|A\cup B|}\sum_{x\in A\cup B} \lVert x - \mu_{A\cup B} \rVert^2 = \text{Var}(A\cup B)</math>
|-
|Ligação Mini-Max<ref>{{citar periódico|último1=Ao |primeiro1=S. I. |último2=Yip |primeiro2=K. |último3=Ng |primeiro3=M. |último4=Cheung |primeiro4=D. |último5=Fong |primeiro5=P.-Y. |último6=Melhado |primeiro6=I. |último7=Sham |primeiro7=P. C. |data=2004-12-07 |título=CLUSTAG: hierarchical clustering and graph methods for selecting tag SNPs |periódico=Bioinformatics |volume=21 |número=8 |páginas=1735–1736 |doi=10.1093/bioinformatics/bti201 |pmid=15585525 |issn=1367-4803|doi-access=free }}</ref>
|<math>\min_{x\in A\cup B} \max_{y\in A\cup B} d(x,y)</math>
|-
|Ligação de Hausdorff<ref>{{citar periódico|último1=Basalto |primeiro1=Nicolas |último2=Bellotti |primeiro2=Roberto |último3=De Carlo |primeiro3=Francesco |último4=Facchi |primeiro4=Paolo |último5=Pantaleo |primeiro5=Ester |último6=Pascazio |primeiro6=Saverio |data=2007-06-15 |título=Hausdorff clustering of financial time series |url=https://www.sciencedirect.com/science/article/pii/S0378437107001124 |periódico=Physica A: Statistical Mechanics and Its Applications |língua=en |volume=379 |número=2 |páginas=635–644 |doi=10.1016/j.physa.2007.01.011 |arxiv=physics/0504014 |bibcode=2007PhyA..379..635B |s2cid=27093582 |issn=0378-4371}}</ref>
|<math>\max_{x\in A\cup B} \min_{y\in A\cup B} d(x,y)</math>
|-
|Ligação de Medoid de Soma Mínima<ref name=":1">{{citar conferência|último=Schubert |primeiro=Erich |data=2021 |título=HACAM: Hierarchical Agglomerative Clustering Around Medoids – and its Limitations |url=http://star.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-2993/paper-19.pdf |conferencia=LWDA’21: Lernen, Wissen, Daten, Analysen September 01–03, 2021, Munich, Germany |páginas=191–204 |via=CEUR-WS}}</ref>
|<math>\min_{m\in A\cup B} \sum_{y\in A\cup B} d(m, y)</math> tal que m é o medoid do agrupamento resultante
|-
|Ligação de Aumento de Soma Mínima de Medoid<ref name=":1" />
|<math>\min_{m\in A\cup B} \sum_{y\in A\cup B} d(m,y)
- \min_{m\in A} \sum_{y\in A} d(m,y)
- \min_{m\in B} \sum_{y\in B} d(m,y)</math>
|-
|Ligação de Medoid<ref>{{citar conferência|último1=Miyamoto |primeiro1=Sadaaki |último2=Kaizu |primeiro2=Yousuke |último3=Endo |primeiro3=Yasunori |data=2016 |título=Hierarchical and Non-Hierarchical Medoid Clustering Using Asymmetric Similarity Measures |url=https://ieeexplore.ieee.org/document/7801678 |conferencia=2016 Joint 8th International Conference on Soft Computing and Intelligent Systems (SCIS) and 17th International Symposium on Advanced Intelligent Systems (ISIS) |páginas=400–403 |doi=10.1109/SCIS-ISIS.2016.0091}}</ref><ref>{{citar conferência|data=2016 |título=Visual Clutter Reduction through Hierarchy-based Projection of High-dimensional Labeled Data|conferencia=Graphics Interface |url=https://graphicsinterface.org/wp-content/uploads/gi2016-14.pdf |primeiro1=Dominik|último1=Herr|primeiro2=Qi|último2=Han|primeiro3=Steffen|último3=Lohmann|primeiro4=Thomas |último4=Ertl |acessodata=2022-11-04 |website=Graphics Interface |língua=en-CA |doi=10.20380/gi2016.14}}</ref>
|<math>d(m_A, m_B)</math> onde <math>m_A</math>, <math>m_B</math> são os medoids dos agrupamentos anteriores
|-
| [[:en:Energy_distance|Agrupamento de energia mínima]]
| <math>  \frac {2}{nm}\sum_{i,j=1}^{n,m} \|a_i- b_j\|_2 - \frac {1}{n^2}\sum_{i,j=1}^{n} \|a_i-a_j\|_2 - \frac{1}{m^2}\sum_{i,j=1}^{m} \|b_i-b_j\|_2 </math>
|}
Alguns desses só podem ser recalculados recursivamente (WPGMA, WPGMC), para muitos um cálculo recursivo com equações de [[:en:Lance_Williams_(graphics_researcher)|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).<ref>{{citar livro|último1=Zhang|primeiro1=Wei|último2=Wang|primeiro2=Xiaogang|último3=Zhao|primeiro3=Deli|último4=Tang|primeiro4=Xiaoou|título=Computer Vision – ECCV 2012 |capítulo=Graph Degree Linkage: Agglomerative Clustering on a Directed Graph |data=2012|editor-sobrenome=Fitzgibbon|editor-nome=Andrew|editor-sobrenome2=Lazebnik|editor-nome2=Svetlana|editor2-link= Svetlana Lazebnik |editor-sobrenome3=Perona|editor-nome3=Pietro|editor-sobrenome4=Sato|editor-nome4=Yoichi|editor-sobrenome5=Schmid|editor-nome5=Cordelia|series=Lecture Notes in Computer Science|língua=en|publicado=Springer Berlin Heidelberg|volume=7572|páginas=428–441|doi=10.1007/978-3-642-33718-5_31|isbn=9783642337185|arxiv=1208.5092|bibcode=2012arXiv1208.5092Z|s2cid=14751}} Veja também: https://github.com/waynezhanghk/gacluster</ref>
* 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.<ref>{{citar periódico|primeiro1=W. |último1=Zhang |primeiro2=D. |último2=Zhao |primeiro3=X. |último3=Wang |título=Agglomerative clustering via maximum incremental path integral |periódico=Pattern Recognition |volume=46 |número=11 |páginas=3056–65 |data=2013 |doi=10.1016/j.patcog.2013.04.013 |citeseerx=10.1.1.719.5355 |bibcode=2013PatRe..46.3056Z}}</ref><ref>{{citar livro|último1=Zhao |primeiro1=D. |último2=Tang |primeiro2=X. |capítulo=Cyclizing clusters via zeta function of a graph |capítulourl= |título=NIPS'08: Proceedings of the 21st International Conference on Neural Information Processing Systems |data=2008 |isbn=9781605609492 |páginas=1953–60 |publicado=Curran |citeseerx=10.1.1.945.1649}}</ref><ref>{{citar periódico|primeiro1=Y. |último1=Ma |primeiro2=H. |último2=Derksen |primeiro3=W. |último3=Hong |primeiro4=J. |último4=Wright |título=Segmentation of Multivariate Mixed Data via Lossy Data Coding and Compression |periódico=IEEE Transactions on Pattern Analysis and Machine Intelligence |volume=29 |número=9 |páginas=1546–62 |data=2007 |doi=10.1109/TPAMI.2007.1085 |pmid=17627043 |hdl=2142/99597 |s2cid=4591894 |hdl-access=free }}</ref>

== Exemplo de Agrupamento Aglomerativo ==

[[Imagem:Clusters.svg|quadro|nenhum|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:

[[Imagem:Hierarchical clustering simple diagram.svg|quadro|nenhum|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):
::<math> \max \{\, d(x,y) : x \in A,\, y \in B\,\}. </math>
* A '''distância mínima''' entre elementos de cada agrupamento (também chamado de agrupamento por ligação simples):
::<math> \min \{\, d(x,y) : x \in A,\, y \in B \,\}. </math>
* 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):
::<math> {1 \over {|A|\cdot|B|}}\sum_{x \in A}\sum_{ y \in B} d(x,y). </math>
* 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<ref name="wards method"/>)
* 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.<ref>{{citar periódico| doi=10.1007/s00357-008-9004-x |último1=Fernández |primeiro1=Alberto |último2=Gómez |primeiro2=Sergio |título=Resolvendo a Não-unicidade no Agrupamento Hierárquico Aglomerativo Usando Multidendrogramas |periódico=Journal of Classification | volume=25 |ano=2008 |número=1 |páginas=43–65| arxiv=cs/0608049 | s2cid=434036 }}</ref>

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<ref>{{citar livro|primeiro1=P. |último1=Legendre |primeiro2=L.F.J. |último2=Legendre |capítulo=Análise de Agrupamento §8.6 Reversões |título=Ecologia Numérica |capítulourl=https://books.google.com/books?id=DKlUIQcHhOsC&pg=PA376 |data=2012 |publicado=Elsevier |isbn=978-0-444-53868-0 |páginas=376–7 |edição=3rd |series=Desenvolvimento em Modelagem Ambiental |volume=24}}</ref> (inversões, desvios da ultrametricidade) podem ocorrer.

== Agrupamento Divisivo ==

O princípio básico do agrupamento divisivo foi publicado como o algoritmo DIANA (Análise Divisiva de Agrupamento).<ref>{{citar livro|primeiro1=L. |último1=Kaufman |primeiro2=P.J. |último2=Rousseeuw |capítulo=6. Análise Divisiva (Programa DIANA) |título=Encontrando Grupos em Dados: Uma Introdução à Análise de Agrupamento |capítulourl=https://books.google.com/books?id=YeFQHiikNo0C&pg=PA253 |anooriginal=1990 |data=2009 |publicado=Wiley |isbn=978-0-470-31748-8 |páginas=253–279}}</ref> Inicialmente, todos os dados estão no mesmo agrupamento e o maior agrupamento é dividido até que cada objeto esteja separado.
Como existem <math>O(2^n)</math> 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:

# Deixe <math>C_0 = \{1\dots n\}</math> ser o conjunto de todos os <math>n</math> índices de objetos e <math>\mathcal{C} = \{C_0\}</math> o conjunto de todos os agrupamentos formados até agora.
# Itere o seguinte até que <math>|\mathcal{C}| = n</math>:
## Encontre o agrupamento atual com 2 ou mais objetos que tenha o maior diâmetro: <math>C_* = \arg\max_{C\in \mathcal{C}} \max_{i_1,i_2\in C} \delta(i_1,i_2)</math>
## Encontre o objeto neste agrupamento com a maior dissimilaridade em relação ao restante do agrupamento: <math>i^* = \arg\max_{i\in C_*} \frac{1}{|C_*|-1}\sum_{j\in C_*\setminus\{i\}} \delta(i,j)</math>
## Retire <math>i^*</math> do seu antigo agrupamento <math>C_*</math> e coloque-o em um novo <i>grupo fragmentado</i> <math>C_\textrm{new} = \{i^*\}</math>.
## Enquanto <math>C_*</math> não estiver vazio, continue migrando objetos de <math>C_*</math> para adicioná-los a <math>C_\textrm{new}</math>. Para escolher quais objetos migrar, não considere apenas a dissimilaridade com <math>C_*</math>, mas também ajuste pela dissimilaridade com o grupo fragmentado: defina <math>i^* = \arg\max_{i\in C} D(i)</math> onde definimos <math>D(i) = \frac{1}{|C_*|-1}\sum_{j\in C_*\setminus\{i\}} \delta(i,j) - \frac{1}{|C_\textrm{new}|}\sum_{j\in C_\textrm{new}} \delta(i,j)</math>, então ou pare de iterar quando <math>D(i^*) < 0</math>, ou migre <math>i^*</math>.
## Adicione <math>C_\textrm{new}</math> a <math>\mathcal{C}</math>.

Intuitivamente, <math>D(i)</math> 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 <math>C_\textrm{new}</math> seja um filho do agrupamento esvaziado <math>C_*</math> a cada vez. Isso constrói uma árvore com <math>C_0</math> como sua raiz e <math>n</math> agrupamentos únicos de um único objeto como suas folhas.

== Software ==

=== Implementações de código aberto ===

[[Arquivo:Iris dendrogram.png|miniatura|Dendrograma de agrupamento hierárquico do conjunto de dados da flor Iris (usando [[R (linguagem de programação)|R]]). [https://cran.r-project.org/web/packages/dendextend/vignettes/Cluster_Analysis.html Fonte] ]]

[[Arquivo:Orange-data-mining-hierarchical-clustering.png|miniatura|Visualização interativa de dendrograma e agrupamento hierárquico na suíte de mineração de dados [[Orange (software)|Orange]].]]

* [[:en:ALGLIB|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³).
* [[:en:ELKI|ELKI]] inclui múltiplos algoritmos de agrupamento hierárquico, várias estratégias de ligação e também inclui os algoritmos eficientes SLINK,<ref name="SLINK" /> CLINK<ref name="CLINK" /> e Anderberg, extração flexível de agrupamentos de dendrogramas e vários outros algoritmos de análise de agrupamento.
* [[Julia (linguagem de programação)|Julia]] tem uma implementação dentro do pacote Clustering.jl.<ref>{{citar web|título=Agrupamento Hierárquico · Clustering.jl |url=https://juliastats.org/Clustering.jl/stable/hclust.html |acessodata=2022-02-28 |website=juliastats.org |língua=en}}</ref>
* [[GNU Octave|Octave]], o análogo do [[GNU]] para [[MATLAB]] implementa agrupamento hierárquico na função "linkage".
* [[Orange (software)|Orange]], uma suíte de software de mineração de dados, inclui agrupamento hierárquico com visualização interativa de dendrograma.
* [[R (linguagem de programação)|R]] possui funções internas<ref>{{citar web|título=função hclust - RDocumentation |url=https://www.rdocumentation.org/packages/stats/versions/3.6.2/topics/hclust |acessodata=2022-06-07 |website=www.rdocumentation.org |língua=en}}</ref> e pacotes que fornecem funções para agrupamento hierárquico.<ref>{{Citation |último1=Galili |primeiro1=Tal |título=dendextend: Extendendo a Funcionalidade de 'dendrograma' no R|data=2021-10-28 |url=https://cran.r-project.org/package=dendextend |acessodata=2022-06-07 |último2=Benjamini |primeiro2=Yoav |último3=Simpson |primeiro3=Gavin |último4=Jefferis |primeiro4=Gregory}}</ref><ref>{{citar web|último1=Paradis|primeiro1=Emmanuel|display-authors=etal |título=ape: Análises de Filogenética e Evolução|url=https://cran.r-project.org/web/packages/ape/index.html|acessodata=2022-12-28}}</ref><ref>{{citar web|último1=Fernández|primeiro1=Alberto|último2=Gómez|primeiro2=Sergio|data=2021-09-12|título=mdendro: Aglomeração Hierárquica Estendida|url=https://sergio-gomez.github.io/mdendro/|acessodata=2022-12-28}}</ref>
* [[SciPy]] implementa agrupamento hierárquico em Python, incluindo o algoritmo SLINK eficiente.
* [[Scikit-learn]] também implementa agrupamento hierárquico em Python.
* [[:en:Weka_(software)|Weka]] inclui análise de agrupamento hierárquico.

=== Implementações comerciais ===
* [[MATLAB]] inclui análise de agrupamento hierárquico.
* [[SAS System|SAS]] inclui análise de agrupamento hierárquico no PROC CLUSTER.
* [[Mathematica]] inclui um Pacote de Agrupamento Hierárquico.
* [[:en:NCSS_(statistical_software)|NCSS]] inclui análise de agrupamento hierárquico.
* [[SPSS]] inclui análise de agrupamento hierárquico.
* [[:en:Qlucore|Qlucore]] Omics Explorer inclui análise de agrupamento hierárquico.
* [[Stata]] inclui análise de agrupamento hierárquico.
* [[:en:CrimeStat|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 ==
{{Div col|colwidth=20em}}
* [[Cladística]]
* [[Dendrograma]]
* [[Filogenética computacional]]
* [[Hashing sensível à localidade]]
* [[Homologia persistente]]{{Div col end}}

== Referências ==
{{Reflist|30em}}

{{Authority control}}

{{DEFAULTSORT:Hierarchical Clustering}}
[[Categoria:Network analysis]]
[[Categoria:Cluster analysis algorithms]]