Tutorial 6: Machine Learning — Clustering

⇤ Zurück zur Startseite

Lernziele

  • Verständnis des K-Means Algorithmus
  • Implementieren es iterativen Prozesses in R

K-Means by hand

Daten

Sie haben die folgenden Datenpunkte gegeben:

Datenpunkt x y
A1 2 10
A2 2 5
A3 8 4
A4 5 8
A5 7 5
A6 6 4
A7 1 2
A8 4 9

Benutzen Sie dazu die Funktion matrix() und die Funktion c() um die Datenpunkte zu definieren. Die Matrix soll zwei Spalten haben, die die x- und y-Koordinaten der Punkte enthalten. Benennen Sie die Spalten mit der Funktion colnames() und die Zeilen mit der Funktion rownames(). Alternativ können Sie das gewohntes data.table Paket nutzen.

Algorithmus implementieren

Sie werden nun Schritt für Schritt durch den K-Means-Algorithmus geführt. Dabei sollen Sie einige Schritte selbst durchführen. Die hier beschriebenen Schritte sind eine Vereinfachung des eigentlichen Algorithmus, aber die Kernideen sind äquivalent.

  1. Benutzen Sie die Funktion dist() mit dem Argument method = "euclidean", um die euklidische Distanz zwischen den Punkten zu berechnen. Speichern Sie das Ergebnis in einer Variablen dist_matrix. Dies ist nicht Teil des eigentlichen K-Means-Algorithmus, sondern dient nur der Visualisierung:
dist_matrix <- as.matrix(dist(points, method = "euclidean"))
  1. Wählen sie zwei beliebige Punkte als Startpunkte für die Clusterzentren. Speichern Sie diese in einer Variablen seeds. Zum Beispiel so:
seeds <- points[c("A1", "A5"), ]

  1. Plotten Sie die Punkte und die Startpunkte. Benutzen Sie ggplot2 oder die Base R Funktionen plot() und text(), um die Punkte zu beschriften und points() um die Startpunkte zu plotten.

  2. Schreiben Sie eine Funktion euclidean_distance(). Die Funktion soll die euklidische Distanz zwischen zwei Punkten berechnen. Die Funktion soll zwei Argumente point und seed haben und die Wurzel der Summe der quadrierten Differenzen der Koordinaten der Punkte zurückgeben. Zur Erinnerung, Funktionen haben die folgende Struktur:

summe_ab = function (a, b) return (a + b)

  1. Zeichnen Sie Linien von jedem Punkt zu den Startpunkten: Benutzen Sie dazu die Base R Funktion lines() oder in ggplot2 die Funktion geom_segment().

  2. Berechnen Sie die Distanzen von jedem Punkt zu den Startpunkten. Speichern Sie die Distanzen in einer Matrix dist_to_seeds unter Verwendung von zwei verschachtelten for-Schleifen.

  3. Weisen Sie jedem Punkt das Clusterzentrum zu, das am nächsten ist. Speichern Sie die Zuweisungen in einem Vektor cluster_assignments. Benutzen Sie dazu die Funktion apply().

  4. Berechnen Sie die neuen Clusterzentren. Speichern Sie die neuen Clusterzentren in einer Matrix new_centroids. Benutzen Sie dazu eine for-Schleife.

  5. Nutzen Sie ggplot2 oder Base R zum Plotten der Ergebnisse.