Dynamic Visualization and Fast Computation for Convex Clustering via Algorithmic Regularization

Abstract

Convex clustering is a promising new approach to the classical problem of clustering, combining strong performance in empirical studies with rigorous theoretical foundations. Despite these advantages, convex clustering has not been widely adopted, due to its computationally intensive nature and its lack of compelling visualizations. To address these impediments, we introduce Algorithmic Regularization, an innovative technique for obtaining high-quality estimates of regularization paths using an iterative one-step approximation scheme. We justify our approach with a novel theoretical result, guaranteeing global convergence of the approximate path to the exact solution under easily-checked non-data-dependent assumptions. The application of algorithmic regularization to convex clustering yields the Convex Clustering via Algorithmic Regularization Paths (CARP) algorithm for computing the clustering solution path. On example data sets from genomics and text analysis, CARP delivers over a 100-fold speed-up over existing methods, while attaining a finer approximation grid than standard methods. Furthermore, CARP enables improved visualization of clustering solutions: the fine solution grid returned by CARP can be used to construct a convex clustering-based dendrogram, as well as forming the basis of a dynamic path-wise visualization based on modern web technologies. Our methods are implemented in the open-source R package clustRviz, available at https://github.com/DataSlingers/clustRviz.

arXiv commentTo appear in the Journal of Computational and Graphical Statistics

References in corpus (25)

• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Natural Scales in Geographical Patterns
• Nearly unbiased variable selection under minimax concave penalty
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• The solution path of the generalized lasso
• Piecewise linear regularized solution paths
• Splitting Methods for Convex Clustering
• Properties and refinements of the fused lasso
• A General Analysis of the Convergence of ADMM
• Convex Biclustering
• Sparse Convex Clustering
• Convex Clustering: An Attractive Alternative to Hierarchical Clustering
• A Practical Scheme and Fast Algorithm to Tune the Lasso With Optimality Guarantees
• Provable Convex Co-clustering of Tensors
• Solution Path Clustering with Adaptive Concave Penalty
• The proximal distance algorithm

Cited by in corpus (11)

• Integrative Generalized Convex Clustering Optimization and Feature Selection for Mixed Multi-View Data
• Model Agnostic Multilevel Explanations
• Splitting Methods for Convex Bi-Clustering and Co-Clustering
• Automatic Registration and Clustering of Time Series
• An Efficient Smoothing Proximal Gradient Algorithm for Convex Clustering
• Simultaneous Grouping and Denoising via Sparse Convex Wavelet Clustering
• Resistant convex clustering: How does the fusion penalty enhance resistantance?
• Network Clustering for Latent State and Changepoint Detection
• Selective inference after convex clustering with ${\ell }_1$ penalization
• Efficient proximal gradient algorithms for joint graphical lasso
• Supervised Convex Clustering