Agrupamento hierárquico

O algoritmo padrão para agrupamento aglomerativo hierárquico (AAH) tem uma complexidade de tempo de O ( n 3 ) {\displaystyle {\mathcal {O}}(n^{3})} e requer Ω ( n 2 ) {\displaystyle \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 O ( n 2 ) {\displaystyle {\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 O ( n 2 log ⁡ n ) {\displaystyle {\mathcal {O}}(n^{2}\log n)} , uma melhoria em relação ao limite mencionado de O ( n 3 ) {\displaystyle {\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.

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.

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.

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 ) {\displaystyle 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ó.