Density Peak Clustering Based on Relative Density Relationship

Abstract The density peak clustering algorithm treats local density peaks as cluster centers, and groups non-center data points by assuming that one data point and its nearest higher-density neighbor are in the same cluster. While this algorithm is shown to be promising in some applications, its clustering results are found to be sensitive to density kernels, and large density differences across clusters tend to result in wrong cluster centers. In this paper we attribute these problems to the inconsistency between the assumption and implementation adopted in this algorithm. While the assumption is based totally on relative density relationship, this algorithm adopts absolute density as one criterion to identify cluster centers. This observation prompts us to present a cluster center identification criterion based only on relative density relationship. Specifically, we define the concept of subordinate to describe the relative density relationship, and use the number of subordinates as a criterion to identify cluster centers. Our approach makes use of only relative density relationship and is less influenced by density kernels and density differences across clusters. In addition, we discuss the problems of two existing density kernels, and present an average-distance based kernel. In data clustering experiments we validate the new criterion and density kernel respectively, and then test the whole algorithm and compare with some other clustering algorithms.