15.7.1. Branch and Bound Clustering Algorithms
As already stated in Chapter 5, branch and bound methods compute the globally optimal solution to combinatorial problems, according to a prespecified criterion (cost) function J, overcoming the need for exhaustive search.[8] They are applicable to monotonic criteria. That is, if k vectors of X have been assigned to clusters, the assignment of an extra vector to a cluster does not decrease the value of J.
8 In the sequel we consider only the minimization problem.
We will first attempt to gain some insight into these methods by considering an example. Let us assume that our goal is to find the best way (with respect to a criterion J) in which three vectors can be clustered in two clusters. To this ...
Get Pattern Recognition, 4th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
