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.
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.
@cite_14
2161806858 2152601912 1971022913 2030780826
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. DBSCAN is a typical clustering algorithm, which can discover clusters with any arbitrary shape and handle noise well. However, it is also slow in comparison due to neighborhood query for each object and faces difficulty in setting density threshold properly. In this paper, a fast density-based clustering algorithm is presented based on DBSCAN. After sorting objects by a certain dimensional coordinates, the new algorithm selects orderly unlabelled points outside a core object's neighborhood as seeds to expand clusters so that the execution frequency of region queries can be decreased. Objects are transformed with a kernel function to improve the clustering accuracy, which diminishes the dependency of density threshold to some extent. Theoretic analysis indicates that the time complexity of this algorithm is approximately linear. Experiments show that the efficiency and the quality for clusters of the proposed algorithm are remarkably superior to those of DBSCAN. This paper presents a new density-based clustering algorithm, ST-DBSCAN, which is based on DBSCAN. We propose three marginal extensions to DBSCAN related with the identification of (i) core objects, (ii) noise objects, and (iii) adjacent clusters. In contrast to the existing density-based clustering algorithms, our algorithm has the ability of discovering clusters according to non-spatial, spatial and temporal values of the objects. In this paper, we also present a spatial-temporal data warehouse system designed for storing and clustering a wide range of spatial-temporal data. We show an implementation of our algorithm by using this data warehouse and present the data mining results. Density-based clustering algorithms are a widely-used class of data mining techniques that can find irregularly shaped clusters and cluster data without prior knowledge of the number of clusters it contains. DBSCAN is the most well-known density-based clustering algorithm. We introduce our version of DBSCAN, called Mr. Scan, which uses a hybrid parallel implementation that combines the MRNet tree-based distribution network with GPGPU-equipped nodes. Mr. Scan avoids the problems of existing implementations by effectively partitioning the point space and by optimizing DBSCAN's computation over dense data regions. We tested Mr. Scan on both a geolocated Twitter dataset and image data obtained from the Sloan Digital Sky Survey. At its largest scale, Mr. Scan clustered 6.5 billion points from the Twitter dataset on 8,192 GPU nodes on Cray Titan in 17.3 minutes. All other parallel DBSCAN implementations have only demonstrated the ability to cluster up to 100 million points.