Refine
Document Type
Language
- German (2)
Keywords
- DBSCAN (1)
- Density-based Clustering (1)
- Leader Neighbourhood (1)
- Leaders (1)
Institute
EFM-DBSCAN: Ein baumbasierter Clusteringalgorithmus unter Ausnutzung erweiterter Leader-Umgebungen
(2017)
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.
DBSCAN ist ein dichte-basierter Clustering-Algorithmus,
der Cluster beliebiger Form auffindet und diese von Rauschen
trennt. Aufgrund des quadratischen Aufwands ist DBSCAN
fur große Datenmengen jedoch oft ungeeignet. In die- ¨
ser Arbeit wird deshalb ein effizienterer Algorithmus namens
FM-DBSCAN vorgestellt, der fur eine beliebige Distanz- ¨
funktion (Metrik) dasselbe Ergebnis wie DBSCAN liefert.
Hierfur partitioniert FM-DBSCAN die Datenkollektion in ¨
Leader-Umgebungen, auf denen anschließend das Clustering
durchgefuhrt wird. Erste Experimente mittels synthetischen ¨
Datenkollektionen zeigen, dass FM-DBSCAN um einen Faktor
> 990 schneller als DBSCAN ist und auch wesentlich
besser mit der Kollektionsgr¨oße skaliert