GB-NClust: A Pioneering Graph-Based Approach for Natural Clustering in Spatial Datasets

Abstract

The exponential rate at which volume of data is increasing, it is actually impractical to avoid the need of analyzing data for decision-making purposes. Clustering is one of the very effective ways for the data analysis. It is a principal tool of data mining for extracting previously unknown patterns existing in spatial datasets. It is a process of gathering similar data objects into one group such that objects in different groups are dissimilar. Datasets having non-uniform data object distribution are not dealt properly by the available clustering algorithms in literature. In this paper, an innovative approach of generating clusters in spatial datasets (uniform or non-uniform) have been proposed which models dataset using Delaunay structure for capturing spatial proximities and the analysis of the Delaunay edges have been carried out based on a range which is computed automatically by the algorithm for determining whether the two vertices are attracted towards each other or there is a repulsion between them. The edges corresponding to the vertices that are repulsive to each other are removed from the Delaunay structure thus obtaining the desired clusters of arbitrary shapes without any human interaction. The edges are classified as very strong edges, weak edges and floating edges. The dense and sparse clusters present in the same dataset have also been identified effectively even in the presence of bridges between the two clusters. The experimental study is conducted on sample datasets, which shows encouraging results.