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

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

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