邵 伦,周新志,赵成萍,张 旭

(四川大学 电子信息学院,成都 610065)(*通信作者电子邮箱xz.zhou@scu.edu.cn)

0 引言

聚类算法是一种典型的无监督学习算法,是利用样本的特征比较样本的相似性,将具有相似属性的样本划分到同一类或簇中的算法[1-5]。聚类算法的应用广泛,在数据挖掘、信息检索和图像分割等方面都有重要的作用[6-11]。迄今为止已经衍生出了众多的聚类算法,这些算法可以分为划分法、层次法、密度法、图论法、网格法和模型法等[5,11-14]。K-means是一种典型的基于划分的聚类算法[12,16-17],其应用非常普遍,但是传统的K-means算法存在一些不足之处,比如随机选择的初始聚类中心通常是不理想的,易使最后的聚类结果局部最优,而非全局最优;另外初始聚类中心选择的不稳定性,也会导致算法迭代次数及聚类结果的不稳定[18-19]。很多研究人员对初始聚类中心的选择提出了优化的方法,文献[11]中提出了一种基于最小生成树的层次K-means聚类算法,文献[20]中提出了一种基于最小方差优化初始聚类中心的K-means算法,但是这些算法在初始聚类中心选择的效果上仍不够理想,聚类结果的稳定性和准确性仍有待提高。

针对上述问题,本文提出了一种基于多维网格空间结构优化初始聚类中心的改进K-means聚类算法。此算法首先根据样本集的属性个数n,将样本集映射到一个包含有限个子网格的n维网格空间结构中。其映射流程如下:以样本集中每一类属性的最大值和最小值作为网格空间中每一维度的上边界和下边界；……