Agrupamiento per enlazamiento complet

El agrupamiento per enlazamiento complet és un de varis métodos d'agrupamiento jeràrquic. Al principi del procés, cada element és, en sí mateixa, un cluster o grup. Estos grups són després combinats en forma seqüencial en grups més grans fins que tots els elements acaben sent part d'un mateix grup. Este método també és conegut com agrupamiento del veí més lluntà. El resultat del agrupamiento pot ser visualisat en forma de dendrograma, el qual mostra la seqüència de fusió dels grups i la distància a la que cada fusió va tindre lloc.

Procediment de agrupamiento

En cada pas, es combinen els dos grups separats per la distància més curta. La definició que s'use de 'la distància més curta' és lo que diferencia als varis métodos de agrupamiento. En el agrupamiento per enlazamiento complet, l'enllaç entre dos grups conté tots els elements emparellats, i la distància entre els grups és igual a la distància entre els dos elements (un en cada grup) que estiguen lo més alluntat de cada u. L'enllaç més curt que quede en cada pas provoca la fusió dels dos grups els elements dels quals estiguen involucrats.

Matemàticament, la funció de enlazamiento complet — és dir, la distància ___MATH_0___ entre els grups ___MATH_1___ i ___MATH_2___ — està descrit per la següent expressió: ___MATH_3___

On

• ___MATH_4___ és la distància entre els elements ___MATH_5___ i ___MATH_6___;
• ___MATH_7___ i ___MATH_8___ són dos conjunts d'elements (grups).

Algoritmes

Esquema Inocent o Ingenu

El següent algoritme és un esquema aglomerativo, el qual borra les files i columnes d'una matriu de proximitat quan els antics grups es fusionen en nou grups. La matriu de proximitat D (___MATH_9___) conté totes les distancies d(i,j). En el agrupamiento s'assignen números en orde seqüencial 0,1,......, (n − 1) i L(k) és el nivell del k-ésimo agrupamiento. Un grup en número de secuencia m s'escriu com (m) i la proximitat entre els grups (r) i (s) s'escriu d[(r),(s)].

L'algoritme complet de l'agrupació per enlazamiento complet consta dels següents passos:

1. S'escomença sense cap grup, per lo tant en un nivell de agrupamiento ___MATH_10___ i un número de seqüència ___MATH_11___.
2. Es troba el parell de grups més similar en l'actual nivell de agrupamiento, és dir, el parell ___MATH_12___ que complixca en ___MATH_13___, que és el valor mínim que es puga trobar en qualsevol dels parells de grups en l'actual nivell de agrupamiento.
3. S'aumenta el número de seqüència: .___MATH_14___. Es fusionen els grups ___MATH_15___ i ___MATH_16___en un sol grup per a formar el pròxim agrupamiento ___MATH_17___. Posar el nivell d'este agrupamiento com ___MATH_18___
4. Actualisar la matriu de proximitat ___MATH_19___, eliminant les files i columnes que corresponien als grups ___MATH_20___ i ___MATH_21___ i s'agrega una nova fila i una nova columna que correspon al recent grup format. La proximitat entre el nou grup, ___MATH_22___ i l'antic grup ___MATH_23___ es definix com ___MATH_24___.
5. Si tots els objectes fan part d'un sol grup, parar. Sino, seguir en el pas 2.

Esquema eficient optimisat

L'algoritme explicat dalt és fàcil d'entendre pero la seua complexitat és ___MATH_25___. En maig de 1976, D. Defays va propondre un algoritme eficient optimisat la complexitat del qual és solament de ___MATH_26___, conegut com CLINK (publicat 1977) i es va inspirar en l'algoritme SLINK usat en el agrupamiento per enllaç únic.