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

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):

$\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:

1. 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.
2. Itere o seguinte até que $|{\mathcal {C}}|=n$:
   1. 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})$
   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)$
   3. Retire $i^{*}$ do seu antigo agrupamento $C_{*}$ e coloque-o em um novo grupo fragmentado $C_{\textrm {new}}=\{i^{*}\}$.
   4. 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^{*}$.
   5. 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

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, 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