Cluster Analysis via Stochastic Approximation Monte Carlo

Abstract

The k-means clustering is one of the simplest unsupervised algorithm used generally in solving clustering problems. However, it may rely on the initial cluster seed and thus it is suffer from the local trap problem due to that its system has multiple local energy minima in a rugged energy landscape. Hence, the global optimal clustering may not be identified. This paper focuses on this problem, and thus we propose to use the Stochastic approximation Monte Carlo(SAMC) algorithm implementing the k-means clustering method to overcome the local trap problem in clustering analysis. SAMC is a general importance sampling and optimization algorithm to search the sample space broadly and escape from the local trap problem regardless of the initial point. The algorithm is tested on simulated and the real dataset, and compared with the k-means clustering algorithm. The numerical results are in favor of SAMC based on the minimization criterion.