Learning finite Gaussian mixtures using differential evolution

• Autorzy: Kwedlo W.

Warianty tytułu

PL

Uczenie skończonych mieszanin rozkładów normalnych przy pomocy algorytmu ewolucji różnicowej

• Języki publikacji: EN

Abstrakty

EN

In the paper the problem of parameter estimation of finite mixture of multivariate Gaussian distributions is considered. A new approach based on differential evolution (DE) algorithm is proposed. In order to avoid problems with infeasibility of chromosomes our version of DE uses a novel representation, in which covariance matrices are encoded using their Cholesky decomposition. Numerical experiments involved three version of DE differing by the method of selection of strategy parameters. The results of experiments, performed on two synthetic and one real dataset indicate, that our method is able to correctly identify the parameters of the mixture model. The method is also able to obtain better solutions than the classical EM algorithm. Keywords: Gaussian mixtures, differential evolution, EM algorithm.

PL

W artykule rozważono problem uczenia parametrów skończonej mieszaniny wielowymiarowych rozkładów normalnych. Zaproponowano nową metodę uczenia opartą na algorytmie ewolucji różnicowej. W celu uniknięcia problemów z niedopuszczalnością chromosomów algorytm ewolucji różnicowej wykorzystuje nową reprezentację, w której macierze kowariancji są reprezentowane przy pomocy dekompozycji Cholesky’ego. W eksperymentach wykorzystano trzy wersje algorytmu ewolucji różnicowej różniące się metodą˛ doboru parametrów. Wyniki eksperymentów, przeprowadzonych na dwóch syntetycznych i jednym rzeczywistym zbiorze danych, wskazują że zaproponowana metoda jest w stanie poprawnie identyfikować parametry modelu. Metoda ta osiąga również lepsze wyniki niż klasyczyny algorytm EM.

Słowa kluczowe

EN

Gaussian mixtures; differential evolution; EM algorithm

PL

mieszaniny rozkładów normalnych; ewolucja różnicowa; algorytm EM

• Wydawca: Oficyna Wydawnicza Politechniki Białostockiej
• Czasopismo: Zeszyty Naukowe Politechniki Białostockiej. Informatyka
• Rocznik: 2010
• Tom: Z. 5
• Strony: 19--33
• Opis fizyczny: Bibliogr. 20 poz., wykr.

Twórcy

autor

Kwedlo W.

• Politechnika Białostocka, Wydział Informatyki, Białystok

Bibliografia

• [1] A. Asuncion and D. J. Newman. UCI machine learning repository, 2007.
• [2] Hans-Georg Beyer and Hans-Paul Schwefel. Evolution strategies – a comprehensive introduction. Natural Computing, 1(1):3–52, 2002.
• [3] C. M. Bishop. Pattern Recognition and Machine Learning. Springer-Verlag, 2006.
• [4] J. Brest, S. Greiner, B. Boskovic, M. Mernik, and V. Zumer. Self-adapting control parameters in differential evolution: A comparative study on numerical benchmark problems. IEEE Transactions on Evolutionary Computation, 10(6):646–657, 2006.
• [5] U. K. Chakraborty, editor. Advances in Differential Evolution. Springer, 2008.
• [6] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society. Series B, 39(1):1–38, 1977.
• [7] M.A.T. Figueiredo and A.K. Jain. Unsupervised learning of finite mixture models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(3):381–396, 2002.
• [8] R. A. Fisher. The use of multiple measurements in taxonomic problems. Ann. Eugenics, 7:179–188, 1936.
• [9] T. Hastie and R. Tibshirani. Discriminant analysis by Gaussian mixtures. Journal of the Royal Statistical Society. Series B (Methodological), 58(1):155– 176, 1996.
• [10] A. K. Jain and R. C. Dubes. Algorithms for Clustering Data. Prentice-Hall, 1988.
• [11] R.A. Johnson and D.W. Wichern. Applied Multivariate Statistical Analysis. Prentice Hall, 6th edition, 2007.
• [12] A. M. Martinez and J. Vitria. Learning mixture models using a genetic version of the EM algorithm. Pattern Recognition Letters, 21(8):759–769, 2000.
• [13] G. McLachlan and D. Peel. Finite Mixture Models. John Wiley and Sons, 2000.
• [14] Z. Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs. Springer Verlag, 1996.
• [15] F. Pernkopf and D. Bouchaffra. Genetic-based EM algorithm for learning Gaussian mixture models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(8):1344–1348, 2005.
• [16] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. Numerical Recipes: The Art of Scientific Computing. Cambridge University Press, 3rd edition, 2007.
• [17] P. Pudil, J. Novovicova, N. Choakjarernwanit, and J. Kittler. Feature selection based on the approximation of class densities by finite mixtures of special type. Pattern Recognition, 28(9):1389–1398, 1995.
• [18] R. Storn and K. Price. Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4):341–359, 1997.
• [19] N. Ueda, R. Nakano, Z. Ghahramani, and G. E. Hinton. SMEM algorithm for mixture models. Neural Computation, 12(9):2109–2128, 2000.
• [20] J. J Verbeek, N. Vlassis, and B. Kröse. Efficient greedy learning of Gaussian mixture models. Neural Computation, 15(2):469–485, 2003.