基于密度RPCL的K.medoids算法

摘 要：针对K.medoids算法需要事先给定聚类数目和初始聚类中心的问题，借助次胜者受罚竞争学习算法RPCL确定数据集的类簇数目，提出以密度RPCL作为预处理步骤的K.medoids聚类算法。通过密度RPCL算法对数据集进行处理，从而确定K.medoids算法的合理类簇数目，然后再运行改进K.medoids算法，由此提高K.medoids算法的聚类效率和聚类准确性。采用UCI机器学习数据库数据集进行实验测试，使用不同的聚类结果评价指标对实验结果进行分析，证明本文基于密度RPCL的K.medoids算法具有很好的聚类效果。

关键词：RPCL算法；K.medoids算法；密度；聚类数目；初始中心

聚类算法是模式识别、机器学习和数据挖掘等领域中一个重要的研究内容，该算法根据一定的相似性准则将样本聚集为若干个类簇。

K.medoids算法是基于划分的聚类算法，该算法用类中心的数据作为中心点来代表类。[1]Park 等人提出一种快速K.medoids 算法，在初始中心点的选择和更新聚类中心上有了改进[2]；自行提出改进K.medoids 算法，使所选的初始中心点位于数据集中样本分布密集区域，并且所选初始中心之间的空间距离较远，目的使其位于不同的类簇中。[3]

本文借助于基于密度的次者受罚竞争学习算法[4.6] （RPCL） 来确定最佳的聚类数目值，在此基础上运行改进的K.medoids 算法，从而改善聚类效果。通过UCI 机器学习数据库数据集实验测试，表明基于密度RPCL 的K.medoids 算法具有非常好的聚类效果。

1 密度RPCL算法

竞争学习算法 （Rival Penalized Competitive Learning，RPCL）[4]可以用于确定数据集的类簇数目值，[5.7]但RPCL算法在学习时对学习率和遗忘率非常敏感。[4]在权值调整中RPCL算法只考虑了输入数据和权矢量间相对位置的影响，却忽略了数据集几何结构的影响。权值的调整就是数据对象对获胜单元和次胜单元产生作用力，且使它们发生位移。获胜单元和次胜单元的位移，不仅仅和数据样本间的相对位置有关，还与数据样本在整个数据集中的几何位置有关。基于此，魏丽梅等[6]引入样本密度，改进了RPCL 算法调整权值的方法。但是该算法定义数据密度时需选择部分参数，缺乏客观性。

为克服传统RPCL算法的不足，基于密度的RPCL算法[7]根据数据集样本的自然分布为每个样本定义密度，将该密度引入到节点权值调节公式，对各节点权矢量进行调节，得到密度RPCL算法。[7]

2 基于密度RPCL 的K.medoids算法

基于密度RPCL 的K.medoids算法利用密度RPCL算法[7]对数据集进行预处理，然后运行改进K.medoids算法[3]而得到聚类结果。算法步骤描述如下。

Step1：由密度RPCL算法得到K.medoids算法的K值。

Step2：初始化中心点：首先计算数据集中数据样本的密度值，将数据对象按照密度值升序排序；选择密度值最小的数据作为中心点，并且从数据集中删去该对象。计算该中心点的邻域，从数据集中删去其邻域中的对象；用同样方法选出K个初始中心点。

Step3：更新所有的类簇中心：把数据对象分配给距离最近的中心点，为每一类寻找一个新的中心点，使聚类误差平方和最小。

Step4：再次分配数据直至聚类误差平方和没有变化，算法结束；否则转Step3。

3 实验结果分析

通过UCI数据集测试本文基于密度RPCL 的改进K.medoids算法。

用UCI中的Iris等6个常用数据集对基于密度RPCL 的K.medoids算法（简称本文K.medoids算法）和改进的K.medoids算法进行比较。UCI数据集描述如表1所示。

通过计算聚类误差平方和、聚类时间和聚类准确率来评价实验结果。[8]在各数据集上两种算法分别运行20次，文中实验结果为20次实验的平均值。表2是改进K.medoids算法和本文K.medoids算法的聚类误差平方和与聚类时间结果比较。图1是两种算法聚类准确率结果比较。

由表2得到，在所有数据集上，本文算法的聚类误差平方和都少于改进K.medoids算法，本文算法的时间性能在部分数据集上和改进K.medoids算法持平，原因在于运行密度RPCL算法耗费了时间，但是本文算法因为选择了合适的聚类数目和最佳初始聚类中心，又加快了算法的收敛速度。上图显示，本文算法的聚类准确率高于改进K.medoids算法。由以上分析可得，本文基于密度RPCL 的K.medoids算法有效改善了现有K.medoids算法的时间性能，聚类效果更优。

4 结语

本文针对K.medoids算法需要事先确定聚类数目以及初始化聚类中心的缺陷，利用RPCL算法的性能，提出一种用密度RPCL算法对K.medoids进行预处理，期望得到最佳的数据类簇数目，在此基础上运行改进K.medoids算法。

UCI機器学习数据库数据集上的实验表明：本文所提出的基于密度RPCL 的K.medoids算法为K.medoids聚类提供了合适的聚类数目；改进K.medoids算法为K.medoids聚类优化了初始聚类中心；聚类运行时间、聚类误差平方和以及聚类准确率的比较结果显示，本文基于密度RPCL 的K.medoids算法获得良好的聚类效果。不足之处是在于本文算法只是针对球型数据分析，对于非球形数据的分析还需要进一步研究。

参考文献：

[1]马箐，谢娟英.基于粒计算的K-medoids 聚类算法[J].计算机应用，2012，32（7）：1973.1977.

[2]Park H S，Jun C H.A simple and fast algorithm for K.medoids clustering[J].Expert Systems with Applications，2009，36 （2）：3336.3341.

[3]谢娟英，郭文娟，谢维信.基于邻域的K中心点聚类算法[J].陕西师范大学学报（自然科学版），2012，40（4）：16.22.

[4]XU L，KRZYZAK A，OJA E.Rival penalized competitive learning for clustering analysis[J].RBF Net，and Curve Detection.IEEE Trans.on Neural Networks，1993，4（4）：636.649.

[5]李听，郑宇，江芳泽.用改进的RPCL算法提取聚类的最佳数目[J].上海大学学报，1999，40（8）：120.122.

[6]魏立梅，谢维信.聚类分析中竞争学习的一种新算法[J].电子科学学刊，2000，22 （1）：13.18.

[7]谢娟英，郭文娟，谢维信，等.基于样本空间分布密度的改进次胜者受罚竞争学习算法[J].计算机应用，2012，32（3）：638.642.

[8]张惟皎，刘春煌，李芳玉.聚类质量的评价方法[J].计算机工程，2005，31（20）：10.12.

作者简介：第一作者郭文娟（1986.），女，甘肃武威人，讲师，研究方向为智能信息处理。