刘 娟，万 静

哈尔滨理工大学 计算机科学与技术学院，哈尔滨 150080

聚类分析作为一种重要的数据挖掘技术，在数据挖掘中起到了十分重要的作用，聚类分析技术被广泛应用于其他研究领域，例如：机器学习、人工智能、图像处理、云计算[1]等。聚类是一个按照数据对象间的相似性将数据集划分为各个不同的簇的过程，要求属于同一个簇的数据对象尽可能类似，同时属于不同簇的数据对象尽可能不同。到目前为止，已经提出了很多不同的聚类算法，主要包括基于划分的聚类算法、基于层次的聚类算法、基于密度的聚类算法、基于网格的聚类算法、基于模糊的聚类算法。

基于划分的聚类算法利用迭代控制策略优化一个目标函数，通过迭代重定位的方法，不断改变聚类中心和簇中的数据对象，进而改进每次的划分结果。K-means 算法[2]是经典的基于划分的聚类算法，由于K-means 算法随机选择聚类中心，初始聚类中心的选择将对聚类结果产生很大影响，而且该算法不能处理非球形的簇。基于层次的聚类算法能够处理非球形的簇，Chameleon 算法[3]是一种混合了“自顶向下”和“自底向上”两种策略的层次聚类算法，Chameleon算法首先在原始数据集上构造k邻域图，然后利用一种高效的图划分算法对k邻域图进行划分得到初始类簇，最后合并子簇，但是该算法对噪声点敏感并且时间复杂度较高。基于密度的聚类算法认为簇是数据空间中被稀疏区域分开的稠密区域所构……