Lorsque l'on étudie des données, il est courant de devoir regrouper les éléments par grandes catégories. La première étape peut être d'utiliser une structuration sous forme de graphe, mais cela n'est pas toujours suffisant. Il faut alors passer à une seconde étape et créer des classes d'éléments à l'intérieur du graphe.
Le premier à avoir mis en place une classification hiérarchique systématique est Aristote, au IVème siècle avant JC. Il distinguera ainsi par exemple le règne animal du règne végétal et il classera les animaux en les plaçant dans deux groupes principaux : les animaux ayant du sang et ceux n'en ayant pas [1]. Le raffinement des groupes se fait au fur et à mesure à l'aide d'une méthode de division dont l'importance est capitale puisque c'est cette dernière qui définit les éléments attribués à tel ou tel groupe.
Dans cet article où nous nous intéresserons à la classification dans des graphes, nous commencerons par définir la façon de mesurer la proximité entre deux sommets avant d'aborder deux méthodes de classification illustrant deux types d'approches.
1. Mesurer la proximité entre deux sommets
La proximité est une mesure qui est définie sur une paire de sommets dans notre cas - et plus généralement d'objets - que l'on peut nommer i et j....
- Accédez à tous les contenus de Connect en illimité
- Découvrez des listes de lecture et des contenus Premium
- Consultez les nouveaux articles en avant-première