FM-DBSCAN: Ein effizienter, dichte-basierter Clustering-Algorithmus Philipp Egert Brandenburgische Technische Universität Cottbus–Senftenberg Institut für Informatik, Informations- und Medientechnik Fachgebiet Datenbank- und Informationssysteme 03013 Cottbus, Deutschland Philipp.Egert@b-tu.de ABSTRACT den Cluster nicht vorgegeben werden muss, ist DBSCAN DBSCAN ist ein dichte-basierter Clustering-Algorithmus, für viele Einsatzgebiete attraktiv. Ein großer Nachteil von der Cluster beliebiger Form auffindet und diese von Rau- DBSCAN ist allerdings seine Laufzeit von O(n2 ), wobei n schen trennt. Aufgrund des quadratischen Aufwands ist DB- die Größe der Datenkollektion ist. Dies macht DBSCAN SCAN für große Datenmengen jedoch oft ungeeignet. In die- für große Datenkollektionen nicht praktikabel. Um den Auf- ser Arbeit wird deshalb ein effizienterer Algorithmus namens wand zu reduzieren, wurden verschiedene Ansätze entwickelt FM-DBSCAN vorgestellt, der für eine beliebige Distanz- [2, 3, 4, 5, 6]. Die bisherigen Verfahren sind jedoch entwe- funktion (Metrik) dasselbe Ergebnis wie DBSCAN liefert. der nur approximativ [2, 4, 6] oder nur für den euklidischen Hierfür partitioniert FM-DBSCAN die Datenkollektion in Raum Rd ausgelegt [2, 3, 5]. Für allgemeine Distanzfunk- Leader-Umgebungen, auf denen anschließend das Clustering tionen existiert bisher kein exakter Ansatz. Als wesentlicher durchgeführt wird. Erste Experimente mittels synthetischen Beitrag dieser Arbeit wird daher ein exakter und effizienter Datenkollektionen zeigen, dass FM-DBSCAN um einen Fak- Algorithmus mit dem Namen Fast Metric DBSCAN vorge- tor > 990 schneller als DBSCAN ist und auch wesentlich stellt, der für beliebige Distanzfunktionen einsetzbar ist. besser mit der Kollektionsgröße skaliert. Die Arbeit ist wie folgt gegliedert: In Abschnitt 2 wird DB- SCAN vorgestellt. Danach wird in Abschnitt 3 der Stand der Technik beleuchtet. FM-DBSCAN wird in Abschnitt 4 ein- Kategorien und Themenbeschreibungen geführt. Die experimentelle Evaluierung von FM-DBSCAN I.5.3 [PATTERN RECOGNITION]: Clustering—Algo- im Vergleich zu DBSCAN erfolgt in Abschnitt 5. In Ab- rithms schnitt 6 werden die Zusammenfassung der Arbeit und ein Ausblick über zukünftige Forschungsvorhaben gegeben. Schlüsselwörter Density-based Clustering, DBSCAN, Leaders 2. DBSCAN In dem folgenden Abschnitt wird der von Ester et al. ent- wickelte, dichte-basierte Clustering-Algorithmus DBSCAN 1. EINLEITUNG eingeführt [1]. Hierzu werden in Abschnitt 2.1 die wesentli- Clustering ist ein wichtiges Teilgebiet des Data Mining, chen Definitionen und Lemmata von Ester et al. zusammen- welches bspw. für die Segmentierung von Kunden oder der gefasst. Auf DBSCAN wird im Abschnitt 2.2 eingegangen. Strukturierung von Textdokumenten eingesetzt wird. Ziel des Clustering ist es, Objekte so in Gruppen (Cluster) ein- 2.1 Definitionen und Lemmata zuteilen, dass Objekte eines Cluster einander möglichst ähn- Im Nachfolgenden sei O eine endliche Menge von Objek- lich und Objekte verschiedener Cluster einander möglichst ten, mit |O| = n. Des Weiteren sei d eine Distanzfunktion unähnlich sind. Die Gruppe der dichte-basierten Clustering- (Metrik) auf der Menge X und O ⊆ X. minPts ∈ N≥0 und Algorithmen lösen dieses Problem, indem sie dichte Regio-  ∈ R≥0 sind die beiden Parameter von DBSCAN. Alle fol- nen von Regionen mit geringer Dichte trennen. DBSCAN genden Definitionen und Lemmata sind immer abhängig von (Density-Based Spatial Clustering of Applications with Noi-  und minPts. se) ist ein dichte-basierter Clustering-Algorithmus mit dem es möglich ist, Cluster beliebiger Form zu erkennen [1]. Auf- Definition 1. Ein Objekt o ∈ O heißt Kernobjekt, wenn grund dieser Eigenschaft und, dass die Anzahl der zu suchen- |N (o)| ≥ minPts ist, mit N (o) = {ô ∈ O | d(o, ô) ≤ }.  und minPts spezifizieren hierbei einen minimalen Dich- tegrenzwert, der festlegt, ob ein Objekt ein Kernobjekt ist. Alle Objekte, welche keine Kernobjekte sind, werden Nicht- Kernobjekte genannt. Definition 2. Ein Objekt p ∈ O ist direkt dichte-erreich- bar von q ∈ O, wenn q ein Kernobjekt und p ∈ N (q) ist. 28th GI-Workshop on Foundations of Databases (Grundlagen von Daten- banken), 24.05.2016 - 27.05.2016, Nörten-Hardenberg, Germany. Nach Definition 2 sind alle Objekte der -Umgebung eines Copyright is held by the author/owner(s). Kernobjektes q direkt dichte-erreichbar von q. Um die Er- 44 FM-DBSCAN: Ein effizienter, dichte-basierter Clustering-Algorithmus ein Wert größer 0 spezifiziert die zugehörige Clusternum- mer. Initial ist für alle Objekte clId auf −1 (nicht klassifi- ziert) 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 -Umge- bung von o berechnet (Z. 1) und überprü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 Abb. 1: Dichte-Erreichbarkeit für minPts = 5 von o aus abgebrochen (Z. 2–4). Es sei angemerkt, dass o später noch einem Cluster zugewiesen werden kann, wenn es in der -Umgebung eines Kernobjekts liegt. Andernfalls reichbarkeit über die Grenzen der -Umgebung eines Ker- ist o ein Kernobjekt und es kann laut Lemma 1 ein neuer nobjektes hinauszuführen, wird der Begriff der Dichte-Er- Cluster mit der Nummer clusterId konstruiert werden. Hier- reichbarkeit eingeführt. zu werden die direkt dichte-erreichbaren Objekte von o, also N (o), dem Cluster hinzugefügt (Z. 6). Anschließend werden Definition 3. Ein Objekt p ∈ O ist dichte-erreichbar von für alle Objekte aus N (o) deren direkt dichte-erreichbaren einem Objekt q ∈ O, wenn es eine Folge von Objekten Objekte ermittelt und dem Cluster zugewiesen. Die Schrit- p1 , . . . , pm ∈ O gibt, sodass p1 = q, pm = p und pi+1 di- te werden solange wiederholt, bis keine neuen Objekte des rekt dichte-erreichbar von pi ist, für 1 ≤ i < m. Clusters mehr gefunden werden können (Z. 8–14). expand- Seeds fügt dabei nur die Objekte aus N (o) \ {o} für das Wie man leicht sieht, bildet die Dichte-Erreichbarkeit den aktuelle Kernobjekt o in die temporäre Menge seeds ein, für transitiven Abschluss über der Relation der direkten Dichte- die clId = −1 ist. setClusterId markiert die Objekte aus Erreichbarkeit. Die Veranschaulichung der Dichte-Erreich- N (o) mit der Nummer clusterId , für die clId < 1 gilt. Die barkeit ist in Abb. 1 zu sehen. Mittels der Dichte-Erreich- Laufzeit von Alg. 1 beträgt O(n2 ). barkeit kann man einen Cluster wie folgt konstruieren [1]. 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. 3. STAND DER TECHNIK Zur Beschleunigung von DBSCAN existieren bereits meh- Aus Lemma 1 folgt, dass ein Cluster C vollständig berech- rere Ansätze, welche sich in exakte (liefern dasselbe Ergebnis net werden kann, indem man ausgehend von einem belie- wie DBSCAN) und approximative Verfahren (garantieren bigen Kernobjekt p ∈ C, alle dichte-erreichbaren Objekte kein exaktes Ergebnis) unterteilen lassen. Exakte Verfahren von p ermittelt. Alle Objekte, die zu keinem solchen Cluster sind in den Arbeiten [2, 3, 5] und approximative Verfahren gehören, werden als Rauschen bezeichnet. in den Arbeiten [2, 4, 6] zu finden. GriDBSCAN ist ein exaktes Verfahren für den euklidi- 2.2 Algorithmus schen Raum Rd [5]. Dabei zerlegt GriDBSCAN den Daten- Ziel von DBSCAN ist es nun, alle solche Cluster zu finden. raum mittels eines Gitters und führt auf den einzelnen Git- Die Erkenntnis aus Lemma 1 fließt dabei in den Alg. 1 ein. terzellen DBSCAN aus, um anschließend deren Ergebnisse in einer Mischphase zusammenzuführen. Alg. 1 DBSCAN(O, , minPts) Ein exaktes Verfahren, welches ebenfalls auf einem Da- 1: clusterId := 1; tengitter basiert, wurde von Gunawan vorgestellt [3]. Zwar 2: for all o ∈ O do ist der Algorithmus nur für den R2 ausgelegt, jedoch konnte 3: if o.clId = −1 then dafür eine Laufzeit von O(n log n) gezeigt werden. 4: if expandCluster(O, o, clusterId, , minPts) then 5: clusterId := clusterId + 1; Die Erweiterung des Verfahrens von Gunawan auf höhere Dimensionen d wurde von Gan und Tao gezeigt [2]. Für d ≥ 2− 2 +δ 4 konnte eine Laufzeit von O(n dd/2e+1 ) nachgewiesen werden, für eine beliebig kleine Konstante δ > 0. Für d = 3 Alg. 2 expandCluster(O, o, clusterId, , minPts) 4 kann die Laufzeit auf O((n log n) 3 ) verbessert werden. 1: neighborhood := N (o); 2: if |neighborhood| < minPts then Gan und Tao stellen ebenfalls noch das ρ-approximative 3: o.clId := 0; DBSCAN für den Rd vor, mit einer Laufzeit von O(n) [2]. 4: return false; ρ > 0 ist eine beliebig kleine Konstante, welche die Quali- 5: seeds := ∅; tät des Ergebnisses beeinflusst. Kleinere Werte für ρ liefern 6: setClusterId(neighborhood, clusterId); 7: expandSeeds(neighborhood, o, clusterId, seeds); bessere Ergebnis als große, benötigen aber mehr Rechenzeit. 8: while seeds 6= ∅ do Rough-DBSCAN ist ein approximatives Verfahren, das 9: Wähle Objekt ô aus der Menge seeds aus; wie FM-DBSCAN auf dem Prinzip der Leader-Umgebun- 10: seeds := seeds \ {ô}; 11: neighborhood := N (ô); gen basiert [6]. Rough-DBSCAN führt auf der Menge der 12: if |neighborhood| ≥ minPts then Leader DBSCAN aus, um die Objekte zu clustern und so- 13: setClusterId(neighborhood, clusterId); mit den Aufwand zu reduzieren. Hierfür wird DBSCAN nur 14: expandSeeds(neighborhood, ô, clusterId, seeds); geringfügig geändert. Um die Größe der -Umgebung eines 15: return true; Leaders zu bestimmen, wird eine leicht zu berechnende Ab- schätzungsformel auf Basis der Leader-Umgebungen verwen- In DBSCAN (Alg. 1) erhält jedes Objekt o ∈ O ein At- det. Rough-DBSCAN ist für beliebige Metriken anwendbar. tribut clId , welches angibt zu welchem Cluster es gehört. Eine Laufzeit von O(n) wurde jedoch nur für den Rd gezeigt. Der Wert 0 bedeutet, das Objekt gehört zum Rauschen und Das approximative Verfahren FDBSCAN für den Rd hat 45 FM-DBSCAN: Ein effizienter, dichte-basierter Clustering-Algorithmus lq )) in O, wenn es eine Folge von Objekten p1 , . . . , pm ∈ NL (lp ) ∪ NL (lq ) gibt, sodass p1 = lq , pm = lp ist und es gilt: 1. pi+1 ist direkt dichte-erreichbar von pi für 1 ≤ i < m, 2. lp ist ein Kernobjekt in O oder |NL (lp )| = 1. Definition 7. Eine Leader-Umgebung (lp , NL (lp )) ist dich- te-erreichbar von einer Leader-Umgebung (lq , NL (lq )) in O, Abb. 2: Beispiel für eine Leader-Partition wenn es eine Folge von Leader-Umgebungen (l1 , NL (l1 )), . . . , (lm , NL (lm )) in O gibt, sodass (l1 , NL (l1 )) = (lq , NL (lq ) ), (lm , NL (lm )) = (lp , NL (lp )) und (li+1 , NL (li+1 )) direkt dichte-erreichbar von (li , NL (li )) in O ist, für 1 ≤ i < m. einen, im Vergleich zu DBSCAN, veränderten Ablauf [4]. Nach dem Auffinden eines Kernobjektes wird nicht in dessen In der Definition 6 Punkt 2 wurde explizit gefordert, dass -Umgebung nach weiteren Kernobjekten gesucht, sondern lp ein Kernobjekt oder |NL (lp )| = 1 ist. Dadurch wird er- außerhalb. Hierfür sind die Objekte nach einer ausgewählten reicht, dass für eine Umgebung (lp , NL (lp )), die von einer Dimension sortiert, sodass mit dem nächsten Objekt in der Umgebung (lq , NL (lq )) direkt dichte-erreichbar ist, gilt, dass Sortierung, welches nicht in der -Umgebung war und noch alle Objekte o ∈ NL (lq ) ∪ NL (lp ) dichte-erreichbar von lq keinem Cluster zugewiesen wurde, fortgesetzt wird. Cluster sind. Dies wäre für eine Umgebung (lp , NL (lp )), mit lp ist werden bei Überschneidungen ggf. zusammengefasst. ein Nicht-Kernobjekt und |NL (lp )| > 1, nicht der Fall. Im Gegensatz zu den hier aufgeführten Verfahren, die ent- Im Anschluss werden noch drei Lemmata vorgestellt, die weder approximativ oder nur für den Rd exakt sind, liefert es dem Alg. 4 aus Abschnitt 4.3 ermöglichen, erheblichen FM-DBSCAN für beliebige Distanzfunktionen ein exaktes Berechnungsaufwand einzusparen. Ergebnis und stellt somit einen universelleren Ansatz dar. Lemma 2. Seien (lp , NL (lp )) und (lq , NL (lq )) zwei Lea- 4. FM-DBSCAN der-Umgebungen und (lp , NL (lp )) ist direkt dichte-erreich- In diesem Abschnitt wird der Clustering-Algorithmus Fast bar von (lq , NL (lq )) in O, dann gelten folgende Aussagen: Metric DBSCAN präsentiert. FM-DBSCAN besteht aus zwei 1. Ist lp ein Kernobjekt, dann existieren zwei Kernobjek- Phasen. In der ersten Phase werden die Objekte mittels des te p ∈ NL (lp ) und q ∈ NL (lq ) mit d(p, q) ≤ . Algorithmus Counted-Leaders [6] zu Leader-Umgebun- gen aggregiert, die zusammen eine Leader-Partition bilden. 2. Ist |NL (lp )| = 1, dann existiert ein Kernobjekt q ∈ Anhand dieser Leader-Partition und unter Ausnutzung der NL (lq ) in O mit d(lp , q) ≤ . Dreiecksungleichung, kann in der zweiten Phase ein effizi- entes Clustering, ähnlich dem von DBSCAN, durchgeführt Lemma 3. Seien p, q zwei Objekte in O. Ist d(p, q) > 2, werden. Hierzu werden in Abschnitt 4.1 die Definitionen und so gilt für alle o ∈ N (p) : d(o, q) > . Lemmata eingeführt, die für FM-DBSCAN benötigt werden. Lemma 4. Seien p, q zwei Objekte in O. Ist d(p, q) > 3, Die Berechnung der Leader-Partition und das anschließende so gilt für alle o1 ∈ N (p) und o2 ∈ N (q) : d(o1 , o2 ) > . Clustering erfolgt in den Abschnitten 4.2 und 4.3. 4.1 Definitionen und Lemmata Lemma 2 beschreibt eine effiziente Möglichkeit, um zu tes- ten, ob eine Leader-Umgebung (lp , NL (lp )) von einer Lea- Seien O, d, minPts und  gegeben wie in Abschnitt 2.1. der-Umgebung (lq , NL (lq )) direkt dichte-erreichbar ist. Hier- Im Folgenden sind die Definitionen und Lemmata immer für müssen wir im ersten Fall nur nachweisen, dass lq und abhängig von  und minPts. lp Kernobjekte sind und dass zwei Kernobjekte p ∈ NL (lp ) Definition 4. Ein Tupel (l, NL (l)) ist eine Leader-Umge- und q ∈ NL (lq ) existieren mit d(p, q) ≤ . Der Test auf bung in O, wenn NL (l) ⊆ N (l) und l ∈ NL (l) ist. l ist der d(p, q) ≤  kann dabei mit Lemma 3 beschleunigt werden. Repräsentant der Menge NL (l) und wird Leader genannt. Für den zweiten Fall reicht es sogar aus, nachzuweisen, dass lq ein Kernobjekt ist und das ein Kernobjekt q ∈ NL (lq ) Die Leader-Umgebung mit dem Leader l ist also ein Aus- existiert mit d(q, lp ) ≤ . Um die Anzahl dieser Tests so ge- schnitt der -Umgebung von l. Mittels der Leader-Umgebun- ring wie möglich zu halten, verwenden wir die Lemmata 3 gen soll nun die Menge der Objekte O partitioniert werden. und 4. Hierzu muss lediglich die Distanz d(lp , lq ) berechnet werden, um zu entscheiden, ob für zwei Objekte p ∈ NL (lp ) Definition 5. Eine Leader-Partition von O ist eine Men- und q ∈ NL (lq ) die Distanz d(p, q) ≤  sein kann. Sollte das ge von Leader-Umgebungen L = {(l1 , NL (l1 )), . . . , (lm , nicht der Fall sein, so ist keine der Leader-Umgebungen von- NL (lS L L m ))}, mit d(li , lj ) >  ∧ N (li ) ∩ N (lj ) = ∅ für i 6= j einander direkt dichte-erreichbar. Auf die Beweise der Lem- und m N L  (l i ) = O. i=1 mata wird aufgrund des eingeschränkten Platzes verzichtet. Ein Beispiel für eine Leader-Partition, die auch der Alg. Im Wesentlichen basieren sie auf der von d erfüllten Drei- 3 aus Abschnitt 4.2 berechnet, ist in Abb. 2 dargestellt. Im ecksungleichung, der direkten Dichte-Erreichbarkeit und der Anschluss sollen die Begriffe der direkten Dichte-Erreichbar- Dichte-Erreichbarkeit von Objekten. keit und der Dichte-Erreichbarkeit auf Leader-Umgebungen übertragen werden. 4.2 Berechnung der Leader-Partition Um eine Leader-Partition zu berechnen, nutzen wir ei- Definition 6. Eine Leader-Umgebung (lp , NL (lp )) ist di- ne angepasste Variante des Algorithmus Counted-Leaders rekt dichte-erreichbar von einer Leader-Umgebung (lq , NL ( (Alg. 3) von Viswanath und Suresh Babu [6]. 46 FM-DBSCAN: Ein effizienter, dichte-basierter Clustering-Algorithmus Alg. 3 computeLeaderPartition(O, ) Alg. 5 expandCluster((l, NL (l)), LN , LC , clusterId, , minPts) 1: leaderPartition := ∅; 1: if isCoreObject(l, LN , LC , , minPts) then 2: for all o ∈ O do 2: setClusterId(NL (l), clusterId); 3: leaderFound := false; 3: LN := LN \ {(l, NL (l))}; 4: for all (l, NL (l)) ∈ leaderPartition do 5: if d(o, l) ≤  then 4: LC := LC ∪ {(l, NL (l))}; 5: seeds := ∅; 6: NL (l) := NL (l) ∪ {o}; 6: ddrLeaders := findDirectDensityReachableLeaders( 7: leaderFound := true; 8: break; (l, NL (l)), LN , LC , , minPts); 7: setClusterId(ddrLeaders, clusterId); 9: if leaderFound = false then 8: expandSeeds(ddrLeaders, LN , LC , clusterId, seeds); 10: leaderPartition := leaderPartition ∪ {(o, {o})}; 9: while seeds 6= ∅ do 11: return leaderPartition; 10: (l̃, NL (l̃)) = arg max |NL (l˜2 )|; L (l˜ ))∈seeds (l˜2 ,N 2 11: seeds := seeds \ {(l̃, NL (l̃))}; 12: ddrLeaders := Die Leader-Partition (leader Partition) wird schrittweise findDirectDensityReachableLeaders((l̃, NL (l̃)), LN , LC , , minPts); aufgebaut. Hierzu wird jedes Objekte o ∈ O der ersten Lea- 13: setClusterId(ddrLeaders, clusterId); der-Umgebung (l, NL (l)) ∈ leaderPartition zugewiesen, für 14: expandSeeds(ddrLeaders, LN , LC , clusterId, seeds); die d(o, l) ≤  gilt (Z. 4–8). Existiert keine solche Leader- 15: return true; Umgebung, so wird (o, {o}) als neue Leader-Umgebung zu 16: else 17: if |NL (l)| = 1 then leaderPartition hinzugefügt (Z. 9–10). Die Reihenfolge, in 18: setClusterId(NL (l), 0); der über leader Partition iteriert wird (Z. 4), ist durch die 19: LN := LN \ {(l, NL (l))}; Einfügereihenfolge der Leader-Umgebungen festgelegt. 20: LC := LC ∪ {(l, NL (l))}; 21: return false; 4.3 Clustering anhand der Leader-Partition 22: LN := LN \ {(l, NL (l))}; 23: for all o ∈ NL (l) do In diesem Abschnitt wird beschrieben, wie anhand einer 24: leaderFound := false; Leader-Partition die Menge der Objekte O effizient in Clus- 25: for all (l̃, NL (l̃)) ∈ LN do ter unterteilt werden kann. Die Grundidee ist dabei analog 26: if l̃.type 6= 0 ∧ d(o, l̃) ≤  then zu DBSCAN. Ausgehend von einer Leader-Umgebung, deren 27: NL (l̃) := NL (l̃) ∪ {o}; 28: leaderFound := true; Leader ein Kernobjekt ist, werden alle dichte-erreichbaren 29: break; Leader-Umgebungen ermittelt. Diese bilden dann zusammen 30: if leaderFound = false then einen Cluster. Probleme bereiten dabei jedoch Leader-Um- 31: LN := LN ∪ {(o, {o})}; gebungen (l, NL (l)), bei denen l ein Nicht-Kernobjekt und 32: if o.type 6= 0 then 33: for all (l̃, NL (l̃)) ∈ LN do |NL (l)| > 1 ist. Von diesen Umgebungen aus kann kein Clus- 34: if l̃.type = 0 ∧ d(o, l̃) ≤  then ter konstruiert werden. Dies ist besonders problematisch, 35: NL (o) := NL (o) ∪ {l̃}; wenn in der Leader-Partition nur solche Umgebungen auf- 36: LN := LN \ {(l̃, NL (l̃))} treten. Außerdem sind diese Umgebungen laut Definition 37: return false; 6 nicht direkt dichte-erreichbar von anderen Umgebungen, wodurch Objekte eines Clusters verloren gehen könnten. Die Lösung dieses Problems besteht darin, jedes Mal, wenn auf Wie bei DBSCAN hat jedes Objekt das Attribut clId (in- so eine Umgebung getroffen wird, deren Objekte auf noch tial −1). Zusätzlich bekommt jedes Objekt ein Attribut type, nicht geclusterte Umgebungen zu verteilen, deren Leader was angibt, ob es sich bei dem Objekt um ein Kernobjekt nicht als Nicht-Kernobjekt markiert wurden. Existiert für (type = 1) oder ein Nicht-Kernobjekt (type = 0) handelt. In- eines der Objekte eine solche Umgebung nicht, so wird eine itial ist type = −1 (undefiniert) für alle Objekte o ∈ O. Die neue Umgebung mit dem Objekt als Leader erzeugt. Ist der Menge LC enthält alle geclusterten und als Rauschen mar- neue Leader l1 noch nicht als Nicht-Kernobjekt markiert, so kierten Leader-Umgebung. LN hingegen enthält alle nicht werden ihm alle als Nicht-Kernobjekte markierten Leader geclusterten Umgebungen (clId = −1). FM-DBSCAN läuft l2 , die noch nicht geclustert wurden und für die d(l1 , l2 ) ≤  solange, bis LN leer ist (Z. 4), also alle Umgebungen geclus- gilt, zugeordnet. Dadurch erreicht man, in mehreren Ausfüh- tert wurden. Das iterative Einsammeln von dichte-erreich- rungen der Neuverteilung, dass alle Objekte entweder einer baren Leader-Umgebungen ist in den Z. 1–15 von expand- Umgebung zugeordnet sind, deren Leader ein Kernobjekt Cluster (Alg. 5) beschrieben. Dabei weist setClusterId ist, oder dass Leader-Umgebungen (l, NL (l)) entstehen, mit der übergebenen Menge von Objekten die übergebene Clus- |NL (l)| = 1. Hierdurch wird die direkte Dichte-Erreichbar- ternummer zu. expandSeeds fügt der temporären Menge keit wieder anwendbar. Die entsprechende Umsetzung dieses seeds lediglich die direkt dichte-erreichbaren Umgebungen Ansatzes ist in Alg. 4 dargestellt. hinzu, deren Leader ein Kernobjekt ist. Sollte die Startum- gebung in Alg. 5 ein Nicht-Kernobjekt sein, so erfolgt die Alg. 4 FM-DBSCAN(O, , minPts) angesprochene Neuverteilung der Objekte (Z. 22–36). 1: LN := computeLeaderPartition(O, ); findDirectDensityReachableLeaders (Alg. 6) ermit- 2: LC := ∅; telt für die übergebene Leader-Umgebung (l, NL (l)) alle di- 3: clusterId := 1; rekt dichte-erreichbaren Leader-Umgebungen, indem mit ei- 4: while LN 6= ∅ do 5: (l, NL (l)) = arg max |NL (l̃)|; ner Kandidatenmenge (candidates) (Z. 1) gearbeitet wird. L (l̃))∈L (l̃,N N candidates wird mit den Leader-Umgebungen aus LN in- 6: if expandCluster((l, NL (l)), LN , LC , clusterId, , minPts itialisiert, deren Leader eine Distanz kleiner gleich 3 zu l ) then aufweisen (Lemma 4). Die Beschränkung auf Umgebungen 7: clusterId := clusterId + 1; aus LN ist korrekt, da nur nicht geclusterte, direkt dichte-er- 47 FM-DBSCAN: Ein effizienter, dichte-basierter Clustering-Algorithmus Alg. 6 findDirectDensityReachableLeaders( three ring clusters gaussian mixture clusters (l, NL (l)), LN , LC , , minPts) 2 1: candidates := N3 ((l, NL (l)), LN ); 2: ddrLeaders := ∅; 2 3: while candidates 6= ∅ do 0 4: (l̃, NL (l̃)) = arg max |NL (l˜2 )|; L (l˜ ))∈candidates (l˜2 ,N 0 2 5: candidates := candidates \ {(l̃, NL (l̃))}; −2 1 6: if isDirectDensityReachable((l, NL (l)), (l̃, NL (l̃)), LN , −1 0 0 LC , , minPts) then −2 −1 0 1 2 1 −1 7: ddrLeaders := ddrLeaders ∪ {(l̃, NL (l̃))}; 8: else if l̃.type = 0 ∧ |NL (l̃)| > 1 then Abb. 3: Evaluierte Datenverteilungen 9: LN := LN \ (l̃, NL (l̃)); 10: for all o ∈ NL (l̃) do 11: leaderFound := false; 12: for all (l˜2 , NL (l˜2 )) ∈ LN do fen über die Leader-Umgebungen (l, NL (l)) und (l2 , NL (l2 )) 13: if l˜2 .type 6= 0 ∧ d(o, l˜2 ) ≤  then realisiert, wenn Fall 1 von Lemma 2 anwendbar ist. Ein Ob- 14: NL (l˜2 ) := NL (l˜2 ) ∪ {o}; jekt o ∈ NL (l) kann als eines der verbindenden Kernobjekte 15: leaderFound := true; p, q (siehe Lemma 2 Fall 1) ausgeschlossen werden, wenn 16: if (l˜2 , NL (l˜2 )) ∈ / candidates ∧ (l˜2 , NL (l˜2 )) ∈ / ddrLeaders ∧ d(l, l˜2 ) ≤ 3 then Lemma 3 für die Distanz d(o, l2 ) gilt. Für den Fall 2 aus 17: candidates := candidates ∪ {(l˜2 , NL (l˜2 ))}; Lemma 2, also |NL (l2 )| = 1, wird für l2 nur über die Ob- 18: break; jekte NL (l) iteriert, wenn Lemma 3 für d(l, l2 ) nicht erfüllt 19: if leaderFound = false then ist, um ein Kernobjekt q ∈ NL (l) zu finden mit d(q, l2 ) ≤ . 20: if d(l, o) ≤ 3 then Vorher muss mittels isCoreObject überprüft werden, ob l2 21: candidates := candidates ∪ {(o, {o})}; ein Kernobjekt ist, um den entsprechenden Fall zu wählen. 22: LN := LN ∪ {(o, {o})}; Aufgrund des Umfangs eines vollständigen Beweises der 23: if o.type 6= 0 then 24: for all (l˜2 , NL (l˜2 )) ∈ LN do Exaktheit von FM-DBSCAN soll hier nur die Idee des Be- 25: if l˜2 .type = 0 ∧ d(o, l˜2 ) ≤  then weises erfolgen. Hierbei wird vorausgesetzt, dass compute- 26: NL (o) := NL (o) ∪ {l˜2 }; LeaderPartition, isDirectDensityReachable und is- 27: LN := LN \ {(l˜2 , NL (l˜2 ))} CoreObject korrekt sind. Da im Alg. 6 in candidates im- 28: return ddrLeaders; mer die Leader-Umgebungen gehalten oder aufgrund der Neuverteilung eingefügt werden (Z. 1, 16–17 und 20–21), die potentiell direkt dichte-erreichbar sein können (Lemma 4), werden alle direkt dichte-erreichbaren Umgebungen ge- reichbare Umgebungen gefunden werden sollen. Die Menge funden. Wie in Abschnitt 4.1 erläutert, folgt daraus, dass candidates wird nun schrittweise abgearbeitet. Ist die ak- alle dichte-erreichbaren Objekte des Leaders der Startum- tuelle Leader-Umgebung (˜ l, NL (˜ l)) direkt dichte-erreichbar gebung gefunden werden. Somit wird in Alg. 5 (Z. 1–15) L von (l, N (l)), so wird sie zu der Ergebnismenge ddrLeaders ein vollständiger Cluster erzeugt (Lemma 1). Aufgrund der hinzugefügt (Z. 6–7). Ansonsten werden, falls ˜ l.type 6= 0 und Neuverteilung in Alg. 5 (Z. 22–36) und 6 (Z. 8–27) wird |NL (˜l)| > 1 gilt, die Objekte neuverteilt (Z. 8–27). Wird ei- nach endlich viele Schritten für jeden Cluster mindestens ne neue Umgebung erzeugt oder eine bestehende erweitert, eine Leader-Umgebung in LN existieren, deren Leader ein muss sie ggf. in candidates eingefügt werden, da sie nun doch Kernobjekt ist und zu dem entsprechenden Cluster gehört. direkt dichte-erreichbar sein kann (Z. 16–17 und 20–21). Von diesen Umgebungen wird in Alg. 5 (Z. 4–7) ein Clus- Die Rauscherkennung erfolgt in Alg. 5 in den Z. 17–21. ter erzeugt, sodass wir alle Cluster finden. Die korrekte Er- An dieser Stelle kann sichergestellt werden, dass es sich bei kennung von Rauschen wurde weiter oben erläutert. Somit der Leader-Umgebung (l, NL (l)) um Rauschen handelt. Da berechnet FM-DBSCAN dasselbe Ergebnis wie DBSCAN. (l, NL (l)) ∈ LN ist, gehört (l, NL (l)) zu keinem der bisheri- gen Cluster. Zusätzlich gilt, aufgrund der absteigenden Bear- beitung der Umgebungen aus LN bzgl. deren Mächtigkeiten 5. EVALUATION (Z. 5 aus Alg. 4), der initialen Partitionierung und der Art In diesem Abschnitt wird FM-DBSCAN mit DBSCAN der Neuverteilung von Objekten, für alle weiteren Leader- verglichen. Beide Algorithmen wurden in C++11 implemen- Umgebungen (l2 , NL (l2 )) ∈ LN : |NL (l2 )| = 1 ∧ (d(l, l2 ) > tiert. Sämtliche Experimente liefen auf einem PC mit einem  ∨ l2 .type = 0). Somit gehört (l, NL (l)) zum Rauschen. Intel R CoreTM i7-2600K Prozessor, 16 GB RAM und De- Die Umsetzungen von isCoreObject und isDirectDen- bian 8. Zur Evaluation wurden zwei synthetische Datenver- sityReachable soll anschließend kurz erklärt werden. In teilungen herangezogen. Die beiden Datenverteilungen three isCoreObject wird für das übergebene Objekt o über die ring clusters (2-dimensional) und gaussian mixture clusters Umgebungen LN ∪LC iteriert und gezählt (Variable counter (3-dimensional) sind für eine Kollektionsgröße von 1000 Ob- ), für wie viele Objekte ô aus den Umgebungen d(o, ô) ≤  jekten in Abb. 3 dargestellt. Die euklidische Distanz diente gilt. Dabei werden Umgebungen mittels Lemma 3 von der als Distanzfunktion zum Vergleich der Objekte. Sämtliche Suche ausgeschlossen. Ist o ein Leader einer Leader-Umge- Daten wurden im Hauptspeicher gehalten. bung, so wird counter um |NL (o)| erhöht, ohne eine Di- Im ersten Experiment wurde der Einfluss der Kollekti- stanz zu berechnen. Sollte counter ≥ minPts sein, so wird onsgröße auf die Effizienz, gemessen anhand der Anzahl der frühzeitig abgebrochen. Wurde isCoreObject schon ein- Distanzberechnungen und der Zeit, evaluiert. Hierfür wur- mal mit o aufgerufen, so werden keine Distanzen berechnet den mittels RapidMiner (https://rapidminer.com/) Daten- und das Ergebnis anhand von o.type ermittelt. isDirect- kollektionen in den Größen n = 10.000, 20.000, . . . , 100.000 DensityReachable wird durch zwei verschachtelte Schlei- für beide Datenverteilungen generiert. Über alle n wurden 48 FM-DBSCAN: Ein effizienter, dichte-basierter Clustering-Algorithmus DBSCAN FM-DBSCAN FM-DBSCAN Anzahl Distanzberechnungen (log.) Anzahl Distanzberechnungen (log.) 103 1010 105 Zeit in Millisekunden (log.) Zeit in Millisekunden (log.) 109 104 10 8 103 107 102 2 107 10 106 101 106 101 105 100 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 4 4 Größe der Datenkollektion n ·10 Größe der Datenkollektion n ·10 Größe von  Größe von  (a) three ring clusters (minPts = 5,  = 0, 4) (a) three ring clusters (minPts = 5, n = 100.000) Anzahl Distanzberechnungen (log.) Anzahl Distanzberechnungen (log.) 1010 105 108 Zeit in Millisekunden (log.) Zeit in Millisekunden (log.) 103 109 104 108 103 107 102 107 102 106 101 106 105 101 100 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 4 4 Größe der Datenkollektion n ·10 Größe der Datenkollektion n ·10 Größe von  Größe von  (b) gaussian mixture clusters (minPts = 5,  = 0, 2) (b) gaussian mixture clusters (minPts = 5, n = 100.000) Abb. 4: Clustering-Performanz für variierendes n Abb. 5: Clustering-Performanz für variierendes  die selben Werte für  und minPts verwendet. Dabei wurden gebungen ein Clustering durchgeführt werden kann. Erste die Werte für  und minPts so festgelegt, dass die in Abb. Experimente zeigen, dass FM-DBSCAN um ein Vielfaches 3 dargestellten Cluster gefunden wurden. Das Experiment schneller als DBSCAN ist (Faktor > 990), wodurch FM-DB- wurde für jedes n zehnmal durchgeführt und anschließend SCAN für große Datenkollektionen vorteilhaft wird. die Werte gemittelt. Die Ergebnisse sind in Abb. 4 zu sehen. In zukünftigen Arbeiten sollen weitere Datenkollektionen Auf beiden Verteilungen konnte im Vergleich zu DBSCAN (synthetisch und real) evaluiert werden, um die Effizienz von eine erhebliche Anzahl an Distanzberechnungen eingespart FM-DBSCAN zu bestätigen. Außerdem soll untersucht wer- und die Rechenzeit drastisch reduziert werden. Für three den, wie  und minPts zu wählen sind, sodass zum einen eine ring clusters berechnet FM-DBSCAN um einen Faktor 727 gute Qualität (Clustering-Ergebnis) und zum anderen eine bis 3956 weniger Distanzberechnungen als DBSCAN, wo- hohe Effizienz erzielt wird. Die durchgeführten Experimente durch FM-DBSCAN um einen Faktor 999 bis 3418 weniger zu  geben hierfür erste Aufschlüsse. Ebenfalls sollen neue Zeit benötigt. Bei gaussian mixture clusters sind die Einspa- Partitionierungsalgorithmen untersucht werden, um die Par- rungen noch deutlich höher. Dort kann ein Faktor 2664 bis titionierung noch weiter zu beschleunigen. 23.075 an Distanzberechnungen eingespart und die Rechen- zeit um einen Faktor 1128 bis 17.404 reduziert werden. Literatur Als zweites wurde der Einfluss des Parameters  auf die Effizienz von FM-DBSCAN evaluiert. Auch hier wurde das [1] Ester, M., H. Kriegel, J. Sander und X. Xu: A Density- Experiment zehnmal ausgeführt und die Werte anschließend Based Algorithm for Discovering Clusters in Large Spa- gemittelt. Die Ergebnisse sind in der Abb. 5 zu finden. tial Databases with Noise. In: Proc. of the 2nd Int. Conf. Für three ring clusters ist für wachsendes  eine fallende on Knowledge Discovery and Data Mining, S. 226–231, Tendenz sowohl für die Anzahl der Distanzberechnungen, als 1996. auch für die Zeit ersichtlich. Lediglich im Bereich 0, 4 bis 0, 5 [2] Gan, J. und Y. Tao: DBSCAN Revisited: Mis-Claim, ist ein Steigen zu erkennen. Dies liegt daran, dass sich die - Un-Fixability, and Approximation. In: Proc. of the 2015 Umgebungen zweier Leader aus unterschiedlichen Clustern ACM SIGMOD Int. Conf. on Management of Data, S. immer mehr in einem großen leeren Bereich überschneiden 519–530, 2015. und somit die Lemmata 3 und 4 nicht mehr effektiv angewen- [3] Gunawan, A.: A faster algorithm for DBSCAN. Diplom- det werden können. Vereinigen sich diese Cluster aufgrund arbeit, Technische Universität Eindhoven, 2013. des größeren , fallen die Werte wieder. Das gleiche Verhal- [4] Liu, B.: A Fast Density-Based Clustering Algorithm for ten tritt auch bei gaussian mixture clusters auf, nur öfter, Large Databases. In: Proc. of the 2006 Int. Conf. on da es dort mehr Cluster gibt. Machine Learning and Cybernetics, S. 996–1000, 2006. [5] Mahran, S. und K. Mahar: Using grid for accelerating density-based clustering. In: Proc. of 8th IEEE Int. 6. ZUSAMMENFASSUNG UND AUSBLICK Conf. on Computer and Information Technology, S. 35– In dieser Arbeit wurde der Clustering-Algorithmus FM- 40, 2008. DBSCAN vorgestellt, der für beliebige Distanzfunktionen [6] Viswanath, P. und V. S. Babu: Rough-DBSCAN: A fast dasselbe Ergebnis wie DBSCAN liefert. Dabei nutzt FM- hybrid density based clustering method for large data sets. DBSCAN das Prinzip der Leader-Umgebungen, um die Ob- Pattern Recognition Letters, 30(16):1477–1488, 2009. jekte zusammenzufassen, sodass anschließend auf den Um- 49