Skeleton-based validation for density-based clustering

Abstract

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.