Convex Clustering through MM: An Efficient Algorithm to Perform Hierarchical Clustering
This work addresses the problem of scaling convex clustering to large datasets for researchers and practitioners in data analysis, representing an incremental improvement.
The paper tackles the scalability and hierarchical structure issues of convex clustering by proposing the CCMM algorithm, which efficiently handles over one million objects in seven-dimensional space with an average solution time of 51 seconds.
Convex clustering is a modern method with both hierarchical and $k$-means clustering characteristics. Although convex clustering can capture complex clustering structures hidden in data, the existing convex clustering algorithms are not scalable to large data sets with sample sizes greater than several thousands. Moreover, it is known that convex clustering sometimes fails to produce a complete hierarchical clustering structure. This issue arises if clusters split up or the minimum number of possible clusters is larger than the desired number of clusters. In this paper, we propose convex clustering through majorization-minimization (CCMM) -- an iterative algorithm that uses cluster fusions and a highly efficient updating scheme derived using diagonal majorization. Additionally, we explore different strategies to ensure that the hierarchical clustering structure terminates in a single cluster. With a current desktop computer, CCMM efficiently solves convex clustering problems featuring over one million objects in seven-dimensional space, achieving a solution time of 51 seconds on average.