Graphengradverknüpfung: Agglomeratives Clustering auf einem gerichteten Graphen

Dieses Papier präsentiert einen einfachen, aber effektiven, graphbasierten agglomerativen Algorithmus zur Clusterverarbeitung hochdimensionaler Daten. Wir untersuchen die verschiedenen Rollen zweier grundlegender Konzepte der Graphentheorie, des Eingrades (indegree) und des Ausgrades (outdegree), im Kontext der Clusterverarbeitung. Der durchschnittliche Eingrad spiegelt die Dichte in der Nähe eines Stichprobenpunktes wider, während der durchschnittliche Ausgrad die lokale Geometrie um einen Stichprobenpunkt charakterisiert. Aufgrund dieser Erkenntnisse definieren wir das Affinitätsmaß von Clustern über das Produkt des durchschnittlichen Eingrads und des durchschnittlichen Ausgrads. Das produktbasierte Affinitätsmaß macht unseren Algorithmus robust gegenüber Rauschen. Der Algorithmus hat drei Hauptvorteile: gute Leistung, einfache Implementierung und hohe Recheneffizienz. Wir testen den Algorithmus anhand zweier grundlegender Probleme der Computer Vision: Bildclustering und Objektkorrespondenz. Umfangreiche Experimente zeigen, dass er in beiden Anwendungen den Stand der Technik übertreffen kann.