2.4 Clusteranalyse

Die PCA reduziert die Zahl der Variablen. Die Clusteranalyse dagegen fasst Datenpunkte zu Gruppen zusammen. Beides sind unüberwachte Verfahren und lassen sich kombinieren.

Was ist Clusteranalyse?

📄 03_dimred.pdf, Folie 39

Situation: Die Daten werden in einem Merkmalsraum repräsentiert. Ihre Ähnlichkeit entspricht der Distanz im Merkmalsraum: nahe Punkte sind ähnlich, ferne unähnlich.

Clusteranalyse (cluster analysis)

Gegeben eine Objektmenge. Ordne die Objekte in Gruppen von zueinander ähnlichen Mengen (Cluster) an, so dass Punkte im selben Cluster ähnlich sind und Punkte in verschiedenen Clustern weniger ähnlich.

• Die Clusteranalyse braucht ein Ähnlichkeits- oder Distanzmaß.
• Sie gehört zu den unüberwachten Lernverfahren (unsupervised learning), da die Daten nicht gelabelt sein müssen. Es gibt keine „richtige Antwort“, mit der man vergleichen könnte.

Ergänzung zum Unterschied zur Klassifikation: Bei der Klassifikation (überwacht) sind die Klassen vorgegeben und man lernt aus Beispielen mit Label, neue Punkte zuzuordnen. Bei der Clusteranalyse werden die Gruppen erst aus den Daten gefunden.

Clusteranalyse ist nicht immer eindeutig

📄 03_dimred.pdf, Folie 40

Dieselben 20 Punkte lassen sich sinnvoll in zwei, vier oder sechs Cluster einteilen. Welche Einteilung „richtig“ ist, hängt vom Zweck und vom gewünschten Detaillierungsgrad ab, nicht nur von den Daten.

Konsequenz: Ein Clusterverfahren braucht immer Zusatzannahmen, z.B. die Anzahl der Cluster ($K$ bei k-Means) oder eine Distanzschwelle. Ein Ergebnis ist kein Beweis, dass die Daten „wirklich“ so gruppiert sind.

Ähnlichkeitsmaße und Gruppenbildung

📄 03_dimred.pdf, Folie 41

Je nach Art der Variablen braucht man unterschiedliche Ähnlichkeitsmaße:

Variablentyp	Beispiel	Ähnlichkeitsmaß
binär (zwei Werte)	Merkmal vorhanden ja/nein	z.B. Jaccard-Koeffizient
nominal/ordinal (mehrere diskrete Werte)	Farbe, Schulnote	z.B. Chi-Quadrat-Koeffizient, Phi-Koeffizient
metrisch (kontinuierlich)	Größe, Pixelhelligkeit	z.B. euklidische Distanz, Korrelation, Kovarianz, Korrelationskoeffizient

Ergänzung, zwei Maße genauer:

• Euklidische Distanz: $d(\mathbf x,\mathbf y)=\lVert\mathbf x-\mathbf y\rVert=\sqrt{\sum_i(x_i-y_i)^2}$. Das ist das Maß, das k-Means verwendet.
• Jaccard-Koeffizient zweier Mengen (bzw. binärer Vektoren): $J(A,B)=\frac{\lvert A\cap B\rvert}{\lvert A\cup B\rvert}$. Beispiel: $A=\{1,2,3\}$, $B=\{2,3,4\}$ ergibt $J=2/4=0.5$. Gemeinsames Fehlen eines Merkmals zählt nicht als Ähnlichkeit. Das ist sinnvoll, wenn die meisten Merkmale bei den meisten Objekten fehlen (z.B. gekaufte Produkte).

Man unterscheidet drei Formen der Gruppenbildung:

Form	Bedeutung
nichtüberlappend (hard)	jedes Objekt ist in genau einem Cluster
überlappend	ein Objekt kann in mehreren Clustern sein
fuzzy	jedes Objekt gehört jedem Cluster mit einem bestimmten Grad des Zutreffens an (z.B. 70 % Cluster A, 30 % Cluster B)

Partitionierende und hierarchische Clusterverfahren

📄 03_dimred.pdf, Folie 42

Partitionierende Clusterverfahren (partitional clustering):

• nichtüberlappende Gruppenbildung,
• die Anzahl der Cluster wird vorab festgelegt,
• gelernt werden die Partitionsgrenzen.
• Beispiel: k-Means. Im Bild werden die Simpsons in zwei Gruppen geteilt: Familie Simpson und Schulpersonal.

Hierarchische Clusterverfahren (hierarchical clustering):

• überlappende Gruppenbildung: Die Cluster sind ineinander verschachtelt, ein Objekt gehört zu einem kleinen Cluster und gleichzeitig zu allen größeren, die diesen enthalten,
• die Objekte werden hierarchisch zusammengefasst, das Ergebnis ist ein Baum (Dendrogramm),
• entweder ausgehend von den Einzelobjekten (agglomerativ, bottom up: immer die zwei ähnlichsten Gruppen verschmelzen)
• oder von der Gesamtmenge (divisiv, top down: immer eine Gruppe aufteilen).

Ergänzung: Der Vorteil hierarchischer Verfahren ist, dass man $K$ nicht vorher festlegen muss. Man schneidet den Baum nachträglich auf der gewünschten Höhe ab und erhält so jede der Einteilungen von 📄 03_dimred.pdf, Folie 40.

Datenreduktion durch Clustern

📄 03_dimred.pdf, Folie 43

Clustern ist nicht nur Selbstzweck, sondern auch ein Werkzeug zur Datenreduktion:

1. Weniger Datenpunkte: Eine große Datenmenge wird durch eine kleinere Menge von Repräsentanten (z.B. die Clusterzentren) dargestellt. Das erleichtert das Training vieler Lernalgorithmen, deren Laufzeit stark mit der Datenmenge ansteigt.
2. Merkmalsextraktion: Die gefundenen Clusterzentren dienen als Codebuch (codebook), in das neue Eingabedaten projiziert werden. Neue Merkmale sind dann z.B.:
   • die Projektion auf die Clusterzentren,
   • die Distanz zu jedem der $K$ Zentren (ergibt $K$ Merkmale),
   • eine binäre Indikatorfunktion („gehört zu Cluster $k$“, also One-Hot-Kodierung).
3. Ein einfacher, häufig eingesetzter Clusteralgorithmus ist k-Means bzw. die Vektorquantisierung. Er konvergiert beweisbar immer, das zugrunde liegende Optimierungsproblem ist aber NP-hart.
4. Vorsicht: Der Algorithmus funktioniert nur bei relativ niedrigdimensionalen Daten gut. Eventuell muss vorher eine Dimensionsreduktion erfolgen, z.B. mit der PCA.

Ergänzung, warum niedrigdimensional: In hohen Dimensionen werden euklidische Abstände immer ähnlicher (alle Punkte sind „ungefähr gleich weit“ voneinander entfernt, ein Aspekt des Fluchs der Dimensionalität). Ein Verfahren, das nur auf Abständen beruht, hat dann kaum noch Unterscheidungskraft. Typische Pipeline: erst PCA auf wenige Komponenten, dann k-Means auf den Scores.

Ergänzung zum Namen „Vektorquantisierung“: Jeder Datenvektor wird durch den Index seines nächsten Codebuchvektors ersetzt, also „quantisiert“, so wie beim Runden eine reelle Zahl durch die nächste Ganzzahl ersetzt wird. Bei $K=256$ Zentren genügt ein Byte pro Datenpunkt.

Wie k-Means genau funktioniert, zeigt 2.5.