Hostname: page-component-599cfd5f84-2stsh Total loading time: 0 Render date: 2025-01-07T07:05:17.509Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  01 January 2025

Michael J. Brusco
Michael J. Brusco*
Affiliation:
Florida State University
*
Requests for reprints should be sent to Michael J. Brusco, Marketing Department, College of Business, Florida State University, Tallahassee, FL 32306-1110. Voice: (850)644-6512, FAX: (850)644-4098. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Keywords

combinatorial data analysiscluster analysisK-meansbranch and bound
Type
Original Paper
Information
Psychometrika , Volume 71 , Issue 2 , June 2006 , pp. 347 - 363
Copyright
Copyright © 2006 The Psychometric Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Anderberg, M.R. (1973). Cluster analysis for applications. New York: Academic Press.Google Scholar
Anderson, E. (1935). The irises of the Gaspé peninsula. Bulletin of the American Iris Society, 59, 2–5.Google Scholar
Arabie, P., & Hubert, L.J. (1992). Combinatorial data analysis. Annual Review of Psychology, 43, 169–203.CrossRefGoogle Scholar
Arabie, P., & Hubert, L.J. (1996). An overview of combinatorial data analysis. In Arabie, P., Hubert, L.J., & De Soete, G. (Eds.), Clustering and classification (pp. 5–63). River Edge, NJ: World Scientific.CrossRefGoogle Scholar
Blashfield, R.K., & Aldenferer, M.S. (1988). The methods and problems of cluster analysis. In Nesselroade, J.R., Cattell, R.B. (Eds.), Handbook of multivariate experimental psychology 2nd ed., (pp. 447–473). New York: Plenum.CrossRefGoogle Scholar
Brusco, M.J. (2002). A branch-and-bound algorithm for fitting anti-Robinson structures to symmetric dissimilarity matrices. Psychometrika, 67, 459–471.CrossRefGoogle Scholar
Brusco, M.J. (2003). An enhanced branch-and-bound algorithm for a partitioning problem. British Journal of Mathematical and Statistical Psychology, 56, 83–92.CrossRefGoogle ScholarPubMed
Brusco, M.J., & Stahl, S. (2005). Branch-and-bound applications in combinatorial data analysis. New York: Springer-Verlag.Google Scholar
Clapham, C. (1996). The concise Oxford dictionary of mathematics 2nd ed., Oxford, UK: Oxford University Press.Google Scholar
Day, W.H.E. (1996). Complexity theory: An introduction for practitioners of classification. In Arabie, P., Hubert, L.J., & De Soete, G. (Eds.), Clustering and classification (pp. 199–233). River Edge, NJ: World Scientific.CrossRefGoogle Scholar
DeCani, J.S. (1972). A branch and bound algorithm for maximum likelihood paired comparison ranking by linear programming. Biometrika, 59, 131–135.CrossRefGoogle Scholar
Defays, D. (1978). A short note on a method of seriation. British Journal of Mathematical and Statistical Psychology, 31, 49–53.CrossRefGoogle Scholar
Diehr, G. (1985). Evaluation of a branch and bound algorithm for clustering. SIAM Journal for Scientific and Statistical Computing, 6, 268–284.CrossRefGoogle Scholar
Du Merle, O., Hansen, P., Jaumard, B., & Mladenović, N. (2000). An interior point algorithm for minimum sum-of-squares clustering. SIAM Journal on Scientific Computing, 21, 1485–1505.CrossRefGoogle Scholar
Edwards, A.W.F., & Cavalli-Sforza, L.L. (1965). A method for cluster analysis. Biometrics, 21, 362–375.CrossRefGoogle ScholarPubMed
Fisher, R.A. (1936). The use of multiple measurements in taxonomic problems. Annals of Eugenics, 7, 179–188.CrossRefGoogle Scholar
Fisher, W.D. (1958). On grouping for maximum heterogeneity. Journal of the American Statistical Association, 53, 789–798.CrossRefGoogle Scholar
Flueck, J.A., & Korsh, J.F. (1974). A branch search algorithm for maximum likelihood paired comparison ranking. Biometrika, 61, 621–626.CrossRefGoogle Scholar
Forgy, E.W. (1965). Cluster analyses of multivariate data: Efficiency versus interpretability of classifications. Biometrics, 21, 768.Google Scholar
Furnival, G.M., & Wilson, R.W. (1974). Regression by leaps and bounds. Technometrics, 16, 499–512.CrossRefGoogle Scholar
Hair, J.F., Anderson, R.E., Tatham, R. L., & Black, W. C. (1998). Multivariate data analysis 5th ed., Upper Saddle River, NJ: Prentice Hall.Google Scholar
Hand, D.J. (1981a). Discrimination and classification. New York: Wiley.Google Scholar
Hand, D.J. (1981b). Branch and bound in statistical data analysis. The Statistician, 30, 1–13.CrossRefGoogle Scholar
Hartigan, J.A. (1975). Clustering algorithms. New York: Wiley.Google Scholar
Hartigan, J.A., & Wong, M.A. (1979). Algorithm AS136: A k-means clustering program. Applied Statistics, 28, 100–128.CrossRefGoogle Scholar
Hubert, L., Arabie, P., & Meulman, J. (2001). Combinatorial data analysis: Optimization by dynamic programming. Philadelphia: Society for Industrial and Applied Mathematics.CrossRefGoogle Scholar
Jensen, R.E. (1969). A dynamic programming algorithm for cluster analysis. Operations Research, 17, 1034–1057.CrossRefGoogle Scholar
Klein, G., & Aronson, J.E. (1991). Optimal clustering: A model and method. Naval Research Logistics, 38, 447–461.3.0.CO;2-0>CrossRefGoogle Scholar
Koontz, W.L.G., Narendra, P.M., & Fukunaga, K. (1975). A branch and bound clustering algorithm. IEEE Transaction on Computers, C-24, 908–915.CrossRefGoogle Scholar
Luce, R.D., & Krumhansl, C. (1988). Measurement, scaling, and psychophysics. In Atkinson, R.C., Hernnstein, R.J., Lindzey, G., & Luce, R.D. (Eds.), Stevens' handbook of experimental psychology (pp. 3–74). New York: Wiley.Google Scholar
MacQueen, J.B. (1967). Some methods for classification and analysis of multivariate observations. In Le Cam, L.M., & Neyman, J. (Eds.), Proceedings of the fifth Berkeley symposium on mathematical statistics and probability (Vol. 1, pp. 281–297). Berkeley, CA: University of California Press.Google Scholar
Miller, K.F. (1987). Geometric methods in developmental research. In Bisanz, J., Brainerd, C.J., & Kail, R. (Eds.), Formal methods in developmental psychology (pp. 216–262). New York: Springer-Verlag.CrossRefGoogle Scholar
Milligan, G.W. (1980). An examination of the effect of six types of error perturbation on fifteen clustering algorithms. Psychometrika, 45, 325–342.CrossRefGoogle Scholar
Murtaugh, F. (2003). Classification literature automated search service (Vol. 23–31, pp. 1994–2002). Chicago: Classification Society of North America.Google Scholar
Narendra, P.M., Fukunaga, K. (1977). A branch and bound algorithm for feature subset selection. IEEE Transactions on Computers C, 26, 917–922.CrossRefGoogle Scholar
Palubeckis, G. (1997). A branch-and-bound approach using polyhedral results for a clustering problem. INFORMS Journal on Computing, 9, 30–42.CrossRefGoogle Scholar
Rao, M.R. (1971). Cluster analysis and mathematical programming. Journal of the American Statistical Association, 66, 622–626.CrossRefGoogle Scholar
Späth, H. (1980). Cluster analysis algorithms for data reduction and classification of objects. New York: Wiley.Google Scholar
Steinley, D. (2003). Local optima in K-means clustering: What you don't know may hurt you. Psychological Methods, 8, 294–304.CrossRefGoogle ScholarPubMed
Van Os, B.J., & Meulman, J.J. (2004). Improving dynamic programming strategies for partitioning. Journal of Classification, 21, 207–230.CrossRefGoogle Scholar
Ward, J.H. (1963). Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58, 236–244.CrossRefGoogle Scholar