Blatt 5 Aufgabe 3 Cluster

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Blatt 5 Aufgabe 3 Cluster
Hallo, kann mir jemand erklären, was in der dritten Aufgabe b und c eigentlich gefragt ist? Was sollen die Cluster sein? Stehe total auf dem Schlauch ._.


Ich bemühe mich hier an dieser Stelle mal etwas Licht ins Dunkle zu bringen, ohne gleich die ganze Aufgabe zu spoilern. Fangen wir mit dem an, was gegeben ist:

def compute_clusters(pixels, means):
    """Text aus Aufgabenstellung:
       Schreiben Sie eine Funktion `compute_clusters`, die für eine
       gegebene Pixelliste `pixels` und gegebene Mittelwerte `means`
       die zugehörigen Cluster zu jedem Mittelwert berechnet."""
    # Hier kommt Ihre Implementierung hin :)
    pass

Ich stelle das im Folgenden nun etwas graphisch dar, was diese Cluster sind und gebe den Text der Aufgabenstellung dann nochmal in etwas anderen Worten wieder:

Schritt 1 – Was haben wir eigentlich gegeben/was bekommen wir übergeben?

Diese Frage ist mit die wichtigste und wie mir die Rechnerübungen der letzten zwei Wochen gezeigt haben, ist das vielen erstmal noch gar nicht so klar. Deswegen an dieser Stelle nochmal:
* [m]pixels[/m]: Wir bekommen hier eine Liste von 5-Tupeln der Art [m](r, g, b, x, y)[/m] übergeben, sprich in dem Format, wie es in Aufgabe 1a beschrieben wurde.
An dieser Stelle interessieren uns aber nur die ersten drei Einträge des Tupels, die x- und y-Koordinate des Tupels erstmal nicht. (Man sollte sich an dieser Stelle ‘Warum?’ fragen und darauf eine Antwort finden!)
Stellt man dies graphisch dar, so ergibt sich vlt. ein solches Bild: (Zur Vereinfachung wurden hier immer nur zwei Farbkanäle resp. Dimensionen angenommen.)

* [m]means[/m]: An dieser Stelle werden uns die Mittelwerte übergeben. Aus der Aufgabenstellung zitiert:

     (Hinweis zur Frage von oben: Die Antwort ist eng mit dem obigen Zitat verbunden ...) Zeichnet man beispielhafte Mittelwerte in obiges Beispiel ein, so kann das dann bspw. wie folgt aussehen:
     [img]https://wwwcip.cs.fau.de/~yq53ykyr/AlgoKS/extra/lec05/cluster_2.png[/img]

Schritt 2 – Und was soll ich jetzt tun?

Ziel der gesamten Teilaufgabe ist es, zu jedem Mittelpunkt genau ein Cluster zu formen, also eine Liste von Pixeln, welche eine bestimmte Eigenschaft haben.
Diese Eigenschaft wird dir durch die weiter untenstehende Formel (siehe untriges Bild) beschrieben:

Drückt man diese Eigenschaft nun in Worte aus, so könnte man beispielsweise sagen, dass das Cluster [m]C[/m] zum gegebenen Mittelpunkt [m]m[/m] all diejenigen Pixel aus der ursprünglichen Pixelliste [m]pixels[/m]
enthält, welche “am nähesten” an [m]m[/m] sind. Das heißt, dass die Distanz zu allen anderen Mittelpunkten entweder größer oder gleich als die Distanz zu sich ist.

Und was passiert bei Gleichheit? Sprich wenn zwei Distanzen zu unterschiedlichen Mittelpunkten gleich sind? Ist der Punkt dann in beiden Clustern zu finden?

Das steht auch in der Aufgabenstellung, siehe gleich und NEIN! Die Cluster sind zueinander disjunkt. Das heißt, dass ein Punkt sich nicht gleichzeitig in mehreren Clustern befinden darf. (Auch hier wieder: Warum? – Hinweis: Siehe Teilaufgabe c) …)
Ich zitiere hierfür nochmals die Aufgabenstellung:

Sprich bei Gleichheit wählen wir immer das Cluster zu dem Mittelpunkt mit dem niedrigsten Index in der Mittelpunktsliste [m]means[/m] aus! Das musst du eventuell – m.a.W. kommt auf deine Umsetzung an – noch eigens implementieren.

Finalerweise kann man das natürlich auch an dem obigen Beispiel durchführen. Das wird dann in der folgenden Abbildung dargestellt:

Und ganz zum Schluss vlt. noch ein kurzer Hinweis zum Anordnen der Cluster. In den finalen Tests wird erwartet, dass das Cluster an der Stelle [m]i[/m] zum Mittelpunkt an der Stelle [m]i[/m] passt. Dementsprechend sollte

assert(len(YOUR_CLUSTER_ARRAY) == len(means))

keinen Fehler werfen.

Ich hoffe ich konnte dir helfen und wünsche dir noch viel Erfolg bei der restlichen Aufgabe.

1 Like