Revised DBSCAN Clustering Algorithm Based on Dual Grid

Abstract

As one of the most important density-based clustering algorithms, DBSCAN has been widely used in many application fields due to its simplicity and good clustering effect. However, the original DBSCAN method exists two main problems, which include difficulty selecting the suitable external parameters and time consuming. In this paper, an improved version of the DBSCAN, namely DG-DBSCAN (dual grid-based DBSCAN) clustering algorithm, has been proposed. It adopts two types of grid (i.e. inner grid and outer gird) to solve the aforementioned problems respectively. Experimental results show that the new algorithm can not only determine the appropriate external input parameters, but also greatly reduce the running time. Therefore, the proposed DG-DBSCAN is successfully implemented as a novel clustering method.