Automatic clustering based on density peak detection using generalized extreme value distribution

Density peaks clustering (DPC) algorithm is able to get a satisfactory result with the help of artificial selecting the clustering centers, but such selection can be hard for a large amount of clustering tasks or the data set with a complex decision diagram. The purpose of this paper is to propose an automatic clustering approach without human intervention. Inspired by the visual selection rule of DPC, the judgment index which equals the lower value within density and distance (after normalization) is proposed for selecting the clustering centers. The judgment index approximately follows the generalized extreme value (GEV) distribution, and each clustering center’s judgment index is much higher. Hence, it is reasonable that the points are selected as clustering centers if their judgment indices are larger than the upper quantile of GEV. This proposed method is called density peaks clustering based on generalized extreme value distribution (DPC-GEV). Furthermore, taking the computational complexity into account, an alternative method based on density peak detection using Chebyshev inequality (DPC-CI) is also given. Experiments on both synthetic and real-world data sets show that DPC-GEV and DPC-CI can achieve the same accuracy as DPC on most data sets but consume much less time.