Abstract: To deal with the problem of premature convergence of the traditional K-means algorithm, a novel K-means cluster method based on the enhanced Particle Swarm Optimization(PSO) algorithm is presented. In this approach, the stochastic mutation operation is introduced into the PSO evolution, which reinforces the exploitation of global optimum of the PSO algorithm. In order to avoid the premature convergence and speed up the convergence, traditional K-means algorithm is used to explore the local search space more efficiently dynamically according to the variation of the particle swarms fitness variance. Comparison of the performance of the proposed approach with the cluster method based on K-means, traditional PSO algorithm and other PSO-K-means algorithm is experimented. The experimental results show the proposed method can not only effectively solve the premature convergence problem, but also significantly speed up the convergence.