随着智能设备的普及和存储技术的发展,客户端进行数据存储和处理的能力得到显著提升。对这些数据的分析挖掘能够带来巨大的经济效益和社会价值。随着各行业数字化建设的深入,来自于各领域的大规模数据已难以进行直观分析和观察。层次聚类算法作为大数据分析挖掘中的一种重要工具,通过分析数据之间的关系,能将数据组织成多层次、多分辨率的结构形态,有助于人们挖掘数据中的潜在知识。但传统层次聚类算法的计算复杂度高,可扩展性不足,限制了其应用范围。因此,针对大规模数据集,如何解决聚类时间与聚类效果之间的矛盾是一项长期且艰巨的挑战。为此,本文提出了一种新颖的层次聚类算法（互惠最近邻聚类算法）,并针对基于互惠最近邻的层次聚类框架中存在的相关问题进行了探索和研究,主要研究内容如下:（1）提出了互惠最近邻聚类算法（Reciprocal-nearest-neighbor Supported Clustering,简称RSC）。RSC算法的基础假设和算法逻辑与经典层次聚合聚类（HAC）算法和基于CF Tree的增量层次聚类算法不同,它基于一个优雅的假设:互为最近邻居的两个数据点应该被分配在一个聚类簇中。在此基础上,RSC算法通过最近邻居搜索将其他数据点聚合在一起,找到互惠最近邻节点对,并将节点对的质心作为聚类子树的根节点进一步聚合,以构造多层次、多分辨率的聚类树。RSC算法中包含了基于簇规模的剪枝策略,解决了层次聚类中常见的连锁效应问题（chain effect）。真实世界数据上的对比实验表明,在大部分情况下,RSC算法的聚类准确性高于其他基准算法。并且针对RSC算法的算法复杂度分析表明,其时间复杂度为O（n log n）,低于绝大多数传统层次聚类算法。（2）针对潜在的数据特征复杂性问题对RSC算法进行了优化,将其扩展到复杂网络数据的社区检测应用中。社区检测算法作为复杂网络数据上的一种特殊聚类,具有广泛的应用价值。但因复杂网络数据的稀疏性和非对称性,传统聚类算法并不能直接用于社区检测。本文通过引入随机游走方法,实现了节点之间的距离关系（包括无权网络）的估算。利用空间几何关系,实现了非向量根节点之间距离的近似计算。并通过计算社区之间潜在连边的介数,将网络节点组织成为具有树形结构的社区。在真实世界网络上的对比实验显示,扩展后的RSC算法的社区检测性能显著地优于经典GN算法。这表明,RSC算法在社区检测中具有一定的应用价值。（3）针对互惠最近邻节点的重要性评分问题,提出了基于互惠最近邻节点重要性的层次聚类算法（简称SRSC）,解决了RSC算法空间复杂度偏高所带来的应用局限性问题。利用互惠最近邻构造虚拟的根节点需要消耗大量的内存空间。SRSC算法将基于互惠最近邻的层次聚类问题形式化为一个图模型,结合图的拓扑结构和数据边界采样策略,从结构重要性和相对空间重要性两方面对互惠最近邻节点的重要性进行评分。重要性评估方法使聚类簇具有更平衡的树形结构,从而节省了额外剪枝所带来的开销,并使之成为无参数算法。在大量真实世界数据集上进行的对比实验表明,SRSC算法的聚类准确性高于层次聚类标杆算法PERCH。同时,算法复杂度分析表明,SRSC算法在保持其时间复杂度与RSC相同的情况下,将空间复杂度降低到O（log n）。（4）针对大规模数据聚类的时间成本与聚类准确性的平衡问题,提出了数据并行化的选举树算法。选举树算法的基本思想是分组聚合,将数据分组中产生的候选人（簇的根节点）视为新的节点进行迭代聚合,实现聚类簇的合并。选举树算法以“相对位置因子”为基础,实现了数据边界的快速十字采样,使采样所得的边界点分布更加均匀;还实现了针对簇重叠区域的叶子节点交换,修正了叶子节点的归属误差,提高了聚类准确性。在真实世界上的对比实验显示,选举树算法的聚类准确性显著优于经典算法和层次聚类标杆算法PERCH,并且准确性对参数不敏感。在多种类型人工数据上的可扩展性测试表明,选举树算法的CPU Time增长率约为1.18,达到准线性水平,且对数据分布不敏感。选举树的分组聚合过程无需共享内存,分组数据的大小与聚类结果之间无显著影响,在大规模数据聚类应用中将有较好的应用前景。综上所述,本文提出了基于互惠最近邻的层次聚类框架,并从社区检测的应用价值、解决空间复杂度过高问题、大规模数据集的层次聚类三个角度对该框架进行了探索和研究,并通过实例分析验证了算法的实证性能和可扩展性。本文针对层次聚类中一个新的分支方向进行了研究,为平衡层次聚类的实证性能和可扩展性问题提供了有意义的探索,为数据的结构化分析和挖掘工具提供了新的可能。