Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

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

A Repetitive Branch-and-Bound Procedure for Minimum Within-Cluster Sums of Squares Partitioning 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Psychometrika Springer Journals

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

Psychometrika , Volume 71 (2) – Feb 11, 2017

Loading next page...
 
/lp/springer-journals/a-repetitive-branch-and-bound-procedure-for-minimum-within-cluster-kABKbqUiRP

References (47)

Publisher
Springer Journals
Copyright
Copyright © 2006 by Springer Science + Business Media, Inc.
Subject
Psychology; Psychometrics; Assessment, Testing and Evaluation; Statistics for Social Science, Behavorial Science, Education, Public Policy, and Law; Statistical Theory and Methods
ISSN
0033-3123
eISSN
1860-0980
DOI
10.1007/s11336-004-1218-1
Publisher site
See Article on Publisher Site

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.

Journal

PsychometrikaSpringer Journals

Published: Feb 11, 2017

There are no references for this article.