Refining k-means by Bootstrap and Data Depth

Many iterative techniques are sensitive to the initial conditions, thus getting stuck in local optima. This paper explores two simple, computationally fast methods that allow the refinement of the initial points of k-means to cluster a given data set. They are based on alternating k-means and the search of the deepest (most representative) point of each cluster, and on the combination of bootstrapped k-means results and the search of the deepest points of each cluster on the space of cluster centers. In addition, this second alternative can be used to provide a soft clustering of the data assigning a cluster belongingness index to each element. The methods are tested in simulated and real data and prove to be efficient and faster than previous proposals