基于多球分裂的增量式k-means聚类算法

作者：曲福恒; 钱超越; 杨勇^*; 陆洋; 宋剑飞; 胡雅婷

来源：吉林大学学报（工学版）, 2022, 52(06): 1434-1441.

DOI：10.13229/j.cnki.jdxbgxb20210098

• 模式识别
• k-means
• 增量聚类
• ball k-means
• 多球分裂

针对Ball k-means(BKM)算法对初始化中心敏感、求解精度不高的问题，提出了一种基于多球分裂的增量式k-means聚类算法。该算法利用BKM需要记录各球聚类半径的特点，从给定的初始聚类中心个数开始，按照固定步长一次性产生多个增量聚类中心，直至得到k个初始中心。本文算法避免了所有n个s维数据之间的距离计算，在不增加空间复杂度的前提下将传统增量聚类中心选取的计算量由O (n2s)降低至O (k log k)(k<n)。在8组UCI数据上与k-means、BKM、IK-+以及3个典型增量聚类算法的对比实验结果表明，本文算法降低了BKM的初始化敏感性，解的精度提升了37.15%～66.92%，是对比增量算法中唯一能够提升k-means效率的算法，且随着聚类个数的增加，效率优势更加明显。

• 单位
  教育学院; 长春师范大学; 长春理工大学; 吉林农业大学