An Iterative Improvement Procedure for Hierarchical Clustering

We describe a procedure which finds a hierarchical clustering by hill- climbing. The cost function we use is a hierarchical extension of the k-means cost; our local moves are tree restructurings and node reorder- ings. We show these can be accomplished efficiently, by exploiting spe- cial properties of squared Euclidean distances and by using techniques from scheduling algorithms.