On Convex Clustering: Convexity, Bounding Balls and Characteristics
摘要
Convex clustering is an attractive clustering algorithm with favorable properties such as efficiency and optimality owing to its convex formulation. It is thought to relax the formulations of both k-means and agglomerative clustering. However, it remains unknown if convex clustering preserves desirable properties of these algorithms, including the effectiveness of k-means and the flexibility to learn nonconvex clusters of agglomerative clustering. Studies on convex clustering’s properties have focused on only consistency results on well-separated clusters. In this work, we characterize in detail the clusters learnt by convex clustering. We show that convex clustering can only learn convex clusters, enclosed by bounding balls with significant gaps among them. Additionally, we determine the range of the hyperparameter for obtaining nontrivial solutions. Our results show that the clusters learnt by convex clustering have significant differences from those by k-means and agglomerative clustering.