A DETERMINISTIC ANNEALING APPROACH TO CLUSTERING

A deterministic annealing technique is proposed for the nonconvex optimization problem of clustering. Deterministic annealing is used in order to avoid local minima of the given cost function which trap traditional techniques. A set of temperature parametrized Gibbs probability density functions relate each data point to each cluster. An effective cost function is defined and minimized at each temperature. It is shown that as the temperature approaches zero, the algorithm becomes the basic ISODATA algorithm. The method is independent of the initial choice of cluster means. Simulation results are given and show how the method succeeds in avoiding local minima. © 1990.