Knowledge Discovery in Databases - Knowledge Discovery in Databases - page 72

צെ ୩ ൌ ୨ୀଵǡǥǡ୬ צെ ୨ צ gilt.

Zur Bestimmung des Abstandes kann z. B. der Euklidische oder der Mahalanobis-Abstand
herangezogen werden (Runkler 2010, 96). Eine abgewandelte Form, der k-Nearest-Neighbor-
Algorithmus, wurde bereits im Jahre 1994 von Yang/Chute (1994) entwickelt. Hier wird im
Gegensatz die am häufigsten vorkommende Klasse wiedergegeben, indem nicht nur der
nächste Nachbar, sondern die nächsten Nachbarn berücksichtigt werden (Runkler 2010). Die
Nachteile der Methode entstehen durch induktive Verzerrungen oder Modellverzerrungen
(Datenobjekte sind gleichmäßig in den Kategorien verteilt), die durch eine von Tan (2006,
292-297) entwickelte Methode namens DragPushing abgeschwächt werden können.

3.5.2.1.4 DBSCAN
Der Density-Based Spatial Clustering of Applications with Noise-Algorithmus (DBSCAN) ist
in der Lage, Cluster innerhalb einer Menge von Datenpunkten zu finden, ohne a priori die
Anzahl der Klassen zu bestimmen. Er basiert auf einer dichtebasierten Vorstellung von Clus-
tern, die es nicht nur ermöglichen konvexe Cluster zu finden, sondern auch welche von belie-
biger Form (Pal/Mitra 2004, 127f.). Zusätzlich wird Rauschen weitestgehend ignoriert und
separat ausgegeben (Ester et al. 1996, 3). Abbildung 3-9 zeigt auf der linken Seite eine Da-
tenmenge mit nur konvexen Clustern, in der Mitte eines mit Clustern beliebiger Form und auf
der rechten Seite eine Zuweisung von beliebigen Formen und Rauschen.

Abbildung 3-9: Mögliche Verteilungen von Datenpunkten

(Quelle: (Ester et al. 1996, 2))

Die Grundidee ist, dass DBSCAN für jeden Datenpunkt p innerhalb eines Clusters die Dichte
in der Nachbarschaft des Bereichs N mit dem Radius Eps hat, einen Schwellenwert über-
schreiten muss (Chen/Gao/Li 2010, 1). Formal ist der Bereich definiert als:

ܰ ா௣௦ ሺ݌ሻൌሼݍאܦȁ݀݅ݏݐሺ݌ǡݍሻ൑ܧ݌ݏሽ

Wenn die Nachbarschaft des Datenpunkts q mindestens eine minimale Anzahl von Daten-
punkten ( ȁܰܧ݌ݏሺ݌ሻȁ൒ܯ݅݊ܲݐݏሻ enthält, wird q als Kernobjekt und die Datenpunkte (p) in
der Nachbarschaft als direkt dichteerreichbar von q ( ݌אܦܦܴ ௤ ሻ bezeichnet. Diese Beziehung
ist transitiv, so dass wenn ݔאܦܦܴ ௬ רݕאܦܦܴ ௭ gilt, dann wird x als dichteerreichbar von z
und die Datenpunkte x, y, z als dichteverbunden bezeichnet. Dies bedeutet somit, dass sie Be-