Graph Degree Linkage : Classification Hiérarchique Agglomérative sur un Graphe Orienté

Ce travail propose un algorithme agrégatif basé sur les graphes, simple mais efficace, pour le regroupement de données de grande dimension. Nous explorons les rôles différents de deux concepts fondamentaux de la théorie des graphes, le degré entrant et le degré sortant, dans le contexte du clustering. Le degré entrant moyen reflète la densité près d'un échantillon, tandis que le degré sortant moyen caractérise la géométrie locale autour d'un échantillon. Sur la base de ces observations, nous définissons la mesure d'affinité des clusters par le produit du degré entrant moyen et du degré sortant moyen. Cette affinité basée sur le produit rend notre algorithme robuste au bruit. L'algorithme présente trois avantages principaux : une bonne performance, une mise en œuvre facile et une haute efficacité computationnelle. Nous avons testé l'algorithme sur deux problèmes fondamentaux en vision par ordinateur : le regroupement d'images et l'appariement d'objets. Des expériences approfondies montrent qu'il surpasse les méthodes actuelles dans les deux applications.