Classification hiérarchique ascendante

Considérons une population d'individus. Pour chaque individu, nous avons prélevé deux attributs que l'on notera x et y. Cela nous permet de représenter les individus par un nuage de points dans un repère Oxy.

#exemple :
values = [(83, 80), (37, 33), (82, 89), (89, 80), (27, 35), (85, 80), (86, 74), (35, 34), (27, 36), (80, 80), (73, 68), (35, 35), (84, 75), (46, 38), (88, 83), (32, 36), (73, 92), (80, 67), (36, 32), (83, 75), (34, 36), (69, 78), (40, 46), (80, 78), (27, 35), (80, 80), (76, 71), (96, 71), (34, 37), (35, 33), (84, 84), (35, 35), (33, 39), (77, 86), (66, 73), (80, 81), (94, 91), (48, 31), (45, 35), (43, 27), (37, 27), (35, 35), (80, 75), (35, 31), (76, 63), (82, 83), (43, 35), (79, 79), (80, 80), (77, 68), (75, 93), (26, 25), (39, 28), (75, 79), (89, 88), (96, 77), (36, 32), (35, 35), (35, 35), (35, 35), (39, 45), (73, 65), (44, 34), (43, 36), (87, 80), (29, 47), (33, 35), (38, 31), (48, 38), (80, 79), (35, 30), (43, 26), (40, 32), (80, 63), (79, 83), (25, 30), (83, 90), (34, 35), (35, 35), (94, 77), (31, 28), (27, 40), (35, 38), (36, 35), (31, 33), (84, 85), (30, 35), (64, 80), (38, 38), (35, 35), (95, 73), (76, 75), (35, 35), (86, 80), (80, 69), (68, 85), (37, 45), (42, 38), (41, 28), (77, 79)]

Et la représentation graphique de cet exemple :

On souhaite, automatiquement, identifier les deux sous-groupes.

Nous allons constituer un arbre dont chaque nœud aura les attributs suivants :

• un point, ou une paire de coordonnées,
• une poids entier positif,
• une mesure de distance

On amorce la méthode en créant un nœud pour chaque points du nuage.

• chacun de ces nœuds est donc associer à un point du nuage,
• il a un poids égal à 1,
• la distance est 0

Ces nœuds n'ont pas de parents, ils sont orphelins.

Ensuite, on démarre un action répétitive, tant qu'il reste plus d'un orphelin :

• on calcule la distance entre chaque paire d'orphelins – on précise ensuite comment on calcule cette distance,
• on sélectionne la paire avec la distance la plus faible,
• on crée un nouveau nœud qui deviendra le parent des deux nœuds sélectionnés,
• ce nouveau nœud reçoit les attributs :
  • le centre de gravité des points dont il est le parent
  • un poids égal au total des poids dont il est le parent
  • une distance correspondant à la distance entre les deux nœuds enfants

Comme les deux orphelins sélectionnés à chaque étape reçoivent un parent, cela fait deux orphelins de moins, mais on crée un nouveau nœud qui est orphelin. Donc à chaque étape, le nombre d'orphelins diminue de 1.

Il existe plusieurs options. Celle qui semble donner les meilleurs résultats est appelée la distance de Ward. Voici comment elle fonctionne : Chaque nœud est associé à un point C et à une pondération n.

La distance entre deux nœuds 1 et 2 sera alors $\frac{n_1\cdot n_2}{n_1 + n_2} C_1C_2$ où $C_1C_2$ est la distance entre $C_1$ et $C_2$ – on peut utiliser la distance ordinaire.

À chaque étape on sélectionne une distance minimale. Mais à mesure que l'on progresse dans l'algorithme, ce minimum est de plus en plus grand (en gros on supprime le minimum à chaque étape, le minimum de ce qui reste est donc de plus en plus grand)

Quand on est encore en train de rassembler des points proches, les minimums sont encore faibles. Mais quand on passe au regroupement de deux sous-nuages éloignés, la distance considérée devient nettement plus grande. C'est donc en détectant une brusque augmentation de distance que l'on reconnaît que l'on a des groupes différents.

Toutefois, cela peut être difficile – à vous de voir – et on peut simplifier en ajoutant une information a priori : Si on sait que l'on doit trouver deux sous-groupes, c'est plus facile : Les deux sous-groupes correspondent aux deux enfants de la racine.

Vous pouvez aussi fixer une distance seuil : si le seuil est S, on considère les sous-arbres que l'on aurait obtenu si on s'était arrêté avant de dépasser la distance S.

Pour visualiser le bon fonctionnement, vous pouvez reproduire le graphique mais en coloriant automatiquement les sous-groupes avec des couleurs différentes.