[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki18\/2021\/01\/19\/dbscan-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki18\/2021\/01\/19\/dbscan-wikipedia\/","headline":"DBSCAN – Wikipedia","name":"DBSCAN – Wikipedia","description":"Ein dichtebasierter Datencluster-Algorithmus Dichtebasierte r\u00e4umliche Clusterbildung von Anwendungen mit Rauschen (DBSCAN) ist ein Datencluster-Algorithmus, der 1996 von Martin Ester, Hans-Peter","datePublished":"2021-01-19","dateModified":"2021-01-19","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki18\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki18\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/a\/af\/DBSCAN-Illustration.svg\/400px-DBSCAN-Illustration.svg.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/a\/af\/DBSCAN-Illustration.svg\/400px-DBSCAN-Illustration.svg.png","height":"288","width":"400"},"url":"https:\/\/wiki.edu.vn\/wiki18\/2021\/01\/19\/dbscan-wikipedia\/","wordCount":7044,"articleBody":"Ein dichtebasierter Datencluster-Algorithmus Dichtebasierte r\u00e4umliche Clusterbildung von Anwendungen mit Rauschen (DBSCAN) ist ein Datencluster-Algorithmus, der 1996 von Martin Ester, Hans-Peter Kriegel, J\u00f6rg Sander und Xiaowei Xu vorgeschlagen wurde.[1]Es handelt sich um einen dichtebasierten nichtparametrischen Clustering-Algorithmus: Bei einer Reihe von Punkten in einem bestimmten Raum werden Punkte zusammengefasst, die eng zusammengepackt sind (Punkte mit vielen Nachbarn in der N\u00e4he), und als Ausrei\u00dferpunkte markiert, die allein in Regionen mit niedriger Dichte liegen (deren n\u00e4chste Nachbarn zu weit weg sind). DBSCAN ist einer der am h\u00e4ufigsten verwendeten Clustering-Algorithmen und wird auch in der wissenschaftlichen Literatur am h\u00e4ufigsten zitiert.[2]2014 wurde der Algorithmus auf der f\u00fchrenden Data-Mining-Konferenz ACM SIGKDD mit dem Test of Time Award (einer Auszeichnung f\u00fcr Algorithmen, die in Theorie und Praxis gro\u00dfe Beachtung gefunden haben) ausgezeichnet.[3] Stand Juli 2020[update], das Folgepapier “DBSCAN Revisited, Revisited: Warum und wie Sie DBSCAN (noch) verwenden sollten”[4] erscheint in der Liste der 8 am h\u00e4ufigsten heruntergeladenen Artikel des renommierten TODS-Journals (ACM Transactions on Database Systems).[5] Table of ContentsGeschichte[edit]Vorl\u00e4ufig[edit]Algorithmus[edit]Urspr\u00fcnglicher abfragebasierter Algorithmus[edit]Abstrakter Algorithmus[edit]Komplexit\u00e4t[edit]Vorteile[edit]Nachteile[edit]Parameter Sch\u00e4tzung[edit]Beziehung zur spektralen Clusterbildung[edit]Erweiterungen[edit]Verf\u00fcgbarkeit[edit]Verweise[edit]Geschichte[edit]1972 ver\u00f6ffentlichte Robert F. Ling einen eng verwandten Algorithmus in “The Theory and Construction of k-Clusters”.[6] im Das Computerjournal mit einer gesch\u00e4tzten Laufzeitkomplexit\u00e4t von O (n\u00b3).[6] DBSCAN hat einen Worst-Case von O (n\u00b2), und die datenbankorientierte Bereichsabfrageformulierung von DBSCAN erm\u00f6glicht eine Indexbeschleunigung. Die Algorithmen unterscheiden sich geringf\u00fcgig in der Behandlung von Grenzpunkten.Vorl\u00e4ufig[edit]Betrachten Sie eine Reihe von Punkten in einem zu gruppierenden Bereich. Lassen \u03b5 ein Parameter sein, der den Radius einer Nachbarschaft in Bezug auf einen bestimmten Punkt angibt. F\u00fcr die Zwecke des DBSCAN-Clusters werden die Punkte als klassifiziert Kernpunkte, (Dichte-) erreichbare Punkte und Ausrei\u00dfer, wie folgt:Ein Punkt p ist ein Kernpunkt wenn zumindest minPts Punkte sind in Reichweite \u03b5 davon (einschlie\u00dflich p).Ein Punkt q ist direkt erreichbar von p wenn Punkt q ist in Reichweite \u03b5 vom Kernpunkt p. Punkte sollen nur direkt von Kernpunkten aus erreichbar sein.Ein Punkt q ist erreichbar von p wenn es einen Weg gibt p1, …, pn mit p1 = p und pn = q, wo jeder pich+1 ist direkt erreichbar von pich. Beachten Sie, dass dies bedeutet, dass der Anfangspunkt und alle Punkte auf dem Pfad Kernpunkte sein m\u00fcssen, mit der m\u00f6glichen Ausnahme von q.Alle Punkte, die von keinem anderen Punkt aus erreichbar sind, sind Ausrei\u00dfer oder Ger\u00e4uschpunkte.Nun wenn p ist ein Kernpunkt, dann bildet es eine Cluster zusammen mit allen Punkten (Kern oder Nicht-Kern), die von dort aus erreichbar sind. Jeder Cluster enth\u00e4lt mindestens einen Kernpunkt. Nicht-Kernpunkte k\u00f6nnen Teil eines Clusters sein, bilden jedoch dessen “Kante”, da sie nicht zum Erreichen weiterer Punkte verwendet werden k\u00f6nnen. In diesem Diagramm ist minPts = 4. Punkt A und die anderen roten Punkte sind Kernpunkte, da der diese Punkte umgebende Bereich in einem \u03b5 Radius enth\u00e4lt mindestens 4 Punkte (einschlie\u00dflich des Punktes selbst). Da sie alle voneinander erreichbar sind, bilden sie einen einzigen Cluster. Die Punkte B und C sind keine Kernpunkte, sondern von A aus (\u00fcber andere Kernpunkte) erreichbar und geh\u00f6ren somit auch zum Cluster. Punkt N ist ein Rauschpunkt, der weder ein Kernpunkt ist noch direkt erreichbar ist.Die Erreichbarkeit ist keine symmetrische Beziehung: Per Definition k\u00f6nnen nur Kernpunkte Nicht-Kernpunkte erreichen. Das Gegenteil ist nicht der Fall, so dass ein Nicht-Kernpunkt erreichbar sein kann, aber nichts von ihm aus erreicht werden kann. Daher ein weiterer Begriff von Verbundenheit wird ben\u00f6tigt, um das Ausma\u00df der von DBSCAN gefundenen Cluster formal zu definieren. Zwei Punkte p und q sind dichteverbunden, wenn es einen Punkt gibt \u00d6 so dass beide p und q sind erreichbar von \u00d6. Dichte-Verbundenheit ist symmetrisch.Ein Cluster erf\u00fcllt dann zwei Eigenschaften:Alle Punkte innerhalb des Clusters sind miteinander verbunden.Wenn ein Punkt von einem Punkt des Clusters aus dichterreichbar ist, ist er auch Teil des Clusters.Algorithmus[edit]Urspr\u00fcnglicher abfragebasierter Algorithmus[edit]DBSCAN erfordert zwei Parameter: \u03b5 (eps) und die Mindestanzahl von Punkten, die zur Bildung eines dichten Bereichs erforderlich sind[a] (minPts). Es beginnt mit einem beliebigen Startpunkt, der nicht besucht wurde. Die \u03b5-Nachbarschaft dieses Punktes wird abgerufen, und wenn sie ausreichend viele Punkte enth\u00e4lt, wird ein Cluster gestartet. Andernfalls wird der Punkt als Rauschen gekennzeichnet. Es ist zu beachten, dass dieser Punkt sp\u00e4ter in einer ausreichend gro\u00dfen \u03b5-Umgebung eines anderen Punkts gefunden werden kann und daher Teil eines Clusters sein kann.Wenn festgestellt wird, dass ein Punkt ein dichter Teil eines Clusters ist, ist seine \u03b5-Nachbarschaft ebenfalls Teil dieses Clusters. Daher werden alle Punkte, die innerhalb der \u03b5-Nachbarschaft gefunden werden, addiert, ebenso wie ihre eigene \u03b5-Nachbarschaft, wenn sie ebenfalls dicht sind. Dieser Prozess wird fortgesetzt, bis der mit der Dichte verbundene Cluster vollst\u00e4ndig gefunden ist. Dann wird ein neuer nicht besuchter Punkt abgerufen und verarbeitet, was zur Entdeckung eines weiteren Clusters oder Rauschens f\u00fchrt.DBSCAN kann mit jeder Distanzfunktion verwendet werden[1][4] (sowie \u00c4hnlichkeitsfunktionen oder andere Pr\u00e4dikate).[7] Die Distanzfunktion (dist) kann daher als zus\u00e4tzlicher Parameter angesehen werden.Der Algorithmus kann wie folgt im Pseudocode ausgedr\u00fcckt werden:[4]DBSCAN(DB, distFunc, eps, minPts) { C\u00a0:= 0 \/* Cluster counter *\/ for each point P in database DB { if label(P) \u2260 undefined then continue \/* Previously processed in inner loop *\/ Neighbors N\u00a0:= RangeQuery(DB, distFunc, P, eps) \/* Find neighbors *\/ if |N| < minPts then { \/* Density check *\/ label(P)\u00a0:= Noise \/* Label as Noise *\/ continue } C\u00a0:= C + 1 \/* next cluster label *\/ label(P)\u00a0:= C \/* Label initial point *\/ SeedSet S\u00a0:= N {P} \/* Neighbors to expand *\/ for each point Q in S { \/* Process every seed point Q *\/ if label(Q) = Noise then label(Q)\u00a0:= C \/* Change Noise to border point *\/ if label(Q) \u2260 undefined then continue \/* Previously processed (e.g., border point) *\/ label(Q)\u00a0:= C \/* Label neighbor *\/ Neighbors N\u00a0:= RangeQuery(DB, distFunc, Q, eps) \/* Find neighbors *\/ if |N| \u2265 minPts then { \/* Density check (if Q is a core point) *\/ S\u00a0:= S \u222a N \/* Add new neighbors to seed set *\/ } } }}Dabei kann RangeQuery mithilfe eines Datenbankindex f\u00fcr eine bessere Leistung oder mithilfe eines langsamen linearen Scans implementiert werden:RangeQuery(DB, distFunc, Q, eps) { Neighbors N\u00a0:= empty list for each point P in database DB { \/* Scan all points in the database *\/ if distFunc(Q, P) \u2264 eps then { \/* Compute distance and check epsilon *\/ N\u00a0:= N \u222a {P} \/* Add to result *\/ } } return N}Abstrakter Algorithmus[edit]Der DBSCAN-Algorithmus kann in die folgenden Schritte abstrahiert werden:[4]Finden Sie die Punkte in der Nachbarschaft \u03b5 (eps) jedes Punkts und identifizieren Sie die Kernpunkte mit mehr als minPts Nachbarn.Finden Sie die angeschlossenen Komponenten von Ader Punkte im Nachbardiagramm, wobei alle Nicht-Kernpunkte ignoriert werden.Weisen Sie jeden Nicht-Kernpunkt einem nahe gelegenen Cluster zu, wenn der Cluster ein \u03b5 (eps) -Nachbar ist, andernfalls weisen Sie ihn dem Rauschen zu.Eine naive Implementierung erfordert das Speichern der Nachbarschaften in Schritt 1, wodurch ein erheblicher Speicher erforderlich ist. Der urspr\u00fcngliche DBSCAN-Algorithmus erfordert dies nicht, indem diese Schritte jeweils f\u00fcr einen Punkt ausgef\u00fchrt werden.Komplexit\u00e4t[edit]DBSCAN besucht jeden Punkt der Datenbank, m\u00f6glicherweise mehrmals (z. B. als Kandidaten f\u00fcr verschiedene Cluster). Aus praktischen Gr\u00fcnden wird die zeitliche Komplexit\u00e4t jedoch haupts\u00e4chlich von der Anzahl der regionQuery-Aufrufe bestimmt. DBSCAN f\u00fchrt genau eine solche Abfrage f\u00fcr jeden Punkt aus, und wenn eine Indexierungsstruktur verwendet wird, die eine Nachbarschaftsabfrage in ausf\u00fchrt O (log n), eine durchschnittliche Laufzeitkomplexit\u00e4t von \u00d6(n Log n) erhalten wird (wenn Parameter \u03b5 wird auf sinnvolle Weise gew\u00e4hlt, dh so, dass im Durchschnitt nur O (log n) Punkte werden zur\u00fcckgegeben). Ohne die Verwendung einer beschleunigenden Indexstruktur oder f\u00fcr entartete Daten (z. B. alle Punkte innerhalb einer Entfernung von weniger als \u03b5) bleibt die Laufzeitkomplexit\u00e4t im ung\u00fcnstigsten Fall bestehen \u00d6(n\u00b2). Die Distanzmatrix der Gr\u00f6\u00dfe (n\u00b2-n) \/ 2 kann materialisiert werden, um Entfernungsberechnungen zu vermeiden, dies ist jedoch erforderlich \u00d6(n\u00b2) Speicher, w\u00e4hrend eine nicht matrixbasierte Implementierung von DBSCAN nur ben\u00f6tigt \u00d6(n) Erinnerung. DBSCAN kann nicht linear trennbare Cluster finden. Dieser Datensatz kann mit k-means oder Gaussian Mixture EM Clustering nicht ausreichend geclustert werden.Vorteile[edit]DBSCAN erfordert nicht, dass die Anzahl der Cluster in den Daten a priori angegeben wird, im Gegensatz zu k-means.DBSCAN kann beliebig geformte Cluster finden. Es kann sogar einen Cluster finden, der vollst\u00e4ndig von einem anderen Cluster umgeben ist (aber nicht mit diesem verbunden ist). Aufgrund des MinPts-Parameters wird der sogenannte Single-Link-Effekt (verschiedene Cluster werden durch eine d\u00fcnne Punktlinie verbunden) reduziert.DBSCAN hat eine Vorstellung von Rauschen und ist robust gegen\u00fcber Ausrei\u00dfern.DBSCAN ben\u00f6tigt nur zwei Parameter und ist meist unempfindlich gegen\u00fcber der Reihenfolge der Punkte in der Datenbank. (Punkte, die am Rand von zwei verschiedenen Clustern sitzen, k\u00f6nnen jedoch die Clustermitgliedschaft austauschen, wenn die Reihenfolge der Punkte ge\u00e4ndert wird und die Clusterzuweisung nur bis zum Isomorphismus eindeutig ist.)DBSCAN wurde f\u00fcr die Verwendung mit Datenbanken entwickelt, die Regionsabfragen beschleunigen k\u00f6nnen, z. B. mithilfe eines R * -Baums.Die Parameter minPts und \u03b5 k\u00f6nnen von einem Domain-Experten eingestellt werden, wenn die Daten gut verstanden werden.Nachteile[edit]DBSCAN ist nicht vollst\u00e4ndig deterministisch: Grenzpunkte, die von mehr als einem Cluster aus erreichbar sind, k\u00f6nnen abh\u00e4ngig von der Reihenfolge, in der die Daten verarbeitet werden, Teil eines der beiden Cluster sein. Bei den meisten Datens\u00e4tzen und Dom\u00e4nen tritt diese Situation nicht h\u00e4ufig auf und hat nur geringe Auswirkungen auf das Clustering-Ergebnis:[4] Sowohl an Kernpunkten als auch an Rauschpunkten ist DBSCAN deterministisch. DBSCAN *[8] ist eine Variation, die Grenzpunkte als Rauschen behandelt und auf diese Weise ein vollst\u00e4ndig deterministisches Ergebnis sowie eine konsistentere statistische Interpretation von dichteverbundenen Komponenten erzielt.Die Qualit\u00e4t von DBSCAN h\u00e4ngt vom Abstandsma\u00df ab, das in der Funktion regionQuery (P, \u03b5) verwendet wird. Die am h\u00e4ufigsten verwendete Entfernungsmetrik ist die euklidische Entfernung. Insbesondere f\u00fcr hochdimensionale Daten kann diese Metrik aufgrund des sogenannten “Fluches der Dimensionalit\u00e4t” nahezu unbrauchbar gemacht werden, was es schwierig macht, einen geeigneten Wert f\u00fcr \u03b5 zu finden. Dieser Effekt ist jedoch auch bei jedem anderen Algorithmus vorhanden, der auf der euklidischen Entfernung basiert.DBSCAN kann Datens\u00e4tze mit gro\u00dfen Dichteunterschieden nicht gut clustern, da die minPts-\u03b5-Kombination dann nicht f\u00fcr alle Cluster geeignet ausgew\u00e4hlt werden kann.[9]Wenn die Daten und der Ma\u00dfstab nicht gut verstanden werden, kann es schwierig sein, eine sinnvolle Abstandsschwelle \u03b5 zu w\u00e4hlen.Im folgenden Abschnitt zu Erweiterungen finden Sie algorithmische \u00c4nderungen, um diese Probleme zu beheben.Parameter Sch\u00e4tzung[edit]Jede Data Mining-Aufgabe hat das Problem der Parameter. Jeder Parameter beeinflusst den Algorithmus auf bestimmte Weise. F\u00fcr DBSCAN sind die Parameter \u03b5 und minPts wird gebraucht. Die Parameter m\u00fcssen vom Benutzer angegeben werden. Idealerweise ist der Wert von & epsi; durch das zu l\u00f6sende Problem gegeben (z. B. eine physikalische Entfernung), und minPts ist dann die gew\u00fcnschte minimale Clustergr\u00f6\u00dfe.[a]MinPts: Als Faustregel ein Minimum minPts kann aus der Anzahl der Dimensionen abgeleitet werden D. im Datensatz als minPts \u2265 D. + 1. Der niedrige Wert von minPts = 1 macht keinen Sinn, da dann jeder Punkt f\u00fcr sich schon ein Cluster ist.[dubious \u2013 discuss] Mit minPts \u2264 2, das Ergebnis ist das gleiche wie beim hierarchischen Clustering mit der Single-Link-Metrik, wobei das Dendrogramm in der H\u00f6he \u03b5 geschnitten wird. Deshalb, minPts muss mindestens 3 gew\u00e4hlt werden. Gr\u00f6\u00dfere Werte sind jedoch normalerweise besser f\u00fcr Datens\u00e4tze mit Rauschen und ergeben signifikantere Cluster. Als Faustregel gilt, minPts = 2 \u00b7dim kann verwendet werden,[7] Es kann jedoch erforderlich sein, gr\u00f6\u00dfere Werte f\u00fcr sehr gro\u00dfe Daten, f\u00fcr verrauschte Daten oder f\u00fcr Daten mit vielen Duplikaten zu w\u00e4hlen.[4]\u03b5: Der Wert f\u00fcr \u03b5 kann dann unter Verwendung eines k-Abstandsgraphen ausgew\u00e4hlt werden, wobei der Abstand zum k = minPts-1 n\u00e4chster Nachbar vom gr\u00f6\u00dften zum kleinsten Wert geordnet.[4] Bei guten Werten von & epsi; zeigt dieses Diagramm einen “Ellbogen”:[1][7][4] Wenn \u03b5 viel zu klein gew\u00e4hlt wird, wird ein gro\u00dfer Teil der Daten nicht geclustert. Bei einem zu hohen Wert von \u03b5 werden Cluster zusammengef\u00fchrt und die meisten Objekte befinden sich im selben Cluster. Im allgemeinen sind kleine Werte von & epsi; vorzuziehen,[4] und als Faustregel sollte nur ein kleiner Bruchteil der Punkte in diesem Abstand voneinander liegen. Alternativ kann ein OPTICS-Diagramm verwendet werden, um \u03b5,[4] Dann kann der OPTICS-Algorithmus selbst zum Clustering der Daten verwendet werden.Distanzfunktion: Die Wahl der Distanzfunktion ist eng mit der Wahl von \u03b5 gekoppelt und hat einen gro\u00dfen Einfluss auf die Ergebnisse. Im Allgemeinen muss zun\u00e4chst ein angemessenes \u00c4hnlichkeitsma\u00df f\u00fcr den Datensatz ermittelt werden, bevor der Parameter \u03b5 gew\u00e4hlt werden kann. F\u00fcr diesen Parameter gibt es keine Sch\u00e4tzung, aber die Abstandsfunktionen m\u00fcssen f\u00fcr den Datensatz entsprechend ausgew\u00e4hlt werden. Bei geografischen Daten ist beispielsweise die Entfernung zum Gro\u00dfkreis h\u00e4ufig eine gute Wahl.OPTICS kann als Verallgemeinerung von DBSCAN angesehen werden, die den Parameter \u03b5 durch einen Maximalwert ersetzt, der sich haupts\u00e4chlich auf die Leistung auswirkt. MinPts dann wird im Wesentlichen die minimale Clustergr\u00f6\u00dfe zu finden. W\u00e4hrend der Algorithmus viel einfacher zu parametrisieren ist als DBSCAN, sind die Ergebnisse etwas schwieriger zu verwenden, da er normalerweise ein hierarchisches Clustering anstelle der einfachen Datenpartitionierung erzeugt, die DBSCAN erzeugt.K\u00fcrzlich hat einer der urspr\u00fcnglichen Autoren von DBSCAN DBSCAN und OPTICS erneut besucht und eine verfeinerte Version von hierarchischem DBSCAN (HDBSCAN *) ver\u00f6ffentlicht.[8] die nicht mehr den Begriff der Grenzpunkte hat. Stattdessen bilden nur die Kernpunkte den Cluster.Beziehung zur spektralen Clusterbildung[edit]DBSCAN kann als spezielle (effiziente) Variante des Spektralclusters angesehen werden: Verbundene Komponenten entsprechen optimalen Spektralclustern (kein Kantenschnitt – Spektralclustering versucht, die Daten mit einem minimalen Schnitt zu partitionieren); DBSCAN findet verbundene Komponenten im (asymmetrischen) Erreichbarkeitsgraphen.[10] Spektrale Clusterbildung kann jedoch rechenintensiv sein (bis zu \u00d6(n3){ displaystyle O (n ^ {3})} ohne Ann\u00e4herung und weitere Annahmen), und man muss die Anzahl der Cluster w\u00e4hlen k{ displaystyle k} sowohl f\u00fcr die Anzahl der zu w\u00e4hlenden Eigenvektoren als auch f\u00fcr die Anzahl der mit k-Mitteln zu erzeugenden Cluster bei der spektralen Einbettung. Aus Leistungsgr\u00fcnden bleibt der urspr\u00fcngliche DBSCAN-Algorithmus einer spektralen Implementierung vorzuziehen, und diese Beziehung ist bislang nur von theoretischem Interesse.Erweiterungen[edit]Generalisierte DBSCAN (GDBSCAN)[7][11] ist eine Verallgemeinerung derselben Autoren auf willk\u00fcrliche “Nachbarschafts” – und “dichte” Pr\u00e4dikate. Die \u03b5 und minPts Parameter werden aus dem urspr\u00fcnglichen Algorithmus entfernt und in die Pr\u00e4dikate verschoben. Bei Polygondaten kann die “Nachbarschaft” beispielsweise ein sich \u00fcberschneidendes Polygon sein, w\u00e4hrend das Dichtepr\u00e4dikat die Polygonbereiche anstelle nur der Objektanzahl verwendet.Es wurden verschiedene Erweiterungen des DBSCAN-Algorithmus vorgeschlagen, einschlie\u00dflich Verfahren zur Parallelisierung, Parametersch\u00e4tzung und Unterst\u00fctzung f\u00fcr unsichere Daten. Die Grundidee wurde durch den OPTICS-Algorithmus auf hierarchisches Clustering erweitert. DBSCAN wird auch als Teil von Subraum-Clustering-Algorithmen wie PreDeCon und SUBCLU verwendet. HDBSCAN[8] ist eine hierarchische Version von DBSCAN, die auch schneller als OPTICS ist, aus der eine flache Partition, die aus den bekanntesten Clustern besteht, aus der Hierarchie extrahiert werden kann.[12]Verf\u00fcgbarkeit[edit]Es wurde festgestellt, dass verschiedene Implementierungen desselben Algorithmus enorme Leistungsunterschiede aufweisen, wobei die schnellste in einem Testdatensatz in 1,4 Sekunden endet, die langsamste in 13803 Sekunden.[13] Die Unterschiede sind auf Implementierungsqualit\u00e4t, Sprach- und Compilerunterschiede sowie die Verwendung von Indizes zur Beschleunigung zur\u00fcckzuf\u00fchren.Apache Commons Mathematik enth\u00e4lt eine Java-Implementierung des Algorithmus, der in quadratischer Zeit ausgef\u00fchrt wird.ELKI bietet eine Implementierung von DBSCAN sowie GDBSCAN und anderen Varianten an. Diese Implementierung kann verschiedene Indexstrukturen f\u00fcr die subquadratische Laufzeit verwenden und unterst\u00fctzt beliebige Abstandsfunktionen und beliebige Datentypen. Sie kann jedoch durch optimierte (und spezialisierte) Implementierungen auf niedriger Ebene f\u00fcr kleine Datenmengen \u00fcbertroffen werden.mlpack enth\u00e4lt eine Implementierung von DBSCAN, die mit Dual-Tree-Range-Suchtechniken beschleunigt wurde.PostGIS enth\u00e4lt ST_ClusterDBSCAN – eine 2D-Implementierung von DBSCAN, die den R-Tree-Index verwendet. Jeder Geometrietyp wird unterst\u00fctzt, z. B. Point, LineString, Polygon usw.R enth\u00e4lt Implementierungen von DBSCAN in den Paketen dbscan und fpc. Beide Pakete unterst\u00fctzen beliebige Distanzfunktionen \u00fcber Distanzmatrizen. Das Paket fpc hat keine Indexunterst\u00fctzung (und hat daher eine quadratische Laufzeit und Speicherkomplexit\u00e4t) und ist aufgrund des R-Interpreters ziemlich langsam. Das Paket dbscan bietet eine schnelle C ++ – Implementierung unter Verwendung von kd-B\u00e4umen (nur f\u00fcr euklidische Entfernung) und enth\u00e4lt auch Implementierungen von DBSCAN *, HDBSCAN *, OPTICS, OPTICSXi und anderen verwandten Methoden.scikit-learn enth\u00e4lt eine Python-Implementierung von DBSCAN f\u00fcr beliebige Minkowski-Metriken, die mithilfe von kd-B\u00e4umen und Ball-B\u00e4umen beschleunigt werden kann, jedoch den quadratischen Speicher im ung\u00fcnstigsten Fall verwendet. EIN Beitrag zum Scikit-Lernen bietet eine Implementierung des HDBSCAN * -Algorithmus.Pyclustering Die Bibliothek enth\u00e4lt eine Python- und C ++ – Implementierung von DBSCAN nur f\u00fcr euklidische Entfernungen sowie einen OPTICS-Algorithmus.SPMF Enth\u00e4lt eine Implementierung des DBSCAN-Algorithmus mit kd-Baumunterst\u00fctzung nur f\u00fcr die euklidische Entfernung.Weka enth\u00e4lt (als optionales Paket in den neuesten Versionen) eine grundlegende Implementierung von DBSCAN, die in quadratischer Zeit und linearem Speicher ausgef\u00fchrt wird.^ ein b W\u00e4hrend minPts intuitiv die minimale Clustergr\u00f6\u00dfe ist, ist in einigen F\u00e4llen DBSCAN k\u00f6nnen kleinere Cluster erzeugen.[4] Ein DBSCAN-Cluster besteht aus mindestens ein Kernpunkt.[4] Da andere Punkte Grenzpunkte zu mehr als einem Cluster sein k\u00f6nnen, gibt es keine Garantie daf\u00fcr, dass in jedem Cluster mindestens minPts-Punkte enthalten sind.Verweise[edit]^ ein b c Ester, Martin; Kriegel, Hans-Peter; Sander, J\u00f6rg; Xu, Xiaowei (1996). Simoudis, Evangelos; Han, Jiawei; Fayyad, Usama M. (Hrsg.). Ein dichtebasierter Algorithmus zum Erkennen von Clustern in gro\u00dfen r\u00e4umlichen Datenbanken mit Rauschen. Vortr\u00e4ge der zweiten internationalen Konferenz \u00fcber Wissensentdeckung und Data Mining (KDD-96). AAAI Dr\u00fccken Sie. S. 226\u2013231. CiteSeerX 10.1.1.121.9220. ISBN 1-57735-004-9.^ “Archivierte Kopie”. Archiviert von das Original am 21. April 2010. Abgerufen 2010-04-18.CS1-Wartung: Archivierte Kopie als Titel (Link) Die meisten zitierten Data Mining-Artikel laut Microsoft Academic Search; DBSCAN ist auf Rang 24.^ “2014 SIGKDD Test of Time Award”. ACM SIGKDD. 18.08.2014. Abgerufen 2016-07-27.^ ein b c d e f G h ich j k l Schubert, Erich; Sander, J\u00f6rg; Ester, Martin; Kriegel, Hans Peter; Xu, Xiaowei (Juli 2017). “DBSCAN Revisited, Revisited: Warum und wie Sie DBSCAN (noch) verwenden sollten”. ACM Trans. Datenbank Syst. 42 (3): 19: 1\u201319: 21. doi:10.1145 \/ 3068335. ISSN 0362-5915. S2CID 5156876.^ “TODS Home”. tods.acm.org. Verband f\u00fcr Rechenmaschinen. Abgerufen 2020-07-16.^ ein b Ling, RF (1972-01-01). “Zur Theorie und Konstruktion von k-Clustern”. Das Computerjournal. 15 (4): 326\u2013332. doi:10.1093 \/ comjnl \/ 15.4.326. ISSN 0010-4620.^ ein b c d Sander, J\u00f6rg; Ester, Martin; Kriegel, Hans-Peter; Xu, Xiaowei (1998). “Dichtebasiertes Clustering in r\u00e4umlichen Datenbanken: Der Algorithmus GDBSCAN und seine Anwendungen”. Data Mining und Knowledge Discovery. Berlin: Springer-Verlag. 2 (2): 169\u2013194. doi:10.1023 \/ A: 1009745219419. S2CID 445002.^ ein b c Campello, Ricardo JGB; Moulavi, Davoud; Zimek, Arthur; Sander, J\u00f6rg (2015). “Hierarchische Dichtesch\u00e4tzungen f\u00fcr Datenclustering, Visualisierung und Ausrei\u00dfererkennung”. ACM-Transaktionen zur Wissensermittlung aus Daten. 10 (1): 1\u201351. doi:10.1145 \/ 2733381. ISSN 1556-4681. S2CID 2887636.^ Kriegel, Hans-Peter; Kr\u00f6ger, Peer; Sander, J\u00f6rg; Zimek, Arthur (2011). “Dichtebasiertes Clustering”. WIREs Data Mining und Knowledge Discovery. 1 (3): 231\u2013240. doi:10.1002 \/ widm.30.^ Schubert, Erich; He\u00df, Sibylle; Morik, Katharina (2018). Die Beziehung von DBSCAN zu Matrixfaktorisierung und spektraler Clusterbildung (PDF). Lernen, Wissen, Daten, Analysen (LWDA). S. 330\u2013334 – \u00fcber CEUR-WS.org.^ Sander, J\u00f6rg (1998). Generalisiertes dichtebasiertes Clustering f\u00fcr Spatial Data Mining. M\u00fcnchen: Herbert Utz Verlag. ISBN 3-89675-469-6.^ Campello, RJGB; Moulavi, D.; Zimek, A.; Sander, J. (2013). “Ein Rahmen f\u00fcr die halb\u00fcberwachte und unbeaufsichtigte optimale Extraktion von Clustern aus Hierarchien”. Data Mining und Knowledge Discovery. 27 (3): 344. doi:10.1007 \/ s10618-013-0311-4. S2CID 8144686.^ Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur (2016). “Die (schwarze) Kunst der Laufzeitbewertung: Vergleichen wir Algorithmen oder Implementierungen?” Wissens- und Informationssysteme. 52 (2): 341. doi:10.1007 \/ s10115-016-1004-2. ISSN 0219-1377. S2CID 40772241."},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki18\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki18\/2021\/01\/19\/dbscan-wikipedia\/#breadcrumbitem","name":"DBSCAN – Wikipedia"}}]}]