聚类问题是数据挖掘领域的重要研究课题,它不仅能用作独立工具来发现数据集的特征信息,而且能作为其他数据挖掘算法的预处理过程,因此,聚类算法的聚类性能具有极其重要的研究价值。层次聚类算法是常用的聚类算法之一,层次聚类算法通常存在着静态模型选参与期望值相差巨大,或者模型不适于某些数据特性等缺点。Chameleon聚类算法是一种基本的凝聚层次聚类算法,依据自相似性构造动态模型。Chameleon聚类算法的主要优点是算法结构简单、快捷,而且能有效地处理大数据集,并且对数据特性要求较低。但是,Chameleon算法的聚类效果依赖于对KNN图的划分效果。本文针对Chameleon聚类算法的图划分方法-Metis算法进行研究,优化了图的划分效果,从而优化了最终聚类结果。最后利用改进后的算法对UCI数据集和人工数据集进行聚类,实验结果表明,改进算法聚类效果明显优于原算法及某些其他改进算法的聚类效果。本文的主要研究结果如下:1.改进了Chameleon算法。Chameleon算法是利用Metis算法完成图划分的,因而,聚类结果也随子簇的划分效果而改变,同时,在图划分的细化过程中,前一层的局部最优划分未必就是下一层的局部最优划分。本文利用改进的K均值聚类算法和DP聚类算法进行图划分,既能使聚类结果的稳定性得到提高,而且保持了子簇的高内聚性,也使得图划分过程与子簇合并过程中的迭代次数明显减少,时间复杂度明显降低。2.改进了 Metis算法。Metis算法依据随机匹配原则和递归二级划分法来完成对KNN图的粗化和初始划分步骤,容易使得相似度较大的点被分离,本文利用最大权重匹配原则和最小生成树法替换原方法,从而实现算法的粗化和初始划分过程,最大可能地将相似度较大的点划到一个子簇,提高了聚类效果。3.利用UCI数据集和二维人工数据集,对本文的改进算法进行了实证研究,研究结果表明本文的改进算法在聚类精度和运行效率方面都具有更好的效果。