An Alternating Optimization Approach Based on Hierarchical Adaptations of DBSCAN
Alexander Dockhorn, Christian Braune, Rudolf Kruse · 2015
DBSCAN is one of the most common density-based clustering algorithms. While multiple works tried to present an appropriate estimate for needed parameters we propose an alternating optimization algorithm, which finds a locally optimal parameter combination. The algorithm is based on the combination of two hierarchical versions of DBSCAN, which can be generated by fixing one parameter and iterating through possible values of the second parameter. Due to monotonicity of the neighborhood sets and the core-condition, successive levels of the hierarchy can efficiently be computed. An local optimal parameter combination can be determined using internal cluster validation measures. In this work we are comparing the measures edge-correlation and silhouette coefficient. For the latter we propose a density-based interpretation and show a respective computational efficient estimate to detect non-convex clusters produced by DBSCAN. Our results show, that the algorithm can automatically detect a good DBSCAN clustering on a variety of cluster scenarios.