On Convex Clustering Solutions

2021/05/18 by Canh Hao Nguyen, Nguyen, Canh Hao, Hiroshi Mamitsuka +1
Engineering · Computer Science · Mathematics · #Sparse and Compressive Sensing Techniques #Face and Expression Recognition #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2105.08348

Abstract

Convex clustering is an attractive clustering algorithm with favorable properties such as efficiency and optimality owing to its convex formulation. It is thought to generalize both k-means clustering and agglomerative clustering. However, it is not known whether convex clustering preserves desirable properties of these algorithms. A common expectation is that convex clustering may learn difficult cluster types such as non-convex ones. Current understanding of convex clustering is limited to only consistency results on well-separated clusters. We show new understanding of its solutions. We prove that convex clustering can only learn convex clusters. We then show that the clusters have disjoint bounding balls with significant gaps. We further characterize the solutions, regularization hyperparameters, inclusterable cases and consistency.

Related

• The Why and How of Convex Clustering
• Statistical Properties of Convex Clustering
• Convex Clustering Redefined: Robust Learning with the Median of Means Estimator
• Convex Clustering through MM: An Efficient Algorithm to Perform Hierarchical Clustering
• Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm