Clustering de ligação completa

O clustering de ligação completa é um dos vários métodos de clustering hierárquico aglomerativo . No início do processo, cada elemento está em um cluster próprio. Os clusters são então combinados sequencialmente em clusters maiores até que todos os elementos acabem no mesmo cluster. O método também é conhecido como agrupamento de vizinhos mais distantes . O resultado do agrupamento pode ser visualizado como um dendograma , que mostra a sequência de fusão do agrupamento e a distância em que ocorreu cada fusão. [1] [2] [3]

Procedimento de agrupamento

Em cada etapa, os dois clusters separados pela menor distância são combinados. A definição de 'distância mais curta' é o que diferencia os diferentes métodos de agrupamento aglomerativo. No clustering de ligação completa, o link entre dois clusters contém todos os pares de elementos, e a distância entre os clusters é igual à distância entre os dois elementos (um em cada cluster) que estão mais distantes um do outro. O mais curto desses links que permanece em qualquer etapa causa a fusão dos dois clusters cujos elementos estão envolvidos.

Matematicamente, a função de ligação completa – a distância entre clusters e – é descrita pela seguinte expressão:

onde

  • é a distância entre os elementos e  ;
  • e são dois conjuntos de elementos (clusters).

Algoritmos

Esquema ingênuo

O algoritmo a seguir é um esquema aglomerativo que apaga linhas e colunas em uma matriz de proximidade à medida que clusters antigos são mesclados em novos. A matriz de proximidade D contém todas as distâncias d ( i , j ). Os agrupamentos recebem números de sequência 0,1,......, ( n  − 1) e L ( k ) é o nível do k-ésimo agrupamento. Um cluster com número de sequência m é denotado ( m ) e a proximidade entre clusters ( r ) e ( s ) é denotada d [( r ),( s )].

O algoritmo completo de clustering de ligação consiste nas seguintes etapas:

  1. Comece com o agrupamento disjunto tendo nível e número de sequência .
  2. Encontre o par de clusters mais semelhante no cluster atual, digamos pair , de acordo com onde o máximo está sobre todos os pares de clusters no cluster atual.
  3. Aumente o número de sequência: . Mesclar clusters em um único cluster para formar o próximo cluster . Defina o nível deste cluster como
  4. Atualize a matriz de proximidade, excluindo as linhas e colunas correspondentes aos clusters e adicionando uma linha e coluna correspondentes ao cluster recém-formado. A proximidade entre o novo cluster, denotado , e um cluster antigo é definida como .
  5. Se todos os objetos estiverem em um cluster, pare. Caso contrário, vá para a etapa 2.

Esquema idealmente eficiente

O algoritmo explicado acima é fácil de entender, mas complexo . Em maio de 1976, D. Defays propôs um algoritmo otimamente eficiente de apenas complexidade conhecido como CLINK (publicado em 1977) [4] inspirado no algoritmo semelhante SLINK para clustering de ligação única .

Exemplo de trabalho

O exemplo prático é baseado em uma matriz de distância genética JC69 calculada a partir do alinhamento da sequência de RNA ribossômico 5S de cinco bactérias: Bacillus subtilis ( ), Bacillus stearothermophilus ( ), Lactobacillus viridescens ( ), Acholeplasma modicum ( ) e Micrococcus luteus ( ). [5] [6]

Primeiro passo

  • Primeiro agrupamento

Suponhamos que temos cinco elementos e a seguinte matriz de distâncias aos pares entre eles:

a b c d e
a 0 17 21 31 23
b 17 0 30 34 21
c 21 30 0 28 39
d 31 34 28 0 43
e 23 21 39 43 0

Neste exemplo, é o menor valor de , então juntamos os elementos e .

  • Estimativa do comprimento do primeiro ramo

Vamos denotar o nó ao qual e agora estão conectados. A configuração garante que os elementos e sejam equidistantes de . Isso corresponde à expectativa da hipótese de ultrametricidade . Os ramos se unem e passam a ter comprimentos ( veja o dendograma final )

  • Primeira atualização da matriz de distância

Em seguida, procedemos à atualização da matriz de proximidade inicial em uma nova matriz de proximidade (veja abaixo), reduzida em tamanho em uma linha e uma coluna devido ao agrupamento de with . Os valores em negrito correspondem às novas distâncias, calculadas mantendo a distância máxima entre cada elemento do primeiro cluster e cada um dos restantes elementos:

Os valores em itálico não são afetados pela atualização da matriz, pois correspondem a distâncias entre elementos não envolvidos no primeiro cluster.

Segundo passo

  • Segundo agrupamento

Reiteramos agora os três passos anteriores, partindo da nova matriz de distância  :

(a,b) c d e
(a,b) 0 30 34 23
c 30 0 28 39
d 34 28 0 43
e 23 39 43 0

Aqui, está o valor mais baixo de , então unimos cluster com elemento .

  • Estimativa do comprimento do segundo ramo

Vamos denotar o nó ao qual e agora estão conectados. Devido à restrição de ultrametricidade, os ramos que unem or to e to são iguais e têm o seguinte comprimento total:

Deduzimos o comprimento do ramo que falta: ( veja o dendograma final )

  • Atualização da segunda matriz de distância

Em seguida, procedemos à atualização da matriz em uma nova matriz de distância (veja abaixo), reduzida em tamanho em uma linha e uma coluna devido ao agrupamento de with  :

Terceiro passo

  • Terceiro agrupamento

Reiteramos novamente as três etapas anteriores, partindo da matriz de distância atualizada .

((a,b),e) c d
((a,b),e) 0 39 43
c 39 0 28
d 43 28 0

Aqui, está o menor valor de , então juntamos os elementos e .

  • Estimativa do comprimento do terceiro ramo

Vamos denotar o nó ao qual e agora estão conectados. Os ramos se unem e passam a ter comprimentos ( veja o dendograma final )

  • Atualização da terceira matriz de distância

Há uma única entrada para atualizar:

Passo final

A matriz final é:

((a,b),e) (cd)
((a,b),e) 0 43
(cd) 43 0

Então, juntamos clusters e .

Vamos denotar o nó (raiz) ao qual e agora estão conectados. Os ramos se unem e passam a ter comprimentos:

Deduzimos os dois comprimentos de ramificação restantes:

O dendograma de ligação completa

Dados do Dendrograma WPGMA 5S
Dados do Dendrograma WPGMA 5S

O dendograma agora está completo. É ultramétrico porque todas as pontas ( a ) são equidistantes de  :

O dendograma é, portanto , enraizado em seu nó mais profundo.

Comparação com outras ligações

Esquemas de ligação alternativos incluem agrupamento de ligação única e agrupamento de ligação média - implementar uma ligação diferente no algoritmo ingênuo é simplesmente uma questão de usar uma fórmula diferente para calcular distâncias entre clusters no cálculo inicial da matriz de proximidade e na etapa 4 acima algoritmo. No entanto, um algoritmo idealmente eficiente não está disponível para ligações arbitrárias. A fórmula que deve ser ajustada foi destacada em negrito.

O agrupamento de ligação completa evita uma desvantagem do método alternativo de ligação única - o chamado fenômeno de encadeamento , onde clusters formados por meio de agrupamento de ligação única podem ser forçados a se unir devido a elementos únicos estarem próximos uns dos outros, mesmo que muitos dos elementos em cada cluster podem estar muito distantes um do outro. A ligação completa tende a encontrar aglomerados compactos de diâmetros aproximadamente iguais. [7]

Comparação de dendrogramas obtidos sob diferentes métodos de agrupamento a partir da mesma matriz de distâncias.
Clustering de ligação única . Clustering de ligação completa. Clustering de ligação médio: WPGMA . Clustering de ligação médio: UPGMA .

Veja também

Referências

  1. ^ Sorensen T (1948). “Um método para estabelecer grupos de igual amplitude na sociologia vegetal com base na similaridade de espécies e sua aplicação às análises da vegetação em áreas comuns dinamarquesas”. Biologiske Skrifter . 5 : 1–34.
  2. ^ Legendre P, Legendre L (1998). Ecologia Numérica (segunda edição em inglês). pág. 853.
  3. ^ Everitt BS, Landau S , Leese M (2001). Análise de Cluster (Quarta ed.). Londres: Arnold. ISBN 0-340-76119-9.
  4. ^ Desafia D (1977). “Um algoritmo eficiente para um método de link completo”. O Jornal de Informática . 20 (4). Sociedade Britânica de Computação: 364–366. doi :10.1093/comjnl/20.4.364.
  5. ^ Erdmann VA, Wolters J (1986). "Coleção de sequências de RNA ribossômico 5S, 5.8S e 4.5S publicadas". Pesquisa de ácidos nucléicos . 14 Suplemento (Suplemento): r1-59. doi :10.1093/nar/14.suppl.r1. PMC341310 .PMID2422630  . 
  6. ^ Olsen GJ (1988). Análise filogenética utilizando RNA ribossômico . Métodos em Enzimologia. Vol. 164. pp. doi :10.1016/s0076-6879(88)64084-5. PMID3241556  .
  7. ^ Everitt, Landau e Leese (2001), pp.

Leitura adicional

  • Späth H (1980). Algoritmos de Análise de Cluster . Chichester: Ellis Horwood.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Complete-linkage_clustering&oldid=1190349026"