基于模拟划分的SP-k-means-+算法

作者：杨勇; 陈强; 曲福恒; 刘俊杰; 张磊

来源：吉林大学学报（工学版）, 2021, 51(05): 1808-1816.

DOI：10.13229/j.cnki.jdxbgxb20200645

• 人工智能
• I-k-means-+
• 目标函数优化
• 分裂与删除
• 模拟划分
• 合适的簇对

I-k-means-+算法作为一种新的k-means目标函数优化算法,通过分裂与删除簇提高解的质量,在一定程度上克服了k-means算法容易陷入局部最优解而导致目标函数优化效果不佳的问题,但该算法采用一种比较粗糙的方式估计各簇的Gain值和Cost值,影响了目标函数优化效果。针对此问题本文提出了一种基于模拟划分的SP-k-means-+算法,根据各簇模拟划分的情况,更准确地计算各簇的Gain值和Cost值,降低了簇对匹配过程中漏检与误判的可能性,在每次迭代中选择更合适的簇对执行分裂删除操作,进一步优化了目标函数并且避免了无效迭代造成的冗余计算问题。实验结果表明:当无需-+操作时,本文算法与I-kmeans-+算法的目标函数一致且效率提升了16%;当需要-+操作时,本文算法在不降低计算效率的前提下目标函数优化效果较I-k-means-+算法更佳,聚类模型解的精度提高了10%以上,最高达到47%。

• 单位
  长春理工大学; 长春师范大学; 教育学院