# Agrupamento hierárquico

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 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 ${\mathcal {O}}(2^{n})$) pode garantir encontrar a solução ótima.

## Complexidade

O algoritmo padrão para agrupamento aglomerativo hierárquico (AAH) tem uma complexidade de tempo de ${\mathcal {O}}(n^{3})$ e requer $\Omega (n^{2})$ 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 ${\mathcal {O}}(n^{2})$): SLINK para agrupamento por ligação única e CLINK para agrupamento por ligação completa. Com um heap, o tempo de execução do caso geral pode ser reduzido para ${\mathcal {O}}(n^{2}\log n)$, uma melhoria em relação ao limite mencionado de ${\mathcal {O}}(n^{3})$, 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 é ${\mathcal {O}}(2^{n})$, mas é comum usar heurísticas mais rápidas para escolher divisões, como 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:
| Nomes | Fórmula |
| Máximo ou agrupamento por ligação completa | $\max _{a\in A,\,b\in B}d(a,b)$ |
| Mínimo ou agrupamento por ligação única | $\min _{a\in A,\,b\in B}d(a,b)$ |
| Ligação média não ponderada (ou UPGMA) | ${\frac {1}{|A|\cdot |B|}}\sum _{a\in A}\sum _{b\in B}d(a,b).$ |
| Ligação média ponderada (ou WPGMA) | $d(i\cup j,k)={\frac {d(i,k)+d(j,k)}{2}}.$ |
| Ligação de centróide, ou UPGMC | $\lVert \mu _{A}-\mu _{B}\rVert ^{2}$ onde $\mu _{A}$ e $\mu _{B}$ são os centróides de A resp. B. |
| Ligação mediana, ou WPGMC | $d(i\cup j,k)=d(m_{i\cup j},m_{k})$ onde $m_{i\cup j}={\tfrac {1}{2}}\left(m_{i}+m_{j}\right)$ |
| Ligação versátil | ${\sqrt[{p}]{{\frac {1}{|A|\cdot |B|}}\sum _{a\in A}\sum _{b\in B}d(a,b)^{p}}},p\neq 0$ |
| Ligação de Ward, Aumento Mínimo da Soma dos Quadrados (MISSQ) | ${\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}$ |
| Soma Mínima de Erro dos Quadrados (MNSSQ) | $\sum _{x\in A\cup B}\lVert x-\mu _{A\cup B}\rVert ^{2}$ |
| Aumento Mínimo na Variância (MIVAR) | ${\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}$$={\text{Var}}(A\cup B)-{\text{Var}}(A)-{\text{Var}}(B)$ |
| Variância Mínima (MNVAR) | ${\frac {1}{|A\cup B|}}\sum _{x\in A\cup B}\lVert x-\mu _{A\cup B}\rVert ^{2}={\text{Var}}(A\cup B)$ |
| Ligação Mini-Max | $\min _{x\in A\cup B}\max _{y\in A\cup B}d(x,y)$ |
| Ligação de Hausdorff | $\max _{x\in A\cup B}\min _{y\in A\cup B}d(x,y)$ |
| Ligação de Medoid de Soma Mínima | $\min _{m\in A\cup B}\sum _{y\in A\cup B}d(m,y)$ tal que m é o medoid do agrupamento resultante |
| Ligação de Aumento de Soma Mínima de Medoid | $\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)$ |
| Ligação de Medoid | $d(m_{A},m_{B})$ onde $m_{A}$, $m_{B}$ são os medoids dos agrupamentos anteriores |
| Agrupamento de energia mínima | ${\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}$ |
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).
* 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.

## Exemplo de Agrupamento Aglomerativo

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:
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):
       $\max\{\,d(x,y):x\in A,\,y\in B\,\}.$
* A distância mínima entre elementos de cada agrupamento (também chamado de agrupamento por ligação simples):
       $\min\{\,d(x,y):x\in A,\,y\in B\,\}.$
* 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):
       ${1 \over {|A|\cdot |B|}}\sum _{x\in A}\sum _{y\in B}d(x,y).$
* 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)
* 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.
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 (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). Inicialmente, todos os dados estão no mesmo agrupamento e o maior agrupamento é dividido até que cada objeto esteja separado. Como existem $O(2^{n})$ 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 $C_{0}=\{1\dots n\}$ ser o conjunto de todos os $n$ índices de objetos e ${\mathcal {C}}=\{C_{0}\}$ o conjunto de todos os agrupamentos formados até agora.
* Itere o seguinte até que $|{\mathcal {C}}|=n$:
** Encontre o agrupamento atual com 2 ou mais objetos que tenha o maior diâmetro: $C_{*}=\arg \max _{C\in {\mathcal {C}}}\max _{i_{1},i_{2}\in C}\delta (i_{1},i_{2})$
** Encontre o objeto neste agrupamento com a maior dissimilaridade em relação ao restante do agrupamento: $i^{*}=\arg \max _{i\in C_{*}}{\frac {1}{|C_{*}|-1}}\sum _{j\in C_{*}\setminus \{i\}}\delta (i,j)$
** Retire $i^{*}$ do seu antigo agrupamento $C_{*}$ e coloque-o em um novo grupo fragmentado $C_{\textrm {new}}=\{i^{*}\}$.
** Enquanto $C_{*}$ não estiver vazio, continue migrando objetos de $C_{*}$ para adicioná-los a $C_{\textrm {new}}$. Para escolher quais objetos migrar, não considere apenas a dissimilaridade com $C_{*}$, mas também ajuste pela dissimilaridade com o grupo fragmentado: defina $i^{*}=\arg \max _{i\in C}D(i)$ onde definimos $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)$, então ou pare de iterar quando $D(i^{*})<0$, ou migre $i^{*}$.
** Adicione $C_{\textrm {new}}$ a ${\mathcal {C}}$.
Intuitivamente, $D(i)$ 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 $C_{\textrm {new}}$ seja um filho do agrupamento esvaziado $C_{*}$ a cada vez. Isso constrói uma árvore com $C_{0}$ como sua raiz e $n$ agrupamentos únicos de um único objeto como suas folhas.

## Software
### Implementações de código aberto

* 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, CLINK 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.
* 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 e pacotes que fornecem funções para agrupamento hierárquico.
* 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

* 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

* Cladística
* Dendrograma
* Filogenética computacional
* Hashing sensível à localidade
* Homologia persistente