An effective strategy for initializing the EM algorithm in finite mixture models. (English) Zbl 1414.62256
Summary: Finite mixture models represent one of the most popular tools for modeling heterogeneous data. The traditional approach for parameter estimation is based on maximizing the likelihood function. Direct optimization is often troublesome due to the complex likelihood structure. The expectation-maximization algorithm proves to be an effective remedy that alleviates this issue. The solution obtained by this procedure is entirely driven by the choice of starting parameter values. This highlights the importance of an effective initialization strategy. Despite efforts undertaken in this area, there is no uniform winner found and practitioners tend to ignore the issue, often finding misleading or erroneous results. In this paper, we propose a simple yet effective tool for initializing the expectation-maximization algorithm in the mixture modeling setting. The idea is based on model averaging and proves to be efficient in detecting correct solutions even in those cases when competitors perform poorly. The utility of the proposed methodology is shown through comprehensive simulation study and applied to a well-known classification dataset with good results.
MSC:
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
References:
| [1] | Azzalini A, Valle DA (1996) The multivariate skew-normal distribution. Biometrika 83:715-726 · Zbl 0885.62062 · doi:10.1093/biomet/83.4.715 |
| [2] | Baudry J-P, Raftery A, Celeux G, Lo K, Gottardo R (2010) Combining mixture components for clustering. J Comput Graph Stat 19:332-353 · doi:10.1198/jcgs.2010.08111 |
| [3] | Biernacki C (2004) Initializing EM using the properties of its trajectories in Gaussian mixtures. Stat Comput 14:267-279 · doi:10.1023/B:STCO.0000035306.77434.31 |
| [4] | Biernacki C, Celeux G, Govaert G (2003) Choosing starting values for the EM algorithm for getting the highest likelihood in multivariate Gaussian mixture models. Comput Stat Data Anal 413:561-575 · Zbl 1429.62235 · doi:10.1016/S0167-9473(02)00163-9 |
| [5] | Bouveyron C, Brunet C (2013) Model-based clustering of high-dimensional data: a review. Comput Stat Data Anal 71:52-78 · Zbl 1471.62032 · doi:10.1016/j.csda.2012.12.008 |
| [6] | Campbell NA, Mahon RJ (1974) A multivariate study of variation in two species of rock crab of genus Leptograsus. Austr J Zool 22:417-425 · doi:10.1071/ZO9740417 |
| [7] | Celebi ME, Kingravi HA, Vela PA (2012) A comparative study of efficient initialization methods for the \[k\] k-means clustering algorithm. Comput Res Reposit. arXiv:1209.1960 |
| [8] | Celeux G, Diebolt J (1985) The SEM algorithm: a probabilistic teacher algorithm derived from the EM algorithm for the mixture problem. Comput Stat 2:73-82 |
| [9] | Chen WC, Maitra R (2015) EMCluster: EM Algorithm for Model-Based Clustering of Finite Mixture Gaussian Distribution, R Package. http://cran.r-project.org/package=EMCluster |
| [10] | Dias J, Wedel M (2004) An empirical comparison of EM, SEM and MCMC performance for problematic Gaussian mixture likelihoods. Stat Comput 14:323-332 · doi:10.1023/B:STCO.0000039481.32211.5a |
| [11] | Forgy E (1965) Cluster analysis of multivariate data: efficiency vs. interpretability of classifications. Biometrics 21:768-780 |
| [12] | Fraley C (1998) Algorithms for model-based gaussian hierarchical clustering. SIAM J Sci Comput 20:270-281 · Zbl 0911.62052 · doi:10.1137/S1064827596311451 |
| [13] | Fraley C, Raftery AE (1998) How many clusters? Which cluster method? Answers via model-based cluster analysis. Comput J 41:578-588 · Zbl 0920.68038 · doi:10.1093/comjnl/41.8.578 |
| [14] | Fraley C, Raftery AE (2002) Model-based clustering, discriminant analysis, and density estimation. J Am Stat Assoc 97:611-631 · Zbl 1073.62545 · doi:10.1198/016214502760047131 |
| [15] | Fraley C, Raftery AE (2006) MCLUST version 3 for R: normal mixture modeling and model-based clustering. Tech. Rep. 504. University of Washington, Department of Statistics, Seattle |
| [16] | Hennig C (2010) Methods for merging Gaussian mixture components. Adv Data Anal Class 4(1):3-34 · Zbl 1306.62141 |
| [17] | Hershey JR, Olsen PA (2007) Approximating the kullback leibler divergence between gaussian mixture models. In: IEEE International Conference on Acoustics, Speech and Signal Processing-ICASSP’07, pp IV-317-IV-320 |
| [18] | Hoeting JA, Madigan DM, Raftery AE, Volinsky CT (1999) Bayesian model averaging: a tutorial. Stat Sci 14:382-417 (with discussion) · Zbl 1059.62525 · doi:10.1214/ss/1009212519 |
| [19] | Hubert L, Arabie P (1985) Comparing partitions. J Classif 2:193-218 · Zbl 0587.62128 · doi:10.1007/BF01908075 |
| [20] | Kaufman L, Rousseuw PJ (1990) Finding Groups in Data. Wiley, New York · Zbl 1345.62009 · doi:10.1002/9780470316801 |
| [21] | Lebret R, Iovleff S, Langrognet F, Biernacki C, Celeux G, Govaert G (2015) Rmixmod: the R package of the model-based unsupervised, supervised, and semi-supervised classification mixmod library. J Stat Softw 67(6). doi:10.18637/jss.v067.i06 |
| [22] | MacQueen J (1967) Some methods for classification and analysis of multivariate observations. Proc Fifth Berkeley Symp 1:281-297 · Zbl 0214.46201 |
| [23] | Madigan D, Raftery AE (1994) Model selection and accounting for model uncertainty in graphical models using Occams window. J Am Stat Assoc 89:1535-1546 · Zbl 0814.62030 · doi:10.1080/01621459.1994.10476894 |
| [24] | Maitra R (2009) Initializing partition-optimization algorithms. IEEE/ACM Trans Comput Biol Bioinf 6:144-157 · doi:10.1109/TCBB.2007.70244 |
| [25] | Maitra R, Melnykov V (2010) Simulating data to study performance of finite mixture modeling and clustering algorithms. J Comput Graph Stat 19:354-376 · doi:10.1198/jcgs.2009.08054 |
| [26] | McLachlan G, Peel D (2000) Finite Mixture Models. Wiley, New York · Zbl 0963.62061 · doi:10.1002/0471721182 |
| [27] | Melnykov V (2013) Challenges in model-based clustering. WIREs Comput Stat 5:135-148 · Zbl 1540.62018 · doi:10.1002/wics.1248 |
| [28] | Melnykov V (2016) Merging mixture components for clustering through pairwise overlap. J Comput Graph Stat 25:66-90 · doi:10.1080/10618600.2014.978007 |
| [29] | Melnykov V, Chen W-C, Maitra R (2012) MixSim: R package for simulating datasets with pre-specified clustering complexity. J Stat Softw 51:1-25 · doi:10.18637/jss.v051.i12 |
| [30] | Melnykov V, Melnykov I (2012) Initializing the EM algorithm in Gaussian mixture models with an unknown number of components. Comput Stat Data Anal 56:1381-1395 · Zbl 1246.65025 · doi:10.1016/j.csda.2011.11.002 |
| [31] | Melnykov V, Melnykov I, Michael S (2015a) Semi-supervised model-based clustering with positive and negative constraints. In: Advances in data analysis and classification, pp 1-23 · Zbl 1414.62255 |
| [32] | Melnykov V, Michael S, Melnykov I (2015b) Recent developments in model-based clustering with applications. In: Celebi ME (ed) Partitional clustering algorithms, vol 1. Springer, Berlin, pp 1-39 · Zbl 1347.62116 |
| [33] | Prates M, Lachos V, Cabral C (2013) Mixsmsn: fitting finite mixture of scale mixture of skew-normal distributions. J Stat Softw 54(12):1-20 |
| [34] | Sneath P (1957) The application of computers to taxonomy. J Gener Microbiol 17:201-226 |
| [35] | Sorensen T (1948) A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons. Biologiske Skrifter 5:1-34 |
| [36] | Stahl D, Sallis H (2012) Model-based cluster analysis. Wiley Interdiscipl Rev Comput Stat 4:341-358 · doi:10.1002/wics.1204 |
| [37] | Ward JH (1963) Hierarchical grouping to optimize an objective function. J Am Stat Assoc 58:236-244 · doi:10.1080/01621459.1963.10500845 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
