稳定的K-多均值聚类算法

2021-05-14 03:42:36张倪妮葛洪伟
计算机与生活 2021年5期

张倪妮,葛洪伟+

1.江苏省模式识别与计算智能工程实验室(江南大学),江苏无锡214122

2.江南大学物联网工程学院,江苏无锡214122

聚类分析是数据挖掘中的重要技术。它将一组没有标记的对象分组,使具有高度相似性的对象为一组。经过数十年的发展,研究人员提出了大量的聚类算法[1-5]。其中最经典的是K-均值聚类算法[1]。K-均值算法简单高效,其基于平方误差的划分方法在超球面簇中表现良好。但是它存在对初始点的选取敏感并且不擅长识别非凸模式簇的问题。

针对第一个问题,相应的改进算法有使初始聚类中心间距离尽可能大的K-means++[6];基于蒙特卡洛取样进行初始化的方法AFKMC2[7](assumption-freek-Markov chain Monte Carlo);基于采样和密度峰值选择初始中心的方法SDPC[8](sampled-clustering by fast search and find of density peaks)等。这些算法在一定程度上提高了K-均值算法聚类效果的稳定性,但是这些方法的聚类结果还是因为初始点的选取存在一定的波动。因此,K-均值类的算法如何选取初始中心仍是一个有意义的课题。

针对第二个问题,考虑到在很多实际应用中,每个类包含很多子类,不能用一个聚类原型来表示,出现了两类解决方法。第一类是非线性的聚类方法,例如基于核的聚类和谱聚类[9-13];第二类是将每个类设置多原型的聚类方法,例如文献[14-19]。2019 年Nie 等人在ACM SIGKDD 上提出的指定k个聚类的多均值聚类算法(multiple-means clustering method with specifiedK,KMM)[20]属于第二类方法。该算法不同于其他同类方法,它将含多个次聚类中心的数据分配给特定的k类变成一个优化问题,交替更新数据对次聚类中心的划分和k个类的划分。……

登录APP查看全文