---
title: "Tutorial 6"
author: "Lars Abt"
format: pdf
editor: visual
---

## Setup: Pakete installieren

```{r}
pacman::p_load(ggplot2, data.table)
```

Wie gewohnt starten wir damit, dass wir unseren package Manager "pacman" laden, und diesen verwenden um die benötigten Pakete, falls notwendig, zu installieren und anschließend zu laden.

## Erstellen der zu bearbeitenden Punkte

```{r}
# Punkte definieren
points <- data.table(
  name = c("A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8"),
  x = c(2, 2, 8, 5, 7, 6, 1, 4),
  y = c(10, 5, 4, 8, 5, 4, 2, 9)
)

# Kopie der Punkte erstellen, um die bisherigen Werte nicht zu verwerfen (für später)
basic_points <- copy(points)

# Euklidische Distanz berechnen
dist_matrix <- as.matrix(dist(points, method = "euclidean"))
print(dist_matrix)
```

Wir haben die Punkte definiert, und können uns die euklidische Distanz zwischen den Punkten in einer Matrix ausgeben lassen. Dies dient zur Visualisierung und dem besseren Verständnis.

## Seeds/Startpunkte definieren

```{r}
# Funktioniert mit data.table:
seeds <- points[name %in% c("A1", "A5")]

# Funktioniert nicht mit data.table:
# seeds <- points[c("A1", "A5")]
```

Die Startpunkte für die Clusterzentren speichern wir in einem weiteren data.table "seeds" ab. Hierbei handelt es sich um die Punkte A1 und A5.

## Plotten unserer Punkte, sodass wir eine bessere Übersicht haben

```{r}
basic_plot <- ggplot(points, aes(x = x, y = y, label = name)) +
  geom_point(color = "blue", size = 3) +
  geom_text(vjust = -1) +
  geom_point(data = seeds, aes(x = x, y = y), color = "red", size = 3) +
  xlim(0, 11) +
  ylim(0, 11) +
  ggtitle("K-Means Clustering - Initialisierung") +
  theme_minimal()
basic_plot
```

Wir sehen unsere 10 Punkte, und heben dabei unsere beiden Startwerte farblich hervor.

## Funktionen definieren

```{r}
# Beispiel: Funktion einer Summe:
summe_ab_v1 = function (a, b) return (a + b)
summe_ab_v2 = function (a, b) { (a + b) }

# Test der Funktionalität
print(summe_ab_v1(8, 15))
print(summe_ab_v2(8, 15))

# Funktion zur Berechnung der euklidischen Distanz
euclidian_distance <- function(point, center) {
  sqrt(sum((point - center)^2))
}
```

Wir schreiben uns eine Funktion "euclidian_distance", die die euklidische Distanz zwischen zwei Punkten berechnet. Diese Funktion wird später benötigt, um die Distanz zwischen den Punkten und den Clusterzentren zu berechnen. Wir geben ihr zwei Argumente mit, "point" und "center", die die beiden Punkte darstellen, zwischen denen die Distanz berechnet werden soll. Wenn wir diese Funktion verwenden müssen wir darauf achten, dass wir immer beide Argumente mitgeben.

## Plotten der Distanzen zu unseren Seeds

```{r}
enhanced_plot <- basic_plot + geom_segment(data = points, aes(x = x, y = y, xend = seeds$x[1], yend = seeds$y[1]), color = "orange") +
  geom_segment(data = points, aes(x = x, y = y, xend = seeds$x[2], yend = seeds$y[2]), color = "green")
enhanced_plot
```

Wir sehen ein Netz, welches von unseren Startpunkten aufgespannt wird, und erhalten somit eine gute erste Übersicht über die mögliche Lage unserer Clusterzentren.

## Distanzen unserer Punkte zu den Seeds/Startpunkten berechnen, mit Hilfe unserer neuen Funktion

```{r}
dist_to_seeds <- matrix(NA, nrow = nrow(points), ncol = nrow(seeds))
for (i in 1:nrow(points)) {
  for (j in 1:nrow(seeds)) {
    dist_to_seeds[i, j] <- euclidian_distance(points[i, .(x, y)], seeds[j, .(x, y)])
  }
}
colnames(dist_to_seeds) <- paste(seeds$name)
rownames(dist_to_seeds) <- paste(points$name)
print(dist_to_seeds)
```

Wir sehen, dass unsere Distanzen erfolgreich berechnet werden, und wir für den Punkt A1, sowie den Punkt A5, je einmal den Wert 0 erhalten, und alle anderen Werte positive Distanzen darstellen. Die Funktion erfüllt somit ihren Zweck und wir können die Distanzen zu Punkt A1 (in der ersten Spalte) mit den Distanzen zu Punkt A5 (in der zweiten Spalte) vergleichen.

## Zuweisung der Clusterzentren und Berechnung der neuen Zentren und plotten der Ergebnisse

```{r}
# Zuweisung der Cluster
points[, cluster_assignment := apply(dist_to_seeds, 1, which.min)]
points

# Neue Clusterzentren berechnen
new_centroids <- points[, .(x = mean(x), y = mean(y)), by = cluster_assignment]
new_centroids[, name := paste("C", cluster_assignment, sep = "")]
cat("Neue Clusterzentren:\n")
print(new_centroids)

# Visualisierung der Cluster und Zentren
ggplot(points, aes(x = x, y = y, color = as.factor(cluster_assignment), label = name)) +
  geom_point(size = 3) +
  geom_text(vjust = -1) +
  geom_point(data = seeds, aes(x = x, y = y), color = "purple", size = 3, shape = 8) +
  geom_point(data = new_centroids, aes(x = x, y = y), color = "black", size = 3, shape = 4) +
  geom_text(data = new_centroids, aes(x = x, y = y), vjust = -1) +
  xlim(0, 11) +
  ylim(0, 11) +
  ggtitle("K-Means Clustering - Eine Iteration") +
  theme_minimal()
```

Wir sehen unsere beiden neuen Zentren, C1 und C2. Insbesondere C1 ist ein schönes anschauliches Beispiel, wie der Punkt ausgewählt wird. C2 hingegen verdeutlicht, dass auch scheinbare Ausreißer, wie A7, in die Berechnung mit einfließen müssen, und die Lage des Zentrums dann ein wenig verschieben können.

## Extra: Über das Aufgabenblatt hinaus

## Alternatives Vorgehen: Wir nutzen die in R implementierte kmeans-Funktion, welche uns die Arbeit erleichtert

Mit der kmeans Funktion kann man die ganze Arbeit, die wir händisch gemacht haben, sehr schnell von R erledigen lassen. Wir nutzen dafür die Punkte, die wir am Anfang definiert haben, und die Startpunkte, die wir ebenfalls definiert haben. Die Funktion kmeans() erwartet als Argumente die Datenpunkte und die Zentren, und berechnet dann die Clusterzuweisungen und Zentren für uns.


```{r}
# Wir nutzen wieder unsere Punkte vom Anfang
kmeans_points <- copy(basic_points)

# Wir arbeiten mit einem Seed und unserer Kopie von points
set.seed(12345)
kmeans_results <- kmeans(kmeans_points[, .(x, y)], centers = seeds[, .(x, y)])

# Extrahieren der Clusterzuweisungen und Zentren
kmeans_points[, cluster_kmeans := kmeans_results$cluster]
center_kmeans <- data.table(kmeans_results$centers)
center_kmeans[, name := c("C1", "C2")]
cat("Neue Clusterzentren mit kmeans-Funktion:\n")
print(center_kmeans)
```

Wir berechnen, in einer Zeile, die Resultate der kmeans-Funktion, und können mit ihrer Hilfe erneut die Zuweisungen der Punkte zu den Clustern, sowie die Zentren berechnen. Wir sehen, dass die Zentren, die wir erhalten, mit unseren eigenen Berechnungen übereinstimmen.

## Visualisierung der Ergebnisse

```{r}
kmeans_plot <- ggplot(kmeans_points, aes(x = x, y = y, color = as.factor(cluster_kmeans), label = name)) +
  geom_point(size = 3) +
  geom_text(vjust = -1) +
  geom_point(data = seeds, aes(x = x, y = y), color = "purple", size = 3, shape = 8) +
  geom_point(data = center_kmeans, aes(x = x, y = y), color = "gold", size = 3, shape = 4) +
  geom_text(data = center_kmeans, aes(x = x, y = y), color = "gold", vjust = -1) +
  xlim(0, 11) +
  ylim(0, 11) +
  ggtitle("K-Means Clustering mit Bestimmten Zentren") +
  theme_minimal()
kmeans_plot
```

Wir sehen nun eine etwas abweichende Zuordnung zu unseren beiden Clustern. Dies liegt an der abweichenden Implementierung in R (unsere "per Hand" Methode ist eine Vereinfachung). Zudem werden mit Hilfe der Funktion kmeans() die Clusterzentren solange berechnet, bis wir eine Convergence erreichen, das heißt, sich die Zentren nicht mehr verändern. Dies ist ein weiterer Unterschied zu unserer Methode, bei der wir nur eine Iteration durchführen (vgl. diesbezüglich die Folien und Visualisierung aus der Vorlesung).

## Zum Vergleich: Eine Visualisierung, wie die Ergebnisse mit zwei anderen Startpunkten aussehen könnten

```{r}
# Neue Seeds definieren und neue Punkte nutzen
new_points <- copy(basic_points)
new_seeds <- points[name %in% c("A3", "A7")]

# Wir arbeiten wieder mit einem Seed und unserer Kopie von points
set.seed(12345)
new_kmeans_results <- kmeans(new_points[, .(x, y)], centers = new_seeds[, .(x, y)])

# Extrahieren der Clusterzuweisungen und Zentren
new_points[, cluster_kmeans := new_kmeans_results$cluster]
new_center_kmeans <- data.table(new_kmeans_results$centers)
new_center_kmeans[, name := c("C1", "C2")]
cat("Neue Clusterzentren mit kmeans-Funktion:\n")
print(new_center_kmeans)
```

Jetzt plotten wir das ganze noch einmal:

```{r}
new_kmeans_plot <- ggplot(new_points, aes(x = x, y = y, color = as.factor(cluster_kmeans), label = name)) +
  geom_point(size = 3) +
  geom_text(vjust = -1) +
  geom_point(data = new_seeds, aes(x = x, y = y), color = "purple", size = 3, shape = 8) +
  geom_point(data = new_center_kmeans, aes(x = x, y = y), color = "gold", size = 3, shape = 4) +
  geom_text(data = new_center_kmeans, aes(x = x, y = y), color = "gold", vjust = -1) +
  xlim(0, 11) +
  ylim(0, 11) +
  ggtitle("K-Means Clustering mit anderen Zentren") +
  theme_minimal()
new_kmeans_plot

# Zum Vergleich noch der alte Plot:
kmeans_plot
```

Abschließend können wir festhalten, dass die Wahl der Startpunkte von großer Bedeutung ist, da sie das Ergebnis entscheidend beeinflussen. Es kann sinnvoll sein, sich mehrere mögliche Startpunkte anzuschauen.
