Kleinster spannender Baum

Author: Hans Lohninger

Alle agglomerativen Clusteralgorithmen, die auf der Lance-Williams-Gleichung basieren, haben den Nachteil, dass die gesamte Distanzmatrix während der Clusteranalyse berechnet werden muss. Das kann eine beträchtliche Rechenleistung und viel Speicherplatz beanspruchen. Abhilfe kann ein graphentheoretisch begründetes Verfahren schaffen, das auf einem minimal spannenden Baum (engl. minimal spanning tree) beruht. Leider kann dieser Algorithmus nur auf Single-Linkage-Clustering angewendet werden. Er kann jedoch im Fall von großen Datensätzen um Größenordnungen schneller sein.

Ein minimal spannender Baum ist ein Graph, der folgende Bedingungen erfüllt:

• keine Zyklen (= Baum)
• spannend (alle Knoten sind eingebunden)
• die Summe der gewichteten Kanten ist ein Minimum

Es gibt einen einfachen Algorithmus, von Prim beschrieben, wie der minimal spanning tree bestimmt werden kann. Der resultierende Baum entspricht den Ergebnissen des Single-Linkage-Clusterings:

1. Wählen Sie ein beliebiges Objekt als Startknoten eines partiellen Graphen M.
2. Finden Sie für alle Objekte, die noch nicht Teil des Graphen M sind, den nächsten Nachbarn zu irgendeinem Knoten des Graphen M.
3. Verbinden Sie diesen nächsten Nachbarn mit M.
4. Beginnen Sie erneut bei Schritt 2, bis alle Knoten Teil des Graphen M sind.