计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (15): 48-52.DOI: 10.3778/j.issn.1002-8331.1706-0223

• 理论与研发 • 上一篇    下一篇

最小化误差平方和k-means初始聚类中心优化方法

周本金,陶以政,纪  斌,谢永辉   

  1. 中国工程物理研究院 计算机应用研究所,四川 绵阳 621900
  • 出版日期:2018-08-01 发布日期:2018-07-26

Optimizing k-means initial clustering centers by minimizing sum of squared error

ZHOU Benjin, TAO Yizheng, JI Bin, XIE Yonghui   

  1. Institute of Computer Application, China Academy of Engineering Physics, Mianyang, Sichuan 621900, China
  • Online:2018-08-01 Published:2018-07-26

摘要: 传统的k-均值算法对初始聚类中心和孤立点敏感,文中以最大程度地减少误差平方和为基本思想,提出一种最大化减少当前误差平方和的k-means初始聚类中心优化方法。在初始聚类中心选择阶段,每次增加聚类中心时,计算所有数据点作为当前聚类中心能够减少的误差平方和,选择能够最大化减少误差平方和的数据点作为聚类初始中心。利用真实数据集,同其他算法进行对比,实验结果表明该方法在选择初始聚类中心方面能够有效地减少聚类的迭代次数,提高聚类质量。同时人工模拟数据表明该方法对孤立点相对不敏感。

关键词: 聚类, k-均值算法, 误差平方和, 孤立点

Abstract: Traditional k-means algorithm is sensitive to initial clustering centers and isolated points, based on the principal of minimizing the sum of squared error to the most extent, an optimized k-means method is presented on selecting initial clustering centers. At the phase of initial selecting clustering centers, when adding a clustering point each time, compute reduced sum of squared error of each point and select the point that can maximize the square of the reduced error. Using real datasets and compared with the results of other algorithms, the experimental results show the number of iteration is reduced on selecting initial clustering centers and the quality of clustering is improved. Besides, artificial dataset demonstrates the method is much less sensitive to isolated points.

Key words: clustering, k-means algorithm, sum of squared error, isolated points