Evaluation of a Branch and Bound Algorithm for Clustering
George Diehr · SIAM Journal on Scientific and Statistical Computing · 1985
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.