クラスタリング・アルゴリズム
三中信宏
農業環境技術研究所
minaka@affrc.go.jp
http://cse.niaes.affrc.go.jp/minaka/
クラスター分析の前半で，OTU間の非類似度が，程度のちがいこそあれ，計量性をもつ「距離」によって数値化されたならば，次に，その距離尺度のもとで「近接している」と判断されたOTUの集合を逐次的に群（クラスター，cluster）の階層的な構造を組み上げる段階に進むことができる．このクラスタリングの手順（アルゴリズム）にもさまざまな方法がある．以下では，代表的と思われる「SAHN手法群」を紹介するが，その前にクラスタリングの基本的な考えを説明する．
クラスターを形成するための基準は「近いものどうしをまとめる」ことにある．とすると，まずはじめにOTU-OTU間・OTU-クラスター間・クラスター-クラスター間の「近さ」を定量化しなければならない．OTUとOTUとの「近さ」は採用された距離尺度によって自動的に決まるので，論じなければならないのはクラスターとの「近さ」をどう定義するかという点である．もっとも単純な「単連結法（single linkage method）」によるクラスタリングを例にとって説明する．
１）単連結法では，あるクラスターと別のクラスター（またはOTU）との「近さ」を「当該クラスターに属するOTUの間の距離尺度の最小値」によって定義する．したがって，クラスターどうしの「近さ」は，最も「近い」OTU間の距離と同一になる．いま，次のような距離行列がデータとして与えられたとしよう：
b 2
c 6 5
d 10 9 4
a b c
まずはじめに出発点として最小の距離をもつOTUのペアを見つける．この例では距離d[a,b]＝2をもつ(ab)というクラスターがそれにあたる．次に，クラスター(ab)と他のOTUとの近さを調べると：
d[(ab),c]＝min{d[a,c], d[b,c]}＝min{6, 5}＝5
d[(ab),d]＝min{d[a,d], d[b,d]}＝min{10, 9}＝9
d[c,d]＝4
であるから，距離行列は：
c 5
d 9 4
(ab) c
となる．
次にクラスターを形成するのは(cd)であるから，同様にクラスター間の「近さ」を計算すると：
d[(ab),(cd)]＝min{d[a,c], d[b,c], d[a,d], d[b,d]}＝min{6,5,10,9}＝5
より，距離行列は：
(cd) 5
(ab)
となる．よって，このクラスタリングの結果をデンドログラムで表示すると：
5 2
━━┳━━━━┳━━ a
┃ ┃
┃ ┗━━ b
┃ 4
┗━━┳━━━━ c
┃
┗━━━━ d
となる．
２）単連結法の対極にあるクラスタリング法は「完全連結法（complete linkage method）」である．この方法は，クラスター間の距離を「最大OTU間距離」によって定義する．上と同じデータを用いると：
d[(ab),c]＝max{d[a,c], d[b,c]}＝max{6, 5}＝6
d[(ab),d]＝max{d[a,d], d[b,d]}＝max{10, 9}＝10
d[c,d]＝4
c 6
d 10 4
(ab) c
となる．さらに
d[(ab),(cd)]＝max{d[a,c], d[b,c], d[a,d], d[b,d]}＝max{6,5,10,9}＝10
と計算される．自明のことだが，単連結法と比較して，完全連結法の方がクラスター・リンクの値が大きくなる（とくに，深いクラスターで顕著）．
10 2
━━┳━━━━┳━━ a
┃ ┃
┃ ┗━━ b
┃ 4
┗━━┳━━━━ c
┃
┗━━━━ d
３）生物学系のクラスター分析で最もよく用いられるアルゴリズムが「群平均法（group average method）」である．この方法は，数量表形学では「UPGMA（Unweighted Pair-Group Method using Arithmetic averages ）」と呼ばれてきた．群平均法では，クラスター間の「近さ」をOTU間距離の平均によって算出する．再び，上のデータを用いると：
d[(ab),c]＝(1/2)×{d[a,c]＋d[b,c]}＝(1/2)×(6＋5)＝5.5
d[(ab),d]＝(1/2)×{d[a,d]＋d[b,d]}＝(1/2)×(10＋9)＝9.5
d[c,d]＝4
c 5.5
d 9.5 4
(ab) c
となる．さらに
d[(ab),(cd)]＝(1/4)×{d[a,c]＋d[b,c]＋d[a,d]＋d[b,d]}＝(1/4)×(6＋5＋10＋9)＝7.5
得られるデンドログラムは下記の通り：
7.5 2
━━┳━━━━┳━━ a
┃ ┃
┃ ┗━━ b
┃ 4
┗━━┳━━━━ c
┃
┗━━━━ d
４）その他にも，クラスターに属するOTUの重心（セントロイド）間の距離をもって「近さ」を定義する「セントロイド法（centroid method）」や，クラスタリングの過程での形質の重み付けを行なう「McQuitty法」，群内の分散に対する群間の分散の比を最大化する「ウォード法（Ward法）」などさまざまなクラスタリングの手法が提唱されている．しかし，生物分類学や系統学に関していえば「群平均法（UPGMA）」以外の方法はないに等しい．
上記の単純な例では，手法によるクラスタリング結果の差が明瞭にはならなかった．しかし，もっと多くのOTUと形質を含む現実的なデータ（〈Ｒ〉の実例を別に示した）では，たとえ同一の距離尺度を用いても，クラスタリング手法によって結果が大きく異なってくることがある．概論で述べた通り，いずれが正しいのかを問うのは無意味である．われわれの分類認知能力が「美しい」と認めたパターンを産んだクラスター分析の手法が「勝ち」なのだ．
（8 September 2003）