Minimizing stochastic complexity using local search and GLA with applications to classification of bacteria

In this paper, we compare the performance of two iterative clustering metho ds when applied to an extensive data set describing strains of the bacteria l family Enterobacteriaceae. In both methods, the classification (i.e. the number of classes and the partitioning) is determined by minimizing stochas tic complexity. The first method performs the minimization by repeated appl ication of the generalized Lloyd algorithm (GLA). The second method uses an optimization technique known as local search (LS). The method modifies the current solution by making global changes to the class structure and it, t hen, performs local fine-tuning to find a local optimum. II is observed tha t if we fix the number of classes, the LS finds a classification with a low er stochastic complexity value than GLA. In addition, the valiance of the s olutions is much smaller for the LS due to its more systematic method of se arching. Overall, the two algorithms produce similar classifications but th ey merge cel tain natural classes with microbiological relevance in differe nt ways. (C) 2000 Elsevier Science Inland Ltd. All rights reserved.