5.1 Clustering

Worum geht’s#

Bisher in diesem Modul war fast jedes Lernverfahren überwacht: Zu jedem Trainingsbeispiel gab es eine richtige Antwort — ein Klassenlabel, einen Zielwert — und das Verfahren lernte, sie nachzubilden. Clustering dreht diese Voraussetzung um. Die Daten kommen ohne Etiketten; die Aufgabe ist, von selbst Struktur zu finden: Welche Objekte gehören zusammen, welche nicht?

Das macht Clustering zum Prototyp des unüberwachten Lernens und zugleich zum naheliegendsten Werkzeug, wenn man einen frischen Datensatz vor sich hat und noch gar nicht weiß, welche Klassen es überhaupt gibt. Genau hier sitzt es im Data Mining: Man sucht „interessante strukturelle Beziehungen”, die vorher niemand benannt hat. Mich reizt an dem Thema, dass schon ein einziger, fast trivialer Algorithmus — k-Means — die zentrale Spannung sichtbar macht: Er findet zuverlässig eine Lösung, aber ob es die richtige ist, hängt vom Zufall der Initialisierung und von einer Zahl ab, die man vorher raten muss (dem $k$). Diese Spannung ist die rote Linie der ganzen Seite.

Kernkonzepte#

Was ein Cluster sein soll#

Ein Cluster ist eine Gruppe von Objekten, die einander ähnlich sind und sich von den Objekten anderer Cluster deutlich unterscheiden. „Ähnlich” heißt: ein kleiner Abstand in einem vorher gewählten Maß. Diese Wahl ist keine Nebensache — sie definiert erst, was als Cluster gilt.

Das grenzt Clustering scharf von Klassifikation (Thema 3.2) ab: Dort sind die Klassen $K_1, \dots, K_n$ vorgegeben, und ein Beispiel wird einer davon zugeordnet. Beim Clustering gibt es zu Beginn keine Klassen; sie entstehen erst aus den Daten. Knapp: Klassifikation ordnet in bekannte Schubladen ein, Clustering baut die Schubladen.

k-Means: der Lloyd-Algorithmus#

Das mit Abstand bekannteste partitionierende Verfahren ist k-Means. Man gibt die Clusterzahl $k$ vor und sucht $k$ Schwerpunkte (Zentroide), die die Trägheit (Inertia, die Summe der quadrierten Abstände jedes Punktes zu seinem Zentroid) minimieren:

Dieses Optimierungsproblem ist NP-schwer; k-Means löst es nicht exakt, sondern durch die Lloyd-Iteration — zwei Halbschritte, die abwechselnd wiederholt werden:

Genau diese Zerlegung macht die folgende Insel sichtbar: „Zuordnen” färbt die Punkte nach ihrem nächsten Zentrum, „Verschieben” rückt die Zentren in den Schwerpunkt. Die angezeigte Trägheit fällt mit jedem Schritt monoton — bis sie sich nicht mehr bewegt.

Wie viele Cluster? Die Wahl von k#

Die Achillesferse ist das vorzugebende $k$. Da $J$ mit wachsendem $k$ ohnehin monoton sinkt (bei $k = n$ wird es null), taugt $J$ allein nicht als Kriterium. Zwei verbreitete Heuristiken helfen:

• Ellenbogen-Methode. Man trägt die Inertia über $k$ auf und sucht den „Knick”, ab dem zusätzliche Cluster kaum noch Gewinn bringen. Im Praxisteil ist dieser Knick bei der wahren Clusterzahl deutlich zu sehen.
• Silhouette. Für jeden Punkt vergleicht man den mittleren Abstand zum eigenen Cluster ($a$) mit dem zum nächsten fremden Cluster ($b$): $s = \frac{b - a}{\max(a, b)} \in [-1, 1]$. Werte nahe $1$ heißen „gut einsortiert”; das über alle Punkte gemittelte $s$ bewertet ein ganzes $k$.

Weiche Zuordnung: EM/GMM statt harter Grenzen#

k-Means trifft harte Entscheidungen: Jeder Punkt gehört zu genau einem Cluster, und laut Foliensatz „kann [es] nur konvexe Cluster bilden” und ist „nicht geeignet, um unbekannte Cluster zu entdecken”. Das EM-Verfahren (Erwartungs-Maximierung) mit einem Gaußschen Mischmodell (GMM) lockert beides. Es modelliert jeden Cluster als Verteilung mit eigenem Mittelwert und eigener Kovarianzmatrix und ordnet jedem Punkt über $P(C_i \mid x) = W_i \cdot \frac{P(x \mid C_i)}{P(x)}$ eine Wahrscheinlichkeit der Zugehörigkeit zu — eine weiche Zuordnung ($W_i$ ist der Anteil der Punkte in $C_i$). Dadurch kann EM auch längliche, unterschiedlich große oder leicht überlappende Cluster erfassen, an denen k-Means scheitert. Wichtig: Auch bei GMM/EM muss die Zahl der Komponenten normalerweise vorgegeben oder über ein zusätzliches Modellwahlkriterium wie BIC/AIC bestimmt werden; EM allein „findet” $k$ nicht automatisch. k-Means ist im Grunde der harte Grenzfall von EM (Zugehörigkeit 0/1).

Hierarchisches Clustern#

Will man sich gar nicht auf ein festes $k$ festlegen, bietet sich hierarchisches Clustern an. Agglomerativ (Bottom-up) startet jeder Punkt als eigenes Cluster; dann werden iterativ die beiden nächsten Cluster verschmolzen, bis alles in einem Cluster liegt. Das Ergebnis ist ein Dendrogramm — ein Verschmelzungsbaum, den man auf jeder gewünschten Höhe durchschneiden kann und so $k$ im Nachhinein wählt. Wie „nächste Cluster” gemessen wird (nächster Nachbar, mittlerer paarweiser Abstand, Zentroid-Abstand), ändert die Form der entstehenden Cluster spürbar.

Praxis#

Die Übung auf Blatt 9 verlangt k-Means und kNN auf demselben Wachstums-Datensatz (data/wachstum.csv), den ich in Thema 3.2 bereits für die Klassifikation benutzt habe — ideal, um beide Paradigmen am selben Material zu kontrastieren. Ich habe die Aufgaben von Hand gerechnet und den Code das Ergebnis nachrechnen lassen.

Aufgabe 1 (Blatt 9): Ziel, Beziehung, Gütekriterien#

a) Ziel. In einer ungelabelten Datensammlung eine möglichst kleine Zahl von Gruppen finden, sodass Objekte im selben Cluster einander ähnlich, Objekte aus verschiedenen Clustern einander unähnlich sind. Es geht um das Aufdecken bislang unbekannter Struktur, nicht um das Reproduzieren vorgegebener Klassen.

b) Beziehung zur Klassifikation. Beide ordnen Objekte Gruppen zu und nutzen dazu oft denselben Abstandsbegriff — aber an entgegengesetzten Enden: Klassifikation ist überwacht (Klassen vorgegeben, aus gelabelten Beispielen gelernt), Clustering ist unüberwacht (Klassen entstehen erst aus den Daten). Häufig steht Clustering daher vor der Klassifikation: Erst gruppiert man die Daten, dann benennt und verwendet man die Gruppen als Klassen. Genau diesen Übergang macht Aufgabe 3 vor — A3a clustert, A3b klassifiziert per kNN gegen die Cluster.

c) Gütekriterien. Ein gutes Clustering-Verfahren sollte: (i) das Cluster-Kriterium erfüllen (hohe innere Ähnlichkeit, große äußere Distanz — messbar etwa über Inertia oder Silhouette); (ii) robust gegenüber der Initialisierung und der Eingabereihenfolge sein; (iii) mit der Datenmenge skalieren; (iv) mit verschiedenen Merkmalstypen (nominal/ordinal/metrisch) und mit Ausreißern umgehen; (v) ein nachvollziehbares, idealerweise nicht von zu vielen geratenen Parametern abhängiges Ergebnis liefern.

Aufgabe 2 (Blatt 9): Prinzip-Skizzen#

(a) Was ein Clustering-Algorithmus leistet. Aus einer Wolke ungelabelter Punkte macht er Gruppen, in denen die Punkte nah beieinander (klein im inneren Abstand) und von anderen Gruppen weit entfernt (groß im äußeren Abstand) liegen:

(b) Clustern vs. Klassifizieren. Beide ordnen Punkte Gruppen zu, aber mit gegensätzlicher Ausgangslage. Beim Clustern (links) gibt es keine Labels; die Gruppen entstehen aus der Lage der Punkte. Bei der Klassifikation (rechts) sind die Klassen vorgegeben (verschiedene Marker), und gelernt wird eine Trennlinie, die neue Punkte einsortiert:

(c) k-Means-Prinzip. k-Means partitioniert die Punkte in $k$ Gruppen, indem es abwechselnd jeden Punkt dem nächsten Zentrum zuordnet und jedes Zentrum in den Schwerpunkt seiner Punkte schiebt (Lloyd-Iteration, siehe Kernkonzepte). Die Zahl $k$ muss man vorgeben — sie bestimmt, in wie viele Gruppen geteilt wird, und ist die Hauptstellschraube; weitere Einflussgrößen sind die Initialisierung der Startzentren (verschiedene Starts → verschiedene lokale Optima, daher mehrfacher Lauf), das Abstandsmaß bzw. die Skalierung der Merkmale und die maximale Iterationszahl.

(d) Vorteil von EM/GMM. Während k-Means harte Zuordnungen trifft (jeder Punkt in genau ein Cluster) und nur etwa kugelförmige, gleich große Cluster gut findet, ordnet das EM-Verfahren mit Gaußschem Mischmodell jedem Punkt eine Wahrscheinlichkeit je Cluster zu (weiche Zuordnung) und modelliert pro Cluster eine eigene Kovarianz — es erfasst dadurch auch längliche, unterschiedlich große und leicht überlappende Cluster (Details in den Kernkonzepten). k-Means ist der harte Grenzfall von EM.

Aufgabe 3a (Blatt 9): k-Means von Hand#

Zuerst die numerische Kodierung — ohne sie gibt es kein Abstandsmaß: trocken/feucht $\to 0/1$ (binär), die Säure ordinal entlang der Alkalinitäts-Achse neutral < basisch < alkalisch $\to 0/1/2$, die Temperatur bleibt metrisch. Jeder Punkt ist damit ein Tripel $(\text{Feuchte}, \text{Säure}, \text{Temp})$. Die Startzentren sind $S_1 = d_1 = (0,1,7)$ und $S_2 = d_8 = (0,0,9)$. Der Code rechnet die Lloyd-Iteration explizit:

def _kmeans_by_hand(X, init, max_iter=10):
    cents = init.astype(float).copy()
    assign = np.full(len(X), -1)
    for it in range(1, max_iter + 1):
        # Zuordnen: jeder Punkt zum nächsten Zentrum (euklidisch)
        dists = np.linalg.norm(X[:, None, :] - cents[None, :, :], axis=2)
        new_assign = dists.argmin(axis=1)
        # Verschieben: Zentren = Schwerpunkt ihrer Punkte
        for c in range(len(cents)):
            if (new_assign == c).any():
                cents[c] = X[new_assign == c].mean(axis=0)
        if (new_assign == assign).all():
            return new_assign, cents       # Zuordnung stabil -> konvergiert
        assign = new_assign

Das Verfahren konvergiert hier schon nach der ersten Iteration — die zweite bestätigt nur, dass sich nichts mehr ändert:

=== A3a: k-Means (k=2) auf den ersten 10 Datenpunkten ===
  Startzentren: S1 = d1 = (0, 1, 7),  S2 = d8 = (0, 0, 9)

  Iteration 1 — Zuordnung: C1={d1, d3, d4, d6, d10}; C2={d2, d5, d7, d8, d9}
               neue Zentren: S1=(0.20, 1.00, 6.60); S2=(0.20, 0.40, 9.00)
  Iteration 2 — Zuordnung: C1={d1, d3, d4, d6, d10}; C2={d2, d5, d7, d8, d9}
               neue Zentren: S1=(0.20, 1.00, 6.60); S2=(0.20, 0.40, 9.00)
  -> Zuordnung stabil, k-Means konvergiert.

  Endergebnis:  C1 = {d1, d3, d4, d6, d10}
                C2 = {d2, d5, d7, d8, d9}
  Gegenprobe sklearn KMeans: gleiche Partition = True

Die beiden Cluster trennen die zehn Punkte praktisch entlang der Temperatur: $C_1$ sammelt die kühleren Punkte (Temp 5–8) um $S_1 = (0{,}2; 1{,}0; 6{,}6)$, $C_2$ die wärmeren (Temp 8–11) um $S_2 = (0{,}2; 0{,}4; 9{,}0)$. sklearn.cluster.KMeans mit identischer Initialisierung liefert exakt dieselbe Partition — die Handrechnung stimmt.

Interessant ist der Abgleich mit der (für das Clustering ungenutzten) Wachstums-Klasse: $C_1$ ist mehrheitlich „gut” (4:1), $C_2$ mehrheitlich „schlecht” (4:1). Die gefundenen Cluster decken sich also nur grob, nicht exakt mit der Zielklasse — ein schönes Beispiel dafür, dass unüberwachtes Lernen seine eigene Struktur findet (hier: die Temperatur), die mit der vom Menschen gemeinten Klasse nicht identisch sein muss.

Aufgabe 3b (Blatt 9): kNN-Zuordnung der Punkte 11 und 16#

Jetzt sind die zehn Punkte mit ihrem Cluster-Label aus A3a fixiert, und die neuen Punkte werden gegen diese Cluster klassifiziert — derselbe euklidische Abstand wie in A3a, aber als kNN-Einordnung:

=== A3b: kNN-Zuordnung der Punkte Nr.11 und Nr.16 ===
  k=1: Nr.11 = (1, 1, 7) -> C1   (nächste: d1)
  k=1: Nr.16 = (0, 1, 4) -> C1   (nächste: d4)
  k=3: Nr.11 = (1, 1, 7) -> C1   (nächste: d1, d3, d2)
  k=3: Nr.16 = (0, 1, 4) -> C1   (nächste: d4, d6, d1)

Beide Punkte landen — für $k=1$ wie für $k=3$ — in $C_1$, dem kühleren Cluster: Nr. 11 $(1,1,7)$ liegt am dichtesten an $d_1$, Nr. 16 $(0,1,4)$ an $d_4$, beide $C_1$-Mitglieder. Das passt zur Anschauung, da $C_1$ die niedrigen Temperaturen versammelt und beide Anfragen mit Temp 7 bzw. 4 dort hineingehören.

Wahl von k: Ellenbogen auf make_blobs#

Um die Wahl von $k$ greifbar zu machen, lasse ich k-Means zusätzlich auf einem synthetischen Datensatz mit vier bekannten Clustern laufen und trage die Inertia über $k$ auf:

=== Ellenbogen-Heuristik auf make_blobs (4 echte Cluster) ===
  k=1: Inertia =  21335.9
  k=2: Inertia =   8215.0
  k=3: Inertia =   2725.9
  k=4: Inertia =    460.8
  k=5: Inertia =    412.5
  ...
  -> deutlicher Knick bei k=4 (die wahre Clusterzahl).

Der Sprung von $k=3$ auf $k=4$ senkt die Inertia drastisch (von 2726 auf 461), danach bringt jedes weitere Cluster fast nichts mehr — der „Ellenbogen” sitzt sauber bei der wahren Clusterzahl 4.

Querbezüge#

• 3.2 (Klassifikation, kNN): Der direkteste Bezug. Thema 3.2 verarbeitet denselben Wachstums-Datensatz, dort aber überwacht — mit dem Label „Wachstum” als Ziel. Hier ignoriert das Clustering dieses Label und findet stattdessen die Temperatur-Struktur. A3b benutzt obendrein dasselbe kNN-Verfahren wie 3.2, nur gegen selbst erzeugte statt vorgegebene Klassen — der Kontrast Schubladen bauen vs. einsortieren wird am gleichen Material buchstäblich vorgeführt.
• 3.1 (ML-Grundlagen): Clustering ist hier der Hauptvertreter des unüberwachten Lernens und ergänzt die dort eingeführte Dreiteilung überwacht / unüberwacht / bestärkend.
• 5.2 (Assoziationsregeln): Das Nachbarthema im Data Mining sucht ebenfalls unüberwacht nach Struktur — dort allerdings nach häufigen Merkmalskombinationen statt nach Punktgruppen.
• Lineare Algebra & Numerik: Inertia ist eine Summe quadrierter euklidischer Normen, die Zentren sind Mittelwertvektoren; der Verschiebe-Schritt ist eine Projektion auf den Schwerpunkt. k-Means ist damit Gradientenfreies Block-Koordinaten-Optimieren eines nicht-konvexen Ziels — die lokalen Optima sind kein Bug, sondern Folge der Nicht-Konvexität.
• Stochastik: Das EM/GMM-Verfahren ist Maximum-Likelihood-Schätzung für ein Mischmodell aus Normalverteilungen; die „weiche” Zugehörigkeit $P(C_i \mid x)$ ist eine Posterior-Wahrscheinlichkeit nach Bayes.
• Algorithmen & Datenstrukturen: Das exakte k-Means-Optimum ist NP-schwer; Lloyd ist die klassische Heuristik. Agglomeratives hierarchisches Clustern ist im Kern wiederholtes „Finde-das-nächste-Paar” — verwandt mit Greedy-Verschmelzung wie beim Aufbau eines Minimal-Spannbaums.

Quellen#

• Foliensatz _410_DM_Cluster.pdf — Grundlage für die Einordnung ins Data Mining, die Schrittfolge des k-Means (Initialisierung / Zuordnen / Verschieben) und die Abgrenzung Klassenbildung vs. Klassifizieren. Die Folien betonen zu Recht die starke Abhängigkeit des Ergebnisses von der Initialisierung — genau das, was die Insel sichtbar macht. Die EM-Herleitung dort habe ich nur als Skizze übernommen und in eigenen Worten auf den Kern (weiche vs. harte Zuordnung) verdichtet.
• Übungsblatt 9 ki_ueb370_DM.pdf — die hier gelösten Aufgaben 1, 2 (Prinzip-Skizzen) und 3 (A3a/A3b auf dem Wachstums-Datensatz); die Cluster-Berechnung ist in Python vollständig nachgerechnet.
• Lloyd (1982), Least squares quantization in PCM (IEEE Trans. Information Theory) — die Primärquelle des namensgebenden Lloyd-Algorithmus, der hinter k-Means steht.
• Russell & Norvig, Artificial Intelligence: A Modern Approach, Kap. 20 (Learning with Complete Data / Unsupervised Clustering) — als Referenz für die saubere Formulierung von k-Means als Spezialfall von EM konsultiert.
• scikit-learn (KMeans, make_blobs, KNeighborsClassifier) — als unabhängige Gegenprobe zur Handrechnung benutzt; die Dokumentationsseite zum Clustering (auch in den Folien verlinkt) gibt einen guten Überblick über die hier nur gestreiften Verfahren (DBSCAN, agglomeratives Clustern).