"分层子树合并聚类算法 (2006年),由李玉盘提出,旨在解决传统分层合并聚类算法可能导致非唯一二叉树结果的问题。该算法通过分析数据集的最小树中的θ-极大紧邻子树,合并其顶点集,以多叉树形式表示聚类结果,理论证明了结果树在不考虑分支顺序时的唯一性,并在具有大量等距点对的样本中展现出更合理的聚类效果。"
在聚类分析领域,分层合并聚类是一种常用的方法,它始于每个样本作为一个独立的类别,然后逐步将最近的两个类别合并,直到满足特定的终止条件。然而,这种方法可能会导致多种可能的二叉树结构,从而影响聚类结果的稳定性和解释性。为了解决这个问题,李玉盘在2006年提出的分层子树合并聚类算法引入了新的思路。
该算法的核心是构建最小树和分析极大紧邻子树。最小树(Minimum Spanning Tree, MST)是从所有样本点构建的无环加权图,其中边的权重代表样本间的距离。在最小树中,θ-极大紧邻子树是指树中包含一定数量顶点的子树,这些顶点间的距离都小于或等于给定的阈值θ。通过对这些子树的分析,算法可以识别出紧密相连的对象群体,进而进行聚类。
算法的具体步骤包括:
1. 构建数据集的最小树。
2. 找到所有θ-极大紧邻子树。
3. 合并每个子树的顶点集,形成新的类别。
4. 重复步骤2和3,直到所有顶点都合并到同一个类别中或者满足预设的终止条件。
理论上,这种分叉树结构在不考虑分支顺序的情况下是唯一的,因为它基于样本间的真实距离关系。实验表明,当样本集中存在大量距离相等的点对时,分层子树合并聚类算法生成的多叉树能更好地反映数据的内在结构,提供更加合理的聚类结果。
此外,相比于传统分层合并聚类算法仅合并两个最近的类别,此算法每一步可以合并多个对象,这增加了算法的效率,并可能产生更符合实际应用场景的聚类结构。在实际应用中,例如在语音和图像处理、生物信息学以及数据挖掘等领域,这种算法的优越性尤其显著,因为它能处理复杂的聚类模式,尤其是那些包含多个紧密子群的情况。
分层子树合并聚类算法是一种创新性的聚类方法,它克服了传统分层合并算法的局限性,提供了更稳定、唯一的聚类结果,特别是在处理等距点对时表现优秀。同时,它扩展了聚类树的表示方式,由二叉树转变为多叉树,使得聚类结构更直观地反映了数据的层次关系。这项工作为聚类算法的研究和应用开辟了新的路径。