UPGMA

UPGMA （unweighted pair group method with arithmetic mean）是一种相对简单的层次聚类方法。这个方法存在另一种变体 WPGMA。这个方法的创始人被认为是Sokal和Michener 。

演算方法

UPGMA 演法构建出一棵有根树（树状图）表现相似矩阵或相异矩阵中的特征与结构。在算法里的每一步，距离最近的两个集群（子树）将被组合成一个更高级别的集群。任意两个集群${\mathcal {A}}$和${\mathcal {B}}$ 之间的距离，是由所有${\mathcal {A}}$里的$x$元素和所有${\mathcal {B}}$里的$y$元素的距离$d(x,y)$的平均值，即每个集群的元素之间的平均距离，其中 ${|{\mathcal {A}}|}$和${|{\mathcal {B}}|}$是该两个集群的基数（集合大小）：

$d_{{\mathcal {A}},{\mathcal {B}}}={1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\sum _{x\in {\mathcal {A}}}\sum _{y\in {\mathcal {B}}}d(x,y)$

换句话说，在每一次组合成新集群的步骤中，可以由$d_{{\mathcal {A}},X}$和$d_{{\mathcal {B}},X}$的加权平均给出集群${\mathcal {A}}\cup {\mathcal {B}}$和一个新集群$X$之间的距离：

$d_{({\mathcal {A}}\cup {\mathcal {B}}),X}={\frac {|{\mathcal {A}}|\cdot d_{{\mathcal {A}},X}+|{\mathcal {B}}|\cdot d_{{\mathcal {B}},X}}{|{\mathcal {A}}|+|{\mathcal {B}}|}}$

UPGMA 算法生成的有根树状图是一个超度量树，该树需要套用等速率的假设，也就是说根到每个分支尖端的距离皆相等。当尖端是同时采样的分子数据（即DNA 、 RNA和蛋白质）时，超度量假设就等同于分子钟假设。

示例

这个示例是基于JC69基因距离矩阵，该矩阵是根据五种细菌的5S 核糖体 RNA序列计算出来的，五种细菌如下所列 ：

枯草杆菌 Bacillus subtilis( $a$ )

嗜热脂肪芽孢杆菌 <i>Bacillus stearothermophilus</i>( $b$ )

魏斯氏菌 Lactobacillus viridescens( $c$ )

无原枯草杆菌 Acholeplasma modicum( $d$ )

藤黄微球菌 <i>Micrococcus luteus</i>( $e$ )

第一步

• 首次集群

假设有五个物件$(a,b,c,d,e)$和他们之间的相异矩阵$D_{1}$：

	a	b	c	d	e
a	0	17	21	31	23
b	17	0	30	34	21
c	21	30	0	28	39
d	31	34	28	0	43
e	23	21	39	43	0

在这里，$D_{1}(a,b)=17$是最小值，所以将$a$和$b$集群。

• 第一分支长度估计

令$u$表示现在$a$ 和 $b$ 的祖先。为了让$a$ 和 $b$ 与 $u$等距，假设$\delta (a,u)=\delta (b,u)=D_{1}(a,b)/2$，这对应到了超度量的假设。在这个范例中：$\delta (a,u)=\delta (b,u)=17/2=8.5$

• 第一次相异矩阵更新

然后将$D_{1}$更新成一个新的距离矩阵$D_{2}$（计算在下方），由于$a$和$b$的集群，该矩阵的尺寸减少了一行一列。（$D_{2}$中粗体表示的值是由加权平均计算出的新距离）

$D_{2}((a,b),c)=(D_{1}(a,c)\times 1+D_{1}(b,c)\times 1)/(1+1)=(21+30)/2=25.5$

$D_{2}((a,b),d)=(D_{1}(a,d)+D_{1}(b,d))/2=(31+34)/2=32.5$

$D_{2}((a,b),e)=(D_{1}(a,e)+D_{1}(b,e))/2=(23+21)/2=22$

$D_{2}$中的斜体值不受矩阵更新影响，因为他们与第一个集群中的元素完全美有关连。

第二步

• 第二次集群

现在重复前面的三个步骤，并从新的相异矩阵$D_{2}$开始

	(a,b)	ｃ	d	ｅ
(a,b)	0	25.5	32.5	22
ｃ	25.5	0	28	39
d	32.5	28	0	43
ｅ	22	39	43	0

在这个矩阵中， $D_{2}((a,b),e)=22$是$D_{2}$中的最小值，所以将$(a,b)$和元素$e$集成新群。

• 第二次分支长度估计

令$v$表示节点$(a,b)$和$e$的祖先。由超度量假设可以得到$a,b,e$三顶点到$v$的距离相等，即：$\delta (a,v)=\delta (b,v)=\delta (e,v)=22/2=11$，从而可以计算出$u$到$v$的距离$\delta (u,v)=\delta (e,v)-\delta (a,u)=\delta (e,v)-\delta (b,u)=11-8.5=2.5$

• 第二次距离矩阵更新

然后将$D_{2}$更新成新的距离矩阵$D_{3}$，数值计算如下：

$D_{3}(((a,b),e),c)=(D_{2}((a,b),c)\times 2+D_{2}(e,c)\times 1)/(2+1)=(25.5\times 2+39\times 1)/3=30$

$D_{3}(((a,b),e),d)=(D_{2}((a,b),d)\times 2+D_{2}(e,d)\times 1)/(2+1)=(32.5\times 2+43\times 1)/3=36$

第三、四步

重复上述动作可以得到$D_{3}$是

	((a,b),e)	c	d
((a,b),e)	0	30	36
c	30	0	28
d	36	28	0

$D_{4}$是：

	((a,b),e)	（c,d）
((a,b),e)	0	33
（c,d）	33	0

UPGMA树状图

这里显示了完成的树状图。它是超度量的，所有尖端（ $a$到$e$ ) 与$r$等距离 :

$\delta (a,r)=\delta (b,r)=\delta (e,r)=\delta (c,r)=\delta (d,r)=16.5$

这个树状图的根是它最深的节点$r$ 。

时间复杂度

构建 UPGMA 树的算法有$O(n^{3})$时间复杂度。使用一个堆维护两个即群之间的距离可以使时间达到$O(n^{2}\log n)$ . 另外Fionn Murtagh 提出了一个$O(n^{2})$时空复杂度的算法。

See also

• 邻接法
• 集群分析
• 单链接聚类
• 完全连锁聚类
• 层次即群
• DNA进化模型
• 分子钟

外部链接

• UPGMA聚类算法在Ruby中的实现（AI4R） （页面存档备份，存于互联网档案馆）
• 使用相似矩阵计算 UPGMA 的示例 （页面存档备份，存于互联网档案馆）
• 使用距离矩阵计算 UPGMA 的示例 （页面存档备份，存于互联网档案馆）