胡雅婷, 陈营华, 宝音巴特, 曲福恒, 李卓识

(1. 吉林农业大学 信息技术学院, 长春 130118； 2. 吉林省科学技术工作者服务中心, 长春 130021；3. 长春理工大学 计算机科学技术学院, 长春 130022)

聚类分析[1-4]是数据分析的一种基本方法, 既可作为一种无监督机器学习方法独立发现未标签数据结构, 完成数据分类、 压缩等工作, 也可与其他方法相结合以提高其性能.k-means算法是一种经典的划分聚类算法, 通过最小化类内方差之和获得硬聚类划分, 因其计算简单、 聚类效率高等优点广泛应用于模式识别、 机器学习、 图像处理及故障诊断等领域[5-8]. 但k-means聚类结果对初始聚类中心依赖较大, 导致算法易陷入局部极小值[9]. 为改善该问题, 可通过改进中心初始化方法降低初始化对算法的影响, 以获得目标函数的更优解[10-12].k-means++算法[13]通过随机选择程序实现初始化中心对整个数据空间的全覆盖, 在理论上保证了获得聚类划分可达到近似最优. 该类算法计算效率相对较高, 但对目标函数解的改善程度有待提高. 全局k-means聚类算法[14-17]作为一种增量式k-means聚类算法, 以每次迭代增加一个聚类中心的方式完成聚类数目的递增, 通过在数据中选择使目标函数值减少最多的数据点作为新增的聚类中心. 该算法明显提升了目标函数解的质量, 但计算效率较低.

针对上述改进算法存在的问题, Tzortzis等[18]提出了MinMaxk-means聚类算法. MinMaxk-means 算法以最小化最大的方差为聚类准则确定目标函数, 该准则能改善k-means算法迭代中产生过……