层次聚类是一类根据对象之间的相似性或相异性,将对象组织成嵌套群组的方法。它并非只给出一种划分结果,而是构建一个小簇隶属于大簇的层次结构。结果通常用树状图表示:这是一种分支图,叶节点对应单个对象,内部节点则代表群组。在机器学习中,层次聚类通常归为无监督学习,因为它不需要带标签的样本,就能推断出对象的分组。
构建层次结构的两种主要方法沿相反方向进行。凝聚式方法从彼此独立的对象出发,反复合并簇;分裂式方法则从包含所有对象的单个簇出发,反复将簇拆分。两者的输出都支持从精细划分到宽泛类别等多个尺度的分析。其应用包括按表达模式对基因分组、组织文档、比较生态群落,以及探索图像或其他高维观测对象之间的关系。
数据集并不能唯一确定一个层次结构。层次结构的形态取决于对象的表示方式、相异性的度量方法、所采用的合并或拆分规则,以及对最终树结构的解读方式。这些选择既决定了分析所需的计算资源,也决定了分析结果的科学含义。
数学结构与树表示
设 为一个有限对象集。层次聚类可以描述为由 的非空子集构成的集合族 ,其中包含所有单元素子集和全集 ,且任意两个成员要么互不相交,要么彼此嵌套。形式上,对于 ,有
这一条件将层次结构与一组相互重叠的簇区分开来。沿着通向根的路径,一个对象可以属于多个群组,但它不能同时属于两个相交却又互不包含的分支。
最自然的表示方式是一棵有根的树(数据结构)。叶节点表示观测对象,根节点表示整个数据集,内部节点则表示簇。如果每次操作都恰好合并两个簇,结果就是一棵具有 个叶节点和 个内部节点的二叉树。因此,完整的凝聚过程会依次经过簇数为 的各个划分。这些划分必须彼此嵌套:两个观测对象一旦合并,后续操作就不会再将它们分开。分裂式层次结构也有相应的限制,即已经分开的分支不会重新合并。
树状图通常为每个内部节点赋予一个高度 ,表示其子簇合并时的相异度或目标函数增量。当高度朝根的方向始终不减时,在高度 处进行水平切割便可得到一个划分。例如,假设 和 在高度 1 处合并, 和 在高度 2 处合并,而这两对对象在高度 5 处合并。在 2 与 5 之间切割,就会得到 和 。叶节点的水平位置主要取决于展示方式:调换某个节点下各子节点的位置,只会改变图形的外观,不会改变聚类结果。
对于单调树状图,将 定义为同时包含这两个观测对象的最低节点的高度,并令 。这些共表型相异度满足强三角不等式
这样的距离称为超度量,不过,如果不同的观测对象在零高度处合并,严格来说得到的就是伪超度量。因此,单调层次聚类可以视为原始相异度的一种超度量表示。这种表示简化了对象间的关系,而不一定精确保留这些关系。有些链接准则会产生非单调的高度,即高度倒置,此时就需要对上述解释作出调整。
对象表示与相异度
大多数经典方法都以对称的相异度矩阵 为起点,其元素满足 和 。相异度不必满足度量空间的全部公理。例如,基于簇间最小、最大或平均相异度的算法,可以处理许多不满足三角不等式的矩阵。不过,所得聚类的含义仍然取决于输入数值的含义。算法无法判断一个较大的数值代表的是生物学上的分化、文本差异、测量噪声,还是某种任意的编码选择。
对于数值向量,欧几里得距离是一种常见选择:
它对变量的单位和尺度很敏感。在同时包含年收入和年龄的数据集中,未经缩放的收入值可能仅仅因为数值范围较大,就主导了距离的计算。特征缩放会改变这种几何关系。标准化是将中心化后的数值除以某个衡量离散程度的量;稳健的替代方法则采用中位数和四分位距等统计量。这些变换是具有实质影响的选择,而非中性的预处理步骤:将一个噪声较大的变量标准化,可能会使其获得与可靠变量相当的影响力。
不同类型的数据需要采用不同的比较方式。余弦相似度比较向量的方向,常用于文档和通过学习得到的表示。基于相关性的相异度强调各维数值所呈现的变化形态,而非其绝对水平。对于表示存在与否的二元数据,可以使用交并比(Jaccard 相似度)进行比较,尤其是在共同缺失并不能提供有效信息的情况下。汉明距离统计等长序列中取值不同的位置数,而编辑距离则允许插入和删除操作。对于混合了数值变量和类别变量的数据,Gower 相异度将各变量对应的比较结果加以整合,同时需要明确规定权重和缺失值的处理方式。
若不指定转换方式,相似度与距离就不能互换。对于归一化为单位长度的非零向量,
因此,在单位球面上,余弦相异度与欧几里得距离的平方成正比。经过适当的中心化和归一化后,相关性与欧几里得距离之间也存在类似关系。然而,对相异度施加单调变换,并不能保持所有方法得到的层次结构不变。除并列值的处理规则可能造成影响外,单链接和全链接在严格递增变换下会保持合并顺序,因为取最小值和最大值的操作保持次序关系。平均链接则未必如此,因为对变换后的数值取平均,可能改变比较结果。缺失数据的处理还会带来进一步的复杂性:基于不同变量子集计算出的距离可能难以相互比较,即使每一次单独的计算看起来都很合理。
凝聚式聚类的链接准则
凝聚式方法反复从当前各簇中选取簇间相异度最小的两个簇。定义这种相异度的规则称为链接准则。对于簇 和 ,单链接和全链接分别定义为
单链接能够识别通过短距离逐步相连的细长或不规则群组,但也会出现链化现象:一连串中间观测对象可能将端点相距很远的区域连接起来。全链接能抵御这类链化效应,倾向于形成最大成对相异度较小的群组,但极端观测值可能对其合并决策产生很大影响。
平均链接采用两个簇之间所有观测对象对的相异度均值:
这种方法也称为非加权算术平均成对分组法,简称 UPGMA。这里的“非加权”指原始观测对象的贡献相同。相比之下,加权算术平均成对分组法(WPGMA)在更新距离时,对两个子簇赋予相同权重,而不考虑它们的大小。因此,原始观测对象的实际权重取决于合并历史。如果不说明加权约定,这些名称就可能引起误解。
沃德法采用了不同的思路:每次合并使簇内平方和增量最小的两个簇。对于欧氏空间中的向量,设 和 为两个簇的均值,则增量为
这一准则倾向于形成在平方欧氏距离意义下较为紧凑的群组。与K均值聚类一样,它关注簇内离散程度,但采用的是不可逆的局部合并,而不是反复重新分配观测对象。对于每一种给定的簇数,它通常不能得到全局最优划分。软件包显示的沃德法合并高度可能是 、其缩放值或其平方根,因此,输入距离与输出高度所采用的约定十分重要。
质心链接直接比较簇的均值,而中位链接则递归地对两个子簇的代表点取等权平均。两者都可能产生逆转,即较晚发生的合并,其高度反而低于较早发生的合并。新形成的质心与另一个簇的距离,可能比它的两个子簇与该簇的距离都更近。相比之下,在各自适用的假设下,标准的单链接、全链接、平均链接和沃德法的合并高度均单调不减。没有哪一种链接准则能脱离具体应用而始终占优:单链接刻画连通性,全链接强调最不利情况下的分离程度,平均链接概括簇间相异度,而沃德法则强调离散程度的增量。这些准则对什么样的群组才算内部一致,给出了不同的定义。
算法、递推公式与计算成本
最直接的凝聚式算法首先建立 个仅含一个对象的簇,找出距离最近的一对簇,将其合并,更新相关距离,然后重复这一过程。在 个阶段中,每个阶段都扫描当前所有簇对,就得到一种简单直接、时间复杂度为 的实现。存储所有原始对象之间的两两距离需要 的内存。压缩距离矩阵包含 个元素;当 时,仅以双精度存储这些元素就需要约 400 亿字节,即 40 GB,这还不包括工作数组和程序本身的额外开销。这种平方级的存储需求往往是实际应用中遇到的第一个障碍。
许多连接准则都可以使用 1967 年提出的 Lance–Williams 更新公式。若将 和 合并,则合并后的簇与另一簇 之间的相异度按下式更新:
各系数决定了所采用的连接准则。对于单连接,、,且 ,得到的结果是最小值。全连接将 改为 ,得到最大值。平均连接采用 、,以及 。Ward 法的更新则须采用与之相应的平方距离约定或目标函数约定。
更高效的算法利用结构性质,而不是反复扫描所有簇对。单连接与以观测对象为顶点的加权图的最小生成树密切相关。删除权重大于某一阈值的边后,得到的连通分量与在该阈值处截断单连接层次结构所得到的结果相同。罗宾·西布森于 1973 年发表的 SLINK 算法,在可以按需提供相异度的情况下,能够以 的时间和 的辅助存储空间构建单连接层次结构。最近邻链算法对若干标准连接准则可达到平方级的最坏情况时间复杂度,包括全连接、平均连接、加权平均连接,以及采用适当约定的 Ward 法。质心连接和中位数连接则不具备同样的保证。
相关的计算复杂性取决于输入模型。如果显式提供一个完整的任意相异度矩阵,那么输入规模本身就已经是平方级的。如果观测对象是低维空间中的向量,几何方法在有利情况下可以避免计算所有对象对之间的距离。优先队列可以加快候选项的选择,但必须谨慎管理已经失效的条目。近似邻居图、采样和预先压缩可以提升可扩展性,但也可能改变层次结构。并行计算较容易加速距离计算,却较难消除连续合并步骤之间的依赖。因此,报告性能时,需要区分距离的构建、聚类过程本身、存储以及树状图的绘制。
分裂方法及相关层次模型
分裂聚类最初将所有观测对象置于同一个簇中,然后递归地划分各簇,直至满足停止条件。二分操作不一定是某次凝聚合并的逆过程:自顶向下与自底向上的过程通常针对不同的局部决策进行优化。对于包含 个对象的簇,穷举其所有二分方案,需要考察 种互不相同、且两部分均非空的划分。因此,实用算法会采用启发式方法、几何准则或受限优化问题。设计这类算法时,主要需要确定当前应划分哪个簇、如何划分,以及何时停止。
DIANA 是一种经典的、基于相异度的分裂方法,与 Leonard Kaufman 和 Peter Rousseeuw 的研究工作密切相关。其常见形式是先选择一个直径较大的簇,再从中选取一个与其他观测对象的平均相异度较高的观测对象,用它初始化一个“分离组”。对于其他观测对象,如果它与剩余组的平均相异度大于它与分离组的平均相异度,就将其移入分离组。随后,对选定的簇重复这一过程。与穷举搜索不同,这是一种结构化的启发式方法;其输出会受到初始分离对象的选择及后续转移规则的影响。
其他分裂方法则递归地应用将数据划分为两个簇的方法。二分 k 均值算法反复使用 的 k 均值算法划分选定的簇,通常会尝试多种初始化方案,并根据离散程度准则选择划分结果。基于图的方法可以利用割或谱信息来划分相似度图。这些方法能够适应不同的分离性定义,但其节点高度并不天然具有与凝聚聚类的连接距离相同的含义。此外,即使数据更自然地适合划分为三个子群或不均衡的子群,递归二分也可能强行施加二分结构。
有些方法虽然生成层次结构,却不属于经典的成对连接框架。1996 年提出的 BIRCH 首先用聚类特征树概括数值型观测数据,之后可选择进一步聚类;其树主要是一种紧凑的数据结构,而不只是对所有原始对象对执行精确连接所得的结果。HDBSCAN 构建基于密度的簇层次结构,并根据各簇的持久性提取群组,同时允许将某些观测对象视为噪声。决策树学习也会生成嵌套划分,但监督式决策树依据目标结果选择划分,而经典层次聚类并不如此。同样,层次概率模型通过指定的概率分布表示嵌套的潜在结构,而非仅仅记录一系列合并过程。它们共有的树状形式不应掩盖这些不同的目标与解释。
选择划分与评估层次结构
层次结构将嵌套群组的构建与最终划分的选择分开。切割规则可以指定簇数 、相异度阈值,也可以采用更复杂的规则,对不同分支分别处理。对于完全解析的二叉凝聚树,在完成 次合并后停止,恰好得到 个簇。水平阈值不一定能得到所有可能的 值,因为多次合并可能发生在同一高度。针对不同分支分别处理的方法,可以在树的某些部分保留精细的子群,而在其他部分保留较粗的群组,但也会引入额外的假设和调参选择。
内部验证利用数据及其相异度本身来评估聚类结果。轮廓系数将一个观测对象与其所在簇内其他对象的平均相异度 ,同它与其他簇的平均相异度中的最小值 进行比较:
取值接近 1,表示在所用相异度度量下分离程度较高;接近 0,表示该对象靠近簇的边界;负值则表明该对象平均而言与另一个群组更接近。对于仅含一个对象的簇,需要约定其得分,通常设为零。对所有观测对象的轮廓系数取平均,可以比较候选切割方案,但这种做法可能偏向紧凑且分离良好的群组,而不利于在其他聚类模型下具有意义的细长结构或连通结构。
另一种评估方式是比较原始相异度 与共表型相异度 。两者的相关系数称为共表型相关系数,用来衡量树在这一意义上保留成对相异度关系的程度。较高的值表明层次表示较为忠实,但并不能证明数据集中存在离散的自然类别。层次结构也可以相当好地表示连续梯度,而具有生物学意义的划分未必会使该系数最大化。树状图中视觉上的分离程度也会受到坐标轴缩放和绘图方式的影响。
稳定性分析考察在对观测对象重采样、对特征重采样或添加测量噪声等扰动之后,各分支是否仍会出现。自助采样可以量化分支的可重复性,但采样单位和所假定的采样过程决定了结果的含义。在对样本进行聚类的分析中,对基因重采样与对患者重采样所回答的是不同的问题。如果存在外部标签,可以使用调整兰德指数等指标,将选定的划分与这些标签进行比较;这些指标并不能直接验证层次结构的每一个层级。当聚类用于后续预测研究时,如果利用评估集中的观测对象来学习预处理步骤,就可能造成数据泄漏。稳定性、几何分离程度、与外部标签的一致性以及对预测的实用价值,是不同类型的证据,而不是可以相互替代的正确性定义。
历史发展
层次分类的历史早于电子计算机。在数值聚类算法得到形式化表述之前很久,生物分类系统就已将生物组织为相互嵌套的类群。这类分类依据的是对解剖结构等特征的判断,而非一套统一规定的距离矩阵和更新规则。20世纪中叶,数值分类学的发展力求使相似性评估和分组过程更加明确、更易复现。计算机的应用使同时比较大量性状,并按照明确的操作序列构建树成为切实可行的做法。
罗伯特·索卡尔与查尔斯·米切纳于1958年发表的关于蜂类统计关系的研究,是平均连接数值分类法的重要早期文献。索卡尔与彼得·斯尼斯合著的《数值分类学原理》于1963年出版,推动了数值分类学整体研究纲领的确立。彼得·斯尼斯于1957年开展的研究,也促进了计算分类方法在微生物学中的应用。这些进展推动了基于大量实测性状的分类,同时也提出了一些至今仍受关注的问题,包括性状赋权、相似系数,以及观测到的相似性与演化历史之间的关系。
小乔·H. 沃德于1963年发表的论文提出了一种层次分组方法,其依据是目标函数以及合并群组所造成的信息损失。该方法中广泛使用的平方和形式,成为一类标准方法,可替代那些直接以成对距离的最小值、最大值或平均值定义的方法。G. N. 兰斯与W. T. 威廉斯于1967年提出了通用递推公式,将多种凝聚方法纳入统一的计算框架。S. C. 约翰逊于1967年对层次聚类方案开展的研究,阐明了层次结构与距离表示之间的数学关系。这些贡献使层次聚类逐渐成为一个系统的研究领域,而不再只是若干互不相关的分类方法的集合。
此后的算法研究主要致力于降低计算成本,并探究哪些性质能够支持高效构建。西布森于1973年提出的SLINK算法,是单连接法的一项重要成果。最近邻链方法以及后续的实现研究,使其他标准连接方法在大型数据集上的应用更加切实可行。考夫曼与鲁塞厄于1990年出版的《在数据中寻找群组》系统梳理了多种聚类方法,其中包括分裂式方法,并强调了图形解读与定量解释。20世纪90年代,大规模数据库分析推动了BIRCH等压缩方法和近似方法的发展。随着高通量测量的普及,层次聚类在分子生物学中也日益受到重视。如今,层次聚类的应用遍及传统统计软件、科学计算库和探索性分析界面,而可扩展性、可复现性以及树结构的解释仍持续受到关注。
在科学与信息领域的应用
一个重要应用是分析基因表达。表达矩阵可以以基因为行、以生物样本为列。对行进行聚类,可将不同样本中表达谱相似的基因归为一组;对列进行聚类,则可将表达模式相似的样本归为一组。迈克尔·艾森及其同事于 1998 年开展的研究,推动了层次聚类与彩色矩阵图相结合的方法在基因组分析中的应用。两个坐标轴均配有树状图的热图,能够显现出协同表达的区块。基于相关性的比较突出响应曲线形状的相似性,而基于欧氏距离的比较则会保留幅度差异,除非预处理消除了这些差异。基因聚为一组可能提示它们受到共同调控或具有共同功能,但这一结果本身并不能确立因果机制。
在生态学中,层次方法可依据物种组成对采样地点进行分组,也可依据物种的出现模式对物种进行分组。基于有无数据的比较与基于丰度的相异度,所强调的生态关系有所不同。某个地点拥有许多其他地点没有的物种,使用一种系数时可能显得十分独特,但使用另一种降低高丰度物种权重的系数时,其独特性可能就不那么明显。当目标群组必须构成连通区域时,可以施加空间邻接约束。这类受约束聚类所解决的问题,不同于不受约束的相似性分组:即使某些地点在生态上与远处的地点更为相似,它们仍可能因地理上相邻而被合并。
在文本分析和信息检索中,文档可以用词频—逆文档频率向量或学习得到的嵌入表示。层次分组支持从宽泛主题逐步浏览到更细分的主题,而不必事先确定一个固定的类别数。科学文献的一个顶层群组可以分为生物学和物理学,随后再在各分支内部继续细分。然而,涉及多个主题的文档很难自然地归入严格嵌套且互不重叠的层次结构。在计算机视觉中,对图像表示进行聚类,可以辅助浏览图像集合、查找重复图像,以及考察学习得到的特征空间。所得群组反映的是表示方式的特点:一种嵌入可能侧重物体身份、视觉纹理或语义关联。
商业和工业中的应用包括根据观测到的行为对客户进行分组、考察产品相似性,以及探索运行测量数据中的群组。层次结构可以揭示单一平面划分所掩盖的子群,而合并高度则提供了一种考察不同群组以多快速度合并的方式。在生物分类中,UPGMA 也可根据进化距离构建有根树,但若要将这棵树解释为系统发育学意义上的树,就需要作出描述性聚类所不需要的额外假设;尤其是在将分支高度解释为时间时,需要假定进化速率近似恒定,如同时钟一般。相似性树状图、进化树和组织分类体系看起来可能相似,但它们对各自分支所代表的含义作出了根本不同的主张。
局限性、敏感性与可复现的结果报告
对于有限数据集,总能构建出一个层次结构,即使观测对象实际上来自一片连续分布的点云,并不存在离散群组。因此,仅凭分支的存在,并不能证明数据中存在自然类别。凝聚方法还会作出不可逆的决策:如果早期某次合并是由噪声或不合适的相异度度量造成的,之后也无法撤销。分裂方法则存在相应的问题,即早期的一次划分会制约后续所有细分。这些限制使得嵌套结构易于解释,但也可能导致层次结构无法在每个分辨率下都与独立求得的最优划分一致。
离群值、采样密度不均和高维性对不同方法的影响各不相同。在单链接法中,一条稀疏的点链就可能将原本分离的群组连接起来;在全链接法中,极端观测值可能主导簇间距离;而沃德法可能为了限制离差平方和的增加,将细长的群组拆开。在高维空间中,有些分布会出现成对距离集中的现象,从而削弱远近观测对象之间的差异。特征选择和表征学习会改变这种几何结构,但也会引入建模上的选择。基于学习得到的嵌入构建的层次结构,描述的是该学习空间中的关系,而非对原始对象不依赖任何假设的组织方式。
并列情况是结果不唯一的另一个来源。如果多对簇具有相同的最小相异度,优先合并哪一对就可能影响后续合并,尤其是对于那些更新方式依赖于新形成簇的链接规则。因此,输入顺序、浮点数舍入以及实现细节都可能改变二叉树状图。对于单链接法,即使对并列合并作出的二叉化处理不同,固定阈值下的连通分量划分仍然不变。多分叉表示有时比任意选定的二叉树更能忠实表达同时发生的合并。另外,不应将叶节点的排列顺序与成员归属混为一谈:外观不同的树状图,可能表达的恰好是同一组嵌套群组。
为确保结果可复现,报告应明确说明观测单位、特征定义、预处理方式、缺失值处理方式、相异度度量、链接或分裂规则,以及划分选择准则。对于沃德聚类,距离是否取平方以及树状图高度的约定尤为重要。报告还应区分精确聚类与受图约束、基于采样或基于压缩的近似方法,并说明所用的软件实现,以及任何随机初始化方式或并列情况处理策略。验证若能针对具体主张展开,就最有参考价值:例如分支是否可复现、是否与外部类别对应、是否忠实保留距离关系,或是否有助于下游任务。一个层次结构可能支持其中一项主张,却不支持其他主张;要作出有实质意义的解释,就必须明确区分这些主张。