Ein bedeutender Algorithmus der dichtebasierten Clusteranalyse ist das DBSCAN-Verfahren, welches wir in diesem Abschnitt besprechen werden. Zur Veranschaulichung stellen wir das Verfahren anhand von Punkten in der Ebene vor. Zudem muss ein geeignetes Abstandsmaß festgelegt werden, im folgenden Beispiel ist dies die Euklidische Metrik.
Gegeben ist zunächst ein Datensatz bestehend aus Punkten in der Ebene:
Nun werden jeweils zwei Punkte miteinander verbunden, sofern diese einen Abstand zueinander haben, der kleiner oder gleich als ein gewisser Schwellwert ist. Um genauer zu sein wird als Parameter ein Radius zur Spezifikation einer Nachbarschaft definiert:
| radius | positive (rationale) Zahl |
Zwei Punkte werden genau dann verbunden, wenn der Abstand kleiner oder gleich dem Wert radius ist. Zur Bestimmung des Abstands kommt dabei das zuvor festgelegte Abstandsmaß zum Einsatz. Das Ergebnis könnte (je nach Wahl von radius) etwa so aussehen:
Nun kommt ein zweiter Parameter ins Spiel, um zu spezifizieren, wann ein Punkt als dicht definiert wird:
| samples | ganze Zahl, größer oder gleich 2 |
Ein Punkt gilt als dicht, wenn er mit mindestens samples-1 weiteren Punkten verbunden ist. Anders ausgedrückt:
Ein Punkt bzw. Objekt p heißt dicht, wenn sich in der Nachbarschaft von p mindestens samples Objekte befinden. Die Nachbarschaft besteht dabei aus allen Objekten, die einen Abstand zu p haben, der kleiner oder gleich radius ist. Das Objekt p zählt dabei selbst zur eigenen Nachbarschaft dazu.
Dank der Definition von dicht können bereits die Cluster bestimmt werden: Alle Punkte, die dicht und verbunden sind, gehören zum gleichen Cluster. Für samples=4 erhalten wir im Beispiel etwas zwei Cluster:
Damit sind bereits einige Punkte einem Cluster zugewiesen. Im nächsten Schritt werden alle Punkte, die mit einem dichten Punkt (also einem bereits eingefärbten Objekt) verbunden sind, ebenfalls dem entsprechenden Cluster zugewiesen:
Im Beispiel zuvor ist zu beachten, dass der Punkt A tatsächlich beiden Clustern hätte zugewiesen werden können. An dieser Stelle kann man sich frei entscheiden oder auch eine zufällige Wahl treffen, im Beispiel fiel die Wahl auf das blaue Cluster. Schließlich bleiben noch einige Punkte übrig, die auch als Rauschpunkte bezeichnet werden:
Je nach Anforderung kann der Algorithmus an dieser Stelle beendet werden, ohne dass Rauschpunkte einem Cluster zugewiesen werden. Falls aber eine Zuweisung stattfinden soll, so werden Rauschpunkte dem Cluster zugewiesen, dem sie am nächsten sind:
Damit ist das DBSCAN-Verfahren abgeschlossen und alle Punkte bzw. Objekte sind einem Cluster zugewiesen. Zusammenfassend sei bereits bemerkt:
Anders als beim k-Means-Algorithmus wird nicht vorgegeben, in wie viele Cluster die Objekte gruppiert werden. Die Anzahl der Cluster ergibt sich hingegen insbesondere in Abhängigkeit der Parameter radius und samples.
Zudem kann auch das Abstandsmaß einen Einfluss auf die Anzahl der Cluster haben.
