Anytime Cell-based DBSCAN Algorithm that Connects Randomly Selected Cells and Its Performance Evaluation

Data clustering is an unsupervised learning method that finds groups of similar features in a dataset without defining class labels. With the growing interest in big data, there is a need for techniques to speed up clustering algorithms. One clustering method that is well-known in the database domain is density-based spatial clustering of applications with noise (DB-SCAN). Since the DBSCAN algorithm was first proposed, several speed-up methods have been introduced, such as the cell-based DBSCAN algorithm. The cell-based DBSCAN algorithm divides the whole dataset into smaller cells and connects them to form clusters. In this paper we propose a novel clustering algorithm called the anytime cell-based DBSCAN algorithm. The proposed algorithm connects some randomly selected cells and calculates the clustering result at high speed. The process is then repeated to improve the clustering accuracy and obtain accurate results. In this paper, we report experimental results on synthetic and real datasets showing that the proposed algorithm can calculate clustering results with high accuracy at high speed.