Search

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.

Density-based clustering algorithms are attractive for the task of class identification in spatial database. However, in many cases, very different local-density clusters exist in different regions of data space, therefore, DBSCAN [Ester, M. et al., A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In E. Simoudis, J. Han, & U. M. Fayyad (Eds.), Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining (pp. 226-231). Portland, OR: AAAI.] using a global density parameter is not suitable. As an improvement, OPTICS [Ankerst, M. et al,(1999). OPTICS: Ordering Points To Identify the Clustering Structure. In A. Delis, C. Faloutsos, & S. Ghandeharizadeh (Eds.), Proc. ACM SIGMOD Int. Conf. on Management of Data (pp. 49-60). Philadelphia, PA: ACM.] creates an augmented ordering of the database representing its density-based clustering structure, but it only generates the clusters whose local-density exceeds some threshold instead of similar local-density clusters and doesn't produce a clustering of a data set explicitly. Furthermore the parameters required by almost all the well-known clustering algorithms are hard to determine but have a significant influence on the clustering result. In this paper, a new clustering algorithm LDBSCAN relying on a local-density-based notion of clusters is proposed to solve those problems and, what is more, it is very easy for us to pick the appropriate parameters and takes the advantage of the LOF [Breunig, M. M., et al.,(2000). LOF: Identifying Density-Based Local Outliers. In W. Chen, J. F. Naughton, & P. A. Bernstein (Eds.), Proc. ACM SIGMOD Int. Conf. on Management of Data (pp. 93-104). Dalles, TX: ACM.] to detect the noises comparing with other density-based clustering algorithms. The proposed algorithm has potential applications in business intelligence and enterprise information systems.

To improve query efficiency, most image retrieval systems utilize clustering algorithms to build indices on image databases. In this paper, we analysis region-based image retrieval (RBIR) system query results, hypothesis test and Hubert's Gamma statistic for cluster validation. Our experiment results suggest that images originated from different categories do form clusters in the feature space and thus can be separated. We then analysis the performance of clustering algorithms including K-means, fuzzy C-mean, CA-clustering, density based spatial clustering of applications with noise (DBSCAN) and the proposed modified DBSCAN algorithm with a second merging phase. Our experiment results suggest that the proposed algorithm has clustering performance among the best algorithms. And the proposed modified DBSCAN algorithm with a second merging phase can avoid some of the drawbacks (e.g., k random initial cluster centers) in the original K-means algorithms.