| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Genetic-Based EM Algorithm for Learning Gaussian Mixture Models
August 2005 (vol. 27 no. 8)
pp. 1344-1348
We propose a genetic-based expectation-maximization (GA-EM) algorithm for learning Gaussian mixture models from multivariate data. This algorithm is capable of selecting the number of components of the model using the minimum description length (MDL) criterion. Our approach benefits from the properties of Genetic algorithms (GA) and the EM algorithm by combination of both into a single procedure. The population-based stochastic search of the GA explores the search space more thoroughly than the EM method. Therefore, our algorithm enables escaping from local optimal solutions since the algorithm becomes less sensitive to its initialization. The GA-EM algorithm is elitist which maintains the monotonic convergence property of the EM algorithm. The experiments on simulated and real data show that the GA-EM outperforms the EM method since: 1) We have obtained a better MDL score while using exactly the same termination condition for both algorithms. 2) Our approach identifies the number of components which were used to generate the underlying data more often than the EM algorithm.
[1] 1344 T. Bäck, Evolutionary Algorithms in Theory and Practice. Oxford Univ. Press, 1996.[2] T. Bäck and H. Schwefel, “Evolutionary Computation: An Overview,” Proc. IEEE Conf. Evolutionary Computation, pp. 20-29, 1996.[3] G. Celeux, S. Chrétien, F. Forbes, and A. Mkhadri, “A Component-Wise EM Algorithm for Mixtures,” Technical Report 3746, INRIA, France, 1999.[4] S. Dasgupta, “Learning Mixtures of Gaussian,” Proc. IEEE Symp. Foundations of Computer Science, pp. 634-644, 1999.[5] A. Dempster, N. Laird, and D. Rubin, “Maximum Likelihood Estimation from Incomplete Data via the EM Algorithm,” J. Royal Statistic Soc., vol. 30, no. B, pp. 1-38, 1977.[6] R.O. Duda, P.E. Hart, and D.G. Stork, Pattern Classification. John Wiley & Sons, 2000.[7] M.A.T. Figueiredo and A.K. Jain, “Unsupervised Learning of Finite Mixture Models,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 3, pp. 1-16. Mar. 2002.[8] A.M. Martinez and J. Vitrià, “Learning Mixture Models Using a Genetic Version of the EM Algorithm,” Pattern Recognition Letters, vol. 21 pp. 759-769, 2000.[9] A.M. Martinez and J. Vitrià, “Clustering in Image Space for Place Recognition and Visual Annotations for Human-Roboter Interaction,” IEEE Trans. Systems, Man, and Cybernetics B, vol. 31, no. 5, pp. 669-682, 2001.[10] G. McLachlan and D. Peel, Finite Mixture Models. John Wiley & Sons, 2000.[11] C. Merz, P. Murphy, and D. Aha, “UCI Repository of Machine Learning Databases,” Univ. California, Irvine, www.ics.uci.edu/mlearnMLRepository.html, 1997.[12] Z. Michalewicz and D.B. Fogel, How to Solve It: Modern Heuristics. Springer Verlag, 2000.[13] F. Pernkopf, “Genetic-Based EM Algorithm for Component Selection and Parameter Estimation of Gaussian Mixture Models,” technical report, Graz Univ. of Tech nology, 2004.[14] D. Titterington, A. Smith, and U. Makov, Statistical Analysis of Finite Mixture Distributions. John Wiley & Sons, 1985.[15] N. Ueda, R. Nakano, Z. Ghahramani, and G.E. Hinton, “SMEM Algoritm for Mixture Models,” Neural Computation, vol. 12, no. 9, pp. 2109-2128, 2000.[16] J.J. Verbeek, N. Vlassis, and B.J.A. Kröse, “Efficient Greedy Learning of Gaussian Mixture Models,” Neural Computation, vol. 15, no. 2, pp. 469-485, 2003.[17] L. Xu and M.I. Jordan, “On Convergence Properties of the EM Algorithm for Gaussian Mixtures,” Neural Computation, vol. 8, pp. 129-151, 1996.[18] L. Xu, “Bayesian Ying-Yang Machine, Clustering and Number of Clusters,” Pattern Recognition Letters, vol. 18, pp. 1167-1178, 1997.[19] L. Xu, “BYY Harmony Learning, Structural RPCL, and Topological Self-Organizing on Mixture Models,” Neural Networks, vol. 15, pp. 1125-1151, 2002.
Index Terms:
Index Terms- Unsupervised learning, clustering, Gaussian mixture models, EM algorithm, Genetic algorithm, minimum description length.
Citation:
Franz Pernkopf, Djamel Bouchaffra, "Genetic-Based EM Algorithm for Learning Gaussian Mixture Models," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 27, no. 8, pp. 1344-1348, Aug. 2005, doi:10.1109/TPAMI.2005.162
