UPGMA

UPGMA （unweighted pair group method with arithmetic mean）是一種相對簡單的層次聚類方法。這個方法存在另一種變體 WPGMA。這個方法的創始人被認為是Sokal和Michener 。 ^[1]

演算方法

UPGMA 演法構建出一棵有根樹（樹狀圖）表現相似矩陣或相異矩陣中的特徵與結構。在算法裡的每一步，距離最近的兩個集群（子樹）將被組合成一個更高級別的集群。任意兩個集群 $𝒜$ 和 $ℬ$ 之間的距離，是由所有 $𝒜$ 裡的 $x$ 元素和所有 $ℬ$ 裡的 $y$ 元素的距離 $d (x, y)$ 的平均值，即每個集群的元素之間的平均距離，其中 $| 𝒜 |$ 和 $| ℬ |$ 是該兩個集群的基數（集合大小）：

d_{𝒜, ℬ} = \frac{1}{| 𝒜 | \cdot | ℬ |} \sum_{x \in 𝒜} \sum_{y \in ℬ} d (x, y)

換句話說，在每一次組合成新集群的步驟中，可以由 $d_{𝒜, X}$ 和 $d_{ℬ, X}$ 的加權平均給出集群 $𝒜 \cup ℬ$ 和一個新集群 $X$ 之間的距離：

$d_{(𝒜 \cup ℬ), X} = \frac{| 𝒜 | \cdot d_{𝒜, X} + | ℬ | \cdot d_{ℬ, X}}{| 𝒜 | + | ℬ |}$

UPGMA 演算法生成的有根樹狀圖是一個超度量樹，該樹需要套用等速率的假設，也就是說根到每個分支尖端的距離皆相等。當尖端是同時採樣的分子數據（即DNA 、 RNA和蛋白質）時，超度量假設就等同於分子鐘假設。

示例

這個示例是基於JC69基因距離矩陣，該矩陣是根據五種細菌的5S 核糖體 RNA序列計算出來的，五種細菌如下所列^[2] ^[3]：

枯草桿菌 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$ 等距，假設 $δ (a, u) = δ (b, u) = D_{1} (a, b) / 2$ ，這對應到了超度量的假設。在這個範例中： $δ (a, u) = δ (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$ 的距離相等，即： $δ (a, v) = δ (b, v) = δ (e, v) = 22 / 2 = 11$ ，從而可以計算出 $u$ 到 $v$ 的距離 $δ (u, v) = δ (e, v) - δ (a, u) = δ (e, v) - δ (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樹狀圖

這裡顯示了完成的樹狀圖。^[4]它是超度量的，所有尖端（ $a$ 到 $e$ ) 與 $r$ 等距離 :

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

這個樹狀圖的根是它最深的節點 $r$ 。

時間複雜度

構建 UPGMA 樹的算法有 $O (n^{3})$ 時間複雜度。使用一個堆維護兩個即群之間的距離可以使時間達到 $O (n^{2} \log n)$ . 另外Fionn Murtagh 提出了一個 $O (n^{2})$ 時空複雜度的算法。 ^[5]

外部連結

[1] Template:Cite journal

[Erdmann1986-2] Template:Cite journal

[Olsen1988-3] Template:Cite journal

[Swofford1996-4] Template:Cite book

[5] Template:Cite journal

[1]

[2]

[3]

[4]

[5]

UPGMA

目录

演算方法

示例

第一步

第二步

第三、四步

UPGMA樹狀圖

時間複雜度

See also

外部連結

导航菜单

UPGMA

演算方法

示例

第一步

第二步

第三、四步

UPGMA樹狀圖

時間複雜度

See also

外部連結

导航菜单

搜索