Grid-Based Clustering Algorithm Based on Intersecting Partition and Density Estimation

摘要

In order to solve the problem that traditional grid-based clustering techniques lack of the capability of dealing with data of high dimensionality, we propose an intersecting grid partition method and a density estimation method. The partition method can greatly reduce the number of grid cells generated in high dimensional data space and make the neighbor-searching easily. On basis of the two methods, we propose grid-based clustering algorithm (GCOD), which merges two intersecting grids according to density estimation. The algorithm requires only one parameter and the time complexity is linear to the size of the input data set or data dimension. The experimental results show that GCOD can discover arbitrary shapes of clusters and scale well.