082_Clusteranalyse.Rmd

\part{Ungeleitetes Modellieren}



# Vertiefung: Clusteranalyse {#cluster}


```{r echo = FALSE, out.width = "30%", fig.align = "center"}
knitr::include_graphics("images/FOM.jpg")
```

```{r echo = FALSE, out.width = "10%", fig.align = "center"}
knitr::include_graphics("images/licence.png")
```



Benötigte Pakte:

```{r}
library(tidyverse)
library(cluster)
```

```{r}
library(broom)
```



```{block2, ziele-cluster, type='rmdcaution', echo = TRUE} 
Lernziele:

- Das Ziel einer Clusteranalyse erläutern können.
- Das Konzept der euklidischen Abstände verstehen.
- Eine k-Means-Clusteranalyse berechnen und interpretieren können.

```


## Grundlagen der Clusteranalyse

Das Ziel einer Clusteranalyse ist es, Gruppen von Beobachtungen (d. h. *Cluster*) zu finden, die innerhalb der Cluster möglichst homogen, zwischen den Clustern möglichst heterogen sind. Um die Ähnlichkeit von Beobachtungen zu bestimmen, können verschiedene Distanzmaße herangezogen werden. Für metrische Merkmale wird z. B. häufig die euklidische Metrik verwendet, d. h., Ähnlichkeit und Distanz werden auf Basis des euklidischen Abstands bestimmt. Aber auch andere Abstände wie "Manhattan" oder "Gower" sind möglich. Letztere haben den Vorteil, dass sie nicht nur für metrische Daten sondern auch für gemischte Variablentypen verwendet werden können. Wir werden uns hier auf den euklidischen Abstand konzentrieren.


### Intuitive Darstellung der Clusteranalayse



```{r cluster-intuition, echo = FALSE}


set.seed(2014)
centers <- data.frame(cluster=factor(1:3), size=c(100, 150, 50), x1=c(5, 0, -3), x2=c(-1, 1, -2))
points <- centers %>% group_by(cluster) %>%
    do(data.frame(x1=rnorm(.$size[1], .$x1[1]),
                  x2=rnorm(.$size[1], .$x2[1])))

p1 <- ggplot(points, aes(x1, x2)) + geom_point() +
  xlab("Lernzeit") + ylab("Klasurpunkte")

p2 <- ggplot(points, aes(x1, x2, color=cluster)) + geom_point() +
  xlab("Lernzeit") + ylab("Klasurpunkte")
```

Betrachten Sie das folgende Streudiagramm (die Daten sind frei erfunden; "simuliert", sagt der Statistiker). Es stellt den Zusammenhang von Lernzeit (wie viel ein Student für eine Statistikklausur lernt) und dem Klausurerfolg (wie viele Punkte ein Student in der Klausur erzielt) dar. Sehen Sie Muster? Lassen sich Gruppen von Studierenden mit bloßem Auge abgrenzen (Abb. \@ref(fig:cluster1))?

```{r cluster1, echo = FALSE, fig.cap = "Ein Streudiagramm - sehen Sie Gruppen (Cluster) ?"}
p1
```

Färben wir das Diagramm mal ein (Abb. \@ref(fig:cluster2)).

```{r cluster2, echo = FALSE, fig.cap = "Ein Streudiagramm - mit drei Clustern"}
p2
```

Nach dieser "Färbung", d.h. nach dieser Aufteilung in drei Gruppen, scheint es folgende "Cluster", "Gruppen" oder "Typen" von Studierenden zu geben:

 - "Blaue Gruppe": Fälle dieser Gruppe lernen wenig und haben wenig Erfolg in der Klausur. Tja.
 
 - "Rote Gruppe": Fälle dieser Gruppe lernen viel; der Erfolg ist recht durchwachsen.
 
 - "Grüne Gruppe": Fälle dieser Gruppe lernen mittel viel und erreichen einen vergleichsweise großen Erfolg in der Klausur.


Drei Gruppen scheinen ganz gut zu passen. Wir hätten theoretisch auch mehr oder weniger Gruppen unterteilen können. Die Clusteranalyse gibt keine definitive Anzahl an Gruppen vor; vielmehr gilt es, aus theoretischen und statistischen Überlegungen heraus die richtige Anzahl auszuwählen (dazu gleich noch mehr).

Unterteilen wir zur Illustration den Datensatz einmal in bis zu 9 Cluster (Abbildung \@ref(fig:cluster3)).


```{r cluster3, echo = FALSE, fig.cap = "Unterschiedliche Anzahlen von Clustern im Vergleich"}


points.matrix <- cbind(x1 = points$x1, x2 = points$x2)
kclust <- kmeans(points.matrix, 3)
kclusts <- data.frame(k=1:9) %>% group_by(k) %>% do(kclust=kmeans(points.matrix, .$k))

clusters <- kclusts %>% group_by(k) %>% do(tidy(.$kclust[[1]]))
assignments <- kclusts %>% group_by(k) %>% do(augment(.$kclust[[1]], points.matrix))
clusterings <- kclusts %>% group_by(k) %>% do(glance(.$kclust[[1]]))

p3 <- ggplot(assignments, aes(x1, x2)) + geom_point(aes(color=.cluster)) + facet_wrap(~ k)


p4 <- p3 + geom_point(data=clusters, size=10, shape="x")
p4
```

Das "X" soll den "Mittelpunkt" des Clusters zeigen. Der Mittelpunkt ist so gewählt, dass die Distanz von jedem Punkt zum Mittelpunkt möglichst kurz ist. Dieser Abstand wird auch "Varianz innerhalb des Clusters" oder kurz "Varianz within" bezeichnet. Natürlich wird diese Varianz within immer kleiner, je größer die Anzahl der Cluster wird.

```{r cluster4, echo = FALSE, fig.cap = "Die Summe der Varianz within in Abhängigkeit von der Anzahl von Clustern. Ein Screeplot."}
ggplot(clusterings, aes(k, tot.withinss)) + geom_line() + geom_vline(xintercept = 3, linetype = "dashed", color = "grey30") +
  xlab("Anzahl der Cluster") +
  ylab("Summe der Varianz within über alle Cluster") +
  scale_x_continuous(breaks = 1:9)

```

Die vertikale gestrichelte Linie zeigt an, wo die Einsparung an Varianz auf einmal "sprunghaft" weniger wird - just an jedem Knick bei x=3; dieser "Knick" wird auch "Ellbogen" genannt (da sage einer, Statistiker haben keine Phantasie). Man kann jetzt sagen, dass 3 Cluster eine gute Lösung seien, weil mehr Cluster die Varianz innerhalb der Cluster nur noch wenig verringern. Diese Art von Diagramm wird als "Screeplot" bezeichnet. Fertig!


### Euklidische Distanz

Aber wie weit liegen zwei Punkte entfernt? Betrachten wir ein Beispiel. Anna und Berta sind zwei Studentinnen, die eine Statistikklausur ~~geschrieben haben~~schreiben mussten (bedauernswert). Die beiden unterscheiden sich sowohl in Lernzeit als auch in Klausurerfolg. Aber wie sehr unterscheiden sie sich? Wie groß ist der "Abstand" zwischen Anna und Berta (vgl. Abb. \@ref(fig:distanz))?

```{r distanz, echo = FALSE, fig.cap = "Distanz zwischen zwei Punkten in der Ebene", out.width = "50%"}

knitr::include_graphics("images/cluster/distanz_crop.png")
```


Eine Möglichkeit, die Distanz zwischen zwei Punkten in der Ebene (2D) zu bestimmen, ist der *Satz des Pythagoras* (leise Trompetenfanfare). Generationen von Schülern haben diese Gleichung ähmm... geliebt:

$$c^2 = a^2 + b^2$$

In unserem Beispiel heißt das $c^2 = 3^2+4^2 = 25$. Folglich ist $\sqrt{c^2}=\sqrt{25}=5$. Der Abstand oder der Unterschied zwischen Anna und Berta beträgt also 5 - diese Art von "Abstand" nennt man den *euklidischen Abstand*\index{euklidischen Abstand}.

Aber kann man den euklidischen Abstand auch in 3D (Raum) verwenden? Oder gar in Räumen mehr mehr Dimensionen??? Betrachten wir den Versuch, zwei Dreiecke in 3D zu zeichnen. Stellen wir uns vor, zusätzlich zu Lernzeit und Klausurerfolg hätten wir als 3. Merkmal der Studentinnen noch "Statistikliebe" erfasst (Bertas Statistikliebe ist um 2 Punkte höher als Annas).

```{r pythagoras2, echo = FALSE, fig.cap = "Pythagoras in 3D", out.width = "50%"}

knitr::include_graphics("images/cluster/pythagoras2_crop.png")
```

Sie können sich Punkt $A$ als Ecke eines Zimmers vorstellen; Punkt $B$ schwebt dann in der Luft, in einiger Entfernung zu $A$.  

Wieder suchen wir den Abstand zwischen den Punkten $A$ und $B$. Wenn wir die Länge $e$ wüssten, dann hätten wir die Lösung; $e$ ist der Abstand zwischen $A$ und $B$. Im orangenen Dreieck gilt wiederum der Satz von Pythagoras: $c^2+d^2=e^2$. Wenn wir also $c$ und $d$ wüssten, so könnten wir $e$ berechnen... $c$ haben wir ja gerade berechnet (5) und $d$ ist einfach der Unterschied in Statistikliebe zwischen Anna und Berta (2)! Also

$$e^2 = c^2 + d^2$$
$$e^2 = 5^2 + 2^2$$
$$e^2 = 25 + 4$$

$$e = \sqrt{29} \approx 5.4$$

Ah! Der Unterschied zwischen den beiden Studentinnen beträgt also ~5.4!

Intuitiv gesprochen, "schalten wir mehrere Pythagoras-Sätze hintereinander".

>   Der euklidische Abstand berechnet sich mit Pythagoras' Satz!


```{r pythagoras, echo = FALSE, fig.cap = "Pythagoras in Reihe geschaltet"}

knitr::include_graphics("images/cluster/pythagoras_crop.png")
```

Das geht nicht nur für "zwei Dreiecke hintereinander", sondern der Algebra ist es wurscht, wie viele Dreiecke das sind.

>   Um den Abstand zweier Objekte mit *k* Merkmalen zu bestimmen, kann der euklidische Abstand berechnet werden mit. Bei k=3 Merkmalen lautet die Formel dann $e^2 = a^2 + b^2 + d^2$. Bei mehr als 3 Merkmalen erweitert sich die Formel entsprechend.


Dieser Gedanken ist mächtig! Wir können von allen möglichen Objekten den Unterschied bzw. die (euklidische) Distanz ausrechnen! Betrachten wir drei Professoren, die einschätzen sollten, wir sehr sie bestimmte Filme mögen (1: gar nicht; 10: sehr). Die Filme waren: "Die Sendung mit der Maus", "Bugs Bunny", "Rambo Teil 1", "Vom Winde verweht" und "MacGyver".

```{r}
profs <- data_frame(
  film1 = c(9, 1, 8),
  film2 = c(8, 2, 7),
  film3 = c(1, 8, 3),
  film4 = c(2, 3, 2),
  film5 = c(7, 2, 6)
)


```

Betrachten Sie die Film-Vorlieben der drei Professoren. Gibt es ähnliche Professoren hinsichtlich der Vorlieben? Welche Professoren haben einen größeren "Abstand" in ihren Vorlieben? 

Wir könnten einen "fünffachen Pythagoras" zu Rate ziehen. Praktischerweise gibt es aber eine R-Funktion, die uns die Rechnerei abnimmt:


```{r}
dist(profs)
```

Offenbar ist der (euklidische) Abstand zwischen Prof. 1 und 2 groß (13.2); zwischen Prof 2 und 3 auch recht groß (10.8). Aber der Abstand zwischen Prof. 1 und 3 ist relativ klein! Endlich hätten wir diese Frage auch geklärt. Sprechen Sie Ihre Professoren auf deren Filmvorlieben an...


### k-Means Clusteranalyse

Beim k-Means Clusterverfahren handelt es sich um eine bestimmte Form von Clusteranalysen; zahlreiche Alternativen existieren, aber die k-Means Clusteranalyse ist recht verbreitet. Im Gegensatz zur z.B. der hierarchischen Clusteranalyse um ein partitionierendes Verfahren. Die Daten werde in $k$ Cluster aufgeteilt -- dabei muss die Anzahl der Cluster im vorhinein feststehen. Ziel ist es, dass die Quadratsumme der Abweichungen der Beobachtungen im Cluster zum Clusterzentrum minimiert wird. 

Der Ablauf des Verfahrens ist wie folgt:

1.  Zufällige Beobachtungen als Clusterzentrum
2.  Zuordnung der Beobachtungen zum nächsten Clusterzentrum (Ähnlichkeit, z. B. über die euklidische Distanz)
3.  Neuberechnung der Clusterzentren als Mittelwert der dem Cluster zugeordneten Beobachtungen

Dabei werden die Schritte 2. und 3. solange wiederholt, bis sich keine Änderung der Zuordnung mehr ergibt -- oder eine maximale Anzahl an Iterationen erreicht wurde. Aufgrund von (1.) hängt das Ergebnis einer k-Means Clusteranalyse vom Zufall ab. Aus Gründen der Reproduzierbarkeit sollte daher der Zufallszahlengenerator gesetzt werden (mit `set.seed`). Außerdem bietet es sich an verschiedene Startkonfigurationen zu versuchen. In der Funktion `kmeans()` erfolgt dies durch die Option `nstart =`.


## Beispiel für eine einfache Clusteranalyse



Nehmen wir uns noch einmal den Extraversionsdatensatz vor. Kann man die Personen clustern anhand von Ähnlichkeiten wie Facebook-Freunde, Partyfrequenz und Katerhäufigkeit? Probieren wir es aus!

```{r read-data-segment}
extra <- read.csv("data/extra.csv")
```

Verschaffen Sie sich einen Überblick mit der Funktion `glimpse`.


### Distanzmaße berechnen

Auf Basis der drei metrischen Merkmale (d. h. `Alter`, `Einkommen` und `Kinder`), die wir hier aufs Geratewohl auswählen, ergeben sich für die ersten sechs Beobachtungen folgende Abstände:
```{r dist-segment}

extra %>% 
  dplyr::select(n_facebook_friends, n_hangover, extra_single_item) %>% 
  head %>% 
  dist(.)
```

Sie können erkennen, dass die Beobachtungen `1` und `3` den kleinsten Abstand haben, während `1` und `5` den größten haben.

Allerdings hängen die Abstände von der Skalierung der Variablen ab (`n_facebook_friends` streut stärker als `extra_single_item`). Daher sollten wir die Variablen vor der Analyse zu standardisieren (z. B. über `scale()`). 

Mit der Funktion `daisy()` aus dem Paket `cluster` kann man sich auch den Abstand zwischen den Objekten ausgeben lassen. Die Funktion errechnet auch Abstandsmaße, wenn die Objekte aus Variablen mit unterschiedlichen Skalenniveaus bestehen. Allerdings mag `daisy` Variablen vom Typ `chr` nicht, daher sollten wir `sex` zuerst in eine Faktorvariable umwandeln.

```{r eval = FALSE}
extra %>% 
  dplyr::select(n_facebook_friends, sex, extra_single_item) %>% 
  mutate(sex = factor(sex)) %>% 
  head %>% 
  cluster::daisy(.)
```



### kmeans für den Extraversionsdatensatz

Versuchen wir, einige Variablen mit `centers = 4` Clustern mithilfe einer kmeans-Clusteranalyse zu clustern.

```{r}
set.seed(1896)

extra %>% 
  mutate(Frau = sex == "Frau") %>% 
  dplyr::select(n_facebook_friends, Frau, extra_single_item) %>% 
  na.omit %>% 
  scale -> extra_cluster

kmeans_extra_4 <- kmeans(extra_cluster, centers = 4, nstart = 10)
```

Lassen Sie sich das Objekt `extra_cluster` ausgeben und betrachten Sie die Ausgabe; auch `str(kmeans_extra_4)` ist interessant. Neben der Anzahl Beobachtungen pro Cluster (z. B. `r kmeans_extra_4$size[2]` in Cluster 2) werden auch die Clusterzentren ausgegeben. Diese können dann direkt verglichen werden. Schauen wir mal, in welchem Cluster die Anzahl der Facebookfreunde im Schnitt am kleinsten ist:

```{r}
kmeans_extra_4$centers
```

Betrachten Sie auch die Mittelwerte der anderen Variablen, die in die Clusteranalyse eingegangen sind. Wie 'gut' ist diese Clusterlösung? Vielleicht wäre ja eine andere Anzahl von Clustern besser? Eine Antwort darauf liefert die Varianz (Streung) innerhalb der Cluster: Sind die Summen der quadrierten Abweichungen vom Clusterzentrum gering, so ist die Varianz 'innerhalb' der Cluster gering; die Cluster sind homogen und die Clusterlösung ist 'gut' (vgl. Abbildung \@ref(fig:cluster-bsp)). 

>   Je größer die Varianz innerhalb der Cluster, um schlechter ist die Clusterlösung.

```{r cluster-bsp, echo = FALSE, fig.cap = "Schematische Darstellung zweier einfacher Clusterlösungen; links: geringe Varianz innerhalb der Cluster; rechts: hohe Varianz innerhalb der Cluster"}

knitr::include_graphics("images/cluster/cluster_bsp-crop.png")

```



In zwei Dimensionen kann man Cluster gut visualisieren (Abbildung \@ref(fig:cluster3)); in drei Dimensionen wird es schon unübersichtlich. Mehr Dimensionen sind schwierig. Daher ist es oft sinnvoll, die Anzahl der Dimensionen durch Verfahren der Dimensionsreduktion zu verringern. Die Hauptkomponentenanalyse oder die Faktorenanalyse bieten sich dafür an.


Vergleichen wir ein paar verschiedene Lösungen, um zu sehen, welche Lösung am besten zu sein scheint.

```{r}
kmeans_extra_2 <- kmeans(extra_cluster, centers = 2, nstart = 10)
kmeans_extra_3 <- kmeans(extra_cluster, centers = 3, nstart = 10)
kmeans_extra_5 <- kmeans(extra_cluster, centers = 5, nstart = 10)
kmeans_extra_6 <- kmeans(extra_cluster, centers = 6, nstart = 10)

```

Dann nehmen wir die Gesamtstreuung jeder Lösung und erstellen daraus erst eine Liste und dann einen Dataframe:

```{r}
streuung_innerhalb <- c(kmeans_extra_2$tot.withinss,
                        kmeans_extra_3$tot.withinss,
                        kmeans_extra_4$tot.withinss,
                        kmeans_extra_5$tot.withinss,
                        kmeans_extra_6$tot.withinss)

streuung_df <- data_frame(
  streuung_innerhalb,
  anzahl_cluster = 2:6
)
```


Jetzt plotten wir die Höhe der Streuung pro Clusteranalyse um einen Hinweis zu bekommen, welche Lösung am besten passen könnte.

```{r}
ggplot(streuung_df) +
  aes(x = anzahl_cluster,
      y = streuung_innerhalb) +
  geom_col() +
  geom_line()
```

Nach der Lösung mit 4 Clustern kann man (vage) einen Knick ausmachen: Noch mehr Cluster verbessern die Streuung innerhalb der Cluster (und damit ihre Homogenität) nur noch unwesentlich oder zumindest deutlich weniger. Daher entscheiden wir uns für eine Lösung mit 4 Clustern.



## Aufgaben^[R, R, F, F, R]

```{block2, exercises-cluster, type='rmdexercises', echo = TRUE} 
Richtig oder Falsch!?

1. Die Clusteranalyse wird gemeinhin dazu verwenden, Objekte nach Ähnlichkeit zu Gruppen zuammenzufassen.

1. Die Varianz innerhalb eines Clusters kann als Maß für die Anzahl der zu extrahierenden Cluster herangezogen werden.

1. Unter euklidischer Distanz versteht jedes Maß, welches den Abstand zwischen Punkten in der Ebene misst.

4. Bei der k-means-Clusteranalyse darf man die Anzahl der zu extrahierenden Clustern nicht vorab festlegen.

5. Cluster einer k-means-Clusteranalyse werden so bestimmt, dass die Cluster möglichst homogen sind, d.h. möglichst wenig Streuung aufweisen (m.a.W. möglichst nah am Cluster-Zentrum sind).

```


Laden Sie den Datensatz `extra` zur Extraversion.

1. Unter Berücksichtigung der 10 Extraversionsitems: Lassen sich die Teilnehmer der Umfrage in eine Gruppe oder in mehrere Gruppen einteilen? Wenn in mehrere Gruppen, wie viele Gruppen passen am besten?

1. Berücksichtigen Sie den Extraversionsmittelwert und einige andere Variablen aus dem Datensatz (aber nicht die Items). Welche Gruppen ergeben sich? Versuchen Sie die Gruppen zu interpretieren!

1. Suchen Sie sich zwei Variablen aus dem Datensatz und führen Sie auf dieser Basis eine Clusteranalyse durch. Visualisieren Sie das Ergebnis anhand eines Streudiagrammes!






## Befehlsübersicht



Tabelle \@ref(tab:befehle-cluster) fasst die R-Funktionen dieses Kapitels zusammen.

```{r befehle-cluster, echo = FALSE}

df <- readr::read_csv("includes/Befehle_Cluster.csv")

knitr::kable(df,
             caption = "Befehle des Kapitels 'Clusteranalyse'")
```



## Verweise

- Diese Übung orientiert sich am Beispiel aus Kapitel 11.3 aus @Chapman2015 und steht unter der Lizenz [Creative Commons Attribution-ShareAlike 3.0 Unported](http://creativecommons.org/licenses/by-sa/3.0). Der Code steht unter der [Apache Lizenz 2.0](http://www.apache.org/licenses/LICENSE-2.0)

- Der erste Teil dieser Übung basiert auf diesem Skript: <https://cran.r-project.org/web/packages/broom/vignettes/kmeans.html>

- Eine weiterführende, aber gut verständliche Einführung findet sich bei @james2013introduction.

- Die Intuition zum euklidischen Abstand mit Pythagoras' Satz kann hier im Detail nachgelesen werden: <https://betterexplained.com/articles/measure-any-distance-with-the-pythagorean-theorem/>.