Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen: http://dx.doi.org/10.25673/13402
Titel: Skeleton-based validation for density-based clustering
Autor(en): Braune, Christian
Körperschaft: Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik
Erscheinungsdatum: 2018
Art: Dissertation
Tag der Verteidigung: 2018
Sprache: Englisch
URN: urn:nbn:de:gbv:ma9:1-1981185920-134655
Schlagwörter: Künstliche Intelligenz
Zusammenfassung: Clustering is an important process in data analysis. It is the process of grouping previously unlabeled data and distinguishing noise or outliers from interesting data. Clustering algorithms can work in many different ways. These are, for example, centroid-based methods like k-means, hierarchical clustering or densitybased methods. DBSCAN is the best-known representative of the latter. Since clustering is an unsupervised learning approach, validation measures are needed to assess whether a found result is good or not. In the case of centroid-based algorithms there exists a plethora of validation measures for the crisp and the fuzzy case. Only recently the validation of density-based clustering has made some progress. The majority of the hitherto used validation measures refer in some way or another to the centroids of the clusters. When using density-based clustering, these centroids to not exist or have no meaning. Therefore, these measures are only help- or meaningful under a limited scope of scenarios. They would favor clusterings that—to the human eye—are obviously sub-optimal. This thesis suggest a way to make centroid-based cluster validation measures available for clusterings obtained by a density-based algorithm. For this the arithmetic mean as centroid is replaced by a cluster skeleton that provides more structural information for a cluster than a single point. It can then be used instead of the former centroid in the calculation of the validation scores. After discussing several different techniques of finding such an object, the behavior of the different validation scores is analyzed.
Clustering ist ein wichtiger Prozess in der Datenanalyse. Innerhalb dieses Prozesses werden ungelabelte Datenpunkte zu sogenannten Clustern zusammengefasst. Einige Clusteringalgorithmen sind außerdem in der Lage, zwischen Rauschen, Ausreißen und interessanten Datenpunkten zu unterscheiden. Hierfür arbeiten Clusteringalgorithmen auf vielfältige Art und Weise. So gibt es zentroidbasierte Verfahren wie k-means, Hierarchisch-Agglomeratives Clustering oder dichtebasierte Methoden wie DBSCAN. Clustering ist im Wesentlichen ein unüberwachtes Lernverfahren und bedarf daher einer sorgfältigen Validierung der Ergebnisse. Für die zentroidbasierten Verfahren gibt es bereits eine Vielzahl verschiedener Maße, die jeweils leicht andere Definitionen eines Clusters implizieren. Diese Maße erlauben es einzuschätzen, wie gut ein jeweils gefundenes Ergebnis mit dieser Clusterdefinition übereinstimmt. Viele dieser Maße können für hartes Clustering ebenso angewendet werden wie für fuzzy Clustering. Für die Validierung dichtebasierter Clusteringverfahren gibt es jedoch erst seit kurzem erste Verfahren. Dies liegt unter anderem daran, dass sich die zentroidbasierten Validierungsmaße nicht ohne weiteres auf dichtebasierte Clusterings übertragen lassen, da der vielfach verwendete Mittelpunkt eines Clusters im Kontext des dichtebasierten Clusterings von geringerer Signifikanz ist. Würden diese Maße zur Bewertung dichtebasierter Clusterings herangezogen, so würden sie Ergebnisse bevorzugen, die – zumindest für das menschliche Auge – suboptimal sind. In dieser Dissertation wird eine Möglichkeit vorgeschlagen, wie zentroidbasierte Clustervalidierungmaße auf dichtebasierte Clusterings angewandt werden können. Hierzu wird der klassischerweise verwendete Mittelpunkt eines Clusters durch ein Clusterskelett ersetzt. Es kann anstelle des Mittelpunktes für die Berechnung der einzelnen Validierungsmaßes genutzt werden. Nach einer Diskussion verschiedener Methoden zum Finden eines solchen Skeletts wird das Verhalten verschiedenen Validierungsmaße analysiert.
URI: https://opendata.uni-halle.de//handle/1981185920/13465
http://dx.doi.org/10.25673/13402
Open-Access: Open-Access-Publikation
Nutzungslizenz: (CC BY-NC 4.0) Creative Commons Namensnennung - Nicht kommerziell 4.0 International
Enthalten in den Sammlungen:Fakultät für Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
dissertation_christian_braune_fin.pdfDissertation49.43 MBAdobe PDFMiniaturbild
Öffnen/Anzeigen


Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons Creative Commons