A Fast Density-Based Clustering Algorithm for Large Databases

DBSCAN is a typical clustering algorithm, which can discover clusters with any arbitrary shape and handle noise well. However, it is also slow in comparison due to neighborhood query for each object and faces difficulty in setting density threshold properly. In this paper, a fast density-based clustering algorithm is presented based on DBSCAN. After sorting objects by a certain dimensional coordinates, the new algorithm selects orderly unlabelled points outside a core object's neighborhood as seeds to expand clusters so that the execution frequency of region queries can be decreased. Objects are transformed with a kernel function to improve the clustering accuracy, which diminishes the dependency of density threshold to some extent. Theoretic analysis indicates that the time complexity of this algorithm is approximately linear. Experiments show that the efficiency and the quality for clusters of the proposed algorithm are remarkably superior to those of DBSCAN