EFM-DBSCAN: Ein baumbasierter Clusteringalgorithmus unter Ausnutzung erweiterter Leader-Umgebungen
- DBSCAN ist ein dichte-basierter Clusteringalgorithmus, der beliebig geformte Cluster erkennt und sie von Rauschen trennt. Aufgrund der Laufzeit von O(n2) ist seine Anwendung jedoch auf kleine Datenkollektionen beschränkt. Um diesen Aufwand zu reduzieren, wurde der auf dem Konzept der Leader-Umgebung basierende Algorithmus FM-DBSCAN vorgestellt, der für beliebige Metriken dasselbe Clustering wie DBSCAN liefert. In dieser Arbeit wird nun basierend auf FM-DBSCAN das Verfahren EFM-DBSCAN entwickelt. EFM-DBSCAN nutzt die folgenden zwei Konzepte zur Eizienzsteigerung: (a) eine baumbasierte Partitionierung und (b) die Erweiterung der Objekte einer Leader-Umgebung um die Distanzen zu ihrem Leader. Erste Experimente zeigen, dass EFM-DBSCAN bis zu einem Faktor 17 weniger Distanzberechnungen und bis zu einem Faktor 13 weniger Rechenzeit als FM-DBSCAN benötigt. Gegenüber DBSCAN wurde ein Faktor von bis zu 104 eingespart.
Author: | Philipp Egert |
---|---|
URL: | http://btw2017.informatik.uni-stuttgart.de/slidesandpapers/F4-11-18-short/paper_web.pdf |
Title of the source (German): | BTW 2017 : Datenbanksysteme für Business, Technologie und Web (Workshopband), Tagung vom 6. - 7.März 2017 in Stuttgart |
Publisher: | Gesellschaft für Informatik e.V. |
Place of publication: | Bonn |
Editor: | Bernhard Mitschang |
Document Type: | Conference Proceeding |
Language: | German |
Year of publication: | 2017 |
Tag: | DBSCAN; Density-based Clustering; Leader Neighbourhood; Leaders |
First Page: | 227 |
Last Page: | 236 |
Series ; volume number: | Lecture notes in informatics |
Faculty/Chair: | Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Datenbank- und Informationssysteme |