Wir haben im letzten Mal gesehen, wie wir mit dem Algorithmus von Kruskal das Problem lösen

können einen minimalen aufspannenden Baum zu finden und der Algorithmus liefert uns quasi

nebenbei auch noch ein Clustering-Algorithmus und das sieht man am besten so. Ich möchte mal ein

typisches Beispiel. Das sind jetzt hier Datenpunkte, zu der wir jetzt eine Grafenstruktur

nach einem Verfahren generieren, das wir uns noch anschauen werden. Also zum Beispiel

man kann natürlich alles mit allem verbinden, aber das ist vielleicht ein bisschen zu viele Kanten,

noch mal so ein bisschen sparsamer, nicht alle Kanten zu jedem Knoten und so weiter. Und schauen

wir uns hier folgende Grafen an. Wir sehen jetzt hier optisch schon, dass es hier so eine Art Clustering

gibt. Also hier ist irgendwie eine Gruppe von fünf Knoten, hier ist eine Gruppe von sechs Knoten und

die scheint irgendwie räumlich voneinander getrennt zu sein. Und wenn wir jetzt den Algorithmus von

Kruskal durchführen, dann müssen wir ja alle Kanten in aufsteigende Reihenfolge sortieren.

Ich tue es einfach so, als wäre die Länge der Kanten einfach genau das Gewicht, damit es optisch

einfach ist. Das heißt jetzt ist das Gewicht der Kante wirklich sozusagen die geografische

Distanz zwischen den Knoten. Also wir fangen an, wir sortieren die Kanten. Jetzt ist vielleicht die

kleinste Kante diese hier und dann kommt vielleicht diese hier dazu, vielleicht die hier, vielleicht die hier und so weiter.

Wir gehen jetzt hier den ganzen Knoten lang. Diese Kante nehmen wir nicht, weil die Baum-Eigenschaft

zerstören würde. Dann kommt vielleicht diese hier und diese hier und diese hier und so weiter. Und wir haben gelernt,

dass bei jeder iteration die Anzahl der Zusammenhangskomponenten in diesem Baum hier,

oder in diesem Wald besser gesagt, um eins reduziert wird. Also jetzt sind wir schon bei,

naja, welche Knoten haben wir eigentlich noch? Wir haben noch diesen Knoten eins, wir haben noch diesen Knoten

eins und wir haben hier zwei Bäume hier und hier. Das heißt wir haben jetzt vier Zusammenhangskomponenten

oder in diesem Wald sind jetzt gerade vier Bäume. Dann müssen wir es hier so weitermachen. Jetzt kommt

vielleicht hier diese Kante zu. Jetzt haben wir noch drei Komponenten und jetzt haben wir nur noch zwei

Komponenten und jetzt könnten wir stoppen und sagen aha, jetzt haben wir zwei Komponenten gefunden,

die so entstanden sind, dass wir immer Kanten mit minimalem Gewicht aufgenommen haben. Und wenn wir jetzt

quasi noch einen weiteren Schritt gehen würden, dann haben wir den minimalen aufspannenden Baum

gefunden. Okay, so sind wir jetzt quasi fertig mit dem Algorithmus von Kruskal. Wenn wir das hier

früher aufhören, dann haben wir jetzt zwei Komponenten gefunden, die nicht zusammenhängen,

also zwei Bäume in diesem Wald gefunden, die in irgendeiner Weise tatsächlich diese Cluster

abbilden, die wir gerade gefunden haben. Genauso könnte man es machen, wenn man nach drei Clustern

sucht, dann hört man einfach zwei Iterationen zu früh auf. Dann bekommt man drei Cluster, indem man

sich jetzt einfach die Knoten anschaut, die in diesen einzelnen Bäumen dran liegen. Das heißt,

jetzt bekommen wir hier durch das Clustering, wir bekommen jetzt folgendes Resultat. In diesem Baum

hier sind diese fünf Knoten und in diesem Baum hier sind diese sechs Knoten. Jetzt können wir

sagen aha, sehr schön, damit haben wir jetzt hier gerade Clustering betrieben. Natürlich ist es jetzt

eher eine Heuristik, aber es ist eine recht gut funktionierende Heuristik in diesem Beispiel,

weil es tatsächlich genau das macht, was man so von Clustering so ein bisschen denken würde. Es

gruppiert Knoten zusammen, die geringen Abstand voneinander haben und das ist in gewisser Hinsicht

schon quantifiziert durch die Tatsache, dass wir immer in der Reihenfolge der Kanten in Aufsteigung

mit einem Gewicht hier durchgehen. Das heißt, sehr eng zusammenhängende Knoten, die werden tatsächlich quasi sofort

miteinander verbunden. Und so bekommen wir Gruppierungen von Knoten, die untereinander geringen

Abstand haben oder die individuell geringen Abstand zu dem Rest des Baums haben und wir

gruppieren nicht zusammen diese unterschiedlichen Gruppen. Und das ist wie man Clustering mithilfe

des Algorithms von Kruskal machen kann. Das heißt einfach, wenn man sich, wenn wir uns

wie viele Cluster wünschen, also wenn wir uns einen Cluster wünschen, dann machen wir den ganzen

Algorithmus durch. Das ist natürlich kein Clustering, das ist einfach nur den minimalen

aufspannenden Baum zu finden. Wenn wir uns zwei Cluster wünschen, dann halten wir einfach eine Interaktion zu früh auf.

Wenn wir uns 17 Cluster wünschen, dann halten wir 18 Interaktionen zu früh auf und so weiter.

Also so können wir Clustering machen und es ist interessant sich anzuschauen, wie dieses Verfahren

performt jetzt auch im Kontrast zu den Verfahren, die wir am Anfang dieser Vorlesung gesehen haben, nämlich