吴清寿, 刘耿耿, 郭文忠

(1. 武夷学院数学与计算机学院, 福建 武夷山 354300; 2. 福州大学数学与计算机科学学院, 福建 福州 350116)

0 引言

聚类分析是无监督学习的重要方法. 聚类分析能够发现数据集自身隐含的内蕴结构信息， 其在模式识别与数据挖掘等研究方向有着广泛的应用. 根据数据集中数据的积聚规则和应用这些规则的方法， 可以将聚类算法大致分成层次化聚类算法、 划分式聚类算法、 基于密度和网格的聚类算法以及其他聚类算法[1].K-means聚类算法是划分式聚类的典型代表.K-means算法的首要问题在于对初始质心的选择是敏感的， 文献[2]提出了一种基于最大最小距离法确定初始质心的方法， 文献[3]利用聚集度函数和层次聚类来获取初始质心. 针对K-means易于收敛到局部最小值而非全局最小值的问题， Ding等[4]提出一致性保留K-means算法(K-means-CP)， 可实现全局聚类目标函数优化. 作为K-means算法的重要变种， 二分K-means也得到了广泛的应用和研究. 文献[5]提出以极大距离点优化二分K-means初始质心的方法， 并对算法进行并行化处理. 文献[6]将二分k-均值与SVM决策树相结合， 用二分k-均值在低维数据空间中聚类， 取得了良好效果.

在各类研究中， 对文献[1]所提出的一个问题未予以解决， 即二分K-means算法存在再分配能力差问题. 问题具体表现为： 若在某个阶段把一些实例(instance)误划分给某个簇， 这些实例将失去回归原应归属簇的机会. 本研究通过引入目标簇和候选簇的概念， 在候选簇中选出若干距离目……