张 梅，陈 梅，李 明

(兰州交通大学电子与信息工程学院，甘肃 兰州 730070)

1 引言

在科学研究中，人们希望在无任何先验知识的情况下挖掘出数据内部潜在的特性，而聚类分析技术正好解决了这一问题[1]。聚类分析是一种无监督的学习方式，通过簇内数据间相似性高、簇间数据相似性低的原则来发现数据点在数据集中的真实分布[2]。

目前已有多种聚类算法被提出[3]。k-Means[4]和k-Mediods[5]算法是2种典型的基于划分的算法。该类算法通常需要用户提前输入簇个数，通过迭代使得簇内误差平方和最小来获得最终划分结果，因此基于划分的方法只能识别球状簇。基于密度的噪声应用空间聚类DBSCAN(Density-Based Spatial Clustering of Applications with Noise)[6]能够在具有噪声的数据中将高密度区域划分成簇，但不同参数组合对最终聚类效果影响很大；OPTICS (Ordering Points To Identify the Clustering Structure)[7]会生成一个增广的有序序列簇，不同密度对应不同簇划分结果，虽然参数选取较容易，但由于其实现涉及到二叉树，生成的又是增广序列，因此计算量较大、速度较慢。Chamelon算法[8]是典型的层次聚类算法，它采用动态模型来确定簇之间的相似性，虽然算法发现子簇的能力很强，但时间复杂度相对较高。网格聚类算法中较有代表性的是STING算法[9]，此算法虽适合大数据集，但对数据维度的可伸缩性较差，网格划分过细时，计算复杂度较高。

近几年来，为了能识别任意形状、任意密度的簇，聚类研究领域学者们相继提出了新的聚类算法[10 -12]。CLASP 算法[13]借鉴了基于划分和基于层次的方法，使用k-Means获取簇代表点，并根据互k近邻相似性度量进行聚类，但输入参数过多。……