New global optimization algorithms for model-based clustering

The Expectation-Maximization (EM) algorithm is a very popular optimization tool for mixture problems and in particular for model-based clustering problems. However, while the algorithm is convenient to implement and numerically very stable, it only produces local solutions. Thus, it may not achieve the globally optimal solution in problems that have a large number of local optima. This paper introduces several new algorithms designed to produce global solutions in model-based clustering. The building blocks for these algorithms are methods from the operations research literature, namely the Cross-Entropy (CE) method and Model Reference Adaptive Search (MRAS). One problem with applying these methods directly is the efficient simulation of positive definite covariance matrices. We propose several new solutions to this problem. One solution is to apply the principles of Expectation-Maximization updating, which leads to two new algorithms, CE-EM and MRAS-EM. We also propose two additional algorithms, CE-CD and MRAS-CD, which rely on the Cholesky decomposition. We conduct numerical experiments of varying complexity to evaluate the effectiveness of the proposed algorithms in comparison to classical EM. We find that although a single run of the new algorithms is slower than a single run of EM, all have the potential for producing significantly better solutions. We also find that although repeat application of EM may achieve similar results, our algorithms provide automated, data-driven decision rules which may significantly reduce the burden of searching for the global optimum. (C) 2009 Elsevier B.V. All rights reserved.