Abstract: After analyzing the disadvantages of initialization sensitive and local maximum of the K-medians algorithm, this paper proposes a novel K-medians clustering based on Particle Swarm Optimization（PSO） algorithm and density initialization. The Initialization of the algorithm is that, it chooses k candidate ranges which are far apart as the selection range for the k cluster centers, that is, the initial values of the particles are included in the k ranges. Through PSO clustering center, to solve the problem of the K-medians algorithm caused by the cluster center iteration is more complex due to the time complexity is higher. Experimental results show that this algorithm has higher accuracy, smaller time complexity, and more stable overall performance.

Key words: Particle Swarm Optimization（PSO）, K-medians algorithm, density initialization, clustering

摘要： 针对K-中心点算法对初始化敏感和容易陷入局部极值的缺点，提出一种基于粒子群算法和密度初始化改进的K-中心点聚类算法。该算法初始化时选择距离较远的k个候选范围作为k个聚类中心的选择范围，即粒子的初始值都在该k个范围内。通过粒子群算法优化聚类中心，以解决K-中心点算法因为聚类中心迭代计算较为复杂而导致的时间复杂度较高的问题。实验结果表明，该算法具有较高的正确率，较小的时间复杂度，综合性能更加稳定。

关键词: 粒子群算法, K-中心点算法, 密度初始化, 聚类