An Enhancement Algorithm of Cluster Boundaries Precision Based on Grid's Density Direction

The grid-based clustering approach uses a multi-resolution grid data structure. It quantizes the object space into a finite number of cells that form a grid structure on which all of the operations for clustering are performed. Existing grid-based clustering algorithms are efficient, but the clustering quality is not very good, especially when dealing with the objects in fringes, the clustering results are not accurate. In order to resolve such problems, a preprocess algorithm based on grid density direction is proposed in this paper. The method is derived from Newton's universal law of gravitation, that is, the smaller the distance between objects, the larger their quality, the more attractive. Similarly, the density inside a cluster is larger than its boundary. That is to say that there is larger gravitation inside a cluster. Therefore, if a grid's density increases at the opposite directions synchronously (that is the case of the extrusion), the grid need to be further refined, which is to determine whether the grid is the edge of cluster grids, and determine the extrusion directions of the objects in the edge of cluster grids. The experimental results show that the new method can enhance cluster boundaries precision effectively and has a higher cluster recognition rate, so it is very useful as a preprocess algorithm of a clustering.