DBSCAN ist ein dichte-basierter Clustering-Algorithmus, der Cluster beliebiger Form auffindet und diese von Rauschen trennt. Aufgrund des quadratischen Aufwands ist DBSCAN fu¨r große Datenmengen jedoch oft ungeeignet. In dieser Arbeit wird deshalb ein effizienterer Algorithmus namens FM-DBSCAN vorgestellt, der fu¨r eine beliebige Distanzfunktion (Metrik) dasselbe Ergebnis wie DBSCAN liefert. Hierfu¨r partitioniert FM-DBSCAN die Datenkollektion in Leader-Umgebungen, auf denen anschließend das Clustering durchgefu¨hrt wird. Erste Experimente mittels synthetischen Datenkollektionen zeigen, dass FM-DBSCAN um einen Faktor > 990 schneller als DBSCAN ist und auch wesentlich besser mit der Kollektionsgro¨ße skaliert.
I.5.3 [PATTERN RECOGNITION]: Clustering—Algorithms
2.
In dem folgenden Abschnitt wird der von Ester et al.
entwickelte, dichte-basierte Clustering-Algorithmus DBSCAN
eingefu¨hrt [
Im Nachfolgenden sei O eine endliche Menge von Objekten, mit |O| = n. Des Weiteren sei d eine Distanzfunktion (Metrik) auf der Menge X und O ⊆ X. minPts ∈ N≥0 und ∈ R≥0 sind die beiden Parameter von DBSCAN. Alle folgenden Definitionen und Lemmata sind immer abha¨ngig von und minPts.
Definition 1. Ein Objekt o ∈ O heißt Kernobjekt, wenn |N (o)| ≥ minPts ist, mit N (o) = {oˆ ∈ O | d(o, oˆ) ≤ }.
und minPts spezifizieren hierbei einen minimalen Dichtegrenzwert, der festlegt, ob ein Objekt ein Kernobjekt ist. Alle Objekte, welche keine Kernobjekte sind, werden NichtKernobjekte genannt.
Definition 2. Ein Objekt p ∈ O ist direkt dichte-erreichbar von q ∈ O, wenn q ein Kernobjekt und p ∈ N (q) ist. Nach Definition 2 sind alle Objekte der -Umgebung eines Kernobjektes q direkt dichte-erreichbar von q. Um die ErAbb. 1: Dichte-Erreichbarkeit fu¨r minPts = 5 reichbarkeit u¨ber die Grenzen der -Umgebung eines Kernobjektes hinauszufu¨hren, wird der Begriff der Dichte-Erreichbarkeit eingefu¨hrt.
Definition 3. Ein Objekt p ∈ O ist dichte-erreichbar von einem Objekt q ∈ O, wenn es eine Folge von Objekten p1, . . . , pm ∈ O gibt, sodass p1 = q, pm = p und pi+1 direkt dichte-erreichbar von pi ist, fu¨r 1 ≤ i < m.
Wie man leicht sieht, bildet die Dichte-Erreichbarkeit den
transitiven Abschluss u¨ber der Relation der direkten
DichteErreichbarkeit. Die Veranschaulichung der
Dichte-Erreichbarkeit ist in Abb. 1 zu sehen. Mittels der
Dichte-Erreichbarkeit kann man einen Cluster wie folgt konstruieren [
Lemma 1. Sei p ein Kernobjekt in O. Dann ist die Menge C = {o ∈ O|o ist dichte-erreichbar von p} ein Cluster in O. Aus Lemma 1 folgt, dass ein Cluster C vollsta¨ndig berechnet werden kann, indem man ausgehend von einem beliebigen Kernobjekt p ∈ C, alle dichte-erreichbaren Objekte von p ermittelt. Alle Objekte, die zu keinem solchen Cluster geho¨ren, werden als Rauschen bezeichnet. 2.2
Ziel von DBSCAN ist es nun, alle solche Cluster zu finden. Die Erkenntnis aus Lemma 1 fließt dabei in den Alg. 1 ein. Alg. 1 DBSCAN(O, , minPts) 1: clusterId := 1; 2: for all o ∈ O do 3: if o.clId = −1 then 4: if expandCluster(O, o, clusterId, , minPts) then 5: clusterId := clusterId + 1; Alg. 2 expandCluster(O, o, clusterId, , minPts) 1: neighborhood := N (o); 2: if |neighborhood| < minPts then 3: o.clId := 0; 4: return false; 5: seeds := ∅; 6: setClusterId(neighborhood, clusterId); 7: expandSeeds(neighborhood, o, clusterId, seeds); 8: while seeds 6= ∅ do 9: Wa¨hle Objekt oˆ aus der Menge seeds aus; 10: seeds := seeds \ {oˆ}; 11: neighborhood := N (oˆ); 12: if |neighborhood| ≥ minPts then 13: setClusterId(neighborhood, clusterId); 14: expandSeeds(neighborhood, oˆ, clusterId, seeds); 15: return true;
In DBSCAN (Alg. 1) erha¨lt jedes Objekt o ∈ O ein Attribut clId , welches angibt zu welchem Cluster es geho¨rt. Der Wert 0 bedeutet, das Objekt geho¨rt zum Rauschen und ein Wert gro¨ßer 0 spezifiziert die zugeho¨rige Clusternummer. Initial ist fu¨r alle Objekte clId auf −1 (nicht klassifiziert) gesetzt. In DBSCAN wird nun versucht, von einem Objekt o mit clId = −1, einen neuen Cluster zu finden (Z. 3–5). Hierzu wird in expandCluster zuerst die -Umgebung von o berechnet (Z. 1) und u¨berpru¨ft, ob es sich bei o um ein Kernobjekt handelt. Ist o ein Nicht-Kernobjekt, wird es als Rauschen markiert und die Suche nach einem Cluster von o aus abgebrochen (Z. 2–4). Es sei angemerkt, dass o spa¨ter noch einem Cluster zugewiesen werden kann, wenn es in der -Umgebung eines Kernobjekts liegt. Andernfalls ist o ein Kernobjekt und es kann laut Lemma 1 ein neuer Cluster mit der Nummer clusterId konstruiert werden. Hierzu werden die direkt dichte-erreichbaren Objekte von o, also N (o), dem Cluster hinzugefu¨gt (Z. 6). Anschließend werden fu¨r alle Objekte aus N (o) deren direkt dichte-erreichbaren Objekte ermittelt und dem Cluster zugewiesen. Die Schritte werden solange wiederholt, bis keine neuen Objekte des Clusters mehr gefunden werden ko¨nnen (Z. 8–14). expandSeeds fu¨gt dabei nur die Objekte aus N (o) \ {o} fu¨r das aktuelle Kernobjekt o in die tempora¨re Menge seeds ein, fu¨r die clId = −1 ist. setClusterId markiert die Objekte aus N (o) mit der Nummer clusterId , fu¨r die clId < 1 gilt. Die Laufzeit von Alg. 1 betra¨gt O(n2).
Zur Beschleunigung von DBSCAN existieren bereits
mehrere Ansa¨tze, welche sich in exakte (liefern dasselbe Ergebnis
wie DBSCAN) und approximative Verfahren (garantieren
kein exaktes Ergebnis) unterteilen lassen. Exakte Verfahren
sind in den Arbeiten [
GriDBSCAN ist ein exaktes Verfahren fu¨r den
euklidischen Raum Rd [
Ein exaktes Verfahren, welches ebenfalls auf einem
Datengitter basiert, wurde von Gunawan vorgestellt [
Die Erweiterung des Verfahrens von Gunawan auf ho¨here
Dimensionen d wurde von Gan und Tao gezeigt [
Gan und Tao stellen ebenfalls noch das ρ-approximative
DBSCAN fu¨r den Rd vor, mit einer Laufzeit von O(n) [
Rough-DBSCAN ist ein approximatives Verfahren, das
wie FM-DBSCAN auf dem Prinzip der
Leader-Umgebungen basiert [
Das approximative Verfahren FDBSCAN fu¨r den Rd hat
Abb. 2: Beispiel fu¨r eine Leader-Partition
einen, im Vergleich zu DBSCAN, vera¨nderten Ablauf [
Im Gegensatz zu den hier aufgefu¨hrten Verfahren, die entweder approximativ oder nur fu¨r den Rd exakt sind, liefert FM-DBSCAN fu¨r beliebige Distanzfunktionen ein exaktes Ergebnis und stellt somit einen universelleren Ansatz dar.
In diesem Abschnitt wird der Clustering-Algorithmus Fast
Metric DBSCAN pra¨sentiert. FM-DBSCAN besteht aus zwei
Phasen. In der ersten Phase werden die Objekte mittels des
Algorithmus Counted-Leaders [
Seien O, d, minPts und gegeben wie in Abschnitt 2.1. Im Folgenden sind die Definitionen und Lemmata immer abha¨ngig von und minPts.
Definition 4. Ein Tupel (l, N L(l)) ist eine Leader-Umgebung in O, wenn N L(l) ⊆ N (l) und l ∈ N L(l) ist. l ist der Repra¨sentant der Menge N L(l) und wird Leader genannt. Die Leader-Umgebung mit dem Leader l ist also ein Ausschnitt der -Umgebung von l. Mittels der Leader-Umgebungen soll nun die Menge der Objekte O partitioniert werden.
Definition 5. Eine Leader-Partition von O ist eine Menge von Leader-Umgebungen L = {(l1, N L(l1)), . . . , (lm, N L(lm))}, mit d(li, lj) > ∧ N L(li) ∩ N L(lj) = ∅ fu¨r i 6= j und Sim=1 N L(li) = O.
Ein Beispiel fu¨r eine Leader-Partition, die auch der Alg. 3 aus Abschnitt 4.2 berechnet, ist in Abb. 2 dargestellt. Im Anschluss sollen die Begriffe der direkten Dichte-Erreichbarkeit und der Dichte-Erreichbarkeit auf Leader-Umgebungen u¨bertragen werden.
Definition 6. Eine Leader-Umgebung (lp, N L(lp)) ist direkt dichte-erreichbar von einer Leader-Umgebung (lq, N L( lq)) in O, wenn es eine Folge von Objekten p1, . . . , pm ∈ N L(lp) ∪ N L(lq) gibt, sodass p1 = lq, pm = lp ist und es gilt: 1. pi+1 ist direkt dichte-erreichbar von pi fu¨r 1 ≤ i < m, 2. lp ist ein Kernobjekt in O oder |N L(lp)| = 1.
Definition 7. Eine Leader-Umgebung (lp, N L(lp)) ist dichte-erreichbar von einer Leader-Umgebung (lq, N L(lq)) in O, wenn es eine Folge von Leader-Umgebungen (l1, N L(l1)), . . . , (lm, N L(lm)) in O gibt, sodass (l1, N L(l1)) = (lq, N L(lq) ), (lm, N L(lm)) = (lp, N L(lp)) und (li+1, N L(li+1)) direkt dichte-erreichbar von (li, N L(li)) in O ist, fu¨r 1 ≤ i < m.
In der Definition 6 Punkt 2 wurde explizit gefordert, dass lp ein Kernobjekt oder |N L(lp)| = 1 ist. Dadurch wird erreicht, dass fu¨r eine Umgebung (lp, N L(lp)), die von einer Umgebung (lq, N L(lq)) direkt dichte-erreichbar ist, gilt, dass alle Objekte o ∈ N L(lq) ∪ N L(lp) dichte-erreichbar von lq sind. Dies wa¨re fu¨r eine Umgebung (lp, N L(lp)), mit lp ist ein Nicht-Kernobjekt und |N L(lp)| > 1, nicht der Fall.
Im Anschluss werden noch drei Lemmata vorgestellt, die es dem Alg. 4 aus Abschnitt 4.3 ermo¨glichen, erheblichen Berechnungsaufwand einzusparen.
Lemma 2. Seien (lp, N L(lp)) und (lq, N L(lq)) zwei Leader-Umgebungen und (lp, N L(lp)) ist direkt dichte-erreichbar von (lq, N L(lq)) in O, dann gelten folgende Aussagen: 1. Ist lp ein Kernobjekt, dann existieren zwei Kernobjekte p ∈ N L(lp) und q ∈ N L(lq) mit d(p, q) ≤ . 2. Ist |N L(lp)| = 1, dann existiert ein Kernobjekt q ∈
N L(lq) in O mit d(lp, q) ≤ .
Lemma 3. Seien p, q zwei Objekte in O. Ist d(p, q) > 2 , so gilt fu¨r alle o ∈ N (p) : d(o, q) > .
Lemma 4. Seien p, q zwei Objekte in O. Ist d(p, q) > 3 , so gilt fu¨r alle o1 ∈ N (p) und o2 ∈ N (q) : d(o1, o2) > .
Lemma 2 beschreibt eine effiziente Mo¨glichkeit, um zu testen, ob eine Leader-Umgebung (lp, N L(lp)) von einer Leader-Umgebung (lq, N L(lq)) direkt dichte-erreichbar ist. Hierfu¨r mu¨ssen wir im ersten Fall nur nachweisen, dass lq und lp Kernobjekte sind und dass zwei Kernobjekte p ∈ N L(lp) und q ∈ N L(lq) existieren mit d(p, q) ≤ . Der Test auf d(p, q) ≤ kann dabei mit Lemma 3 beschleunigt werden. Fu¨r den zweiten Fall reicht es sogar aus, nachzuweisen, dass lq ein Kernobjekt ist und das ein Kernobjekt q ∈ N L(lq) existiert mit d(q, lp) ≤ . Um die Anzahl dieser Tests so gering wie mo¨glich zu halten, verwenden wir die Lemmata 3 und 4. Hierzu muss lediglich die Distanz d(lp, lq) berechnet werden, um zu entscheiden, ob fu¨r zwei Objekte p ∈ N L(lp) und q ∈ N L(lq) die Distanz d(p, q) ≤ sein kann. Sollte das nicht der Fall sein, so ist keine der Leader-Umgebungen voneinander direkt dichte-erreichbar. Auf die Beweise der Lemmata wird aufgrund des eingeschra¨nkten Platzes verzichtet. Im Wesentlichen basieren sie auf der von d erfu¨llten Dreiecksungleichung, der direkten Dichte-Erreichbarkeit und der Dichte-Erreichbarkeit von Objekten. 4.2
Um eine Leader-Partition zu berechnen, nutzen wir
eine angepasste Variante des Algorithmus Counted-Leaders
(Alg. 3) von Viswanath und Suresh Babu [
Die Leader-Partition (leader Parti tion) wird schrittweise aufgebaut. Hierzu wird jedes Objekte o ∈ O der ersten Leader-Umgebung (l, N L(l)) ∈ leaderPartition zugewiesen, fu¨r die d(o, l) ≤ gilt (Z. 4–8). Existiert keine solche LeaderUmgebung, so wird (o, {o}) als neue Leader-Umgebung zu leaderPartition hinzugefu¨gt (Z. 9–10). Die Reihenfolge, in der u¨ber leader Parti tion iteriert wird (Z. 4), ist durch die Einfu¨gereihenfolge der Leader-Umgebungen festgelegt. 4.3
In diesem Abschnitt wird beschrieben, wie anhand einer Leader-Partition die Menge der Objekte O effizient in Cluster unterteilt werden kann. Die Grundidee ist dabei analog zu DBSCAN. Ausgehend von einer Leader-Umgebung, deren Leader ein Kernobjekt ist, werden alle dichte-erreichbaren Leader-Umgebungen ermittelt. Diese bilden dann zusammen einen Cluster. Probleme bereiten dabei jedoch Leader-Umgebungen (l, N L(l)), bei denen l ein Nicht-Kernobjekt und |N L(l)| > 1 ist. Von diesen Umgebungen aus kann kein Cluster konstruiert werden. Dies ist besonders problematisch, wenn in der Leader-Partition nur solche Umgebungen auftreten. Außerdem sind diese Umgebungen laut Definition 6 nicht direkt dichte-erreichbar von anderen Umgebungen, wodurch Objekte eines Clusters verloren gehen ko¨nnten. Die Lo¨sung dieses Problems besteht darin, jedes Mal, wenn auf so eine Umgebung getroffen wird, deren Objekte auf noch nicht geclusterte Umgebungen zu verteilen, deren Leader nicht als Nicht-Kernobjekt markiert wurden. Existiert fu¨r eines der Objekte eine solche Umgebung nicht, so wird eine neue Umgebung mit dem Objekt als Leader erzeugt. Ist der neue Leader l1 noch nicht als Nicht-Kernobjekt markiert, so werden ihm alle als Nicht-Kernobjekte markierten Leader l2, die noch nicht geclustert wurden und fu¨r die d(l1, l2) ≤ gilt, zugeordnet. Dadurch erreicht man, in mehreren Ausfu¨hrungen der Neuverteilung, dass alle Objekte entweder einer Umgebung zugeordnet sind, deren Leader ein Kernobjekt ist, oder dass Leader-Umgebungen (l, N L(l)) entstehen, mit |N L(l)| = 1. Hierdurch wird die direkte Dichte-Erreichbarkeit wieder anwendbar. Die entsprechende Umsetzung dieses Ansatzes ist in Alg. 4 dargestellt.
Alg. 4 FM-DBSCAN(O, , minPts) 1: LN := computeLeaderPartition(O, ); 2: LC := ∅; 3: clusterId := 1; 4: whi(lle, NLLN(l6)) =
= ∅ do 5: 6: 7:
arg max |NL(˜l)|; (l˜,NL(l˜))∈LN if expandCluster((l, NL(l)), LN , LC, clusterId, , minPts ) then clusterId := clusterId + 1;
Alg. 5 expandCluster((l, NL(l)), LN , LC, clusterId, , minPts) 7: 8: 9: 10: 1: if isCoreObject(l, LN , LC, , minPts) then 2: setClusterId(NL(l), clusterId); 3: LN := LN \ {(l, NL(l))}; 4: LC := LC ∪ {(l, NL(l))}; 5: seeds := ∅; 6: ddrLeaders := findDirectDensityReachableLeaders( (l, NL(l)), LN , LC, , minPts); setClusterId(ddrLeaders, clusterId); expandSeeds(ddrLeaders, LN , LC, clusterId, seeds); while seeds 6= ∅ do (˜l, NL(˜l)) = |NL(l˜2)|;
Wie bei DBSCAN hat jedes Objekt das Attribut clId (intial −1). Zusa¨tzlich bekommt jedes Objekt ein Attribut type, was angibt, ob es sich bei dem Objekt um ein Kernobjekt (type = 1) oder ein Nicht-Kernobjekt (type = 0) handelt. Initial ist type = −1 (undefiniert) fu¨r alle Objekte o ∈ O. Die Menge LC entha¨lt alle geclusterten und als Rauschen markierten Leader-Umgebung. LN hingegen entha¨lt alle nicht geclusterten Umgebungen (clId = −1). FM-DBSCAN la¨uft solange, bis LN leer ist (Z. 4), also alle Umgebungen geclustert wurden. Das iterative Einsammeln von dichte-erreichbaren Leader-Umgebungen ist in den Z. 1–15 von expandCluster (Alg. 5) beschrieben. Dabei weist setClusterId der u¨bergebenen Menge von Objekten die u¨bergebene Clusternummer zu. expandSeeds fu¨gt der tempora¨ren Menge seeds lediglich die direkt dichte-erreichbaren Umgebungen hinzu, deren Leader ein Kernobjekt ist. Sollte die Startumgebung in Alg. 5 ein Nicht-Kernobjekt sein, so erfolgt die angesprochene Neuverteilung der Objekte (Z. 22–36).
findDirectDensityReachableLeaders (Alg. 6) ermittelt fu¨r die u¨bergebene Leader-Umgebung (l, N L(l)) alle direkt dichte-erreichbaren Leader-Umgebungen, indem mit einer Kandidatenmenge (candidates) (Z. 1) gearbeitet wird. candidates wird mit den Leader-Umgebungen aus LN initialisiert, deren Leader eine Distanz kleiner gleich 3 zu l aufweisen (Lemma 4). Die Beschra¨nkung auf Umgebungen aus LN ist korrekt, da nur nicht geclusterte, direkt dichte-erAlg. 6 findDirectDensityReachableLeaders( (l, NL(l)), LN , LC, , minPts) 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 1: candidates := N3 ((l, NL(l)), LN ); 2: ddrLeaders := ∅; 3: while candidates 6= ∅ do 4: (˜l, NL(˜l)) = arg max |NL(l˜2)|;
(l˜2,NL(l˜2))∈candidates 5: candidates := candidates \ {(˜l, NL(˜l))}; 6: if isDirectDensityReachable((l, NL(l)), (˜l, NL(˜l)), LN , LC, , minPts) then ddrLeaders := ddrLeaders ∪ {(˜l, NL(˜l))}; else if ˜l.type = 0 ∧ |NL(˜l)| > 1 then
LN := LN \ (˜l, NL(˜l)); for all o ∈ NL(˜l) do leaderFound := false; for all (l˜2, NL(l˜2)) ∈ LN do if l˜2.type 6= 0 ∧ d(o, l˜2) ≤ then
NL(l˜2) := NL(l˜2) ∪ {o}; leaderFound := true; if (l˜2, NL(l˜2)) ∈/ candidates ∧ (l˜2, NL(l˜2)) ∈/ ddrLeaders ∧ d(l, l˜2) ≤ 3 then
candidates := candidates ∪ {(l˜2, NL(l˜2))}; break; if leaderFound = false then if d(l, o) ≤ 3 then
candidates := candidates ∪ {(o, {o})}; LN := LN ∪ {(o, {o})}; if o.type 6= 0 then for all (l˜2, NL(l˜2)) ∈ LN do if l˜2.type = 0 ∧ d(o, l˜2) ≤ then
NL(o) := NL(o) ∪ {l˜2};
LN := LN \ {(l˜2, NL(l˜2))} 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: return ddrLeaders; reichbare Umgebungen gefunden werden sollen. Die Menge candidates wird nun schrittweise abgearbeitet. Ist die aktuelle Leader-Umgebung (˜l, N L(˜l)) direkt dichte-erreichbar von (l, N L(l)), so wird sie zu der Ergebnismenge ddrLeaders hinzugefu¨gt (Z. 6–7). Ansonsten werden, falls ˜l.type 6= 0 und |N L(˜l)| > 1 gilt, die Objekte neuverteilt (Z. 8–27). Wird eine neue Umgebung erzeugt oder eine bestehende erweitert, muss sie ggf. in candidates eingefu¨gt werden, da sie nun doch direkt dichte-erreichbar sein kann (Z. 16–17 und 20–21).
Die Rauscherkennung erfolgt in Alg. 5 in den Z. 17–21. An dieser Stelle kann sichergestellt werden, dass es sich bei der Leader-Umgebung (l, N L(l)) um Rauschen handelt. Da (l, N L(l)) ∈ LN ist, geho¨rt (l, N L(l)) zu keinem der bisherigen Cluster. Zusa¨tzlich gilt, aufgrund der absteigenden Bearbeitung der Umgebungen aus LN bzgl. deren Ma¨chtigkeiten (Z. 5 aus Alg. 4), der initialen Partitionierung und der Art der Neuverteilung von Objekten, fu¨r alle weiteren LeaderUmgebungen (l2, N L(l2)) ∈ LN : |N L(l2)| = 1 ∧ (d(l, l2) > ∨ l2.type = 0). Somit geho¨rt (l, N L(l)) zum Rauschen.
Die Umsetzungen von isCoreObject und isDirectDensityReachable soll anschließend kurz erkla¨rt werden. In isCoreObject wird fu¨r das u¨bergebene Objekt o u¨ber die Umgebungen LN ∪LC iteriert und geza¨hlt (Variable counter ), fu¨r wie viele Objekte oˆ aus den Umgebungen d(o, oˆ) ≤ gilt. Dabei werden Umgebungen mittels Lemma 3 von der Suche ausgeschlossen. Ist o ein Leader einer Leader-Umgebung, so wird counter um |N L(o)| erho¨ht, ohne eine Distanz zu berechnen. Sollte counter ≥ minPts sein, so wird fru¨hzeitig abgebrochen. Wurde isCoreObject schon einmal mit o aufgerufen, so werden keine Distanzen berechnet und das Ergebnis anhand von o.type ermittelt. isDirectDensityReachable wird durch zwei verschachtelte Schleithree ring clusters
gaussian mixture clusters 2 0 fen u¨ber die Leader-Umgebungen (l, N L(l)) und (l2, N L(l2)) realisiert, wenn Fall 1 von Lemma 2 anwendbar ist. Ein Objekt o ∈ N L(l) kann als eines der verbindenden Kernobjekte p, q (siehe Lemma 2 Fall 1) ausgeschlossen werden, wenn Lemma 3 fu¨r die Distanz d(o, l2) gilt. Fu¨r den Fall 2 aus Lemma 2, also |N L(l2)| = 1, wird fu¨r l2 nur u¨ber die Objekte N L(l) iteriert, wenn Lemma 3 fu¨r d(l, l2) nicht erfu¨llt ist, um ein Kernobjekt q ∈ N L(l) zu finden mit d(q, l2) ≤ . Vorher muss mittels isCoreObject u¨berpru¨ft werden, ob l2 ein Kernobjekt ist, um den entsprechenden Fall zu wa¨hlen.
Aufgrund des Umfangs eines vollsta¨ndigen Beweises der Exaktheit von FM-DBSCAN soll hier nur die Idee des Beweises erfolgen. Hierbei wird vorausgesetzt, dass computeLeaderPartition, isDirectDensityReachable und isCoreObject korrekt sind. Da im Alg. 6 in candidates immer die Leader-Umgebungen gehalten oder aufgrund der Neuverteilung eingefu¨gt werden (Z. 1, 16–17 und 20–21), die potentiell direkt dichte-erreichbar sein ko¨nnen (Lemma 4), werden alle direkt dichte-erreichbaren Umgebungen gefunden. Wie in Abschnitt 4.1 erla¨utert, folgt daraus, dass alle dichte-erreichbaren Objekte des Leaders der Startumgebung gefunden werden. Somit wird in Alg. 5 (Z. 1–15) ein vollsta¨ndiger Cluster erzeugt (Lemma 1). Aufgrund der Neuverteilung in Alg. 5 (Z. 22–36) und 6 (Z. 8–27) wird nach endlich viele Schritten fu¨r jeden Cluster mindestens eine Leader-Umgebung in LN existieren, deren Leader ein Kernobjekt ist und zu dem entsprechenden Cluster geho¨rt. Von diesen Umgebungen wird in Alg. 5 (Z. 4–7) ein Cluster erzeugt, sodass wir alle Cluster finden. Die korrekte Erkennung von Rauschen wurde weiter oben erla¨utert. Somit berechnet FM-DBSCAN dasselbe Ergebnis wie DBSCAN.
In diesem Abschnitt wird FM-DBSCAN mit DBSCAN verglichen. Beide Algorithmen wurden in C++11 implementiert. Sa¨mtliche Experimente liefen auf einem PC mit einem Intel R CoreTM i7-2600K Prozessor, 16 GB RAM und Debian 8. Zur Evaluation wurden zwei synthetische Datenverteilungen herangezogen. Die beiden Datenverteilungen three ring clusters (2-dimensional) und gaussian mixture clusters (3-dimensional) sind fu¨r eine Kollektionsgro¨ße von 1000 Objekten in Abb. 3 dargestellt. Die euklidische Distanz diente als Distanzfunktion zum Vergleich der Objekte. Sa¨mtliche Daten wurden im Hauptspeicher gehalten.
Im ersten Experiment wurde der Einfluss der Kollektionsgro¨ße auf die Effizienz, gemessen anhand der Anzahl der Distanzberechnungen und der Zeit, evaluiert. Hierfu¨r wurden mittels RapidMiner (https://rapidminer.com/) Datenkollektionen in den Gro¨ßen n = 10.000, 20.000, . . . , 100.000 fu¨r beide Datenverteilungen generiert. U¨ ber alle n wurden (a) three ring clusters (minPts = 5, inM101 t ieZ 100 FM-DBSCAN (b) gaussian mixture clusters (minPts = 5, = 0, 2) Abb. 4: Clustering-Performanz fu¨r variierendes n Abb. 5: Clustering-Performanz fu¨r variierendes die selben Werte fu¨r und minPts verwendet. Dabei wurden die Werte fu¨r und minPts so festgelegt, dass die in Abb. 3 dargestellten Cluster gefunden wurden. Das Experiment wurde fu¨r jedes n zehnmal durchgefu¨hrt und anschließend die Werte gemittelt. Die Ergebnisse sind in Abb. 4 zu sehen.
Auf beiden Verteilungen konnte im Vergleich zu DBSCAN eine erhebliche Anzahl an Distanzberechnungen eingespart und die Rechenzeit drastisch reduziert werden. Fu¨r three ring clusters berechnet FM-DBSCAN um einen Faktor 727 bis 3956 weniger Distanzberechnungen als DBSCAN, wodurch FM-DBSCAN um einen Faktor 999 bis 3418 weniger Zeit beno¨tigt. Bei gaussian mixture clusters sind die Einsparungen noch deutlich ho¨her. Dort kann ein Faktor 2664 bis 23.075 an Distanzberechnungen eingespart und die Rechenzeit um einen Faktor 1128 bis 17.404 reduziert werden.
Als zweites wurde der Einfluss des Parameters auf die Effizienz von FM-DBSCAN evaluiert. Auch hier wurde das Experiment zehnmal ausgefu¨hrt und die Werte anschließend gemittelt. Die Ergebnisse sind in der Abb. 5 zu finden.
Fu¨r three ring clusters ist fu¨r wachsendes eine fallende Tendenz sowohl fu¨r die Anzahl der Distanzberechnungen, als auch fu¨r die Zeit ersichtlich. Lediglich im Bereich 0, 4 bis 0, 5 ist ein Steigen zu erkennen. Dies liegt daran, dass sich die Umgebungen zweier Leader aus unterschiedlichen Clustern immer mehr in einem großen leeren Bereich u¨berschneiden und somit die Lemmata 3 und 4 nicht mehr effektiv angewendet werden ko¨nnen. Vereinigen sich diese Cluster aufgrund des gro¨ßeren , fallen die Werte wieder. Das gleiche Verhalten tritt auch bei gaussian mixture clusters auf, nur o¨fter, da es dort mehr Cluster gibt.
In dieser Arbeit wurde der Clustering-Algorithmus FMDBSCAN vorgestellt, der fu¨r beliebige Distanzfunktionen dasselbe Ergebnis wie DBSCAN liefert. Dabei nutzt FMDBSCAN das Prinzip der Leader-Umgebungen, um die Objekte zusammenzufassen, sodass anschließend auf den Umgebungen ein Clustering durchgefu¨hrt werden kann. Erste Experimente zeigen, dass FM-DBSCAN um ein Vielfaches schneller als DBSCAN ist (Faktor > 990), wodurch FM-DBSCAN fu¨r große Datenkollektionen vorteilhaft wird.
In zuku¨nftigen Arbeiten sollen weitere Datenkollektionen (synthetisch und real) evaluiert werden, um die Effizienz von FM-DBSCAN zu besta¨tigen. Außerdem soll untersucht werden, wie und minPts zu wa¨hlen sind, sodass zum einen eine gute Qualita¨t (Clustering-Ergebnis) und zum anderen eine hohe Effizienz erzielt wird. Die durchgefu¨hrten Experimente zu geben hierfu¨r erste Aufschlu¨sse. Ebenfalls sollen neue Partitionierungsalgorithmen untersucht werden, um die Partitionierung noch weiter zu beschleunigen.