聚类分析是模式识别与数据挖掘等诸多领域的重要技术之一。然而,由于簇的大小、形状、分布各异,目前已有的聚类算法,包括划分式、层次式、基于密度峰值和基于最小生成树等方法都无法令人满意。大量研究发现,相比均值中心和密度中心,使用代表点作为聚类中心的方法具有较好的性能,该方法受噪声、离群点和簇的形状的影响较小。另外,最小生成树的形状并不会随簇边界的变化而变化,因此,基于最小生成树的聚类算法能解决对簇的形状和噪声敏感的问题。本文重点解决了如何在最小生成树上搜索代表点,计算类间距离,以及簇的合并准则,并构建了基于最小生成树的快速聚类算法。本文从在当前研究现状的基础上,主要进行了以下工作:(1)提出了一种基于最小生成树树形重心的类间距离度量方法。该方法的提出主要基于以下几个原因:首先,传统的基于最小生成树的聚类算法,对最小生成树的几何形状利用率不高;其次,使用欧几里德距离的度量方法对类别的形状分布敏感;最后,传统的基于代表点的类别中心选取方法的时间复杂度较高。最小生成树的树形重心作为代表点能够充分利用其几何形状,测地距离可以适应多种形状的簇。通过树链剖分技术和二分算法快速地合并簇,从而大大降低计算代表点与类间距离的时间复杂度。(2)提出了一种限制条件下,结合广度优先搜索算法的预聚类方法。为使代表点方法不退化为样本点到样本点之间的距离,提出了该预聚类方法来解决算法初期每个类别内部样本点数量过少的问题,以满足后续应用最小生成树树形重心的类间距离度量的需求,从而提高聚类性能。(3)提出了一种基于最小生成树树形重心和割边约束的多阶段层次聚类算法。整体算法分为三个阶段:预聚类、基于割边约束I的小类合并过程和基于割边约束II的最终聚类过程。该算法考虑到了两个因素:类间距离和两个邻接类簇之间的内在联系,从而使得算法中合并的过程更加准确,减少错误的合并过程。经过人工合成数据集和UCI真实数据集上的实验验证,本文算法具有良好的聚类性能。