This paper focuses on density-based clustering, particularly the Density Peak (DP) algorithm and the one based on density-connectivity DBSCAN; and proposes a new method which takes advantage of the individual strengths of these two methods to yield a density-based hierarchical clustering algorithm. Our investigation begins with formally defining the types of clusters DP and DBSCAN are designed to detect; and then identifies the kinds of distributions that DP and DBSCAN individually fail to detect all clusters in a dataset. These identified weaknesses inspire us to formally define a new kind of clusters and propose a new method called DC-HDP to overcome these weaknesses to identify clusters with arbitrary shapes and varied densities. In addition, the new method produces a richer clustering result in terms of hierarchy or dendrogram for better cluster structures understanding. Our empirical evaluation results show that DC-HDP produces the best clustering results on 14 datasets in comparison with 7 state-of-the-art clustering algorithms.
Many variants of DBSCAN have been attempted to overcome the weakness of detecting clusters with varied densities. OPTICS @cite_21 draws a reachability'' plot based on the @math -nearest neighbour distance. In the @math -axis of the plot, adjacent points follow close to each other such that point @math is the closest to @math in terms of the reachability distance'' The reachability-distance'' of object @math to object @math is the greater one between the core distance'' of @math and the distance between @math and @math . The core distance'' of @math is the minimum @math that makes @math a core'' object (the distance to its @math -nearest neighbour, @math ). . The reachability distance for each point is shown in @math -axis. Since clusters centre normally has a higher density or lower reachability distance than the cluster boundaries, each cluster is visible as a valley'' in this plot. Then a hierarchical method can be used to extract different clusters. The overall clustering performance depends on the hierarchical method employed on the reachability plot.
@cite_21
2160642098
Hierarchical clustering is common method used to determine clusters of similar data points in multi-dimensional spaces. @math algorithms, where @math is the number of points to cluster, have long been known for this problem. This paper discusses parallel algorithms to perform hierarchical clustering using various distance metrics. I describe @math time algorithms for clustering using the single link, average link, complete link, centroid, median, and minimum variance metrics on an @math node CRCW PRAM and @math algorithms for these metrics (except average link and complete link) on @math node butterfly networks or trees. Thus, optimal efficiency is achieved for a significant number of processors using these distance metrics. A general algorithm is given that can be used to perform clustering with the complete link and average link metrics on a butterfly. While this algorithm achieves optimal efficiency for the general class of metrics, it is not optimal for the specific cases of complete link and average link clustering.