New Global Optimization Algorithms and Implementations for Model-Based Clustering

The Expectation-Maximization (EM) algorithm is a very popular optimization tool in model-based clustering problems. However, while the algorithm is convenient to implement, it only produces solutions that are locally optimal, and thus may not achieve the globally optimal solution. This paper introduces several new algorithms designed to produce global solutions in model-based clustering problems. The building blocks for these algorithms are methods from the operations research community, namely the Cross-Entropy (CE) method and Model Reference Adaptive Search (MRAS). One problem with applying these algorithms directly is the ecient simulation of positive denite covariance matrices. We propose several solutions to this problem. One solution is to apply the principles of EM, 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 to evaluate the eectiveness of the proposed algorithms in comparison to classical EM. We nd that although a single run of the new algorithms is slower than EM, they have the potential of producing signicantly better global solutions to the model-based clustering problem.