A Grid-based Clustering Algorithm using Adaptive Mesh Refinement
Wei‐keng Liao, Ying Liu, Alok N. Choudhary · 2004
Clustering analysis, an automatic process to find similar groups of objects from a database, has been studied for many years. With the increasing data size generated recently, clustering large databases poses a challenging task that must satisfy both the requirements of the computation efficienc y and result quality. Among the existing clustering algorithms, grid-based algorithms generally have a fast processing time, which first employ a uniform grid to collect the regional statistic data and, then, perform the clustering on the grid, instead of the database directly. The performance of grid-based approach normally depends on the size of the grid which is usually much less than the database. However, for highly irregular data distributions, using a single uniform grid may not be sufficient to obtain a required clustering quality or fulfill the time requirement. In this paper, we propose a grid-based clustering algorithm using adaptive mesh refinement technique that can apply higher resolution grids to the denser regions. With the hierarchical AMR tree constructed from the multi-grain meshes, this algorithm can perform clustering at different levels of resolutions and dynamically discover nested clusters. Our experimental results also show the efficienc y and effectiveness of the proposed algorithm compared to the methods using single uniform grids.