Research and Improvement of DBSCAN Cluster Algorithm

摘要

DBSCAN is a typical density based clustering algorithm, which is able to discover clusters in any size or any shape and identify outliers accurately. To overcome the shortcoming of great time cost of the algorithm, a modified DBSCAN algorithm based on grid cells is proposed, which optimizes the most time-consuming region query process of DBSCAN and reduces lots of unnecessary query operations by dividing data space into grid cells. Then the effect of dividing method of grid cells to the algorithm is analyzed. It can raise the efficiency of algorithm by choosing optimal dividing method. It is verified experimentally that DBSCAN algorithm based on grid cells shows higher accuracy and lower time complexity.