Clustering is an essential task to unsupervised learning. It tries to
automatically separate instances into coherent subsets. As one of the most
well-known clustering algorithms, k-means assigns sample points at the boundary
to a unique cluster, while it does not utilize the information of sample
distribution or density. Comparably, it would potentially be more beneficial to
consider the probability of each sample in a possible cluster. To this end,
this paper generalizes k-means to model the distribution of clusters. Our novel
clustering algorithm thus models the distributions of distances to centroids
over a threshold by Generalized Pareto Distribution (GPD) in Extreme Value
Theory (EVT). Notably, we propose the concept of centroid margin distance, use
GPD to establish a probability model for each cluster, and perform a clustering
algorithm based on the covering probability function derived from GPD. Such a
GPD k-means thus enables the clustering algorithm from the probabilistic
perspective. Correspondingly, we also introduce a naive baseline, dubbed as
Generalized Extreme Value (GEV) k-means. GEV fits the distribution of the block
maxima. In contrast, the GPD fits the distribution of distance to the centroid
exceeding a sufficiently large threshold, leading to a more stable performance
of GPD k-means. Notably, GEV k-means can also estimate cluster structure and
thus perform reasonably well over classical k-means. Thus, extensive
experiments on synthetic datasets and real datasets demonstrate that GPD
k-means outperforms competitors. The github codes are released in
this https URL.

本文基于极值理论的广义帕累托分布，提出了一种新的聚类算法 GPD k-means，它模型化了聚类的距离分布，并用概率模型描述了每个类别。实验证明，在合成数据集和真实数据集上，GPD k-means 优于传统聚类算法。