UPGMA

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

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



換句話說，在每一次組合成新集群的步驟中，可以由和的加權平均給出集群和一個新集群之間的距離：

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

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

枯草桿菌 Bacillus subtilis(  )

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

魏斯氏菌 Lactobacillus viridescens(  )

無原枯草桿菌 Acholeplasma modicum(  )

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

 第一步 

 首次集群

假設有五個物件和他們之間的相異矩陣：
a b c dea 0 17 21 31 23 b 17 0 30 34 21 c 21 30 0 28 39 d 31 34 28 0 43e23 21 39 43 0
在這裡，是最小值，所以將和集群。

 第一分支長度估計

令表示現在 和  的祖先。為了讓 和  與 等距，假設，這對應到了超度量的假設。在這個範例中：

 第一次相異矩陣更新

然後將更新成一個新的距離矩陣（計算在下方），由於和的集群，該矩陣的尺寸減少了一行一列。（中粗體表示的值是由加權平均計算出的新距離）

中的斜體值不受矩陣更新影響，因為他們與第一個集群中的元素完全美有關連。

 第二步 

 第二次集群

現在重複前面的三個步驟，並從新的相異矩陣開始
(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
在這個矩陣中， 是中的最小值，所以將和元素集成新群。

 第二次分支長度估計

令表示節點和的祖先。由超度量假設可以得到三頂點到的距離相等，即：，從而可以計算出到的距離

 第二次距離矩陣更新

然後將更新成新的距離矩陣，數值計算如下：

 第三、四步 
重複上述動作可以得到是

 ((a,b),e) c d ((a,b),e) 0 30 36 c 30 0 28 d 36 28 0
是：
 ((a,b),e) （c,d） ((a,b),e) 0 33 （c,d） 33 0

 UPGMA樹狀圖 
這裡顯示了完成的樹狀圖。它是超度量的，所有尖端（ 到 ) 與等距離 :

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

 時間複雜度 
構建 UPGMA 樹的算法有時間複雜度。使用一個堆維護兩個即群之間的距離可以使時間達到 . 另外Fionn Murtagh 提出了一個時空複雜度的算法。 

 参见 

 鄰接法
 集群分析
 单链接聚类
 完全连锁聚类
 層次即群
 DNA进化模型
 分子鐘

 外部連結 

 UPGMA聚类算法在Ruby中的实现（AI4R） 
 使用相似矩阵计算 UPGMA 的示例 
 使用距离矩阵计算 UPGMA 的示例 
Category:系统发生学
Category:计算系统发生学
Category:生物信息学算法