FAST AND EFFICIENT MODEL-BASED CLUSTERING WITH THE ASCENT-EM ALGORITHM

Abstract In this paper we propose an efficient and fast EM algorithm for model-based clustering of large databases. Drawing ideas from its stochastic descendant, the Monte Carlo EM algorithm, the method uses only a sub-sample of the entire database per iteration. Starting with smaller samples in the earlier iterations for computational efficiency, the algorithm increase the sample size intelligently to-wards the end of the algorithm to assure maximum accuracy of the results. The intelligent sample size updating rule is centered around EM’s highly-appraised likelihood-ascent property and only increases the sample when no further im-provements are possible based on the current sample. In several simulation studies we show the superiority of Ascent-EM over regular EM implementa-tions. We apply the method to an example of clustering online auctions