树状图是一种树形图,用于表示嵌套群组的层次结构。它最常用于聚类分析,展示观测对象如何逐步合并为更大的簇,或划分为更小的簇。叶节点通常代表单个观测对象,内部节点则代表包含其下方所有叶节点的群组。在许多统计树状图中,每个内部节点的高度记录了相应群组合并时的相异度或聚类准则值。分支结构描述归属关系;若图中设有高度标尺,则还能提供定量信息。
结构与解读
用图论的术语来说,树状图是一棵有根树。其主要组成部分包括:
- **叶节点:**被分类的对象,如样本、物种、文档或变量。
- **内部节点:**由较小的簇组成的簇。
- **根节点:**包含图中所有对象的簇。
- **分支:**表示簇之间嵌套关系的连线。
- **节点高度:**当层次结构具有定量标尺时,为合并或分裂赋予的数值水平。
树状图可以纵向、横向或放射状绘制。绘图方向不会改变层次结构。
在常见的纵向树状图中,叶节点排列在底部,合并高度向上递增。如果两个观测对象在较低高度首次归入同一个簇,就表示在所选聚类方法下,两者关系密切。在较高位置发生合并,则说明该方法一直将相应群组分开,直到相异度或聚类代价达到较大值时才将它们合并。
叶节点从左到右的排列顺序通常并不唯一。交换某个内部节点的两个子节点,既不会改变簇的成员归属,也不会改变合并高度。因此,位置相邻的标签所代表的对象未必相似,叶节点之间的水平距离通常也没有定量意义。解读时,应关注连接叶节点的分支,以及它们首次共有的节点的高度。
因此,树状图并不是通常意义上将数据点绘制在坐标系中的图形:它的大部分几何特征取决于布局选择,而非直接表示测得的距离。
通过层次聚类构建
统计树状图主要由层次聚类产生;这种方法得到的是嵌套群组,而不只是单一的划分。
凝聚法
凝聚聚类开始时,将 个观测对象各自视为一个簇。每一步都按照某种衡量簇间相异度的规则,选择一对簇进行合并。这一过程持续进行,直到所有观测对象归入同一个簇。
如果每次都两两合并,最终树状图就有 个叶节点和 个内部节点。遇到并列情况时,可以按照具体实现所采用的规则处理,也可以表示为一次具有两个以上子节点的合并。
输入通常是相异度矩阵 ,其中 衡量观测对象 与 之间的差异程度。相异度可以来自欧几里得距离、相关关系的某种变换,或专为类别数据、序列数据及其他结构化数据设计的度量。它们不必满足度量空间中距离所需的全部条件。
分裂法
分裂聚类开始时,将所有观测对象归入同一个群组,然后反复将群组拆分为更小的群组。它同样会产生可用树状图展示的嵌套层次结构。分裂准则不必对应于任何凝聚式连接规则。
其关键性质是嵌套性:一个群组一旦被划分,后续形成的群组就必须完全位于它的某个后代群组之内。层次结构不允许群组任意重叠。
连接规则及其影响
在凝聚聚类中,连接规则定义了簇之间的相异度。对于相同的观测数据,不同规则可能产生差异显著的树状图。
设 和 为两个簇, 表示观测对象之间的相异度。
单连接法
单连接法采用跨簇观测对象之间的最小相异度:
它能够识别细长或形状不规则的群组,但容易出现链化效应:一连串彼此接近的观测对象,可能将两端相距很远的群组连接起来。
全连接法
全连接法采用跨簇观测对象之间的最大相异度:
它倾向于形成直径较小的群组,但单个距离较远的观测对象就可能显著影响某个簇何时合并。
平均连接法
一种常见的平均连接规则是,对所有跨簇观测对象之间的相异度取平均:
其中, 和 是两个簇中的观测对象数量。这一规则不同于加权平均连接法;后者在更新时,无论此前形成的两个簇大小如何,都赋予它们相同的权重。
沃德法
沃德法选择使簇内离差平方和增量最小的合并。对于欧几里得空间中的观测对象,这一增量为
其中, 和 为簇的质心。
沃德法可以从最小二乘法的角度解释,倾向于形成紧凑的群组。其标准解释依赖于平方欧几里得距离的几何框架。不同软件的约定有所不同:显示的高度可能直接表示上述增量,也可能表示某种相关变换,因此不同实现的高度标尺不能直接互换。
将树状图切分为若干簇
一张树状图同时表示多种可能的聚类结果。对于合并高度不递减的常规树状图,作一条水平切线,就能选出在该高度仍彼此分离的群组。
每次切分都会产生观测对象的一个集合划分:每个观测对象恰好属于一个选定的簇。切分位置越低,通常得到的簇越多;切分位置越高,得到的簇越少。
可以通过以下方式选择聚类结果:
- 指定相异度阈值;
- 指定所需的簇数;
- 考察相邻合并高度之间的较大间隔;
- 应用评价聚类质量或稳定性的外部准则。
较大的垂直间隔可能提示一个有用的分界,但并不能证明某个簇数是唯一正确的选择。合并高度相同时,阈值切分还可能使簇数直接从一个值跳到另一个值。此时,若要得到介于两者之间的簇数,可能需要额外约定如何处理并列情况。
某些连接方法,尤其是质心连接法和中位数连接法,可能产生倒置,即较晚发生的合并,其高度反而低于较早发生的合并。这类树状图仍能表示嵌套的成员归属关系,但按通常的水平切分方式解读时需要谨慎。
数学解释
集合 上的有限层次结构,可以描述为一个由非空子集组成的集合族 。该集合族包含 及其所有单元素子集,并且任意 都满足
这一嵌套条件将层次群组与任意重叠的集合族区分开来。
假设该层次结构具有非负高度,且从任一节点向根节点移动时,高度不递减。对于不同的观测对象 和 ,将共表型相异度 定义为包含两者的最小簇的高度。令 。则有
这就是强三角不等式,也是超度量空间的特征。如果不同观测对象可以在零高度合并,那么这一构造得到的是伪超度量,而不是能够严格区分不同对象的超度量。
因此,即便原始相异度不满足超度量条件,高度不递减的树状图仍表示了对数据的一种超度量描述。共表型值通常不同于原始的成对相异度:层次结构是对这些相异度的概括,而非精确保留。
一种诊断方法是使用相关系数,比较原始相异度与共表型相异度。两者高度一致,说明树保留了成对关系结构的某些方面,但仅凭这一点,不能验证某个特定簇数或实质性解释是否合理。
应用与相关图形
树状图广泛用于探索性统计学和机器学习。其应用包括文档分组、生态群落比较、化合物归类,以及考察变量之间的关系。
在基因表达分析中,树状图常与热图并列展示。一个层次结构可以用于组织样本,另一个则用于组织基因或其他测量特征。由此形成的行列排列能够使某些模式显现出来,但显示出的块状结构取决于预处理和聚类方法的选择。
树状图也与系统发育树相似,后者表示有关进化关系的假说。这两个术语并不能完全互换。统计聚类树状图并不天然证明共同祖先的存在,其合并高度也不一定代表进化时间或累积的进化变化。同样,组织结构图和其他分支图也可以展示层次结构,而不表示数值上的相异度。
局限与解读
树状图既反映数据结构,也反映分析时所作的选择。
**预处理很重要。**使用欧几里得距离时,如果某个变量的数值尺度远大于其他变量,而分析中又未妥善处理尺度问题,该变量就可能主导结果。数据变换、特征选择和缺失数据插补也可能改变层次结构。
**连接规则规定了分组准则。**单连接法强调连通性,全连接法强调直径,沃德法强调组内的平方离散程度。它们产生的树状图回答的是操作定义不同的问题。
**即使不存在泾渭分明的群组,也总能构造出层次结构。**聚类算法可以把来自连续分布的观测对象组织成树。图中存在分支,并不意味着底层总体中存在离散类别。
**分支本身并不表达不确定性。**合并高度不是P值、置信水平,也不是某个簇真实存在的概率。基于自助采样或其他扰动的方法,可以评估稳定性的某些方面,但结果取决于重采样方案及其假设。
**早期决策可能无法撤销。**标准凝聚法不会重新考虑此前的合并。因此,观测数据的微小变化或距离并列的情况,都可能改变树的后续部分。
**大型树状图可能难以阅读。**截断和折叠分支可以提高可读性,但也会隐藏细节。调整叶节点顺序可以在不改变层次结构的前提下帮助比较,不过视觉上突出的模式也可能部分源于这种排序。
**计算成本可能很高。**存储所有成对相异度所需的空间,与观测对象数量的平方成正比。运行时间取决于连接规则及其实现方式;在某些情形下,可以使用无需完整存储距离矩阵的算法。