A fast clustering algorithm based on grid and density

摘要

The efficiency of data mining algorithms is a very important issue as data becoming larger and larger. Density-based clustering analysis can discover clusters with arbitrary shape and is insensitive to noise data. The advantage of grid-based clustering method is linear time complexity. In this paper, we present a new clustering algorithm CLUGD relying on grid and density. We first construct a grid of relevant portion. Then the algorithm finds references by grid and classifies these references to core references and bound references. Then it attaches the data of the bound references to the nearest core references and aggregation the core references in neighboring portions. At last, in-direct graph is used to classify these core references and maps cluster to original data. We performed an experimental evaluation of effectiveness and efficiency of CLUGD using synthetic data and the data of the SEQUOIA 2000 Benchmark. Both theory analysis and experimental results confirm that CLUGD can discover clusters with arbitrary shape and is insensitive to noise data. In the meanwhile, its executing efficiency is much higher than DBSCAN algorithm based on R*-tree