  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.
