In einer Stadt gibt es viele verschiedene Sehenswürdigkeiten, die auf dem ganzen Stadtgebiet verteilt sind. Einige liegen dicht zusammen, andere dagegen nicht. Für Besucher der Stadt ist es wichtig zu wissen, wie viele verschiedene Hotspots es gibt, von denen man diese Sehenswürdigkeiten gut erreichen kann. Es müssen also sogenannte "Cluster" gesucht werden, in denen sich mehrere Sehenswürdigkeiten in unmittelbarer Nähe befinden.
In unserem Beispiel wollen wir die Cluster finden, die Sehenswürdigkeiten enthalten, zu denen mindestens zwei weitere Sehenswürdigkeiten in einer Entfernung von zwei Kilometern liegen.
Betrachte dazu die folgende Karte, auf der jeder Punkt einer Sehenswürdigkeit entspricht:
Wir wollen nun Cluster finden. Dazu werden wir die Punkte in sogenannte Kernpunkte, Randpunkte und Rauschpunkte "klassifizieren" und sie dazu verschiedenfarbig markieren. Wie das geht, erfährst du auf der nächsten Seite im Spielablauf.
Du benötigst ein Lineal (oder noch besser einen Zirkel) zum Messen. Außerdem benötigst du einen roten, einen grünen und einen blauen Stift zum Markieren der Punkte. Zum Darstellen der Cluster benötigst du außerdem noch einen Bleistift.
Spielt in der Gruppe das Spiel nach dem folgenden Spielablauf.
Spielablauf
-
Parameter festlegen:
- Wählt eine maximale Nachbarschaftsgröße ε. Wir starten zuerst mit ε = 2 cm (was 2 km in der Realität entspricht).
- Legt fest, wie viele Nachbarpunkte (MinPts) ein Punkt mindestens haben muss, um ein Kernpunkt zu sein. Wir starten mit MinPts = 2, also mindestens zwei benachbarte Sehenswürdigkeiten.
-
Punkt für Punkt analysieren:
- Ein Spieler wählt einen beliebigen Punkt aus und zählt, wie viele Nachbarn sich im Umkreis von ε befinden.
- Falls der Punkt mindestens MinPts Nachbarn hat, markiert ihn als Kernpunkt mit dem roten Stift.
- Falls der Punkt weniger als MinPts Nachbarn hat, aber sich in der ε-Nähe mindestens eines Kernpunkts befindet, markiert ihn als Randpunkt mit dem blauen Stift.
- Falls der Punkt weder Kernpunkt noch Randpunkt ist, markiert ihn als Rauschpunkt mit dem schwarzen Stift.
-
Cluster bilden:
- Verbinde alle Kernpunkte (rot markiert), die sich gegenseitig in einer Entfernung von ε erreichen können (also wenn sie sich im ε-Radius befinden) mit einem Bleistift.
- Füge Randpunkte (blau markiert) zu dem nächstgelegenen Cluster hinzu, indem du diese jeweils mit dem nächstgelegenen Kernpunkt verbindest. Nutze auch hier den Bleistift.
- Rauschpunkte (schwarz markiert) bleiben allein.
-
Ergebnis diskutieren:
- Ermittelt, wie viele Cluster ihr gefunden habt. Zählt auch die Rauschpunkte.
- Ändert die Voraussetzungen für Cluster: Was passiert, wenn ihr ε oder MinPts verändert, z. B. auf ε = 3 cm und MinPts = 4?
mögliches Ergebnis
