基于网格的密度峰值聚类算法研究及其应用

摘要

近几年来，数据挖掘技术发展非常迅速，各种各样的数据挖掘方法被源源不断地提出，聚类作为数据挖掘领域一种重要的研究方法，已经被广泛地运用在城市热点发现、图像识别、广告推荐、客户细分等各个领域。
　　密度峰值聚类算法是2014年提出的一种具有代表性的聚类算法，在大多数数据集上都可以得到比传统聚类算法更好的聚类效果，并且在聚类过程中，需要人为设定的参数很少，与传统算法相比，具有运行速度较快、可以发现任意形状簇等优点，已经被广泛地应用在图像识别和社区划分等领域。由于近年来数据科学的飞速发展，各种各样的数据形式，越来越大的数据量，使得聚类算法需要不断地适应新的数据要求。本文通过对密度峰值算法聚类过程的详细分析，发现当数据规模达到一定程度时，密度峰值聚类算法就很难在普通计算机上直接处理数据集，而且聚类时间也随着数据量的增长变得越来越长，这就大大限制了密度峰值聚类算法在大规模数据集上的应用。
　　针对以上问题，本文提出了一种基于网格的密度峰值聚类算法。该算法在密度峰值聚类算法的基础上，结合网格聚类算法的思想，对数据进行网格划分，一方面优化了算法计算相关参数所需要的时间，提高了算法运行速度，另一方面避免了密度峰值聚类算法在处理大规模数据集时出现的内存溢出情况，使得算法在单个普通计算机上也能够处理大规模数据集。实验分别在低维和高维的标准数据集上验证了基于网格的密度峰值聚类算法的有效性。
　　本文将基于网格的密度峰值聚类算法运用在国内某城市出租车的真实轨迹数据集，利用乘客上下车的位置信息来发现城市中的热点区域，验证了本文算法在大规模数据上的适用性和优越性，并结合出租车司机的收入信息对各个热点区域进行分析。最后将热点区域之间的来往流量作为区域之间的相似性，对热点区域进行聚类，探究各个热点区域之间的联系。

目录

声明

1 绪论

1.1 研究背景及意义

1.2 国内外研究现状

1.3 研究内容和组织结构

2 密度峰值聚类算法简介

2.1 DPC算法的相关参数

2.2 DPC算法聚类过程及复杂度分析

2.3 DPC算法缺陷分析

2.4 高维数据降维方法

2.5 聚类算法评价指标

3 基于网格的密度峰值聚类算法

3.1 Grid_DPC算法框架

3.2 相关定义

3.3 参数设定

3.4 算法步骤

3.5 复杂度分析

3.6 数值实验

3.7 本章小结

4 Grid_DPC算法在出租车轨迹数据集上的应用

4.1 基于Grid_DPC算法的乘客上下车热点区域发现

4.2 热点区域司机载客收入分析

4.3 基于热点区域间流量的聚类

4.4 本章小结

结论

参考文献

攻读硕士学位期间发表学术论文情况

致谢