关键词: 聚类, K-means算法, 遗传算法

Abstract: A good K-means clustering algorithm should meet two requirements at least.First，it can reflect the validity of clustering，in other words，clustering number consistents with the practical problems.Second，it has the ability to handle the noise.The traditional K-means algorithm is a local search algorithm，which is sensitive to initialization and easy to search a local maximum.To address this shortcoming，a new K-means algorithm is proposed to optimize the initial center.The algorithm finds k data objects，all of which are belong to high density area and the most far away to each other.Experiments show that the algorithm has not only the weak dependence on initial data，but also fast convergence and high clustering quality.To realize the validity of clustering and get clustering results of higher accuracy，the paper proposes a hybrid algorithm，which combines the optimal K-means algorithm and the genetic algorithm.The algorithm can automatically get the optimal value of k with high compact clusters and large separation between at least two clusters，and optimal k initial center in order to get better clustering，then continue to search iteratively to get the optimal solution.Experiments show that the hybrid method has better clustering quality and general performance.

Key words: clustering, K-means algorithm, genetic algorithm