Abstract: The K-medoids algorithm has the disadvantage of global search ability and large amount of the iterative calculation, this paper proposes an improved rough K-medoids algorithm based on Particle Swarm Optimization（PSO）. By introducing PSO to strengthen its global search ability and calculating the dissimilarity matrix of sample set to simplify coding particle swarm, the rough set theory provides a processing method of dealing with the indeterminacy problem of boundary objects. It uses memorization technique to improve K-medoids iterative calculation, to reduce the complexity of the algorithm. Through testing the Iris, Mushroom data set of UCI, the new algorithm’s accuracy is improved and the time is shortened.

Key words: K-medoids algorithm, particle swarm optimization, dissimilarity matrix, rough set, memorization

摘要： 针对K-medoids算法的全局搜索能力弱和迭代计算过程计算量大的不足，提出了一种改进的基于粒子群的粗糙K-medoids算法。该算法通过粒子群算法来改善K-medoids全局搜索能力，通过计算样本集的相异度矩阵来简化粒子群编码，引入粗糙集理论处理边界模糊数据，并利用记忆技术对K-medoids的迭代过程进行优化，降低算法的复杂度。通过对UCI中的Iris、Mushroom数据集测试，该算法的准确率提高，运行时间减少。

关键词: K-medoids算法, 粒子群算法, 相异度矩阵, 粗糙集, 记忆技术