聚类是一种常见的数据分析技术,在很多方面都得到了广泛的应用,比如天文学、生物学、社交网络、模式识别等。聚类算法分为基于中心点的聚类算法、基于密度的聚类算法、基于模型的聚类算法等。但是这些聚类算法普遍存在一些问题,例如对初始输入参数的选取异常敏感、处理大数据时效率低下、对数据的形状有一定的要求等。密度中心聚类算法(DP)是一个最近发表在“Science”上的新型聚类算法,它通过评估每个数据对象的两个属性值(密度值p和斥群值δ)来进行聚类。相对于其他传统聚类算法,它的优越性体现在交互性、无迭代性、无数据分布依赖性等方面。但是,密度中心算法对输入参数dc值非常敏感,不恰当的取值将影响聚类效果。本文针对该问题提出基于K近邻密度的DP算法——KNN-DP算法,有效缓解了算法对dc值选取的依赖性。另外,为了有效对高维大数据集进行聚类,本文利用MapReduce模型,基于分块技术设计了 KNN-DP的简单分布式算法——Naive KNN-DP分布式算法。为了进一步提高算法效率,本文结合位置敏感哈希(Locality Sensitive Hashing,LSH),将距离较近的数据点以较高概率哈希到一个数据块中,提出了基于LSH的KNN-DP分布式算法。该算法避免了大量的无效距离计算和中间结果传递,大大提高了算法的分布式计算效率,缩短了聚类计算时间。为了验证KNN-DP算法及其分布式算法的高效性,本文设计了一系列实验。实验结果显示KNN-DP算法在运行效率和聚类质量上均优于原始的DP算法。另外,实验也测试了本文提出的两种KNN-DP的分布式算法,包括Naive KNN-DP分布式算法和LSH KNN-DP分布式算法,实验结果表明基于LSH的分布式算法在运行效率上高于简单分布式算法,并且不会对聚类质量造成严重影响。