Agrupamento de ligação única

Da Wikipédia, a enciclopédia livre

Nas estatísticas , o agrupamento de ligação única é um dos vários métodos de agrupamento hierárquico . Baseia-se no agrupamento de clusters de baixo para cima (agglomerative clustering), em cada etapa combinando dois clusters que contêm o par mais próximo de elementos que ainda não pertencem ao mesmo cluster.

Este método tende a produzir clusters longos e finos nos quais os elementos próximos do mesmo cluster têm pequenas distâncias, mas os elementos nas extremidades opostas de um cluster podem estar muito mais distantes um do outro do que dois elementos de outros clusters. Para algumas classes de dados, isso pode levar a dificuldades na definição de classes que possam subdividir os dados de maneira útil. [1] No entanto, é popular na astronomia para analisar aglomerados de galáxias , que muitas vezes podem envolver longas cadeias de matéria; neste aplicativo, também é conhecido como algoritmo de amigos de amigos. [2]

Visão geral dos métodos de agrupamento aglomerativo

No início do processo de agrupamento aglomerativo, cada elemento está em um cluster próprio. Os clusters são então combinados sequencialmente em clusters maiores, até que todos os elementos fiquem no mesmo cluster. A cada passo, os dois clusters separados pela menor distância são combinados. A função utilizada para determinar a distância entre dois clusters, conhecida como função de ligação , é o que diferencia os métodos de agrupamento aglomerativo.

No clustering de ligação única, a distância entre dois clusters é determinada por um único par de elementos: aqueles dois elementos (um em cada cluster) que estão mais próximos um do outro. A menor dessas distâncias pareadas que permanecem em qualquer etapa faz com que os dois clusters cujos elementos estão envolvidos sejam mesclados. O método também é conhecido como agrupamento de vizinho mais próximo . O resultado do agrupamento pode ser visualizado como um dendrograma , que mostra a sequência em que os agrupamentos foram mesclados e a distância em que cada fusão ocorreu. [3]

Matematicamente, a função de ligação – a distância D ( X , Y ) entre os clusters X e Y – é descrita pela expressão

onde X e Y são quaisquer dois conjuntos de elementos considerados como clusters, e d ( x , y ) denota a distância entre os dois elementos x e y .

Algoritmo 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. Omatriz de proximidadecontém todas as distâncias. Os agrupamentos recebem números de sequênciaeé o nível do-th agrupamento. Um cluster com número de sequência m é denotado por ( m ) e a proximidade entre os clusterseé denotado.

O algoritmo de ligação única é composto das 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 clustering atual, digamos par, de acordo comonde o mínimo é sobre todos os pares de clusters no clustering atual.
  3. Incremente o número de sequência:. Mesclar clusterseem um único cluster para formar o próximo clustering. Defina o nível desse agrupamento como
  4. Atualize a matriz de proximidade,, excluindo as linhas e colunas correspondentes aos clustersee adicionando uma linha e coluna correspondente ao cluster recém-formado. A proximidade entre o novo cluster, denotadoe um cluster antigoé definido como.
  5. Se todos os objetos estiverem em um cluster, pare. Caso contrário, vá para a etapa 2.

Exemplo de trabalho

Este exemplo de trabalho é 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 moderado () e Micrococcus luteus (). [4] [5]

Primeiro passo

  • Primeiro agrupamento

Suponhamos que temos cinco elementose a seguinte matrizde distâncias pareadas 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 agrupamos os elementos a e b .

  • Primeira estimativa do comprimento do ramo

Seja u o nó ao qual a e b estão agora conectados. Contexto garante que os elementos a e b sejam equidistantes de u . Isso corresponde à expectativa da hipótese de ultrametricidade . Os ramos que unem a e b a u têm comprimentos ( veja o dendrograma final )

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

Em seguida, procedemos à atualização da matriz de proximidade inicialem uma nova matriz de proximidade(veja abaixo), reduzido em tamanho em uma linha e uma coluna devido ao agrupamento de a com b . Valores em negrito emcorrespondem às novas distâncias, calculadas mantendo a distância mínima entre cada elemento do primeiro clustere cada um dos restantes elementos:

Valores em itálico emnã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 as três ações anteriores, partindo da nova matriz de distância :

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

Aqui, e são os valores mais baixos de, então nos juntamos ao clustercom elemento c e com elemento e .

  • Estimativa do comprimento do segundo ramo

Seja v denotando o nó ao qual, c e e agora estão conectados. Devido à restrição de ultrametricidade, os ramos que unem a ou b a v , e c a v , e também e a v são iguais e têm o seguinte comprimento total:

Deduzimos o comprimento do ramo ausente:

( veja o dendrograma final )
  • Atualização da matriz de segunda distância

Em seguida, procedemos à atualização domatriz em uma nova matriz de distância(veja abaixo), reduzido em tamanho por duas linhas e duas colunas por causa do agrupamento decom c e com e  :

Etapa final

O finalmatriz é:

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

Então nos juntamos a clusterse.

Deixardenotar o nó (raiz) ao qualeagora estão conectados. Os ramos que se unemeparaentão tem comprimentos:

Deduzimos o comprimento restante do ramo:

O dendrograma de ligação única

Dados 5S do Dendrograma de Ligação Única

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

O dendrograma é, portanto, enraizado por, seu nó mais profundo.

Outras ligações

O algoritmo ingênuo para agrupamento de ligação única é essencialmente o mesmo que o algoritmo de Kruskal para árvores geradoras mínimas . No entanto, no clustering de ligação única, a ordem em que os clusters são formados é importante, enquanto para as árvores geradoras mínimas o que importa é o conjunto de pares de pontos que formam as distâncias escolhidas pelo algoritmo.

Esquemas de ligação alternativos incluem agrupamento de ligação completa , agrupamento de ligação média ( UPGMA e WPGMA ) e o método de Ward . No algoritmo ingênuo para clustering aglomerativo, a implementação de um esquema de ligação diferente pode ser realizada simplesmente usando uma fórmula diferente para calcular distâncias entre clusters no algoritmo. A fórmula que deve ser ajustada foi destacada usando texto em negrito na descrição do algoritmo acima. No entanto, algoritmos mais eficientes, como o descrito abaixo, não generalizam para todos os esquemas de ligação da mesma maneira.

Comparação de dendrogramas obtidos em diferentes métodos de agrupamento a partir de uma mesma matriz de distâncias .
Ligação simples-5S.svg
Ligação completa Dendrogram 5S data.svg
WPGMA Dendrogram 5S data.svg
UPGMA Dendrogram 5S data.svg
Agrupamento de ligação única Clustering de ligação completa Agrupamento de link médio: WPGMA Agrupamento de link médio: UPGMA

Algoritmos mais rápidos

O algoritmo ingênuo para clustering de ligação única é fácil de entender, mas lento, com complexidade de tempo. [6] Em 1973, R. Sibson propôs um algoritmo com complexidade de tempoe complexidade do espaço(ambos ótimos) conhecidos como SLINK. O algoritmo slink representa um agrupamento em um conjunto deitens numerados por duas funções. Essas funções são determinadas por encontrar o menor clusterque contém ambos os itens e pelo menos um item de numeração maior. A primeira função,, itens de mapas para o item de maior número no cluster. A segunda função,, itens de mapas à distância associada à criação do cluster. Armazenar essas funções em dois arrays que mapeiam cada número de item para seu valor de função ocupa espaço, e essas informações são suficientes para determinar o agrupamento em si. Como mostra Sibson, quando um novo item é adicionado ao conjunto de itens, as funções atualizadas que representam o novo agrupamento de ligação única para o conjunto aumentado, representado da mesma maneira, podem ser construídas a partir do antigo agrupamento no tempo. O algoritmo SLINK faz um loop sobre os itens, um por um, adicionando-os à representação do agrupamento. [7] [8]

Um algoritmo alternativo, rodando nos mesmos limites ótimos de tempo e espaço, é baseado na equivalência entre o algoritmo ingênuo e o algoritmo de Kruskal para árvores geradoras mínimas. Em vez de usar o algoritmo de Kruskal, pode-se usar o algoritmo de Prim , em uma variação sem heaps binários que leva tempoe espaçopara construir a árvore geradora mínima (mas não o agrupamento) dos itens e distâncias fornecidos. Então, aplicando o algoritmo de Kruskal ao grafo esparso formado pelas arestas da árvore geradora mínima produz o próprio agrupamento em um tempo adicionale espaço. [9]

Veja também

Referências

  1. ^ Everitt B (2011). Análise de cluster . Chichester, West Sussex, Reino Unido: Wiley. ISBN  9780470749913.
  2. ^ Feigelson, Eric (2012). "Classificação em astronomia: passado e presente". Em Way, Michael J.; Scargle, Jeffrey D.; Ali, Kamal M.; Srivastava, Ashok N. (eds.). Avanços em Aprendizado de Máquina e Mineração de Dados para Astronomia . Chapman e Hall/CRC. pp. 3–10. Bibcode : 2012amld.book....3F . doi : 10.1201/b11822-7 .
  3. ^ Legendre P, Legendre L (1998). Ecologia Numérica . Desenvolvimentos em Modelação Ambiental. Vol. 20 (segunda ed. inglesa). Amsterdã: Elsevier.
  4. ^ Erdmann VA, Wolters J (1986). "Coleção de sequências de RNA ribossômico 5S, 5.8S e 4.5S publicadas" . Pesquisa de Ácidos Nucleicos . 14 Supl (Supl): r1-59. doi : 10.1093/nar/14.suppl.r1 . PMC 341310 . PMID 2422630 .  
  5. ^ Olsen GJ (1988). "Análise filogenética usando RNA ribossômico". Métodos em Enzimologia . 164 : 793-812. doi : 10.1016/s0076-6879(88)64084-5 . PMID 3241556 . 
  6. ^ Murtagh F, Contreras P (2012). "Algoritmos para agrupamento hierárquico: uma visão geral". Wiley Interdisciplinary Reviews: Data Mining e Knowledge Discovery . Biblioteca on-line Wiley. 2 (1): 86–97. doi : 10.1002/widm.53 .
  7. ^ Sibson R (1973). "SLINK: um algoritmo eficiente para o método de cluster de link único" (PDF) . O jornal do computador . Sociedade Britânica de Computação. 16 (1): 30–34. doi : 10.1093/comjnl/16.1.30 .
  8. ^ Gan G (2007). Agrupamento de dados: teoria, algoritmos e aplicações . Filadélfia, Pa. Alexandria, Virgínia: SIAM, Sociedade de Matemática Aplicada e Industrial Associação Americana de Estatística. ISBN  9780898716238.
  9. ^ Gower JC, Ross GJ (1969). "Árvores geradoras mínimas e análise de cluster de ligação única". Jornal da Royal Statistical Society, Série C. 18 (1): 54–64. doi : 10.2307/2346439 . JSTOR 2346439 . MR 0242315 .  .

Links externos