Abstract: The clustering problems based on minimizing the sum of intra-cluster squared-error are known to be NP-hard. I}he iterative relocating method using by K-Means is essentially a kind of local hill-climbing algorithm, which will find a locally minimal solution eventually and cause much sensitivity to initial representatives. The meta-heuristic strategy was introduced to minimize the squared-error criterion globally. Firstly, an evaluation function was built to approximate the dependency between a series of initial representatives of K-Means and the local minimal of objective criterion,and then the selection of initial representatives was done under the supervision of the evaluation function for the next K-Means. This iterative and self-learning process is called Meta KMeans algorithm. The experimental demonstrations show that Meta K-Means can overcome the sensitivity to initial representatives of K-Means to a great extent.

Key words: K-Means algorithm, Metaheuristic, Iterative self-learning framework