在大数据时代,了解数据的分布与特征,从而发现有用的信息已经成为一个重要的研究课题,因此很多学者结合机器学习、数据库、数理统计等技术提出了数据挖掘。聚类作为一种无监督的数据挖掘手段,可以根据数据内部分布规律将数据按照相似度分成若干类。虽然已经有很多学者提出了多种聚类算法,但是随着实际数据规模的不断扩大、应用场景变得更加复杂,聚类算法仍然面对很多问题。AP(Affinity Propagation)聚类算法是发表在《Science》上的一种新型聚类算法,它无需提前指定聚类类目以及初始代表点,只需要输入数据点的相似度矩阵,就可以通过两种消息的传递机制,自动迭代直到确定合适的类代表点。结果表明该算法在绝大多数数据集上的表现都比传统的聚类算法更优秀。虽然AP聚类算法相较于传统聚类算法有很多优势,且应用于多个领域,但是它依然面临很多挑战。首先,虽然AP聚类算法不需要提前设定聚类类目,但是其输入参数,偏向参数的值会间接地影响聚类类目,它可以描述每个数据点作为类代表点的偏向程度。一般偏向参数越大,最终聚类类目也就越多,因此如何设置一个合适的偏向参数值成为AP聚类算法中的关键问题。且在原始AP聚类算法中所有数据点的偏向参数值为同一常数,这样的做法无疑不适合于实际情况。因此,本文针对偏向参数的取值问题,提出基于数据密度设置偏向参数,即基于数据点的分布给予不同的偏向参数值,并且引入网格的概念计算数据密度分布,尽量减少额外计算带来的开销。其次,AP聚类算法计算复杂度为O(N×N×logN),当数据规模较大时,算法的耗时会急速增加,且需要存储巨大的相似度矩阵。因此,本文引入两种抽样算法,尽量约简输入数据,在得到具有代表性的样本数据后再执行AP聚类算法。第一种采用最简单高效的简单随机抽样,为了避免随机抽样可能带来的小簇的丢失以及抽样结果的不稳定性,加入分层的思想,先利用随机抽样对数据进行分组,并在每个小组上进行第一层次的AP聚类算法选出全局代表样本点,然后再在样本点上进行第二次聚类。第二种采用较复杂的密度偏差抽样,基于数据的密度分布进行抽样,可以克服随机抽样的缺点,在计算数据点密度时,同样引入网格划分。这样直接通过一次抽样就可以直接运行AP算法,在第一种算法的基础上又提高了算法的效率。在UCI数据库以及人工数据集上进行仿真实验,实验结果表明基于偏向参数的改进算法在聚类精度上有很大的提升,基于抽样的两种改进算法在算法效率上明显优于AP聚类算法,其中基于密度偏差抽样的算法耗时最短。其次还结合基于偏向参数的优化与基于抽样的算法,发现结合之后的算法在精度、效率上都比单独应用这两种算效果更好。最后还将本文算法与其它的改进算法进行比较。