Cluster Analysis for Large Datasets: An Effective Algorithm for Maximizing the Mixture Likelihood
Authors:
- 1 December 2000
- journal article
- research article
- Published by Taylor & Francis in Journal of Computational and Graphical Statistics
- Vol. 9 (4) , 672-688
Abstract
The primary model for cluster analysis is the latent class model. This model yields the mixture likelihood. Due to numerous local maxima, the success of the EM algorithm in maximizing the mixture likelihood depends on the initial starting point of the algorithm. In this article, good starting points for the EM algorithm are obtained by applying classification methods to randomly selected subsamples of the data. The performance of the resulting two-step algorithm, classification followed by EM, is compared to, and found superior to, the baseline algorithm of EM started from a random partition of the data. Though the algorithm is not complicated, comparing it to the baseline algorithm and assessing its performance with several classification methods is nontrivial. The strategy employed for comparing the algorithms is to identify canonical forms for the easiest and most difficult datasets to cluster within a large collection of cluster datasets and then to compare the performance of the two algorithms on these datasets. This has led to the discovery that, in the case of three homogeneous clusters, the most difficult datasets to cluster are those in which the clusters are arranged on a line and the easiest are those in which the clusters are arranged on an equilateral triangle. The performance of the two-step algorithm is assessed using several classification methods and is shown to be able to cluster large, difficult datasets consisting of three highly overlapping clusters arranged on a line with 10,000 observations and 8 variables.Keywords
This publication has 16 references indexed in Scilit:
- Identification of Outliers in Multivariate DataJournal of the American Statistical Association, 1996
- A classification EM algorithm for clustering and two stochastic versionsComputational Statistics & Data Analysis, 1992
- Maximum Likelihood Estimation of the Parameters in a Mixture of Two Univariate Normal Distributions; A Comparison of Different AlgorithmsJournal of the Royal Statistical Society: Series D (The Statistician), 1984
- Fitting straight lines to point patternsPattern Recognition, 1984
- Clustering Criteria and Multivariate Normal Mixtures1981
- Asymptotic behaviour of classification maximum likelihood estimatesBiometrika, 1978
- 389: Separating Mixtures of Normal Distributions1975
- Clustering Methods Based on Likelihood Ratio Criteria1971
- A generalized two-sample Wilcoxon test for doubly censored dataBiometrika, 1965
- Hierarchical Grouping to Optimize an Objective FunctionJournal of the American Statistical Association, 1963