宋红海 颜宏文

摘 要：K-medoids算法具有对初始聚类中心敏感，聚类准确度不高及时间复杂度大的缺点。基于此，文中提出一种优化的K-medoids算法；该算法在已有的粒计算初始化基础上进行了改进，以对象之间的相似性作为判断依据，结合最大最小法初始化聚类中心，能有效地获取最佳或近似最佳的聚类中心；在优化的粒计算前提下，提出了基于微粒子动态搜索策略，以初始中心点作为基点，粒子内所有对象到其中心的平均距离为半径，形成一个微粒子；在微粒子内部，采用离中心点先近后远的原则进行搜索，能有效地缩小搜索范围，提高聚类准确率。实验结果表明：在UCI多个标准数据集中测试，且与其他改进的K-medoids算法比较分析，该算法在有效缩短收敛时间的同时保证了算法聚类准确率。

关键字：聚类；K-medoids算法；粒计算；相似性；微粒子动态搜索

文献标志码： A 中图分类号：TP301.6文章编号：2095-2163（2016）02-

Novel K-medoids clustering algorithm based on dynamic search of Microparticlesunder optimizedgranular computing

SONG Honghai，YAN Hongwen

（ Institute of Computer and Communication Engineering， Changsha University of Sciences and Technology， Changsha Hunan 410114， China）

Abstract：The K-medoids algorithm has the disadvantage of sensitivity to cluster center initialization， low clustering accuracyand high the time complexity. So this paper proposes an optimized K-medoids algorithm； this algorithm has been initialized on the basis of granular computing which takes the similarity between objects as the basis to judge， and combined with the maximum and minimum cluster center initialization method the best or near-best cluster centercan be effectively accessed； Under the precondition of optimization of granular computing， the paper puts forward the dynamic search strategy based on the microparticles， the initial center as a base， all objects within the particles to an average distance of the center of the radius， form a microparticle； In microparticles inside， using the first after nearly far from the center of the principle of search， can effectively narrow the search， increase the clustering accuracy. Tested on a number of standard data sets in UCIand compared with other improved K-medoids algorithm， the experimental results show that this new algorithm reuduces the convergence time effectively and improves the accuracy of clustering.

Key word：clustering； K-medoids algorithm； granular computing；similarity； microparticles dynamic search

0 引言

聚类就是将拥有不同属性的事物划分成不同类的过程，不依赖于先验信息，只需考虑数据本身的特征属性以及数据间的相互关系[1]，同一类内的事物属性具有高质的相似性，不同类之间的属性则具有高度不相似性。作为一种重要的数据分析方法，聚类已经成为一种实用开发工具，广泛地应用到数据挖掘、模式识别、信息检索和图像处理等领域。

在时下经典的聚类算法中，K-medoids算法具有了较为普遍应用性。算法优点是实现思想简单，搜索能力强等，但也存在对初始化聚类中心敏感，时间复杂度较高，精确度不高等问题。……