<p>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.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Convex Clustering: Convexity, Bounding Balls and Characteristics

  • Canh Hao Nguyen,
  • Hiroshi Mamitsuka

摘要

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.