Part of Advances in Neural Information Processing Systems 16 (NIPS 2003)
David Kauchak, Sanjoy Dasgupta
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.