Clustering · Verständlich erklärt

DBSCAN verständlich erklärt

Aus der Luft sieht man bei Nacht, wo Dörfer liegen: Dort drängen sich die Lichter, einzelne Höfe stehen allein. Ein Rechenverfahren erkennt solche Gruppen von selbst, ohne dass jemand vorher die Zahl der Dörfer nennt. Wir zeigen, wie, und wo es hakt.

Für Einsteiger Für Fachleute Zur Demo

Zuletzt aktualisiert: 11. November 2026

Teil 1 · Für Einsteiger

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Dörfer von oben erkennen

Stellen Sie sich eine Landschaft bei Nacht vor, von oben gesehen. Jedes Haus ist ein Licht. Wo viele Lichter dicht beieinander stehen, liegt ein Dorf. Einzelne Höfe stehen weit draußen.

Ein Lieferdienst will daraus Sammelrouten bilden. Eine Sammelroute ist eine Fahrt, die alle Pakete eines Dorfes in einem Zug ausliefert. Für einen einzelnen Hof lohnt sie nicht.

Das Rechenverfahren dazu heißt DBSCAN, eine englische Abkürzung für dichtebasiertes Gruppieren mit Rauschen. Es muss nicht vorher wissen, wie viele Dörfer es gibt. Es braucht nur zwei Angaben von Ihnen:

Der Radius. Wie weit darf ein Haus höchstens entfernt sein, um noch als Nachbar zu gelten?
Die Mindestzahl. Wie viele Häuser müssen im Radius um ein Haus stehen, damit die Gegend als dicht gilt? Das Haus selbst zählt mit.

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, kurz Demo. Unten öffnet der erste Knopf es, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie es nicht. Dort heißen Radius und Mindestzahl eps und min_samples. Alle Beispiele hier beschreiben die Demo.

Drei Rollen für jedes Haus

Das Verfahren geht die Häuser der Reihe nach durch und zählt, wie viele im Radius stehen. Jedes Haus bekommt genau eine von drei Rollen.

Kernhaus. Im Radius stehen mindestens so viele Häuser wie die Mindestzahl, das Haus selbst eingerechnet. Hier ist es dicht. Fachleute sagen Core-Punkt.
Randhaus. Es hat zu wenige Nachbarn für ein Kernhaus, steht aber im Radius eines Kernhauses. Es gehört zum Dorf, wie das letzte Haus am Ortsrand. Fachleute sagen Border-Punkt.
Einzelhaus. Es ist weder Kern- noch Randhaus. Es gehört zu keinem Dorf und kommt in keine Sammelroute. Fachleute sagen Noise, auf Deutsch Rauschen.

So wächst ein Dorf: Man startet bei einem Kernhaus und nimmt alle Häuser in seinem Radius auf. Steht darunter wieder ein Kernhaus, nimmt man auch die Häuser in dessen Radius auf. So wandert das Dorf von Kernhaus zu Kernhaus, bis die Kette abreißt. Von Randhäusern aus geht es nicht weiter.

Ein Beispiel mit angenommenen Werten: Vier Häuser stehen an einer Landstraße, je einen Kilometer voneinander entfernt. Ein fünftes Haus steht sieben Kilometer hinter dem letzten. Der Radius beträgt anderthalb Kilometer, die Mindestzahl drei. Die zwei mittleren Häuser haben je drei Häuser im Radius, sich selbst und beide Nachbarn: Kernhäuser. Die zwei äußeren haben nur zwei, stehen aber im Radius eines Kernhauses: Randhäuser. Das ferne Haus findet niemanden: ein Einzelhaus. Die vier Häuser an der Straße bilden zusammen ein Dorf.

Dörfer in jeder Form

Das Dorf wandert von Haus zu Haus. Darum darf es jede Form haben. Ein Straßendorf, das sich über Kilometer zieht, bleibt ein Dorf, ebenso ein Ring oder ein Halbmond. Auch die Zahl der Dörfer legt niemand vorher fest. Sie ergibt sich aus Karte, Radius und Mindestzahl.

Ein Halbmond ist eine gebogene Gruppe wie ein abnehmender Mond. Zwei Halbmonde können ineinandergreifen wie zwei Haken. Andere Verfahren setzen erst Mittelpunkte und ordnen jedes Haus dem nächsten zu. Das passt zu runden Gruppen. Bei zwei Halbmonden liegen manche Häuser näher am Mittelpunkt des anderen Halbmonds und werden falsch zugeordnet. DBSCAN braucht keinen Mittelpunkt, es schaut nur auf die Nachbarn. In der Demo trennt es zwei solche Halbmonde bei passendem Radius sauber.

Alles hängt am Radius

Der Radius ist die heikle Stelle. Ist er winzig, findet kein Haus genug Nachbarn, und fast alle Häuser werden Einzelhäuser. Ist er riesig, erreicht jedes Haus jedes andere, und aus allen Dörfern wird ein einziges. Dazwischen liegt ein Bereich, in dem das Ergebnis sinnvoll ist. Wie breit er ist, hängt von der Karte ab. Wie man ihn findet, steht im zweiten Teil. Im Kleinen hilft es, mehrere Radien nebeneinander anzusehen.

Die Demo zeigt deshalb unter der Hauptkarte dieselben Häuser mit anderen Radien. Bei den Halbmonden bricht ein Halbmond schon bei etwas kleinerem Radius in Stücke. Bei etwas größerem verschmelzen beide zu einem Klumpen.

Wenn Dörfer verschieden dicht sind

Ein enges Dorf hat viele Häuser auf kleinem Raum. Ein lockeres Dorf hat gleich viele Häuser, aber weit verstreut. Ein Radius gilt für die ganze Karte. Ist er klein genug für das enge Dorf, finden die Häuser im lockeren Dorf zu wenige Nachbarn. Viele werden Einzelhäuser, obwohl sie zu einem Dorf gehören. Die Demo enthält dafür eine automatische Prüfung. Bei einem bestimmten Radius ist im engen Dorf kein Haus ein Einzelhaus, im lockeren sind es mehr als 30 Prozent.

Ein größerer Radius holt das lockere Dorf zurück. Im Beispiel der Demo liegen die zwei Dörfer weit auseinander und verschmelzen selbst bei sehr großem Radius nicht. Das ist eine Eigenheit des Beispiels. Liegen ungleich dichte Dörfer dicht beieinander, kann der große Radius das Nachbardorf mitnehmen. Das ist eine Überlegung dieser Seite, in der Demo nicht gemessen.

Einzelhäuser sind ein Ergebnis

Das Verfahren sagt ausdrücklich, welche Häuser zu keinem Dorf gehören. Verfahren mit Mittelpunkten zwingen jedes Haus in eine Gruppe. Das Beispiel „Viele Ausreißer“ der Demo streut viele einzelne Häuser weit draußen über die Karte, Fachleute sagen Ausreißer. Beim dort eingestellten Radius bleiben die meisten davon Einzelhäuser. Wird der Radius größer, werden mehr von ihnen in ein Dorf aufgenommen.

Häufige Missverständnisse

„DBSCAN findet die richtige Zahl der Dörfer von allein.“ Es muss die Zahl nicht kennen. Aber Radius und Mindestzahl legen sie indirekt fest: Ein anderer Radius liefert eine andere Zahl.
„Einzelhäuser sind Fehler oder unwichtig.“ Nein. Es sind Häuser, die für den gewählten Maßstab zu dünn besiedelt stehen. Ob ein Einzelhaus ein echter Ausreißer ist oder dem zu kleinen Radius zum Opfer fiel, zeigt sich erst bei einem anderen Radius.
„Das Verfahren würfelt, es kommt jedes Mal etwas anderes heraus.“ Es enthält keinen Zufall. Bei gleichen Häusern und gleichen Angaben kommen dieselben Kernhäuser, Einzelhäuser und Dörfer heraus, auch bei anderer Reihenfolge der Häuser. Die einzige Ausnahme ist ein Randhaus zwischen zwei Dörfern: Es geht an das Dorf, das es zuerst erreicht.

Woran Sie das im Alltag erkennen

Ein fester Maßstab für „nah“ taugt nicht überall. Ein Nachbar fünf Minuten zu Fuß entfernt ist in der Stadt weit weg und auf dem Land nebenan.
Auf einer Party stehen Menschen in Gesprächsgruppen. Niemand hat vorher festgelegt, wie viele es sein sollen. Wer allein am Rand steht, gehört zu keiner. Wer am Rand einer Gruppe steht, gehört dazu, auch mit nur einem Nachbarn.

Wie ernst ist das Rechenbeispiel zu nehmen?

Die Häuser der Demo sind künstlich und zufällig erzeugt, auf einer flachen Karte, und Entfernung ist die Luftlinie. Straßen, Fahrzeiten und Paketmengen gibt es nicht. Das Beispiel zeigt, wie das Verfahren auf Radius und Dichte reagiert, nicht wo eine echte Sammelroute verlaufen sollte.

Was Sie mitnehmen

Fragen Sie bei jeder automatischen Gruppierung, welche Angaben das Ergebnis bestimmen: Wie nah heißt „nah“, und wie viele heißen „viele“?
Prüfen Sie, ob ein einziger Maßstab für die ganze Karte passt oder ob es dichte und dünne Gegenden gibt.
Sehen Sie sich die aussortierten Einzelfälle an, bevor Sie sie streichen: Sind es echte Ausreißer, oder war der Maßstab zu streng?

Demo ausprobieren Weiter zum Fachteil

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Teil 2 · Für Fachleute

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er beschreibt das Verfahren DBSCAN, das Szenario der Demo und das, was ihre Prüfungen belegen.

Vehikel: Lieferadressen, als Punkte der Ebene gegeben, sollen zu Sammelrouten gebündelt werden, ohne die Zahl der Routen vorzugeben. Dicht beieinanderliegende Adressen bilden eine Route, vereinzelte Adressen gelten als nicht routentauglich (Noise). Der Abstand ist der euklidische Abstand \(\lVert p - q \rVert\).
Szenario: zufällige Punktwolken in zwei Formen. Bei „Gruppen“ erzeugt die Demo \(k\) Gauß-Gruppen mit gleicher Punktzahl, deren Mitten auf einem Kreis liegen. Bei „Halbmonden“ erzeugt sie \(k\) Halbkreisbögen mit Rauschen um die Kurve, bei \(k = 2\) das klassische Zwei-Halbmonde-Bild, darüber wie Blütenblätter angeordnet. Das Dichte-Ungleichgewicht \(u\) (mit \(0 \le u \le 1\)) macht Gruppe 0 diffuser und die übrigen enger, bei gleicher Punktzahl je Gruppe. Dazu kommen wahlweise Ausreißer, gleichmäßig über das umgebende Rechteck verstreut, die zu keiner Gruppe gehören.
Streuung der Gruppen: Die Standardabweichung \(\sigma\) der Gruppe 0 wird mit \(1 + u\) multipliziert, die der übrigen mit \(1 - \tfrac{3}{5}u\); dieser Faktor beträgt für \(0 \le u \le 1\) mindestens zwei Fünftel. Die Basis-Standardabweichung ist das Dreifache des Streuungsreglers, die Einheit von \(\sigma\) und \(\varepsilon\) ist die Karteneinheit, in der die Gruppenmitten auf einem Kreis vom Radius drei liegen. Bei Gruppen und \(u = 1\) streut Gruppe 0 daher fünfmal so stark wie jede andere, die Fläche je Punkt ist fünfundzwanzigmal so groß (Rechnung aus dem Erzeugungscode der Demo, keine Messung).
Parameter: Radius \(\varepsilon\) und Mindestzahl \(m\) (in der Demo minSamples); der Punkt selbst zählt mit. Voreinstellung: hundertfünfzig Punkte in drei Gruppen, Radius sechs Zehntel, \(m\) gleich fünf, keine Ausreißer. Einstellbar sind der Radius zwischen fünf Hundertsteln und drei, \(m\) zwischen zwei und fünfzehn und die Punktzahl bis 400.
Rechenaufwand: Die Demo sucht Nachbarn naiv: Eine Abfrage \(N_{\varepsilon}(p)\) ist linear in \(n\), und es gibt \(n\) davon, also \(O(n^2)\). Mit einem räumlichen Index (zum Beispiel einem k-d-Baum) sinkt der Aufwand in niedriger Dimension mit gutem Index in der Praxis auf \(O(n \log n)\); im ungünstigsten Fall bleibt er quadratisch. Die Demo baut ihn nicht ein, weil bei höchstens 400 Punkten der Unterschied nicht spürbar ist.

Die Formeln

Für einen Punkt \(p\) der Punktmenge \(D\) ist die Nachbarschaft im Radius \(\varepsilon\), mit \(p\) selbst:

\[N_{\varepsilon}(p) = \{q \in D : \lVert p - q \rVert \le \varepsilon\}\]

Der Punkt \(p\) ist ein Kernpunkt, wenn seine Nachbarschaft mindestens minSamples Punkte enthält. Im Folgenden steht \(m\) kurz für minSamples.

\[|N_{\varepsilon}(p)| \ge \text{minSamples}\]

Direkt dichte-erreichbar: \(q\) ist von \(p\) aus direkt dichte-erreichbar, wenn \(q \in N_{\varepsilon}(p)\) gilt und \(p\) ein Kernpunkt ist.
Dichte-erreichbar: die transitive Hülle davon, also eine Kette, deren Glieder bis auf das letzte Kernpunkte sind (das letzte darf ein Randpunkt sein; die Relation ist nicht symmetrisch).
Dichte-verbunden: \(p\) und \(q\) sind dichte-verbunden, wenn es einen Punkt \(o\) gibt, von dem aus beide dichte-erreichbar sind.
Cluster: eine maximale, nicht leere Menge dichte-verbundener Punkte (ein Randpunkt, der von zwei Clustern aus erreichbar ist, macht diese Definition nicht eindeutig; die Demo ordnet ihn dem Cluster zu, das ihn zuerst erreicht). Randpunkt: kein Kernpunkt, liegt aber in der Nachbarschaft eines Kernpunkts. Noise: jeder Punkt, der zu keinem Cluster gehört, also weder Kern- noch Randpunkt ist.

Anschaulich wachsen Cluster von Kernpunkt zu Kernpunkt. Randpunkte hängen an, tragen das Cluster aber nicht weiter.

Ablauf des Verfahrens

Die Demo implementiert DBSCAN selbst und hält jede (Um-)Klassifizierung eines Punkts als Schritt fest, damit man Punkt für Punkt durchblättern kann. Der Ablauf:

Alle Punkte sind unbesucht. Man geht sie in der Reihenfolge des Datensatzes durch und überspringt besuchte.
Für einen unbesuchten Punkt \(p\) wird \(N_{\varepsilon}(p)\) berechnet. Hat die Nachbarschaft weniger als \(m\) Punkte, wird \(p\) vorläufig als Noise vermerkt.
Sonst ist \(p\) Kernpunkt eines neuen Clusters, und seine Nachbarn kommen in eine Warteschlange.
Für jeden Punkt der Warteschlange gilt: Ist er unbesucht, wird seine Nachbarschaft berechnet. Hat sie mindestens \(m\) Punkte, ist er Kernpunkt, und seine Nachbarn werden angehängt. Sonst ist er Randpunkt des Clusters.
Ein Punkt, der zuvor als Noise vermerkt war, wird bei Erreichen aus einem Cluster zum Randpunkt dieses Clusters. Ein Punkt, der schon zu einem Cluster gehört, bleibt dort.
Jeder Punkt wird höchstens zweimal klassifiziert, einmal als vorläufiges Noise und einmal bei späterer Aufnahme als Randpunkt. Das Verfahren endet also nach höchstens \(2n\) Schritten und braucht keine eigene Iterationsgrenze.

Herleitung Schritt für Schritt

Diese Schritte sind Rechnung dieser Seite, keine Messung der Demo. Die Prüfungen der Demo bestätigen die Aussagen von Schritt 2 für Kernpunkte, Cluster der Kernpunkte und Noise an Zufallsinstanzen gegen einen unabhängigen Rechenweg und gegen scikit-learn (Abschnitt Befunde). Vorausgesetzt ist \(m \ge 2\).

Schritt 1, Kernpunkte und der k-Distanz-Wert: Sei \(r_p\) der Abstand von \(p\) zu seinem \((m-1)\)-ten nächsten anderen Punkt. Es gilt \(|N_{\varepsilon}(p)| = 1 + \#\{q \ne p : \lVert p - q \rVert \le \varepsilon\}\). Also hat \(p\) genau dann mindestens \(m\) Punkte in der Nachbarschaft, wenn mindestens \(m-1\) andere Punkte im Abstand höchstens \(\varepsilon\) liegen, das heißt genau dann, wenn \(r_p \le \varepsilon\). Im k-Distanz-Diagramm, in dem die Werte \(r_p\) aufsteigend sortiert sind, sind die Kernpunkte also genau die Punkte, die höchstens auf der Höhe \(\varepsilon\) liegen. Das erklärt, was die Höhe \(\varepsilon\) im Diagramm bedeutet. Dass ein Knick der Kurve ein guter Kandidat für \(\varepsilon\) ist, ist eine Heuristik: Links davon sind viele Punkte Kernpunkte, rechts davon die Einzelgänger. (Der Wert heißt in der Literatur k-Distanz mit \(k = m-1\); dieses \(k\) hat mit der Gruppenzahl \(k\) nichts zu tun.)
Schritt 2, was von der Reihenfolge unabhängig ist: Zwei Kernpunkte sind genau dann dichte-verbunden, wenn eine Kette von Kernpunkten mit Abständen von höchstens \(\varepsilon\) sie verbindet. Die Cluster der Kernpunkte sind also die Zusammenhangskomponenten des Graphen auf den Kernpunkten, dessen Kanten Punktpaare im Abstand höchstens \(\varepsilon\) sind. Auch Noise (kein Kernpunkt und kein Kernpunkt in Reichweite) hängt nicht von der Reihenfolge ab. Nur ein Randpunkt, der in Reichweite von Kernpunkten zweier Cluster liegt, geht an das Cluster, das ihn zuerst erreicht.
Schritt 3, Monotonie in \(\varepsilon\) und \(m\): Wächst \(\varepsilon\) bei festem \(m\), wachsen alle Nachbarschaften. Jeder Kernpunkt bleibt Kernpunkt, und zwei verbundene Kernpunkte bleiben verbunden: Cluster der Kernpunkte können nur verschmelzen. Ein Punkt, der bei größerem \(\varepsilon\) Noise ist, ist auch bei kleinerem Noise: Er ist dort kein Kernpunkt, und weil es dort weniger Kernpunkte und eine kleinere Reichweite gibt, liegt auch keiner in seiner Reichweite. Der Noise-Anteil steigt bei wachsendem \(\varepsilon\) also nie. Die Zahl der Cluster dagegen kann steigen (neue Kernpunkte eröffnen neue Cluster) und fallen (Verschmelzen). Wächst \(m\) bei festem \(\varepsilon\), gilt das Umgekehrte: Es gibt weniger Kernpunkte und mehr Noise.
Schritt 4, warum ein Radius für alle Dichten schwierig ist: Eine Gruppe mit \(n_g\) Punkten sei zweidimensional normalverteilt mit Standardabweichung \(\sigma\). Der Anteil ihrer Punkte im Radius \(\varepsilon\) um die Mitte ist \(1 - e^{-\varepsilon^2/(2\sigma^2)}\). Damit die Mitte im Mittel mindestens \(m\) Punkte in ihrer Nachbarschaft hat, muss gelten \(n_g\,(1 - e^{-\varepsilon^2/(2\sigma^2)}) \ge m\), also \(\varepsilon \ge \sigma \sqrt{-2 \ln(1 - m/n_g)}\). Der nötige Radius wächst linear mit \(\sigma\). Bei fünffacher Streuung ist er fünfmal so groß, die Dichte in der Mitte \(n_g/(2\pi\sigma^2)\) fünfundzwanzigmal so klein. Das ist eine notwendige Bedingung dafür, dass die Gruppenmitte ein Kernpunkt ist, also eine untere Schranke für \(\varepsilon\) und kein Vorhersagewert. Die Ausläufer der Gruppe bleiben bei endlichem \(\varepsilon\) Noise, und andere Gruppen sind nicht berücksichtigt.
Schritt 5, Ketteneffekt: Für \(m = 2\) ist jeder Punkt mit mindestens einem Nachbarn im Radius ein Kernpunkt. Die Cluster sind dann die Zusammenhangskomponenten des Graphen, der Punkte im Abstand höchstens \(\varepsilon\) verbindet, also ein Single-Linkage-Schnitt auf der Höhe \(\varepsilon\) ohne die isolierten Punkte. Eine dünne Brücke aus Punkten, die jeweils höchstens \(\varepsilon\) auseinanderliegen, verschmilzt dann zwei Gruppen. Ein größeres \(m\) verlangt, dass die Brückenpunkte selbst Kernpunkte sind, die Brücke also dichter sein muss.

Durchgerechnetes Beispiel von Hand

Die Handinstanz der Demo: vier Punkte auf einer Linie im Abstand eins, \(p_0\) bis \(p_3\), und ein fünfter Punkt \(p_4\), weit von allen entfernt. Radius \(\varepsilon = \tfrac{3}{2}\), \(m = 3\). Die Zwischenwerte sind Rechnung dieser Seite, die Demo prüft die Rollen.

Punkt	Punkte in der Nachbarschaft	\(r_p\) (Abstand zum zweitnächsten anderen Punkt)	Rolle
\(p_0\)	2 (\(p_0, p_1\))	2, größer als \(\varepsilon\)	Randpunkt, im Radius von \(p_1\)
\(p_1\)	3 (\(p_0, p_1, p_2\))	1, höchstens \(\varepsilon\)	Kernpunkt
\(p_2\)	3 (\(p_1, p_2, p_3\))	1, höchstens \(\varepsilon\)	Kernpunkt
\(p_3\)	2 (\(p_2, p_3\))	2, größer als \(\varepsilon\)	Randpunkt, im Radius von \(p_2\)
\(p_4\)	1 (nur er selbst)	größer als \(\varepsilon\)	Noise

\(p_1\) und \(p_2\) liegen im Abstand eins, höchstens \(\varepsilon\), und sind verbunden: ein Cluster, mit \(p_0\) und \(p_3\) als Randpunkten. Das ergibt ein Cluster und einen Noise-Punkt. Die Spalte \(r_p\) bestätigt Schritt 1: Genau die Punkte mit \(r_p \le \varepsilon\) sind Kernpunkte.

Befunde der Demo

Die Aussagen stammen aus den Prüfungen der Demo. Sie gelten für die genannten Instanzen und Einstellungen. Wo eine Schwelle geprüft wird und kein Messwert, steht es dabei.

Frage	Befund
Stimmen die Rollen auf einer von Hand lösbaren Instanz? (vier Punkte auf einer Linie plus ein Ausreißer, Radius anderthalb, \(m = 3\))	Die zwei mittleren Punkte sind Kernpunkte, die zwei äußeren Randpunkte, der ferne Punkt ist Noise, es gibt ein Cluster. Der Test verlangt genau diese Rollen und Zuordnungen.
Stimmt die Implementierung mit einer Bibliothek (scikit-learn)?	Auf mehreren Szenarien (Gruppen, Halbmonde) und Parameterkombinationen erzeugt die Demo dieselbe Partition bis auf Umbenennung der Cluster, dieselben Noise-Punkte und dieselbe Menge an Kernpunkten wie scikit-learn (drei Szenarien mit je drei Parameterkombinationen).
Stimmt sie mit einem unabhängigen Rechenweg überein, auch bei Gleichständen und Duplikaten?	Auf einhundertzwanzig Zufallsinstanzen, zur Hälfte ganzzahlige Gitter mit Gleichständen und Duplikaten, zur Hälfte normalverteilt, stimmen Kernpunktmenge, Zahl der Cluster, Partition der Kernpunkte und Noise-Menge mit einer Referenz (Distanzmatrix, Zusammenhangskomponenten der Kernpunkte) überein; Kernpunktmenge und Noise-Menge zusätzlich mit scikit-learn. Randpunkte werden nur auf Gültigkeit geprüft: Sie liegen in einem Cluster, zu dem ein Kernpunkt in Reichweite gehört. In jedem Lauf gibt es höchstens \(2n\) Schritte.
Wie verhalten sich extreme Radien? (hundertzwanzig Punkte, drei Gruppen, kleine Streuung, \(m = 5\))	Bei einem winzigen Radius sind mehr als fünfundneunzig Prozent der Punkte Noise. Beim Zehnfachen der Diagonale des Datenrechtecks entsteht ein einziger Cluster ohne Noise.
Bedient ein Radius eine dichte und eine diffuse Gruppe gleich gut? (zwei Gruppen mit gleicher Punktzahl, Dichte-Ungleichgewicht nahe dem Maximum, Radius drei Zehntel, \(m = 5\))	Ein Radius, bei dem die dichte Gruppe 0% Noise hat, lässt die diffuse Gruppe laut Test bei über 30% Noise. Der Test prüft diese Schwelle für einen Radius, keinen Verlauf.
Senkt das Ungleichgewicht wirklich die Dichte der Gruppe 0?	Ja: Die mittlere Nächste-Nachbar-Distanz der Gruppe 0 ist bei Ungleichgewicht nahe dem Maximum mehr als anderthalbmal so groß wie die der übrigen Gruppen, bei drei Gruppen und bei Halbmonden mit zwei und mit vier Gruppen, je an einem Zufallsbeispiel.

Nachrechnung dieser Seite: wie breit ist das Fenster passender Radien?

Die folgenden Befunde sind Rechnung dieser Seite, keine Messung der Demo und nicht in ihren Tests. Sie verwenden die Zufallserzeugung der Demo (je Konfiguration fünfzehn Zufallsbeispiele mit fortlaufenden Startwerten von eins bis fünfzehn), \(m = 5\) und Radien im Raster von fünf Hundertsteln bis drei in Schritten von fünf Hundertsteln. Die Zufallsbeispiele haben hundertfünfzig Punkte ohne Ausreißer; nur die Ausreißer-Konfiguration der Demo hat welche, sie zählen bei der Beurteilung nicht mit. Gerechnet wurde mit einem kurzen Nachbau über die Zusammenhangskomponenten der Kernpunkte. Er stimmt bei Noise und Zahl der Cluster für alle Radien des Rasters und alle vier Beispielkonfigurationen mit der Demo überein. Ein Radius heißt passend (eine Festlegung dieser Seite, die die wahren Gruppen der Erzeugung benutzt; die Schwellen sind gesetzt, nicht begründet, andere Schwellen verschieben das Fenster), wenn genau so viele Cluster wie erzeugte Gruppen entstehen, in jeder Gruppe höchstens fünf Prozent der Punkte Noise sind, mindestens fünfundneunzig Prozent der geclusterten Punkte einer Gruppe in einem gemeinsamen Cluster liegen und keine zwei Gruppen dasselbe Cluster ergeben.

Die vier Beispielkonfigurationen der Demo: Beim Beispiel mit zwei Gruppen und starkem Dichte-Unterschied ist jeder Radius ab etwa drei Vierteln bis zum Ende des Reglers passend. Der Radius der Voreinstellung dieses Beispiels liegt mit fünfunddreißig Hundertsteln weit darunter. Beim Beispiel mit zwei Halbmonden passen nur Radien zwischen etwa fünfundfünfzig und neunzig Hundertsteln; darunter zerfällt ein Halbmond in Stücke, darüber verschmelzen beide. Beim Beispiel mit gleichmäßiger Dichte reicht das Fenster von sechs Zehnteln bis über zwei, beim Beispiel mit Ausreißern von sechs Zehnteln bis knapp zwei.
Ausreißer und Radius: Beim Beispiel mit Ausreißern sind beim Radius fünf Zehntel knapp neun Zehntel der verstreuten Ausreißer Noise. Mit wachsendem Radius sinkt dieser Anteil: Bei einem Radius von eins sind es etwa zwei Drittel, bei eineinhalb gut ein Fünftel, am Ende des Reglers wenige Prozent. Der Radius ist hier ein Kompromiss zwischen dem Erfassen der Gruppenränder und dem Aussortieren der Ausreißer.
Wirkung des Ungleichgewichts: Bei zwei Gruppen gab es in allen fünfzehn Zufallsbeispielen mindestens einen passenden Radius, ohne Ungleichgewicht und mit \(u\) gleich neun Zehntel. Das Fenster wird aber schmaler: Gegenüber dem Fall ohne Ungleichgewicht halbiert sich das Fenster bei großer Streuung (fünfundzwanzig Hundertstel) ungefähr und schrumpft bei kleiner Streuung (zwölf Hundertstel) nur wenig. Bei drei Gruppen ist das Muster ähnlich; mit großer Streuung und Ungleichgewicht gab es in vierzehn von fünfzehn Beispielen einen passenden Radius.
Viele oder breite Gruppen: Bei vier Gruppen und großer Streuung gab es nur in einem Teil der Beispiele überhaupt einen passenden Radius (ohne Ungleichgewicht in fünf von fünfzehn, mit Ungleichgewicht in drei von fünfzehn), bei sechs Gruppen und großer Streuung in keinem. Vermutlich berühren oder überlappen sich die Gruppen dort so stark, dass kein Radius sie trennt; die Ursache wurde nicht geprüft. Das Ungleichgewicht senkt die Trefferzahl von fünf auf drei von fünfzehn; bei so wenigen Beispielen ist das kein gesicherter Unterschied.
Halbmonde: Sie sind empfindlicher als Gruppen. Das Fenster umfasst bei zwei Halbmonden und kleinem Rauschen nur etwa ein Siebtel bis knapp ein Viertel der Rasterradien. Bei zwei Halbmonden und großem Rauschen gab es nicht in jedem Beispiel einen passenden Radius (dreizehn von fünfzehn, mit Ungleichgewicht elf von fünfzehn).

Grenzen und was die Messung zeigt

Das belegen die Prüfungen der Demo: Die Implementierung stimmt mit scikit-learn und mit einem unabhängigen Rechenweg überein, soweit die Prüfungen reichen (Kernpunkte, Cluster der Kernpunkte, Noise). Die Handinstanz und die Extremfälle verhalten sich wie erwartet. Das Ungleichgewicht senkt in der Erzeugung die lokale Dichte der Gruppe 0.

Das belegen sie nicht:

Die Kernaussage zur Dichte ist nur teilweise belegt: Die Beschreibung der Demo sagt, dass bei jedem Radius, der die dichte Gruppe vollständig erfasst, die diffuse Gruppe noch großteils Noise bleibt und dass kein einzelner Radius beide gleich gut bedient. Der Test prüft nur einen Radius. Er verlangt für die diffuse Gruppe mehr als 30% Noise, was nicht großteils heißt; die Nachrechnung dieser Seite ergibt für dieses Beispiel fast die Hälfte. Mehr als die Hälfte der diffusen Gruppe ist nur für Radien von etwa siebzehn bis siebenundzwanzig Hundertsteln Noise. Dieselbe Nachrechnung zeigt ein breites Fenster größerer Radien, in dem beide Gruppen ohne Noise getrennt bleiben, weil die Gruppenmitten weit auseinanderliegen (bei zwei Gruppen etwa sechs Karteneinheiten, ein Vielfaches der Streuung). Belegt ist also nur: Ein kleiner Radius, der die dichte Gruppe erfasst, lässt die diffuse zum Teil als Noise zurück. Ob bei nahe beieinanderliegenden Gruppen ungleicher Dichte kein Radius beide trennt, ist nicht gemessen; Schritt 4 macht es plausibel, mehr nicht.
Ein globaler Radius: Eine einzige Radius-Wahl gilt für die ganze Punktwolke. Wie viel Nachteil das hat, hängt davon ab, wie weit die Gruppen auseinanderliegen und wie viele Ausreißer es gibt, wie die Nachrechnung oben zeigt.
Wahl von \(\varepsilon\) und \(m\): Das k-Distanz-Diagramm ist eine Heuristik (Quelle: Ester et al., 1996). Die Demo zeigt es nur an ihren Zufallsbeispielen, nicht als belegte Regel. Für \(m\) bietet die Demo keine Faustregel.
Randpunkte: Ihre Zuordnung zu einem von zwei erreichbaren Clustern hängt von der Reihenfolge ab (Schritt 2). Die Prüfungen vergleichen Randpunkte deshalb nur auf Gültigkeit.
Ketteneffekt: Eine dünne Brücke von Kernpunkten verschmilzt Gruppen (Schritt 5); die Demo zeigt diesen Fall nicht.
Simulation in der Ebene: Die Punkte sind zufällig erzeugt, der Abstand ist die Luftlinie. Straßennetz, Fahrzeiten, Paketmengen und Fahrzeugkapazitäten fehlen. „Route“ heißt hier nur Gruppe, es wird keine Reihenfolge der Stopps geplant.
Einzelfälle statt Verteilungen: Die Tests nutzen feste Zufallsbeispiele, ihre Schwellen gelten für diese. Die Nachrechnung dieser Seite nutzt fünfzehn Zufallsbeispiele je Konfiguration und ein Radius-Raster; sie sagt nichts über Streuung zwischen Beispielen.

Quellen

Ester, Kriegel, Sander, Xu (1996): A density-based algorithm for discovering clusters in large spatial databases with noise. KDD-96 (Verfahren und k-Distanz-Heuristik).
Schubert, Sander, Ester, Kriegel, Xu (2017): DBSCAN revisited, revisited. ACM Transactions on Database Systems.
Campello, Moulavi, Sander (2013): Density-based clustering based on hierarchical density estimates. PAKDD (HDBSCAN).
Quelltext, Messreihe und Tests der Demo: github.com/sebastian-hanisch/dbscan-demo.

Die Arbeiten wurden für diese Seite nicht nachgeschlagen. Ester et al. nennt die Demo mit Titel, Tagungsband, Schubert et al. und Campello et al. sind aus dem Gedächtnis ergänzt und nicht geprüft.

Demo ausprobieren Zurück zum Thema