In dieser Aufgabe sollt ihr den in der Vorlesung vorgestellte k-means-Algorithmus implementieren.
Dieser soll nach 100 Schritten oder sobald in zwei aufeinanderfolgenden Iterationen keine Änderung stattfindet terminieren.

Als Eingabe erhaltet ihr ein Array aus 2-dimesionalen Punkten namens datenpunkte.

Das Ergebnis sollt ihr in dem Punktearray clusterZentren speichern. Dieses wird in Abhängigkeit von dem von euch gewählten k initialisiert.

k-Means Algorithmus

1. Wähle zufällig k Clusterzentren (zb. aus den gegebenen Punkten)

2. Weise jedem Punkt dem Clusterzentrum zu, welches ihm am Nächsten liegt.

3. Berechne für jedes so enstandene Cluster ein neues Clusterzentrum.

4. Überprüfen ob sich die Clusterzentrum zum vorherigen Durchgang verändert haben. Wenn dies der Fall ist, wiederhole ab Schritt 2, wenn nicht ist dies der Endzustand.


Beispiel
Es sind die Datenpunkte (1,0) , (2,0), (3,0), (10,0) , (11,0) und (12,0) gegeben. Für das k wird k = 2 gewählt. Als Ergebnis steht am Ende im Array clusterzentrum (1.5,0) und (10.5,0) als zwei Clusterzentren der gegebenen Punkte.



Tipps
k ist ein ganzzahliger Wert und muss selbst gewählt werden.
k ist möglichst klein zu wählen, aber so, dass jedem Cluster von Datenpunkten ein Clusterzentrum zugewiesen werden kann.
Die initialen Clusterzentren sollen zufällige Punkte der Datenwolke sein.
Das Ergebnis soll in ein Array von 2D-Punkten namens clusterZentren geschrieben werden.
Es ist der totale Fehler bestehend aus Summiertem Fehler aller Datenpunkte zum jeweiligen Clusterzentrum und Offset für Clusterzentren zu minimieren (die Berechnung dieses Fehlers geschieht automatisch).
Der Offset für Clusterzentren steigt linear mit Anzahl der Clusterzentren.
Daher sollte das bestmögliche Ergebnis mit möglichst wenigen Clusterzentren angestrebt werden.

Die genaue Funktionsweise von k-Means-Clustering kann dem Vorlesungsmaterial entnommen werden.


Hinweis: Für die graphische Ansicht (Ausführen) ist es erforderlich, die Funktion redraw(); einmalig nachdem die Clusterzentren verändert wurden aufzurufen.