聚类分析作为一种非常重要的数据分析方法,已经在科学数据发掘、信息检索和文本挖掘、网页分析、计算机生物学等领域得到了广泛应用。随着信息技术的不断发展,数据量的存储也越来越大,而且对象之间的相互联系也更为复杂。在这种背景下研究如何更快更有效地聚类大规模复杂数据集显得尤为重要。近几年,在处理大规模数据集方面,近邻传播聚类算法(Affinity propagation,简称AP)得到广泛关注,它与传统算法相比,最大的优点在于处理大规模多类别数据集时运算速度快。但是,AP算法是靠传播数据点之间的近邻信息进行聚类的,当数据集中数据点间的关系比较复杂时,AP算法往往得不到最优解。同时,谱聚类算法具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点,但是算法对数据集的大小非常敏感,当数据集不断增大时,谱聚类算法的性能会急剧下降。如何利用上述两种算法的优点提出新的算法,用于大规模复杂数据集的聚类任务,是本课题研究的重点内容。本文提出了两种算法分别用于改进AP算法和谱聚类算法在处理大规模复杂数据集方面的缺点：(1)基于密度敏感距离的多级近邻传播算法。算法首先在密度敏感距离基础上定义了两种新的相似性度量：局部长度和全局距离,然后将原数据集构造为k最近邻稀疏图,接着在稀疏图上以局部长度作为相似性测度并应用AP算法对数据集进行初步聚类；最后,以全局距离作为相似性测度并多次应用AP算法对初步聚类后的数据集再聚类,直到得到合适的聚类数目。通过仿真实验表明该算法比传统的AP算法聚类性能有明显提升,当数据规模较大结构较复杂时,该算法在处理时间上明显比传统的AP算法要快。(2)密度敏感的层次化聚类算法。第一种算法每次迭代都需要选择参数p来最终决定聚类数目,参数p的好坏直接决定着算法是否能在规定的迭代次数内达到全局最优解。为了减弱第一种算法对参数的敏感性,使算法在大多数数据集上得到全局最优解,本文接着提出了一种结合AP算法和谱聚类算法的混合算法,该算法是一种层次化的聚类算法。算法首先利用第一种算法对目标数据集进行预处理(粗聚类),然后将改进的谱聚类算法应用在预处理后的数据集上得到最终的聚类结果(细聚类)。通过仿真实验表明,密度敏感的层次化聚类算法在处理时间、内存占用率和聚类错误率上都优于传统的近邻传播算法和大多数的谱聚类算法。