Evaluation of a Branch and Bound Algorithm for Clustering
Author:
- George DiehrGDGeorge Diehr
- 1 April 1985
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific and Statistical Computing
- Vol. 6 (2) , 268-284
Abstract
A branch and bound algorithm for optimal clustering is developed and applied to a variety of test problems. The objective function is minimization of within-group sum-of-squares although the algorithm can be applied to loss functions which meet certain conditions. The algorithm is based on earlier work of Koontz et. al. (1975). The efficiency of the method for determining optimal solutions is studied as a function of problem size, number of clusters, and underlying degree of separability of the observations. The value of the approach in determining lower bounds is also investigated. We conclude that the method is practical for problems of up to 100 or so observations if the number of clusters is about 6 or less and the clusters are reasonably well separated. If separation is poor and/or a larger number of clusters are sought, the computing time increases significantly. The approach provides very tight lower bounds early in the enumeration for problems with moderate separation and six or fewer clusters.Keywords
This publication has 9 references indexed in Scilit:
- Cluster analysis to determine headache typesJournal of Chronic Diseases, 1982
- Algorithm AS 136: A K-Means Clustering AlgorithmJournal of the Royal Statistical Society Series C: Applied Statistics, 1979
- Complete-Link Cluster Analysis by Graph ColoringJournal of the American Statistical Association, 1978
- A Branch and Bound Clustering AlgorithmIEEE Transactions on Computers, 1975
- Cluster Analysis and Mathematical ProgrammingJournal of the American Statistical Association, 1971
- A Dynamic Programming Algorithm for Cluster AnalysisOperations Research, 1969
- Integer Programming and the Theory of GroupingJournal of the American Statistical Association, 1969
- Branch-and-Bound Methods: A SurveyOperations Research, 1966
- On Grouping for Maximum HomogeneityJournal of the American Statistical Association, 1958