Using global optimization to explore multiple solutions of clustering problems

A classical approach to clustering consists in running an algorithm aimed to minimize the distortion. Apart from very limited and simple cases such problem cannot be solved by a local search algorithm because of multiple local minima. In this paper a Global Optimization (GO) algorithm is used to overcome such difficulty. The proposed algorithm (Controlled Random Search) iterates by maintaining a population of solutions which tends to concentrate around the most "promising" areas. From Data Mining point of view such an approach enables to infer deep information about the underlying structure of data. Collecting and presenting such information in a human understandable manner can help the choice between several possible alternatives. Numerical experiments are carried out on a real dataset, showing that GO produces solutions with much better distortion values than the classical approach, while graphical representation of the whole solution set can be useful to data exploration. © 2008 Springer-Verlag Berlin Heidelberg.