Abstract: The traditional K-means algorithm is widely used because of its simplicity and efficiency. However, it is sensitive to the initial point and easy to fall into local optimum. In this paper, we use cosine measure to evaluate the similarity between objects and construct a new fitness function of genetic algorithm and the new convergence criterion for K-means algorithm. Experimental results show that the new method enhances the clustering accuracy and stability for the combination of K-means and genetic algorithm.