Clustering à liaison complète - Complete-linkage clustering

Le regroupement par liaison complète est l'une des nombreuses méthodes de regroupement hiérarchique agglomératif . Au début du processus, chaque élément est dans un cluster à part. Les clusters sont ensuite combinés séquentiellement en clusters plus grands jusqu'à ce que tous les éléments finissent par être dans le même cluster. La méthode est également connue sous le nom de clustering du voisin le plus éloigné . Le résultat de l'agrégation peut être visualisé sous la forme d'un dendrogramme , qui montre la séquence de fusion d'amas et la distance à laquelle chaque fusion a eu lieu.

Procédure de clustering

A chaque étape, les deux clusters séparés par la distance la plus courte sont combinés. La définition de la «distance la plus courte» est ce qui différencie les différentes méthodes de regroupement agglomératif. Dans le clustering à liaison complète, le lien entre deux clusters contient toutes les paires d'éléments, et la distance entre les clusters est égale à la distance entre ces deux éléments (un dans chaque cluster) qui sont les plus éloignés l'un de l'autre. Le plus court de ces liens qui subsiste à n'importe quelle étape provoque la fusion des deux clusters dont les éléments sont impliqués.

Mathématiquement, la fonction de liaison complète - la distance entre les clusters et - est décrite par l'expression suivante: ${\ displaystyle D (X, Y)}$${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle D (X, Y) = \ max _ {x \ dans X, y \ dans Y} d (x, y)}$

où

• ${\ Displaystyle d (x, y)}$ est la distance entre les éléments et  ; ${\ displaystyle x \ dans X}$${\ displaystyle y \ in Y}$
• ${\ displaystyle X}$ et sont deux ensembles d'éléments (clusters). ${\ displaystyle Y}$

Algorithmes

Schéma naïf

L'algorithme suivant est un schéma agglomératif qui efface les lignes et les colonnes d'une matrice de proximité lorsque d'anciens clusters sont fusionnés en de nouveaux. La matrice de proximité D contient toutes les distances d ( i , j ). Les regroupements reçoivent des numéros de séquence 0,1, ......, ( n  - 1) et L ( k ) est le niveau du kème regroupement. Un cluster avec le numéro de séquence m est noté ( m ) et la proximité entre les groupes ( r ) et ( s ) est noté d [( r ), ( s )]. ${\ displaystyle N \ fois N}$

L'algorithme de clustering de liaison complet comprend les étapes suivantes:

1. Commencez par le regroupement disjoint ayant le niveau et le numéro de séquence . ${\ displaystyle L (0) = 0}$${\ displaystyle m = 0}$
2. Trouvez la paire de clusters la plus similaire dans le clustering actuel, disons paire , en fonction de l' endroit où le minimum est sur toutes les paires de clusters dans le clustering actuel. ${\ displaystyle (r), (s)}$${\ Displaystyle d [(r), (s)] = \ min d [(i), (j)]}$
3. Incrémenter le numéro de séquence: . Fusionner les clusters et en un seul cluster pour former le cluster suivant . Définissez le niveau de ce clustering sur ${\ displaystyle m = m + 1}$${\ displaystyle (r)}$${\ Displaystyle (s)}$${\ displaystyle m}$${\ Displaystyle L (m) = d [(r), (s)]}$
4. Mettre à jour la matrice de proximité , par suppression des rangées et des colonnes correspondant à des groupes et et en ajoutant une rangée et la colonne correspondant au groupe nouvellement formé. La proximité entre le nouveau cluster, noté et l'ancien cluster est définie comme . ${\ displaystyle D}$${\ displaystyle (r)}$${\ Displaystyle (s)}$${\ displaystyle (r, s)}$${\ displaystyle (k)}$${\ Displaystyle d [(r), (s)] = \ max \ {d [(k), (r)], d [(k), (s)] \}}$
5. Si tous les objets sont dans un cluster, arrêtez. Sinon, passez à l'étape 2.

Schéma d'une efficacité optimale

L'algorithme expliqué ci-dessus est facile à comprendre mais complexe . En mai 1976, D. Defays a proposé un algorithme d'une efficacité optimale de la seule complexité connu sous le nom de CLINK (publié en 1977) inspiré de l'algorithme similaire SLINK pour le clustering à liaison unique . ${\ displaystyle O (n ^ {3})}$${\ displaystyle O (n ^ {2})}$

Exemple de travail

L'exemple de travail est basé sur une matrice de distance génétique JC69 calculée à partir de l' alignement de séquence d' ARN ribosomal 5S de cinq bactéries: Bacillus subtilis ( ), Bacillus stearothermophilus ( ), Lactobacillus viridescens ( ), Acholeplasma modicum ( ) et Micrococcus luteus ( ). ${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle c}$${\ displaystyle d}$${\ displaystyle e}$

Premier pas

• Premier regroupement

Supposons que nous ayons cinq éléments et la matrice suivante de distances par paires entre eux: ${\ Displaystyle (a, b, c, d, e)}$${\ displaystyle D_ {1}}$

	une	b	c	ré	e
une	0	17	21	31	23
b	17	0	30	34	21
c	21	30	0	28	39
ré	31	34	28	0	43
e	23	21	39	43	0

Dans cet exemple, est la plus petite valeur de , donc nous joignons des éléments et . ${\ displaystyle D_ {1} (a, b) = 17}$${\ displaystyle D_ {1}}$${\ displaystyle a}$${\ displaystyle b}$

• Estimation de la longueur de la première branche

Soit le nœud auquel et sont maintenant connectés. Le réglage garantit que les éléments et sont équidistants de . Cela correspond à l'attente de l' hypothèse d' ultramétrie . Les branches d' assemblage et d' avoir ensuite des longueurs ( voir la dendrogramme finale ) ${\ displaystyle u}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle \ delta (a, u) = \ delta (b, u) = D_ {1} (a, b) / 2}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle u}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle u}$${\ displaystyle \ delta (a, u) = \ delta (b, u) = 17/2 = 8,5}$

• Mise à jour de la première matrice de distance

Nous procédons ensuite à la mise à jour de la matrice de proximité initiale dans une nouvelle matrice de proximité (voir ci-dessous), de taille réduite d'une ligne et d'une colonne en raison du regroupement de avec . Les valeurs en gras correspondent aux nouvelles distances, calculées en conservant la distance maximale entre chaque élément du premier cluster et chacun des éléments restants: ${\ displaystyle D_ {1}}$${\ displaystyle D_ {2}}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle D_ {2}}$${\ displaystyle (a, b)}$

${\ Displaystyle D_ {2} ((a, b), c) = max (D_ {1} (a, c), D_ {1} (b, c)) = max (21,30) = 30}$

${\ Displaystyle D_ {2} ((a, b), d) = max (D_ {1} (a, d), D_ {1} (b, d)) = max (31,34) = 34}$

${\ Displaystyle D_ {2} ((a, b), e) = max (D_ {1} (a, e), D_ {1} (b, e)) = max (23,21) = 23}$

Les valeurs en italique dans ne sont pas affectées par la mise à jour de la matrice car elles correspondent aux distances entre les éléments non impliqués dans le premier cluster. ${\ displaystyle D_ {2}}$

Deuxième étape

• Deuxième regroupement

Nous réitérons maintenant les trois étapes précédentes, à partir de la nouvelle matrice de distance  : ${\ displaystyle D_ {2}}$

	(un B)	c	ré	e
(un B)	0	30	34	23
c	30	0	28	39
ré	34	28	0	43
e	23	39	43	0

Ici, est la valeur la plus basse de , donc nous joignons le cluster avec l'élément . ${\ displaystyle D_ {2} ((a, b), e) = 23}$${\ displaystyle D_ {2}}$${\ displaystyle (a, b)}$${\ displaystyle e}$

• Estimation de la longueur de la deuxième branche

Soit le nœud auquel et sont maintenant connectés. En raison de la contrainte d'ultramétrie, les branches joignant ou à , et à , sont égales et ont la longueur totale suivante: ${\ displaystyle v}$${\ displaystyle (a, b)}$${\ displaystyle e}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle v}$${\ displaystyle e}$${\ displaystyle v}$${\ displaystyle \ delta (a, v) = \ delta (b, v) = \ delta (e, v) = 23/2 = 11,5}$

On en déduit la longueur de branche manquante: ( voir le dendrogramme final ) ${\ Displaystyle \ delta (u, v) = \ delta (e, v) - \ delta (a, u) = \ delta (e, v) - \ delta (b, u) = 11,5-8,5 = 3}$

• Mise à jour de la deuxième matrice de distance

Nous procédons ensuite à la mise à jour de la matrice dans une nouvelle matrice de distance (voir ci-dessous), de taille réduite d'une ligne et d'une colonne en raison du regroupement de avec  : ${\ displaystyle D_ {2}}$${\ displaystyle D_ {3}}$${\ displaystyle (a, b)}$${\ displaystyle e}$

${\ Displaystyle D_ {3} (((a, b), e), c) = max (D_ {2} ((a, b), c), D_ {2} (e, c)) = max ( 30,39) = 39}$

${\ Displaystyle D_ {3} (((a, b), e), d) = max (D_ {2} ((a, b), d), D_ {2} (e, d)) = max ( 34,43) = 43}$

Troisième étape

• Troisième clustering

Nous réitérons à nouveau les trois étapes précédentes, à partir de la matrice de distance mise à jour . ${\ displaystyle D_ {3}}$

	((a, b), e)	c	ré
((a, b), e)	0	39	43
c	39	0	28
ré	43	28	0

Ici, est la plus petite valeur de , donc nous joignons des éléments et . ${\ displaystyle D_ {3} (c, d) = 28}$${\ displaystyle D_ {3}}$${\ displaystyle c}$${\ displaystyle d}$

• Estimation de la longueur de la troisième branche

Soit le nœud auquel et sont maintenant connectés. Les branches d' assemblage et d' avoir ensuite des longueurs ( voir la dendrogramme finale ) ${\ displaystyle w}$${\ displaystyle c}$${\ displaystyle d}$${\ displaystyle c}$${\ displaystyle d}$${\ displaystyle w}$${\ displaystyle \ delta (c, w) = \ delta (d, w) = 28/2 = 14}$

• Mise à jour de la matrice de troisième distance

Il y a une seule entrée à mettre à jour: ${\ Displaystyle D_ {4} ((c, d), ((a, b), e)) = max (D_ {3} (c, ((a, b), e)), D_ {3} ( d, ((a, b), e))) = max (39,43) = 43}$

Dernière étape

La matrice finale est: ${\ displaystyle D_ {4}}$

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

Nous rejoignons donc les clusters et . ${\ Displaystyle ((a, b), e)}$${\ displaystyle (c, d)}$

Soit le nœud (racine) auquel et sont maintenant connectés. Les branches se rejoignant et pour avoir ensuite des longueurs: ${\ displaystyle r}$${\ Displaystyle ((a, b), e)}$${\ displaystyle (c, d)}$${\ Displaystyle ((a, b), e)}$${\ displaystyle (c, d)}$${\ displaystyle r}$

${\ Displaystyle \ delta (((a, b), e), r) = \ delta ((c, d), r) = 43/2 = 21,5}$

Nous en déduisons les deux longueurs de branche restantes:

${\ Displaystyle \ delta (v, r) = \ delta (((a, b), e), r) - \ delta (e, v) = 21,5-11,5 = 10}$

${\ Displaystyle \ delta (w, r) = \ delta ((c, d), r) - \ delta (c, w) = 21,5-14 = 7,5}$

Le dendrogramme de liaison complète

Le dendrogramme est maintenant terminé. Il est ultramétrique car toutes les pointes ( à ) sont équidistantes de  : ${\ displaystyle a}$${\ displaystyle e}$${\ displaystyle r}$

${\ Displaystyle \ delta (a, r) ​​= \ delta (b, r) = \ delta (e, r) = \ delta (c, r) = \ delta (d, r) = 21,5}$

Le dendrogramme est donc enraciné par son nœud le plus profond. ${\ displaystyle r}$

Comparaison avec d'autres liens

Les schémas de couplage alternatifs incluent le clustering de liaison unique et le clustering de liaison moyen - la mise en œuvre d'un lien différent dans l'algorithme naïf consiste simplement à utiliser une formule différente pour calculer les distances inter-cluster dans le calcul initial de la matrice de proximité et à l'étape 4 de ce qui précède. algorithme. Un algorithme d'une efficacité optimale n'est cependant pas disponible pour les liaisons arbitraires. La formule qui doit être ajustée a été mise en évidence en utilisant du texte en gras.

Le clustering de liaison complet évite un inconvénient de la méthode alternative de liaison unique - le phénomène dit de chaînage , où les clusters formés via un clustering de liaison unique peuvent être forcés ensemble en raison de la proximité d'éléments individuels, même si de nombreux éléments dans chaque cluster peuvent être très éloignés les uns des autres. Une liaison complète a tendance à trouver des grappes compactes de diamètres approximativement égaux.

Comparaison des dendrogrammes obtenus sous différentes méthodes de clustering à partir de la même matrice de distance .

Clustering à liaison unique .	Clustering de liaison complète.	Clustering de liaison moyen: WPGMA .	Clustering de liaison moyen: UPGMA .

Voir également

• L'analyse par grappes
• Classification hiérarchique
• Horloge moléculaire
• Rejoindre un voisin
• Clustering à liaison unique
• UPGMA
• WPGMA

Les références

Lectures complémentaires

• Späth H (1980). Algorithmes d'analyse de cluster . Chichester: Ellis Horwood.