徐晨凯，高茂庭

上海海事大学信息工程学院，上海 201306

改进的最小生成树自适应分层聚类算法

徐晨凯，高茂庭

上海海事大学信息工程学院，上海 201306

1 引言

聚类是将物理或者抽象的集合分组成为由类似的对象组成的多个类的过程[1]，其中最小生成树聚类方法已被广泛地研究[2-12]，而如何快速准确地确定不一致边是一个关键问题。文[2]中使用全局静态阈值确定不一致边，当聚类簇密度相差较大时，聚类效果并不理想；文[3]中使用相对阈值来确定不一致边，但是往往受到不同边的相互干扰，从而使聚类结果不准确；文[4]使用影响域来确定不一致边，但是计算量稍大；文[9]结合了密度的方法来加强聚类的准确度；文[11]添加控制点及优先级的方法来优化聚类结果，但增加控制点需要更多的先验知识；文[12]结合网格的方法增强抵抗噪声的能力。

本文通过分析最小生成树边集内边的关系，提出一种改进的最小生成树自适应分层聚类算法，根据最近邻关系划分最小生成树的边集，为每个聚类簇自动生成合适的相对阈值来确定不一致边；通过多次迭代去除不同边的相互干扰；同时该算法能够自适应生成聚类数目，无需事先给定。在迭代过程中，因为最近邻关系不再改变，所以大大加快了计算速度。实验验证了这种方法的有效性。

2 基本概念

2.1 最小生成树聚类算法

传统最小生成树聚类算法[13]是一种基于图论的全局聚类算法，一般算法如下：将全局数据看成是一个完全图，将数据作为结点，将数据与数据的距离作为权值，则根据最小生成树算法得到一棵最小生成树，再将这棵最小生成树中权重大于阈值的边删除，剩余连通结点作为一类，即得聚类结果。……