12  Clusteranalyse

12.1 Die Folien zur Sitzung

full screen

Der Vorlesungsmitschnitt

Mit der Clusteranalyse wird versucht, Elemente (Fälle) nach ihren Merkmalen (mehrere Variablen) in Gruppen (Clustern) zusammenzufassen. Die Problemstellung lautet als: Wie können Fälle in einem Datensatz nach mehreren Variablen gruppiert werden?

Die Clusteranalyse gehört zu den explorativen Verfahren. Im Kontext des Machine Learnings (ML) wird sie auch zu den «unsupervised learning»-Verfahren gezählt.

Das Grundsätzliche Vorgehen ist bei allen Arten von Clusteranalysen gleich bzw. ähnlich: Wir suchen Gruppen (Cluster) von Fällen, die sich untereinander so stark wie möglich ähneln (homoge Cluster) und so stark von den anderen Gruppen unterscheiden wie möglich. Es geht also um Segmentierung anhand von Mustern in den Daten und nicht um Sortierung anhand vorgegebener Kategorien. Wir wollen also stark Vereinfachen (wenige Cluster), aber auch wenig Heterogenität in den Clustern, wobei die eben immer kleiner wird, je mehr Cluster man bildet. Das führt zu einem Optimierungsproblem (siehe Abbildung 12.1), das die Clusteranalyse ganz gut lösen kann, da in der Regel die Heterogenität innerhalb der Cluster stark sinkt, wenn man ein Cluster in zwei aufteilt und auch dann, wenn man drei Cluster versucht zu finden und zu optimieren, aber schon etwas weniger als von eins auf zwei. Wenn man statt drei, vier Cluster zulässt und verteilt, dann sinkt die Heterogenität nochmals weiter, aber wieder etwas weniger als im Schritt davor. Das schauen wir weiter unten nochmal technisch an, wenn es um den «Heterogenitätsknick» geht, der als «Ellenbogen» gesehen werden und damit als Kriterium für eine gute Clusterlösung herhalten kann.

Abbildung 12.1: Optimierungsproblem der Clusteranalyse

12.2 Voraussetzungen von Clusteranalysen generell

1. Nicht zu viele fehlende Werte, da fehlende Werte die Clusterbildung verzerren.

2. Das Skalenniveau spielt grundsätzlich keine Rolle, da Methoden der Clusteranalyse gibt (hierarchische Clusteranalyse), die auch mit kategorialen (nominale mit mehreren Ausprägungen) Variablen und ordinalen Variablen gut umgehen kann. Bei Clusteranalysemethoden mit Distanzmassen (wie k-Means-Clustering) müssen die Distanzen interpretierbar sein und mithin metrisch skaliert, was aber auch von den Dummys erfüllt wird.

3. Die Fallzahl sollte nicht zu klein sein. Es werden für brauchbare Clusteranalysen ordentliche Fallzahlen benötigt. Vor allem gilt das, wenn einzelne Variablenkombinationen (wichtig für die Gruppenbildung) dünn besetzt sind.

4. Die Variablen sollten ähnlich skaliert sein, damit nicht eine Variable mit einem deutlich grösserem Gewicht in die Clusteranalyse eingeht, nur weil sie breiter skaliert ist. Bei sehr unterschiedlichen Skalierungen empfiehlt sich eine vorherige Standardisierung (z-Transformation bzw. scale) der Variablen (bei vorheriger Faktorenanalyse ist das schon gegeben, weil Faktoren immer standardisiert sind (\(\overline{x}\) = 0, sd = 1)).¹

12.3 Vorgehensweise

1. Als Grundlage von Clusteranalysen dienen Variablen im Datensatz. Man wählt Variablen aus, von denen man annimmt, dass sie charackteristisch sind für die Gruppenbildung, die man anstrebt.

2. Aufbereitung der Variablen:

• Die Variablen für die Clusteranalyse sollten nicht zu stark korrelieren. Sollte das der Fall sein, kann eine explorative Faktorenanalyse durchgeführt werden, um dann die Clusteranalyse mit den Faktoren und separaten Variablen durchzuführen, die eine hohe Uniqueness (kleine Kommunalitäten) in der Faktorenenalyse haben (siehe Kapitel 8).
• Sind die Variablen sehr unterschiedlich skaliert (zB Alter 15-107 und Wahlabsicht 0 und 1), sollte man die Variablen standardisieren (z-transformieren), damit jede Variable in die Clusteranalyse mit demselben Gewicht eingeht (Es sei denn, man möchte einzelen Variablen höher gewichten. In dem Fall empfehle ich, die Variablen nach der Standardisierung mit einem Faktor zu multiplizieren, also zB das standardisierte Alter mit 0.5 und die standardisierte Wahlabsicht mit 2, wenn die höher gewichtet sein soll.)

3. Bevor man zur eigentlichen Clusteranalyse schreitet, muss man ein gutes Mass für die Ähnlichkeit oder die Distanz wählen («Proximitätsmasse»).

4. An dieser Stelle weichen verschiedene Clusteranalysen voneinander ab.

• Bei der hierarchischen Clusteranalyse werden an diesem Punkt die Cluster zusammengelegt, also vom Ausgangspunkt, dass jeder Fall ein Cluster ist, bis dahin, dass alle Fälle in einem Cluster zusammenglegt sind. Das passiert schrittweise, indem in jedem Schritt alle Cluster miteinander verglichen werden und jeweils die beiden ähnlichsten zusammengelegt werden.
• Bei der K-mean-Clusteranalyse muss an dieser Stelle mit Hilfe eines Screeplots bestimmt und festgelegt werden, wie viele Cluster es geben soll.

5. Da der Schritt 4 für verschiedene Clusteranalysen unterschiedlich ist, ist es auch der Schritt 5.

• Bei der hierarchischen Clusteranalyse wird hier die Anzahl Cluster anhand des Dendrogramms (oder alternativ durch einen Screeplot) bestimmt.
• Bei der K-mean-Clusteranalyse werden in diesem Schritt die Cluster extrahiert, indem zunächst die Clusterzentren zufällig in den Merkmalsraum (multidimensionales Koordinatensystem aller Variablen in der Analyse) gelegt werden. Dann werden diesen Clusterzentren alle ihnen jeweils nächsten Fälle zugeordnet. Dann werden die Clusterzentren ins Zentrum ihrer Fälle verschoben und dann die Fälle neu zugeordnet. Das passiert so oft, bis die Clusterzentren nicht mehr ihre Position verändern (und alle Fälle in ihren Clustern verbleiben).

6. Die Clusterzuorndung wird in den Daten gespeichert.

7. Jetzt werden die Cluster charakterisiert (interpretiert), indem geschaut wird, wie die Variablen in den verschiedenen Clustern aussehen, welche Mittelwerte sie zum Beispiel haben oder wie hoch die Prozentanteile einzelner Werte (1 bei Dummys) sind.

12.4 Proximitätsmasse

Diese «Proximitätsmasse» können folgende Distanzmasse sein: euklidische Distanzen bei metrischen Variablen:

Die Distanz d ist die Wurzel der Summe aller quadrierten Abstände in den Richtungen der Variablendimensionen: \(d = \sqrt{(q_1-p_1)^2 + (q_2-p_2)^2}\). Das kommt aus der euklidischen Geometrie und kennen Sie sicher aus der Formel für die Seitenlängen in rechtwinkligen Dreiecken mit \(a^2 + b^2 = c^2\), also Ankathete zum Quadrat plus Gegenkathete zum Quadrat ist gleich der Hypothenuse zum Quadrat. Das nur schnell als Antwort auf ihre alte Frage aus Schulzeiten, wozu sie das wohl jemals brauchen würden. 😃 Siehe auch Abbildung 12.2.

Abbildung 12.2: Euklidische Distanz

Es gibt weitere Distanzmasse auch für metrische Variablen. Bei dichotomen Variablen gibt es noch den M-Koeffizienten, der schlicht die Übereinstimmungen wiedergibt (also in allen Variablen eine 1 oder in allen Variablen eine 0 oder nur in Teilen usw.).

Neben diesen Massen für die Distanz bzw. Nähe im geometrischen Sinne, gibt es noch Ähnlichkeitsmasse. Dazu zählt zum Beispiel der Q-Korrelationskoeffizient, der dasselbe ist, wie Pearsons Korrelationskoeffizient. Die Korrelationen können bei stetigen Variablen verwendet werden. Bei kategoriellen Merkmalen kann \(\chi^2\) verwendet werden. Eine kleine Systematik der Clusteranalyse findet sich in Abbildung 12.3.

Abbildung 12.3: Cluster-Analyse-Systematik

Dann muss noch der Cluster-Algorithmus gewählt werden. Es gibt die «Hierarchische Clusteranalyse» mit «Single-Linkage» und mit «Complete Linkage». Für metrische Variablen können partionierende Clusteranalysen eingesetzt werden, wie der k-Means-Algorithmus oder der Two-Stage-Algorithmus. Die einfachste Methode ist im Grunde die k-Means-Cluster-Methode, die daher hier als erste etwas genauer angeschaut und in R berechnet werden sollte.

Nehmen Sie also den Code und probieren Sie es aus. So können Sie praktisch üben.

12.5 Die k-Means-Cluster-Methode

In der schrittweisen «Animation» der k-Means-Clusterung sieht man, wenn man genau hinschaut, wie die Cluster am Anfang zufällig verteilt werden, dann alle Fälle, den ihnen am nächsten gelegenen Clusterzentrum zugeordnet werden und die «Clusterzentren» eigentlich erst dann in das Zentrum ihres Clusters gelegt werden. Dann kann es vorkommen, dass einzelne Fälle dichter an einem anderen Cluster liegen und werden deshalb eben dem Cluster zugeordnet, in dessen Nähe sie liegen. Danach liegen die Clusterzentren wieder nicht mehr genau im Zentrum ihres eigenen Clusters und werden erneut so verschoben, dass sie genau in dessen Mitte liegen. Das «konvergiert» dann in der Regel irgendwann. Das heisst, bei jedem neuen Schritt würde kein Fall sein Cluster wechseln und darum auch die Clusterzentren unbewegt da bleiben wo sie sind. Das ist dann die Lösung!

Abbildung 12.4: k-means-Cluster Prinzip

Abbildung 12.5: k-means-Cluster Prinzip

Abbildung 12.6: k-means-Cluster Prinzip

Abbildung 12.7: k-means-Cluster Prinzip

Abbildung 12.8: k-means-Cluster Prinzip

Abbildung 12.9: k-means-Cluster Prinzip

Mit diesen Befehlen kann man eine schöne Clusteranalyse laufen lassen.

DATEN <- iris |> 
  select(-Species)

# Compute k-means with k = 3
set.seed(123)
res.km <- kmeans(scale(DATEN), 3, nstart = 25)

# Dimension reduction using PCA
res.pca <- prcomp(DATEN,  scale = TRUE)

# Coordinates of individuals
ind.coord <- as.data.frame(factoextra::get_pca_ind(res.pca)$coord)
# Add clusters obtained using the K-means algorithm
ind.coord$cluster <- factor(res.km$cluster)
# Add Species groups from the original data sett
ind.coord$Species <- iris$Species
# Data inspection
# head(ind.coord)

# Percentage of variance explained by dimensions
eigenvalue <- round(factoextra::get_eigenvalue(res.pca), 1)
variance.percent <- eigenvalue$variance.percent

# head(eigenvalue)

ggpubr::ggscatter(
  ind.coord, x = "Dim.1", y = "Dim.2", 
  color = "cluster", palette = "npg", ellipse = TRUE, ellipse.type = "convex",
  shape = "Species", size = 1.5,  legend = "right", ggtheme = theme_bw(),
  xlab = paste0("Dim 1 (", variance.percent[1], "% )" ),
  ylab = paste0("Dim 2 (", variance.percent[2], "% )" )
) +
  ggpubr::stat_mean(aes(color = cluster), size = 4)

LEF 12

Essayfragen 12

E12.1 a) Was ist das Ziel einer Clusteranalyse? b) Was ist der Unterschied zu einer Faktorenanalyse?

E12.2 Welches Skalenniveau wird benötigt, wenn bei einer Clusteranalyse «Clusterzentren» berechnet werdenn sollen?

E12.3 Wie ist der grobe Ablauf einer k-means-Clusteranalyse?

E12.4 Warum werden Clusteranalysen im Kontext von ML als «unsupervised learning» bezeichnet?

E12.5 Warum kann man nicht einfach sagen, dass die Clusterlösung mit der kleinsten Heterogenität (mittlere Distanz zu Clusterzentren) die beste Lösung ist?

E12.6 Warum werden oft Faktorenanalysen vor den Clusteranalysen durchgeführt?

E12.7 Was verbirgt sich hinter der Abkürzung «ML»?

E12.8 Wozu dient bei einer Clusteranalyse das «Ellbogenkriterium»?

E12.9 Warum sind hierarchische Clusteranalysen für Big Data oder zum Beispiel Bildanalysen ungeeignet?

E12.10 NEU Bringen Sie die folgenden Ablaufschritte einer hierarchischen Clusteranalyse in die richtige Reihenfolge:

• Clusteralgorithmus wählen (single linkage)
• Anzahl Cluster bestimmen (zB mit Dendrogramm)
• Clustervariable(n) festlegen
• jedem Fall ein Cluster bauen
• den letzten Schritt so lange tun, bis es nur noch ein Cluster gibt
• zwei Cluster zusammenlegen
• Clusterlösung interpretieren

MC-Fragen 12

MC 12.1.

MC 12.1: Sind folgende Aussagen richtig oder falsch?

MC_12_1 = [
    ["Clusteranalysen dienen der Zusammenfassung von Fällen in Gruppen.", "richtig"],
    ["Mit Clusteranalysen werden Variablen zusammengefasst.", "falsch"],
    ["Mit der Clusteranalyse werden möglichst unähnliche Fälle in Clustern zusammengefasst.", "falsch"],
    ["Die Clusteranalyse ist ein exploratives Verfahren.", "richtig"]
]

viewof answers_12_1 = quizInput({
  questions: MC_12_1,
  options: ["richtig", "falsch"]
})

Punkte_12_1 = {
const Sum = 
    (answers_12_1[0] == MC_12_1[0][1])*1 + 
    (answers_12_1[1] == MC_12_1[1][1])*1 + 
    (answers_12_1[2] == MC_12_1[2][1])*1 + 
    (answers_12_1[3] == MC_12_1[3][1])*1 

var Punkte_12_1 = Sum - 2
if (Punkte_12_1 < 1) {Punkte_12_1 = 0}
return(Punkte_12_1)
}

Punkte:

MC 12.2.

MC 12.2: Sind folgende Aussagen richtig oder falsch?

MC_12_2 = [
    ["Die Clusteranalyse wird im ML-Kontext als «unsupervised learning» behandelt.", "richtig"],
    ["Ziel der Clusteranalyse ist eine Reduktion der Fälle auf wenige untereinander homegene Cluster bei möglichst geringer Homogenität innerhalb der Cluster.", "falsch"],
    ["Häufig werden Clusteranalysen vor Faktorenanalysen durchgeführt, damit letztere besser fitten.", "falsch"],
    ["Damit die Variablen nicht hoch korrelieren, werden vor CAs oft FAs durchgeführt.", "richtig"]
]

viewof answers_12_2 = quizInput({
  questions: MC_12_2,
  options: ["richtig", "falsch"]
})

Punkte_12_2 = {
const Sum = 
    (answers_12_2[0] == MC_12_2[0][1])*1 + 
    (answers_12_2[1] == MC_12_2[1][1])*1 + 
    (answers_12_2[2] == MC_12_2[2][1])*1 + 
    (answers_12_2[3] == MC_12_2[3][1])*1 

var Punkte_12_2 = Sum - 2
if (Punkte_12_2 < 1) {Punkte_12_2 = 0}
return(Punkte_12_2)
}

Punkte:

MC 12.3.

MC 12.3: Sind folgende Aussagen richtig oder falsch?

MC_12_3 = [
    ["Clusteranalysen sind vor allem für die Analyse fehlender Werte geeignet.", "falsch"],
    ["Es gibt Clusteranalyseverfahren, die mit allen möglichen Skalenniveaus gut klarkommen.", "richtig"],
    ["Clusteranalysen funktionieren besonders gut mit kleinen Fallzahlen.", "falsch"],
    ["Es kann immer höchstens so viele Cluster geben, wie es Variablen gibt.", "falsch"]
]

viewof answers_12_3 = quizInput({
  questions: MC_12_3,
  options: ["richtig", "falsch"]
})

Punkte_12_3 = {
const Sum = 
    (answers_12_3[0] == MC_12_3[0][1])*1 + 
    (answers_12_3[1] == MC_12_3[1][1])*1 + 
    (answers_12_3[2] == MC_12_3[2][1])*1 + 
    (answers_12_3[3] == MC_12_3[3][1])*1 

var Punkte_12_3 = Sum - 2
if (Punkte_12_3 < 1) {Punkte_12_3 = 0}
return(Punkte_12_3)
}

Punkte:

MC 12.4.

MC 12.4: Sind folgende Aussagen richtig oder falsch?

MC_12_4 = [
    ["Proximitätsmasse sind Ähnlichkeits- beziehungsweise Distanzmasse.", "richtig"],
    ["Euklidische Distanzen können nur für metrische Variablen festgestellt werden.", "richtig"],
    ["Für eine Clusteranalyse werden immer mindestens so viele Variablen benötigt, wie man Cluster extrahieren will.", "falsch"],
    ["Manche Clusteralgorithmen nehmen als Ähnlichkeitsmass auch die Korrelation.", "richtig"]
]

viewof answers_12_4 = quizInput({
  questions: MC_12_4,
  options: ["richtig", "falsch"]
})

Punkte_12_4 = {
const Sum = 
    (answers_12_4[0] == MC_12_4[0][1])*1 + 
    (answers_12_4[1] == MC_12_4[1][1])*1 + 
    (answers_12_4[2] == MC_12_4[2][1])*1 + 
    (answers_12_4[3] == MC_12_4[3][1])*1 

var Punkte_12_4 = Sum - 2
if (Punkte_12_4 < 1) {Punkte_12_4 = 0}
return(Punkte_12_4)
}

Punkte:

MC 12.5.

MC 12.5: Sind folgende Aussagen richtig oder falsch?

MC_12_5 = [
    ["k-means-Cluster kann nur auf metrische (und Dummys) angewendet werden.", "richtig"],
    ["Bei k-means-Cluster sind ähnliche Standardabweichungen der Variablen erwünscht.", "richtig"],
    ["Bei k-means-cluster müssen hohe Korrelationen zwischen den Variablen vorliegen. ", "falsch"],
    ["Mit dem Ellbogenkriterium werden Clusterzentren einander zugeordnet.", "falsch"]
]

viewof answers_12_5 = quizInput({
  questions: MC_12_5,
  options: ["richtig", "falsch"]
})

Punkte_12_5 = {
const Sum = 
    (answers_12_5[0] == MC_12_5[0][1])*1 + 
    (answers_12_5[1] == MC_12_5[1][1])*1 + 
    (answers_12_5[2] == MC_12_5[2][1])*1 + 
    (answers_12_5[3] == MC_12_5[3][1])*1 

var Punkte_12_5 = Sum - 2
if (Punkte_12_5 < 1) {Punkte_12_5 = 0}
return(Punkte_12_5)
}

Punkte:

MC 12.6.

MC 12.6: Mal was zu R?

MC_12_6 = [
    ["Clusteranalysen haben eher deskriptiven Analysegehalt.", "richtig"],
    ["Clusteranalysen werden häufig eingesetzt um Typologien zu bilden.", "richtig"],
    ["Hierarchische Clusteranalysen sind bei hohen Fallzahlen so rechenaufwendig, dass  selbst moderne Rechner eher verrottet sind als sie mit der Analyse fertig werden.", "richtig"],
    ["Die Clusterzentren der k-means-Cluster korrelieren hoch miteinander.", "falsch"]
]

viewof answers_12_6 = quizInput({
  questions: MC_12_6,
  options: ["richtig", "falsch"]
})

Punkte_12_6 = {
const Sum = 
    (answers_12_6[0] == MC_12_6[0][1])*1 + 
    (answers_12_6[1] == MC_12_6[1][1])*1 + 
    (answers_12_6[2] == MC_12_6[2][1])*1 + 
    (answers_12_6[3] == MC_12_6[3][1])*1 

var Punkte_12_6 = Sum - 2
if (Punkte_12_6 < 1) {Punkte_12_6 = 0}
return(Punkte_12_6)
}

Punkte:

Punkte_12_max = 12

Punkte_12_Gesamt = Punkte_12_1 + Punkte_12_2 + Punkte_12_3 + Punkte_12_4 + Punkte_12_5 + Punkte_12_6

Prozent_12_Gesamt = round(120*Punkte_12_Gesamt/Punkte_12_max, 0)

Note_12_grob = round((round(Punkte_12_Gesamt/Punkte_12_max,1)*12+2)/2, 1)

Insgesamt von Punkten, was % und etwa einer entspricht.

round = (n, places) => {
  if (!places) return Math.round(n);
  const d = 10 ** places;
  return Math.round(n * d) / d;
}

function quizInput({ questions, options}) {
  let answers = questions.map(() => null);
  let root = htl.html`<div
      style="
        display: grid;
        grid-template-columns: 10% 10% 70% 10%;"
    >
      ${options.map(
        (opt) => htl.html`<div style="font-weight: bold; font-size: HUGE">${opt}</div>`
      )}
      <div style="font-weight: bold">Aussagen</div>
      <div style="font-weight: bold"></div>
      ${Array.from(questions.entries(), ([i, [question, correct]]) =>
        quizInputRow({
          question,
          options,
          correct,
          onChange: (newAnswer) => {
            answers[i] = newAnswer;
            root.value = answers;
            root.dispatchEvent(new CustomEvent("input"));
          }
        })
      )}
    </div>`;
  root.value = answers;
  return root;
}

function quizInputRow({
  question,
  options,
  correct,
  onChange = () => {}
}) {
  let root = htl.html`<div>`;

  function setAnswer(answer, initial = false) {
    morph(
      root,
      htl.html`<div style="display: contents"> 
      <form style="display: contents">
        ${options.map(
          (opt) =>
            htl.html`<label>&emsp;</label> 
            <input  
              name=${question} &emsp;
              type="radio"
              value="${opt}"
              checked=${opt === answer}
              onChange=${() => setAnswer(opt)}
            >
            </input>`
        )}
      </form>
      <div>${question}</div>
      <div> &emsp; ${
       answer === null ? "" : answer === correct ? "💚" : "❌"
      }</div>
    </div>`
    );

    root.value = answer;
    if (!initial) {
      root.dispatchEvent(new CustomEvent("input"));
      onChange(answer);
    }
  }

  setAnswer(null, true);
  return root;
}

morph = require("https://bundle.run/nanomorph@5.4.2")

MathJax = require("https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-AMS_CHTML")
  .catch(() => window.MathJax)
  .then(MathJax => {
    MathJax.Hub.Config({
      CommonHTML: { scale: 110 }, // scaling to get the same size as katex (but katex still has more spacing between lines...)
      tex2jax: { inlineMath: [["$", "$"], ["\\(", "\\)"]] },
      displayMath: [["$$", "$$"], ["\\[", "\\]"]],
      processEscapes: true,
      TeX: { extensions: ["autoload-all.js"] },
    });
    return new Promise(resolve =>
      MathJax.Hub.Register.StartupHook("End", () => resolve(MathJax))
    );
  })

---

1. Wenn man einzelne Variablen besonders wichtig findet in der Clusteranalyse, kann man sie erstmal standardisieren und dann mit einem Faktor multiplizieren, damit sie um den Faktor mit höherem Gewicht in die Analyse eingehen.