Download ALGORITHMES DE CLASSIFICATION

a
b
c
Figure 1.- Phénomène d'inversion. La distance entre l’élément c et le groupe (a, b) est plus faible
que la distance entre a et b.
Quelle que soit la formule adoptée il faut donc s'assurer que les distances reca1culées soient
supérieures au niveau du nœud que 1'on vient de former :
d(iUi', k) 
d(i, i')
Cela est évident pour les formules (1) et (2) puisqu'au moment de la fusion d(i, i') est la plus petite
de toutes les distances. On vérifie aisément que c'est encore vrai de la formule (3), pour la même
raison.
Lorsqu'on utilise la formule (1) , on dit qu’on procède à l’agrégation par "le saut minimum" ou "du
lien simple" (en anglais : "single link"), parce que la fusion de deux groupes est basée sur la plus
petite des distances inter-groupes. La hiérarchie basée sur la formule (2) est appelée hiérarchie du
"diamètre" ou du "lien complet" –(en anglais « complete link »), car elle est basée sur la plus grande
distance interne au groupe résultant, ce qui est la définition même du diamètre de ce groupe. Enfin
la classification fondée sur la formule (3) s'appelle hiérarchie de « la distance moyenne » (« average
link » en anglais).
Deux remarques s'imposent à propos de cette construction hiérarchique :
- les nombreuses recherches et modifications sur les distances obligent à gérer celles-ci en
mémoire centrale de l’ordinateur ; ce qui limite sérieusement la taille de l'échantillon.
- en revanche ce type d'algorithme est peu exigeant sur les propriétés de la distance initiale qui
peut être obtenue par des formules spéciales (cf. annexe 1) ne satisfaisant pas forcément aux
axiomes usuels des distances.
1.2.- Propriétés des formules élémentaires de recalcul
Propriété 1 : Transformation monotone des distances initiales
Soit d(i, i') la distance initiale entre les objets i et i'. Une transformation monotone de ces distances
est une modification de d, que nous appellerons d', qui conserve l'ordre entre les distances. C'est à
dire que
d(i, i’)  d(j, j’) ⇒ d’(i, i’)  d’(j, j’)
En particulier toute fonction croissante de d a cette propriété. Si l'on applique une telle
transformation aux distances initiales, il est clair que l'arbre hiérarchique va être modifié. Cependant
dans le cas de l'agrégation par le diamètre ou par le saut minimum, les nœuds successifs vont
regrouper les mêmes objets tout au long de l'algorithme. Autrement dit les niveaux de regroupement
changent mais la structure de l'arbre hiérarchique est invariante. Ceci relativise la question du choix
de l'indice de distance (cf annexe 1). Cette propriété n'est pas vraie pour l'agrégation par la distance
moyenne.
Propriété 2 : Extrémalité de la hiérarchie du saut minimum