Discovering clusters from a dataset with different shapes, density, and scales is a known challenging problem in data clustering. In this paper, we propose the RElative COre MErge (RECOME) clustering algorithm. The core of RECOME is a novel density measure, i.e., Relative @math nearest Neighbor Kernel Density (RNKD). RECOME identifies core objects with unit RNKD, and partitions non-core objects into atom clusters by successively following higher-density neighbor relations toward core objects. Core objects and their corresponding atom clusters are then merged through @math -reachable paths on a KNN graph. Furthermore, we discover that the number of clusters computed by RECOME is a step function of the @math parameter with jump discontinuity on a small collection of values. A jump discontinuity discovery (JDD) method is proposed using a variant of the Dijkstra's algorithm. RECOME is evaluated on three synthetic datasets and six real datasets. Experimental results indicate that RECOME is able to discover clusters with different shapes, density and scales. It achieves better clustering results than established density-based clustering methods on real datasets. Moreover, JDD is shown to be effective to extract the jump discontinuity set of parameter @math for all tested dataset, which can ease the task of data exploration and parameter tuning.
@cite_14: Clustering algorithms are attractive for the task of class identification in spatial databases. However, the application to large spatial databases rises the following requirements for clustering algorithms: minimal requirements of domain knowledge to determine the input parameters, discovery of clusters with arbitrary shape and good efficiency on large databases. The well-known clustering algorithms offer no solution to the combination of these requirements. In this paper, we present the new clustering algorithm DBSCAN relying on a density-based notion of clusters which is designed to discover clusters of arbitrary shape. DBSCAN requires only one input parameter and supports the user in determining an appropriate value for it. We performed an experimental evaluation of the effectiveness and efficiency of DBSCAN using synthetic data and real data of the SEQUOIA 2000 benchmark. The results of our experiments demonstrate that (1) DBSCAN is significantly more effective in discovering clusters of arbitrary shape than the well-known algorithm CLARANS, and that (2) DBSCAN outperforms CLARANS by a factor of more than 100 in terms of efficiency.
DBSCAN @cite_14 is one of the most classic density-based methods. In DBSCAN, the cut-off density of an object @math is defined as the number of objects falling inside a ball of radius @math centred at @math . If the cut-off density of @math is higher than @math , @math is regarded as a key object. When the distance between two key objects is less than @math , they are called density-reachable. Density-reachable key objects form basic clusters. A non-key object is assigned to a basic cluster if it is within @math distance to a key object in the respective cluster; otherwise, the non-key object is treated as noise. In DBSCAN, @math and @math need to be carefully tuned as they would affect the number and formations of the final clusters. Furthermore, DBSCAN cannot handle clusters of heterogeneous densities well as both parameters, even properly selected, are fixed. In contrast, in this work, we introduce the novel concept of RNKD, which in effect homogenizes density measures and thus can handle clusters of different densities.