Density-based clustering techniques are used in a wide range of data mining applications. One of their most attractive features con- sists in not making use of prior knowledge of the number of clusters that a dataset contains along with their shape. In this paper we propose a new algorithm named Linear DBSCAN (Lin-DBSCAN), a simple approach to clustering inspired by the density model introduced with the well known algorithm DBSCAN. Designed to minimize the computational cost of density based clustering on geospatial data, Lin-DBSCAN features a linear time complexity that makes it suitable for real-time applications on low-resource devices. Lin-DBSCAN uses a discrete version of the density model of DBSCAN that takes ad- vantage of a grid-based scan and merge approach. The name of the algorithm stems exactly from its main features outlined above. The algorithm was tested with well known data sets. Experimental results prove the efficiency and the validity of this approach over DBSCAN in the context of spatial data clustering, enabling the use of a density-based clustering technique on large datasets with low computational cost.
Clustering is one of the basic data mining tasks that can be used to extract hidden information from data in the absence of target classes. One of the most well-known density based clustering algorithms for processing spatial data is Density-Based Spatial Clustering of Application with Noise (DBSCAN) that uses learning parameters epsiv and minPts to define the density that will be sought in the data set while forming the clusters. The major drawbacks of the DBSCAN algorithm are its sensitivity to user input required to execute the algorithm, inability to recognize clusters with different densities, and computational complexity. In this study, we propose a three-level clustering method to address the second issue. The first level selects appropriate grids so that the density is homogeneous in each grid. The second stage merges cells with similar densities and identifies the most suitable values of epsiv and minPts in each grid that remain after merging. The third step of the proposed method executes the DBSCAN method with these identified parameters in the dataset. The proposed method is tested in three artificial benchmark data sets to demonstrate that the clusters are correctly identified.