基于加权空间划分的高效全局K-means聚类算法

曲福恒; 潘曰涛; 杨勇; 胡雅婷; 宋剑飞; 魏成宇

doi:10.13229/j.cnki.jdxbgxb.20221338

吉林大学学报(工学版) ›› 2024, Vol. 54 ›› Issue (05) : 1393 -1400. DOI: 10.13229/j.cnki.jdxbgxb.20221338

基于加权空间划分的高效全局K-means聚类算法

曲福恒, 潘曰涛, 杨勇, 胡雅婷, 宋剑飞, 魏成宇

作者信息 +

Author information +

文章历史 +

摘要

针对全局K-means聚类算法穷举样本点导致计算量大的问题，提出一种基于加权空间划分的高效全局K-means聚类算法。算法首先对样本空间进行网格划分，然后提出密度准则与距离准则对网格进行过滤，保留密度较大且相互距离较远的网格作为候选中心网格。为避免全局K-means算法只在样本集中选取候选中心的局限性，提出权重准则和中心迭代策略扩充候选中心，增加候选中心多样性。最后，通过增量聚类方式遍历候选中心得到最终的聚类结果。在UCI数据集上的实验结果表明：与全局K-means算法相比，新算法在保证聚类精度的前提下，计算效率平均提高了89.39%～95.79%。与K-means++、IK-+和近期提出的CD算法相比，新算法精度更高，并且克服了因随机初始化导致的聚类结果不稳定问题。