title: Annealing and the Normalized N-Cut.
abstract: We describe an annealing procedure that computes the normalized N-cut of a weighted graph G. The first phase transition computes the solution of the approximate normalized 2-cut problem, while the low temperature solution computes the normalized N-cut. The intermediate solutions provide a sequence of refinements of the 2-cut that can be used to split the data to K clusters with 2 </= K </= N. This approach only requires specification of the upper limit on the number of expected clusters N, since by controlling the annealing parameter we can obtain any number of clusters K with 2 </= K </= N. We test the algorithm on an image segmentation problem and apply it to a problem of clustering high dimensional data from the sensory system of a cricket.
authors.affiliation: Department of Mathematical Sciences, Montana State University, Bozeman, MT 59715, USA.
authors.forename: Tomáš
authors.initials: T
authors.lastname: Gedeon
authors.forename: Albert E
authors.initials: AE
authors.lastname: Parker
authors.forename: Collette
authors.initials: C
authors.lastname: Campion
authors.forename: Zane
authors.initials: Z
authors.lastname: Aldworth