陈 迪,刘惊雷

（烟台大学计算机与控制工程学院，烟台，264005）

聚类算法作为机器学习和数据挖掘中最基本的数据分析技术之一，受到各个领域的广泛关注.聚类的目的是将数据集合分成若干簇，使得同一簇内数据点的相似度尽可能大，而不同簇间数据点的相似度尽可能小.在过去的几十年里，大量的聚类方法得到了广泛的发展，并取得了令人瞩目的性能.由于其高效性和简单性，k⁃means聚类方法得到了广泛的研究.为了可视化数据的聚类结构，研究者开发了自组织映射方法［1］，还提出了谱聚类［2］、支持向量聚类［3］和基于核的聚类［4］等聚类算法来研究非线性聚类结构.

k均值型（硬或软）算法在聚类任务和子空间学习中得到了广泛的应用，目前仍是研究的热点.k⁃means聚类［5-6］（又称硬聚类）是一种基于划分的聚类算法，首先通过一定的距离或相似性度量将每个数据样本分配到最近的聚类中，然后更新每个聚类的质心来重新分配数据点.基于划分的聚类算法对在小规模的数据库中发现球状类别很有效，但它本质上属于“爬山”算法，“爬山”算法是一种局部择优的方法，容易收敛到局部最优.k⁃means聚类又是一种基于矩阵分解的聚类方法［7］，Bauckhage［8］证明传统的k⁃means聚类算法的目标函数可以被表达成数据矩阵与其低阶数据矩阵之间差异的Frobenius范数.

基于图的聚类方法［9］通常有三个缺陷.首先，对后处理的要求，例如谱聚类结果需要用k⁃means进行聚类，这会不可避免地引入初值选择……