A Repetitive Branch-and-Bound Procedure for Minimum Within-Cluster Sums of Squares Partitioning

Autor/in	Brusco, Michael J.
Titel	A Repetitive Branch-and-Bound Procedure for Minimum Within-Cluster Sums of Squares Partitioning
Quelle	In: Psychometrika, 71 (2006) 2, S.347-363 (17 Seiten) PDF als Volltext Verfügbarkeit
Sprache	englisch
Dokumenttyp	gedruckt; online; Zeitschriftenaufsatz
ISSN	0033-3123
DOI	10.1007/s11336-004-1218-1
Schlagwörter	Multivariate Analysis; Evaluation Criteria; Heuristics; Problem Solving; Data Analysis + Suchen Sie Ihr Suchwort? Multivariate Analyse; Heuristik; Problemlösen; Auswertung
Abstract	Minimization of the within-cluster sums of squares (WCSS) is one of the most important optimization criteria in cluster analysis. Although cluster analysis modules in commercial software packages typically use heuristic methods for this criterion, optimal approaches can be computationally feasible for problems of modest size. This paper presents a new branch-and-bound algorithm for minimizing WCSS. Algorithmic enhancements include an effective reordering of objects and a repetitive solution approach that precludes the need for splitting the data set, while maintaining strong bounds throughout the solution process. The new algorithm provided optimal solutions for problems with up to 240 objects and eight well-separated clusters. Poorly separated problems with no inherent cluster structure were optimally solved for up to 60 objects and six clusters. The repetitive branch-and-bound algorithm was also successfully applied to three empirical data sets from the classification literature. (Author).
Anmerkungen	Springer. 233 Spring Street, New York, NY 10013. Tel: 800-777-4643; Tel: 212-460-1500; Fax: 212-348-4505; e-mail: service-ny@springer.com; Web site: http://www.springerlink.com
Erfasst von	ERIC (Education Resources Information Center), Washington, DC
Update	2017/4/10