A1389
Title: Scalable convex clustering with adaptive sparse weights
Authors: Mauro Bernardi - University of Padova (Italy) [presenting]
Antonio Canale - University of Padua (Italy)
Marco Stefanucci - University of Rome Tor Vergata (Italy)
Abstract: Convex clustering estimates cluster centroids by penalizing pairwise differences among them, yielding a regularization path that progressively merges individual observations into a single cluster. The effectiveness and computational efficiency of this framework critically depend on the choice of weights associated with the fusion penalties. An efficient alternating direction method of multipliers (ADMM) algorithm for convex clustering under general weighting schemes is introduced, with notable computational advantages in the presence of sparse weights. Beyond improving scalability, sparsity also enhances statistical performance: by restricting fusion penalties to k-nearest-neighbor pairs, the method promotes a localized notion of similarity that leads to improved clustering accuracy. The dual formulation of the general-weight convex clustering problem is derived and exploited to obtain analytical results relevant for both implementation and model selection. In particular, a data-driven strategy for selecting the regularization parameter to recover an interpretable number of clusters is proposed, and a novel expression for the effective degrees of freedom is derived, enabling the direct application of information criteria such as AIC and BIC. Experiments on synthetic and real-world datasets demonstrate that the proposed approach achieves an effective balance between scalability, clustering accuracy, and principled model selection.
