The classical quadratic k-means clustering algorithm is an iterative procedure that partitions a data set into a prescribed number of clusters. The procedure alternates between the computation of clusters and centroids. In this chapter we exploit the duality between partitions and centroids and focus on searching for a set of centroids that defines an optimal partition. This approach transforms the k-means clustering to minimization of a function of a vector argument and lends itself to application of a wide range of existing optimization tools.

A straightforward translation of the clustering procedure into the optimization problem leads to a nonsmooth objective function F which is difficult to tackle. Instead of dealing with a nonsmooth optimization problem we approximate the nonsmooth function F by a family of smooth functions F _s parametrized by a scalar s (as s ? 0 the approximations converge to the original objective). The special form of the smooth objective F _s leads to a very simple iterative algorithm described by an explicit formula. For a given fixed value of the smoothing parameter s this algorithm produces a sequence of centroids , i = 1 , so that the corresponding sequence , i = 1, is monotonically decreasing and bounded below. The computational complexity of one iteration of the proposed method is about the same as that of the classical k-means clustering algorithm.