Python Agglomerating Clustering: Finden der nächsten Punkte in Clustern

Question

Die Verknüpfungsmatrix für das Clustering stellt den Cluster-Index und den Abstand für jeden Schritt der Clusterhierarchie bereit. Wenn zwei Cluster zusammengeführt werden, möchte ich wissen, welche zwei Punkte in den Clustern am nächsten sind. Ich verwende die Metrik "single", d. H. Engste Entfernung

Ich weiß, dass ich dies durch eine erschöpfende Suche und Vergleich trivial tun kann. Sind die Informationen bereits nach der Verknüpfung vorhanden? Gibt es einen klügeren Weg, um diese Informationen zu erhalten?

Answer 1

Ihre Fragen zu beantworten:

• Nein, diese Information nach Verknüpfung nicht verfügbar ist, zumindest nach der offiziellen Python-Dokumentation.

• Das am nächsten Punktepaar Problem ist ein Problem der algorithmischen Geometrie und kann durch eine rekursive divide in logarithmischer Zeit gelöst werden und Algorithmus erobern (beachten Sie, dass erschöpfende Suche quadratisch ist). Siehe diese Wikipedia article für weitere Informationen. Überprüfen Sie auch diese paper von Shamos und Hoey. Beachten Sie, dass die ursprüngliche Formulierung des Problems nur einen Satz von Punkten umfasst. Die Anpassung für zwei Sätze ist jedoch einfach; Sie könnten diese discussion hilfreich finden.