Header
   TUM Logo Clusteranalyse Polytop
Header_Inhalt

Header Bild

Dichteverbundenes Clustern

Dichteverbundene Clusterverfahren erkennen Gebiete mit hoher Datenpunktdichte als Cluster. Man geht davon aus, dass die Dichte von Objekten innerhalb eines Clusters höher ist als außerhalb desselben. DBSCAN, ein 1996 entwickelter Algorithmus, vereint die wichtigsten Konzepte des dichteverbundenen Clusterns. Daher wollen wir diesen hier ausführlicher behandeln und anhand von Beispielen erläutern.

DBSCAN

Zunächst muss man sich überlegen, wie die Dichte eines speziellen Datenpunkts bemessen werden kann. Beim zentrumsbasierten Zugang wird die Dichte für den Punkt p durch die Anzahl der Punkte in einer ε-Umgebung für ein zu bestimmendes ε geschätzt. Die ε-Umgebung von p besteht aus allen Punkten, die höchstens den Abstand ε zu p besitzen.

Epsilon-Umgebung 

Ist der Radius ε sehr groß, so besitzen alle Datenpunkte die Dichte m (= Anzahl Datenpunkte), da dann für jeden Punkt p alle Punkte in der ε-Umgebung von p liegen. Wählt man ε zu klein, so hat jeder Punkt die Dichte 1. Daher ist die Bestimmung von ε im Vorfeld der Analyse von zentraler Bedeutung. Ein weiterer Parameter, den wir für den DBSCAN-Algorithmus benötigen, ist MinPts. Dieser legt fest, wie viele Punkte in der ε-Umgebung von einem Punkt p liegen müssen, damit p zu einem Cluster gehört. 

Wir unterteilen die Daten in drei verschiedene Kategorien: 

Ein Datenpunkt liegt entweder im Inneren einer dichten Region (Kernpunkt), auf dem Rand einer solchen (Randpunkt) oder in einem spärlich besetzten Gebiet (Rauschpunkt). Etwas präziser:

  • Kernpunkt:
    Die Anzahl der Datenpunkte in der ε-Umgebung des Kernpunkts beträgt mindestens MinPts.
  • Randpunkt:
    Ein Randpunkt ist kein Kernpunkt, liegt aber in der ε-Umgebung eines Kernpunktes.
  • Rauschpunkt:
    Ein Rauschpunkt ist weder Kern- noch Randpunkt.
Punkt-Klassifizierung

Jetzt zum DBSCAN-Algorithmus: Informell beschrieben, landen zwei Kernpunkte, deren Abstand höchstens ε beträgt, im gleichen Cluster, Randpunkte werden dem Cluster eines entsprechenden Kernpunktes zugeordnet und Rauschpunkte werden vernachlässigt.

Algorithmus
  1. Benenne Datenpunkte als Kern-, Rand- oder Rauschpunkte.
  2. Lösche alle Rauschpunkte.
  3. Verbinde Kernpunkte, die innerhalb einer ε-Kugel liegen, durch eine Kante.
  4. Eine Menge verbundener Kernpunkte bilden ein separates Cluster.
  5. Weise jeden Randpunkt dem Cluster eines benachbarten Kernpunkts zu.

Zeit- und Speicherplatz-Aufwand 

Der Zeitaufwand beträgt O(m × t), wobei t die Zeit zum Zählen der Punkte in einer ε-Umgebung ist, im Worst-Case daher O(m2). Das bedeutet, im schlimmsten Fall benötigt man m2 viele elementare Rechnungen, wobei m die die Anzahl der Datenpunkte ist. Bei den meisten Anwendungen erreicht man mithilfe spezieller Datenstrukturen sogar O(mlogm). Der Speicheraufwand von DBSCAN beträgt nur O(m), ist also sehr günstig.

Auswahl der DBSCAN-Parameter 

Damit DBSCAN ein gutes Clustering liefert, muss man die Werte der Parameter ε und MinPts geschickt wählen. Der übliche Ansatz zur Bestimmung dieser Werte, ist die Betrachtung der Distanz eines Punktes p zu seinem k-nächstem Nachbarn, also dem Punkt, der den k-größten Abstand zu p hat. Diese Distanz werden wir mit k - dist bezeichnen. Für Punkte innerhalb eines Clusters ist k - dist in der Regel klein, für Rauschpunkte dagegen vergleichsweise groß. Wir berechnen daher k - dist für alle Datenpunkte und zeichnen das Ergebnis aufsteigend in ein Diagramm. Man sollte dann einen scharfen Übergang erkennen können, welcher eine gute Wahl für ε nahelegt. k sollte in etwa die Größe der zu erwartenden Cluster widerspiegeln, für zweidimensionale bietet sich k = 4 an. MinPts geben wir schließlich den Wert von k.

Vor- und Nachteile von DBSCAN

DBSCAN filtert Rauschen meist sehr gut aus den Daten und kann Cluster beliebiger Form und Größe erfassen. Dies ist in den folgenden Beispielen gut zu erkennen: 

Zunächst ein verrauschter Datensatz mit zehn natürlichen Clustern. DBSCAN erkennt diese problemlos, wohingegen der K-Means-Algorithmus kein erwünschtes Clustering liefert.

Beispiel Rauschen

In der nächsten Graphik sehen Sie einen Datensatz, welcher aus einem Ring und einem Häufungspunkt in der Ringmitte besteht. Bei einem Standartwert MinPts = 5 kann man ε zwischen 0,2 und 0,6 frei wählen, um das natürliche Clustering zu erhalten. Auch bei der Wahl von MinPts muss man deutlich vom Standartwert abweichen, sodass DBSCAN ein unerwünschtes Clustering wählt. Folglich behandelt DBSCAN diese Daten mit Clustern besonderer Form recht gut, wohingegen K-Means beim selben Datensatz erhebliche Probleme bekommt.
Clustering Kreis mit Mittelpunkt

Andererseits hat der DBSCAN-Algorithmus Schwierigkeiten mit der Erkennung von Clustern unterschiedlicher Dichten. Wählt man ε sehr groß, um „schwache“ Cluster zu finden, werden möglicherweise Rauschgebiete als Cluster erkannt. Im folgenden Beispiel findet man keine Parameterwerte für ε und MinPts, sodass DBSCAN die drei natürlichen Cluster (Rechtecke) erkennt, da die Punktdichten in den Objekten sehr unterschiedlich sind. K-Means erkennt die Cluster hingegen problemlos. 

Clustering mit unterschiedlichen Dichten

Außerdem treten beim DBSCAN-Algorithmus Probleme bei hochdimensionalen Daten (Datensatz mit vielen Attributen) auf, da hier die Dichte schwierig zu definieren ist. Schließlich kann DBSCAN teuer werden, wenn die Berechnung der nächsten Nachbarn aufwändig ist.

Copyright 2009 - Team Clusteranalyse
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _