UPGMA

Agglomerative hierarchical clustering method

UPGMA（算術平均を用いた重み付けなしペアグループ法）は、単純な凝集型（ボトムアップ）階層的クラスタリング手法です。重み付け版であるWPGMAもあり、これらは一般的にソーカルとミッチェナーに帰属しています。^[1]

重み付けなしという用語は、すべての距離が計算される各平均に等しく寄与することを示しており、平均を達成するための数学的な方法を指すものではないことに注意してください。したがって、WPGMAの単純平均は重み付けされた結果を生成し、UPGMAの比例平均は重み付けされていない結果を生成します（動作例を参照）。^[2]

アルゴリズム

UPGMAアルゴリズムは、ペアワイズ類似度行列（または非類似度行列）に存在する構造を反映した根付き木（デンドログラム）を構築します。各ステップで、最も近い2つのクラスターが結合され、より高次のクラスターになります。サイズ（つまり、カーディナリティ）がそれぞれ2つと1つのクラスターの間の距離は、2つのクラスターと1つのクラスター内のオブジェクトのペア間のすべての距離の平均、つまり各クラスターの要素間の平均距離とみなされます。 ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {|{\mathcal {A}}|}}$ ${\displaystyle {|{\mathcal {B}}|}}$ ${\displaystyle d(x,y)}$ ${\displaystyle x}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle y}$ ${\displaystyle {\mathcal {B}}}$

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

言い換えれば、各クラスタリングステップにおいて、結合されたクラスターと新しいクラスター間の更新された距離は、2つのクラスターと1つのクラスター間の距離 の比例平均によって与えられます ${\displaystyle {\mathcal {A}}\cup {\mathcal {B}}}$ ${\displaystyle X}$ ${\displaystyle d_{{\mathcal {A}},X}}$ ${\displaystyle d_{{\mathcal {B}},X}}$

${\displaystyle 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、タンパク質など）である場合、超距離性仮定は分子時計を仮定することと同等になります。

動作例

この作業例は、5種類の細菌（枯草菌（）、バチルス・ステアロサーモフィルス（）、ラクトバチルス・ビリデセンス（ ）、アコレプラズマ・モディカム（）、およびミクロコッカス・ルテウス（） ）の5SリボソームRNA配列アライメントから計算されたJC69遺伝距離行列に基づいています。^{[3] [4]} ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle e}$

最初のステップ

• 最初のクラスタリング

5つの要素と、それらの間のペアワイズ距離の次の行列があると仮定します。 ${\displaystyle (a,b,c,d,e)}$ ${\displaystyle 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

この例では、は の最小値なので、要素とを結合します。 ${\displaystyle D_{1}(a,b)=17}$ ${\displaystyle D_{1}}$ ${\displaystyle a}$ ${\displaystyle b}$

• 最初の枝の長さの推定

とが現在接続されている ノードをとします。 と設定することで、要素と がから等距離にあること が保証されます。これは、超計量性仮説の期待値に対応します。とを結合する枝の長さは になります （最終的な樹状図 を参照） ${\displaystyle u}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \delta (a,u)=\delta (b,u)=D_{1}(a,b)/2}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle u}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle u}$ ${\displaystyle \delta (a,u)=\delta (b,u)=17/2=8.5}$

• 最初の距離行列の更新

次に、初期距離行列を新しい距離行列（下記参照）に更新します。この行列は、を でクラスタリングしたため、1行1列サイズが縮小されます。 の太字の値は、最初のクラスターの各要素と残りの各要素 間の距離を平均して計算された新しい距離に対応します。 ${\displaystyle D_{1}}$ ${\displaystyle D_{2}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle D_{2}}$ ${\displaystyle (a,b)}$

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

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

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

の斜体の値は、最初のクラスターに含まれない要素間の距離に対応するため、行列の更新の影響を受けません。 ${\displaystyle D_{2}}$

2番目のステップ

• 2番目のクラスタリング

新しい距離行列から始めて、前の3つのステップを繰り返します。 ${\displaystyle D_{2}}$

	(a,b)	c	d	e
(a,b)	0	25.5	32.5	22
c	25.5	0	28	39
d	32.5	28	0	43
e	22	39	43	0

ここで、は の最小値なので、クラスターと要素を結合します。 ${\displaystyle D_{2}((a,b),e)=22}$ ${\displaystyle D_{2}}$ ${\displaystyle (a,b)}$ ${\displaystyle e}$

• 2番目の枝長推定

とが現在接続されているノードをとします。超計量性制約により、またはから、および から に接続する枝は等しく、長さは次のとおりです。 ${\displaystyle v}$ ${\displaystyle (a,b)}$ ${\displaystyle e}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle v}$ ${\displaystyle e}$ ${\displaystyle v}$ ${\displaystyle \delta (a,v)=\delta (b,v)=\delta (e,v)=22/2=11}$

不足している枝の長さを推定します。 （最終的な樹状図 を参照） ${\displaystyle \delta (u,v)=\delta (e,v)-\delta (a,u)=\delta (e,v)-\delta (b,u)=11-8.5=2.5}$

• 2回目の距離行列の更新

次に、によるのクラスタリングにより、1行1列サイズが縮小された新しい距離行列（下記参照）への更新に進みます。 の太字の値は、比例平均によって計算された新しい距離に対応します。 ${\displaystyle D_{2}}$ ${\displaystyle D_{3}}$ ${\displaystyle (a,b)}$ ${\displaystyle e}$ ${\displaystyle D_{3}}$

${\displaystyle 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}$

この比例平均のおかげで、この新しい距離の計算は、（1つの要素）に対する（2つの要素）のより大きなサイズを考慮します。同様に、 ${\displaystyle (a,b)}$ ${\displaystyle e}$

${\displaystyle 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}$

したがって、比例平均は行列 の初期距離に等しい重みを与えます。これが、この方法が数学的手順ではなく初期距離に関して重み付けされていない理由です。 ${\displaystyle D_{1}}$

3番目のステップ

• 3回目のクラスタリング

更新された距離行列 から始めて、前の3つのステップをもう一度繰り返します。 ${\displaystyle D_{3}}$

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

ここで、は の最小値なので、要素とを結合します。 ${\displaystyle D_{3}(c,d)=28}$ ${\displaystyle D_{3}}$ ${\displaystyle c}$ ${\displaystyle d}$

• 3番目の枝の長さの推定

とが現在接続されているノードをとします。とを結合する枝の長さは になります （最終的な樹形図を参照）。 ${\displaystyle w}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle w}$ ${\displaystyle \delta (c,w)=\delta (d,w)=28/2=14}$

• 3番目の距離行列の更新

2つの要素とがそれぞれ平均計算にの寄与を持つことに留意すると、更新するエントリは1つです。 ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle 1}$

${\displaystyle D_{4}((c,d),((a,b),e))=(D_{3}(c,((a,b),e))\times 1+D_{3}(d,((a,b),e))\times 1)/(1+1)=(30\times 1+36\times 1)/2=33}$

最終ステップ

最終的な行列は次のとおりです。 ${\displaystyle D_{4}}$

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

そこで、クラスターとを結合します。 ${\displaystyle ((a,b),e)}$ ${\displaystyle (c,d)}$

とが現在接続されている（ルート）ノードを とします。とを結合する枝の長さは次のとおりです。 ${\displaystyle r}$ ${\displaystyle ((a,b),e)}$ ${\displaystyle (c,d)}$ ${\displaystyle ((a,b),e)}$ ${\displaystyle (c,d)}$ ${\displaystyle r}$

${\displaystyle \delta (((a,b),e),r)=\delta ((c,d),r)=33/2=16.5}$

残りの2つの枝の長さを推定します

${\displaystyle \delta (v,r)=\delta (((a,b),e),r)-\delta (e,v)=16.5-11=5.5}$

${\displaystyle \delta (w,r)=\delta ((c,d),r)-\delta (c,w)=16.5-14=2.5}$

UPGMAデンドログラム

これで樹状図は完成です。^[5]すべての先端（から）がから等距離であるため、これは超距離 です ${\displaystyle a}$ ${\displaystyle e}$ ${\displaystyle r}$

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

したがって、デンドログラムは最も深いノードであるを根としています。 ${\displaystyle r}$

他のリンケージとの比較

代替のリンケージ方式には、単一リンケージクラスタリング、完全リンケージクラスタリング、WPGMA平均リンケージクラスタリングなどがあります。異なるリンケージを実装するには、上記のアルゴリズムの距離行列更新ステップでクラスター間距離を計算するために異なる式を使用するだけです。完全リンケージクラスタリングは、代替の単一リンケージクラスタリング法の欠点、いわゆる連鎖現象を回避します。連鎖現象では、単一リンケージクラスタリングによって形成されたクラスターは、各クラスター内の多くの要素が互いに非常に離れている場合でも、単一の要素が互いに近いために強制的に結合される可能性があります。完全リンケージは、ほぼ等しい直径のコンパクトなクラスターを見つける傾向があります。^[6]

同じ距離行列から異なるクラスタリング法で得られた樹状図の比較。

単連鎖クラスタリング	完全連鎖クラスタリング	平均連鎖クラスタリング：WPGMA	平均連鎖クラスタリング：UPGMA

用途

• 生態学において、関連する記述変数（種組成など）のペアワイズ類似性に基づいて、サンプリング単位（植生区画など）を分類するための最も一般的な方法の1つです。^[7]例えば、海洋細菌と原生生物間の栄養相互作用を理解するために使用されています。^[8]
• バイオインフォマティクスでは、UPGMAは表現型 樹（フェノグラム）の作成に使用されます。UPGMAは当初、タンパク質電気泳動研究での使用を目的として設計されましたが、現在ではより洗練されたアルゴリズムのためのガイドツリーを作成するために最もよく使用されています。このアルゴリズムは、例えば配列アライメント手順で使用され、配列をアライメントする順序を1つ提案します。実際、ガイドツリーは、進化速度や系統学的類似性に関係なく、最も類似した配列をグループ化することを目的としており、まさにそれがUPGMAの目標です^[9]
• 系統学において、UPGMAは進化の速度が一定（分子時計仮説）であり、すべての配列が同時にサンプリングされたと仮定しています。この仮定が使用されているデータセットに対して検証され、正当化されない限り、関係性を推測するための方法としてはあまり評価されていません。「厳密な時計」の下でも、異なる時間にサンプリングされた配列は超距離的樹形図につながらないことに注意してください。

時間計算量

UPGMAツリーを構築するアルゴリズムの単純な実装には時間計算量があり、各クラスターにヒープを使用して他のクラスターとの距離を維持することで、その時間を短縮できます 。Fionn Murtaghは時間と空間のアルゴリズムを発表しました。^[10] ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{2}\log n)}$ ${\displaystyle O(n^{2})}$

参照

• 近隣結合
• クラスター分析
• 単連鎖クラスタリング
• 完全連鎖クラスタリング
• 階層的クラスタリング
• DNA進化モデル
• 分子時計

参考文献

1. Sokal , Michener (1958). "A statistics method for assessment systematic relationships". University of Kansas Science Bulletin . 38 : 1409–1438 .
2. Garcia S, Puigbò P. "DendroUPGMA: A dendrogram construction utility" (PDF) . p. 4
3. Erdmann VA, Wolters J (1986). 「公表された5S、5.8S、および4.5SリボソームRNA配列のコレクション」. Nucleic Acids Research . 14 Suppl (Suppl): r1–59. doi :10.1093/nar/14.suppl.r1 . PMC 341310. PMID  2422630. 
4. Olsen GJ (1988). 「リボソームRNAを用いた系統発生解析」. Ribosomes . Methods in Enzymology. Vol. 164. pp.  793– 812. doi :10.1016/s0076-6879(88)64084-5. ISBN 978-0-12-182065-7PMID 3241556  
5. Swofford DL, Olsen GJ, Waddell PJ, Hillis DM (1996). 「系統学的推論」 Hillis DM, Moritz C, Mable BK (編).分子系統学, 第2版. サンダーランド, MA: Sinauer. pp.  407– 514. ISBN 9780878932825.
6. Everitt, BS; Landau, S.; Leese, M. (2001).クラスター分析. 第4版. ロンドン: Arnold. pp.  62– 64.
7. Legendre P, Legendre L (1998).数値生態学. 環境モデリングの発展. 第20巻（第2英語版）. アムステルダム: Elsevier
8. Vázquez-Domínguez E, Casamayor EO, Català P, Lebaron P (2005年4月). 「異なる海洋従属栄養性ナノ鞭毛藻は、富栄養細菌群集の構成に異なる影響を与える」.微生物生態学. 49 (3): 474–85 . Bibcode :2005MicEc..49..474V. doi :10.1007/s00248-004-0035-5. JSTOR  25153200. PMID  16003474. S2CID  22300174
9. Wheeler TJ, Kececioglu JD (2007年7月). 「アラインメントのアラインメントによる多重アラインメント」. Bioinformatics . 23 (13): i559–68. doi : 10.1093/bioinformatics/btm226 . PMID  17646343.
10. Murtagh F (1984). 「階層的クラスタリングアルゴリズムの複雑性：最新技術」. Computational Statistics Quarterly . 1 : 101–113 .

外部リンク

• Ruby (AI4R) での UPGMA クラスタリングアルゴリズムの実装
• 類似度行列を用いた UPGMA の計算例
• 距離行列を用いた UPGMA の計算例

Retrieved from "https://en.wikipedia.org/w/index.php?title=UPGMA&oldid=1233469513"