An End Points Self-Containment Method to Improve Density-Based Clustering

Clustering is a crucial technique for mining knowledge from various datasets lacking prior knowledge. Handling datasets with highly varying density in data space is one of the challenges for density-based clustering. In this paper, a self-containment property of end points during hill climbing process is discovered, which reflects a phenomenon that end points with longer step-sizes lay sieges to ones with shorter step-sizes, forming naturally shaped enclosures in data space. Based on this favorable property, a concise and effective algorithm is proposed, which define a cluster comprises points whose corresponding end points are in the same enclosure. The self-containment property facilitates the capability of our algorithm on extracting clusters from datasets with widely variation of spatial density, and gain more procedural simplicity for our algorithm by omitting the set of global density threshold. In addition, it decreases the calculation amount by halfway hill climbing and reduces the cache requirements for only the information of end points(spatial locations and step-sizes) is needed for clustering. Furthermore, the mathematical proof is given for this property in Euclidean space. The capability of our method is validated by experimental evaluation on challenging synthetic benchmark datasets, compared with conventional and recent algorithms.