Chamfer-Linkage: Neue Methode verbessert hierarchisches Clustering

Hierarchisches agglomeratives Clustering (HAC) ist ein weit verbreitetes Verfahren, bei dem Cluster schrittweise anhand ihrer Nähe zusammengeführt werden. Dabei bestimmt die gewählte Linkage-Funktion die Abstände zwischen den Clustern, doch HAC optimiert kein einzelnes globales Ziel. Die Qualität der Ergebnisse wird daher meist experimentell beurteilt, und die Wahl der Linkage spielt eine entscheidende Rolle.

Die klassische Linkage, wie Single‑Linkage, Average‑Linkage oder Ward’s Methode, zeigt in der Praxis oft große Schwankungen und liefert nicht immer hochwertige Clusterings. In der neuen Arbeit wird die Chamfer‑Linkage vorgestellt, die die Distanz zwischen Clustern über die Chamfer‑Distanz berechnet – ein in der Computer‑Vision und im maschinellen Lernen häufig genutztes Maß für Punktwolken.

Die Autoren zeigen theoretisch, dass HAC mit Chamfer‑Linkage in O(n²) Zeit implementiert werden kann, also genauso effizient wie die etablierten Linkages. Empirisch über ein breites Spektrum an Datensätzen hinweg liefert Chamfer‑Linkage konsequent bessere Clusterings als Average‑Linkage und Ward’s Methode. Damit stellt die neue Linkage ein praktikables, austauschbares Werkzeug für das hierarchische Clustering dar und erweitert das Repertoire sowohl für theoretische als auch für praktische Anwendungen.