About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SDM 2011
Conference paper
Sequential minimal optimization in adaptive-bandwidth convex clustering
Abstract
Computing not the local, but the global optimum of a cluster assignment is one of the important aspects in clustering. Convex clustering is an approach to acquire the global optimum, assuming some fixed centers and bandwidths of the clusters. The essence of the convex clustering is a convex optimization of the mixture weights whose optimum becomes sparse. One of the limitations in the convex clustering was the computational inefficiency of the Expectation- Maximization algorithm, where an extremely large number of iterations is required for the convergence. This paper proposes a more efficient optimization algorithm for convex clustering to significantly reduce the required number of iterations. The key ideas in the proposed algorithm are accurate pruning while choosing a pair of kernels and an element-wise Newton-Raphson method for fast convergence of the non-zero mixture weights. The proposed algorithm is further accelerated when incorporating locally adaptive bandwidths of the clusters, which are primarily introduced to improve the predictive capability. Copyright © SIAM.