聚类算法在数据挖掘中有着十分重要的作用。它可以在数据集分类信息未知的前提下,发现数据集的结构信息,也能作为其他学习任务的前驱步骤。2014年,Alex Rodriguez等在Science期刊上发表了题为《Clustering by fast search and find of density peaks》的论文。作者在文中提出了一种基于密度和距离的快速聚类算法,称之为密度峰聚类算法。该算法的核心思想是聚类中心是具有局部密度最大的点且远离任意一个密度比它高的点。密度峰聚类算法简单高效,吸引大量国内外学者的关注。该算法也为聚类分析在数据挖掘领域中的具体应用,提供了新的思路。本文分别对密度峰聚类算法的数学理论,自动识别聚类中心点问题以及算法在社团发现中的应用这三个问题进行研究。本文的主要研究内容概括如下:1.对密度峰聚类算法通过决策图选择聚类中心点的行为和高效的标签传播方式进行数学理论分析。人为选择中心点的过程实际上是分别设置距离阈值和密度阈值。在一定条件下,这种方法选取的点是数据集密度分布上的局部最大值,且需满足一定的密度条件。从有监督学习的角度分析样本分配过程。当样本距离最近,密度更大的邻居被正确分配时,样本的标签分配错误率不超过当前贝叶斯最优分类器错误率的两倍。2.针对密度峰聚类算法需要人为分析决策图并手动选择聚类中心点这一问题,提出了采用统计学理论自动识别聚类中心点的方法。根据人为选择的规则,设计了一种判断指标。采用极大似然估计对其广义极值分布进行估计并设置一个上限,大于上限的点被自动视为聚类中心。考虑到算法对计算复杂度的要求,探讨了基于切比雪夫不等式的方法作为替代方案。采用20个数值类型的数据集验证了这两种方法的有效性。3.将密度峰聚类算法应用于社团发现问题。根据社团中心节点的特点,提出了一种度量节点密度的方法。针对密度峰聚类算法中存在“多米诺骨牌效应”,即一个节点被分错将导致后续节点均被分错的问题,提出了一种两阶段标签传播策略。当选取社团中心节点后,先生成种子域,然后根据节点的所有邻居信息传播标签。通过实验对提出算法的性能进行验证。4.针对网络中可能存在“富人俱乐部”等中心节点连接较为复杂的问题,提出了一种称为关系距离的节点间距离度量方法。该方法不仅考虑节点之间的连接信息,同时也考虑了两者一阶邻居节点的连接信息。为了进一步提高算法的社团划分准确性,引入了一种多算法协作框架。在选取社团中心节点后,多次随机传播中心节点标签,融合所有结果得到最终社团结构。数学分析和实验对比展示了该算法的有效性。最后,对本论文的主要研究成果进行了归纳总结,并展望了包括多算法协作框架应用于压缩感知在内的未来工作。