凝集型階層的クラスタリング法
完全リンククラスタリングは、凝集型 階層的クラスタリング のいくつかの手法の 1 つです 。プロセスの開始時には、各要素は独自のクラスターに存在します。その後、クラスターは順次結合されてより大きなクラスターになり、最終的にすべての要素が同じクラスターになります。この方法は、 最遠近傍クラスタリング とも呼ばれます。クラスタリングの結果は、クラスター融合の順序と各融合が行われた距離を示す 樹状図 として視覚化できます。 [1] [2] [3]
クラスタリング手順 各ステップで、最短距離で隔てられた 2 つのクラスターが結合されます。「最短距離」の定義は、さまざまな凝集型クラスタリング手法を区別するものです。完全リンク クラスタリングでは、2 つのクラスター間のリンクにはすべての要素ペアが含まれ、クラスター間の距離は、互いに最も離れた 2 つの要素 (各クラスターに 1 つ) 間の距離に等しくなります 。 どのステップでも残っているこれらのリンクのうち最短のリンクによって、要素が関与する 2 つのクラスターが融合されます。
数学的には、完全なリンク関数（クラスター間の 距離 ） は次の式で表されます。
D
(
X
,
Y
)
{\displaystyle D(X,Y)}
X
{\displaystyle X}
Y
{\displaystyle Y}
D
(
X
,
Y
)
=
max
x
∈
X
,
y
∈
Y
d
(
x
,
y
)
{\displaystyle D(X,Y)=\max _{x\in X,y\in Y}d(x,y)}
どこ
d
(
x
,
y
)
{\displaystyle d(x,y)}
要素と の 間の距離です 。
x
∈
X
{\displaystyle x\in X}
y
∈
Y
{\displaystyle y\in Y}
X
{\displaystyle X}
2 つの要素セット (クラスター) です 。
Y
{\displaystyle Y}
アルゴリズム
素朴な計画 次のアルゴリズムは、 古いクラスターが新しいクラスターにマージされるときに近接行列の行と列を消去する凝集方式です。近接行列 D には、 すべて の 距離 d ( i , j ) が含まれます 。 クラスタリング に は シーケンス 番号 0、1、......、( n − 1) が割り当てられ、 L ( k ) は k 番目のクラスタリングのレベルです。シーケンス番号 mのクラスターは ( m )で示され、クラスター ( r ) と ( s )間の近接性は d [( r ),( s )]で示されます 。
N
×
N
{\displaystyle N\times N}
完全なリンク クラスタリング アルゴリズムは、次の手順で構成されます。
レベルとシーケンス番号 を持つ分離クラスタリングから始めます 。
L
(
0
)
=
0
{\displaystyle L(0)=0}
m
=
0
{\displaystyle m=0}
現在のクラスタリング内のすべてのクラスターのペアの中で最大値となる場所 に従って 、現在のクラスタリングで最も類似したクラスターのペア (ペア とします) を検索します。
(
r
)
,
(
s
)
{\displaystyle (r),(s)}
d
[
(
r
)
,
(
s
)
]
=
max
d
[
(
i
)
,
(
j
)
]
{\displaystyle d[(r),(s)]=\max d[(i),(j)]}
シーケンス番号を増分します: 。クラスタ とを 1つのクラスタにマージして次のクラスタリングを形成します 。このクラスタリングのレベルを に設定します。
m
=
m
+
1
{\displaystyle m=m+1}
(
r
)
{\displaystyle (r)}
(
s
)
{\displaystyle (s)}
m
{\displaystyle m}
L
(
m
)
=
d
[
(
r
)
,
(
s
)
]
{\displaystyle L(m)=d[(r),(s)]}
クラスター および に対応する行と列を削除し 、新しく形成されたクラスター に対応する行と列を追加して、 近接行列 を更新します 。 で示される新しいクラスター と古いクラスター間の近接性 は と定義されます 。
D
{\displaystyle D}
(
r
)
{\displaystyle (r)}
(
s
)
{\displaystyle (s)}
(
r
,
s
)
{\displaystyle (r,s)}
(
k
)
{\displaystyle (k)}
d
[
(
r
,
s
)
,
(
k
)
]
=
max
{
d
[
(
k
)
,
(
r
)
]
,
d
[
(
k
)
,
(
s
)
]
}
{\displaystyle d[(r,s),(k)]=\max\{d[(k),(r)],d[(k),(s)]\}}
すべてのオブジェクトが 1 つのクラスター内にある場合は停止します。それ以外の場合は手順 2 に進みます。
最適に効率的なスキーム 上で説明したアルゴリズムは理解しやすいが、複雑である 。1976年5月、D. Defaysは、 単一リンククラスタリング 用の類似アルゴリズムSLINKに触発され、複雑性のみで最適に効率的なアルゴリズム CLINK（1977年発表） [4] を提案した。
O
(
n
3
)
{\displaystyle O(n^{3})}
O
(
n
2
)
{\displaystyle O(n^{2})}
動作例 この実例は、 5種類の細菌 （枯草菌 （ ）、 バチルス・ステアロサーモフィルス （ ）、 ラクトバチルス ・ビリデセンス（ ） 、アコレプラズマ・ モディカム （ ）、および ミクロコッカス・ルテウス （ ）） の 5S リボソームRNA 配列 アライメントから 計算されたJC69遺伝 距離行列に基づいています。 [5] [6]
a
{\displaystyle a}
b
{\displaystyle b}
c
{\displaystyle c}
d
{\displaystyle d}
e
{\displaystyle e}
最初のステップ 5 つの要素と、それらの間のペアワイズ距離の次の行列 があると仮定します 。
(
a
,
b
,
c
,
d
,
e
)
{\displaystyle (a,b,c,d,e)}
D
1
{\displaystyle D_{1}}
この例では、 は の最小値な ので、要素 と を結合します 。
D
1
(
a
,
b
)
=
17
{\displaystyle D_{1}(a,b)=17}
D
1
{\displaystyle D_{1}}
a
{\displaystyle a}
b
{\displaystyle b}
と が 接続される ノードを とします 。を設定すると 、要素 と が から等距離にあることが保証されます。これは、 超距離性 仮説の期待値に対応します。 と を結合する枝の 長さは ( 最終的な樹形図を参照 )
になります。
u
{\displaystyle u}
a
{\displaystyle a}
b
{\displaystyle b}
δ
(
a
,
u
)
=
δ
(
b
,
u
)
=
D
1
(
a
,
b
)
/
2
{\displaystyle \delta (a,u)=\delta (b,u)=D_{1}(a,b)/2}
a
{\displaystyle a}
b
{\displaystyle b}
u
{\displaystyle u}
a
{\displaystyle a}
b
{\displaystyle b}
u
{\displaystyle u}
δ
(
a
,
u
)
=
δ
(
b
,
u
)
=
17
/
2
=
8.5
{\displaystyle \delta (a,u)=\delta (b,u)=17/2=8.5}
次に、初期の近接行列を新しい近接行列 (下記参照)に 更新します。この行列は、 をでクラスタリングしたため、サイズが 1 行 1 列縮小されます 。 の太字の値は、 最初のクラスターの各要素 と残りの各要素
間の 最大距離 を維持して計算された新しい距離に対応します。
D
1
{\displaystyle D_{1}}
D
2
{\displaystyle D_{2}}
a
{\displaystyle a}
b
{\displaystyle b}
D
2
{\displaystyle D_{2}}
(
a
,
b
)
{\displaystyle (a,b)}
D
2
(
(
a
,
b
)
,
c
)
=
m
a
x
(
D
1
(
a
,
c
)
,
D
1
(
b
,
c
)
)
=
m
a
x
(
21
,
30
)
=
30
{\displaystyle D_{2}((a,b),c)=max(D_{1}(a,c),D_{1}(b,c))=max(21,30)=30}
D
2
(
(
a
,
b
)
,
d
)
=
m
a
x
(
D
1
(
a
,
d
)
,
D
1
(
b
,
d
)
)
=
m
a
x
(
31
,
34
)
=
34
{\displaystyle D_{2}((a,b),d)=max(D_{1}(a,d),D_{1}(b,d))=max(31,34)=34}
D
2
(
(
a
,
b
)
,
e
)
=
m
a
x
(
D
1
(
a
,
e
)
,
D
1
(
b
,
e
)
)
=
m
a
x
(
23
,
21
)
=
23
{\displaystyle D_{2}((a,b),e)=max(D_{1}(a,e),D_{1}(b,e))=max(23,21)=23}
斜体で示された値は、 最初のクラスターに含まれない要素間の距離に対応するため、マトリックスの更新による影響を受けません。
D
2
{\displaystyle D_{2}}
第二段階 新しい距離行列から始めて、前の 3 つの手順を繰り返します 。
D
2
{\displaystyle D_{2}}
ここで、 は の最低値な ので、クラスターを 要素 と結合します 。
D
2
(
(
a
,
b
)
,
e
)
=
23
{\displaystyle D_{2}((a,b),e)=23}
D
2
{\displaystyle D_{2}}
(
a
,
b
)
{\displaystyle (a,b)}
e
{\displaystyle e}
と が現在接続されている ノードを とします 。 超距離制約により、 または を に 、および を に接続する枝は 等しく、合計の長さは次のようになります。
v
{\displaystyle v}
(
a
,
b
)
{\displaystyle (a,b)}
e
{\displaystyle e}
a
{\displaystyle a}
b
{\displaystyle b}
v
{\displaystyle v}
e
{\displaystyle e}
v
{\displaystyle v}
δ
(
a
,
v
)
=
δ
(
b
,
v
)
=
δ
(
e
,
v
)
=
23
/
2
=
11.5
{\displaystyle \delta (a,v)=\delta (b,v)=\delta (e,v)=23/2=11.5}
欠けている枝の長さを推測します:
( 最終的な樹形図を参照 )
δ
(
u
,
v
)
=
δ
(
e
,
v
)
−
δ
(
a
,
u
)
=
δ
(
e
,
v
)
−
δ
(
b
,
u
)
=
11.5
−
8.5
=
3
{\displaystyle \delta (u,v)=\delta (e,v)-\delta (a,u)=\delta (e,v)-\delta (b,u)=11.5-8.5=3}
次に、行列を新しい距離行列（下記参照）に 更新します。この行列は、 の クラスタリングにより、サイズが 1 行 1 列縮小されます 。
D
2
{\displaystyle D_{2}}
D
3
{\displaystyle D_{3}}
(
a
,
b
)
{\displaystyle (a,b)}
e
{\displaystyle e}
D
3
(
(
(
a
,
b
)
,
e
)
,
c
)
=
m
a
x
(
D
2
(
(
a
,
b
)
,
c
)
,
D
2
(
e
,
c
)
)
=
m
a
x
(
30
,
39
)
=
39
{\displaystyle D_{3}(((a,b),e),c)=max(D_{2}((a,b),c),D_{2}(e,c))=max(30,39)=39}
D
3
(
(
(
a
,
b
)
,
e
)
,
d
)
=
m
a
x
(
D
2
(
(
a
,
b
)
,
d
)
,
D
2
(
e
,
d
)
)
=
m
a
x
(
34
,
43
)
=
43
{\displaystyle D_{3}(((a,b),e),d)=max(D_{2}((a,b),d),D_{2}(e,d))=max(34,43)=43}
第三ステップ 更新された距離行列から始めて、前の 3 つの手順をもう一度繰り返します 。
D
3
{\displaystyle D_{3}}
ここで、 は の最小値な ので、要素 と を結合します 。
D
3
(
c
,
d
)
=
28
{\displaystyle D_{3}(c,d)=28}
D
3
{\displaystyle D_{3}}
c
{\displaystyle c}
d
{\displaystyle d}
と が接続された ノードを とします 。 と を 接続する枝の 長さは です ( 最終的な樹形図を参照 )。
w
{\displaystyle w}
c
{\displaystyle c}
d
{\displaystyle d}
c
{\displaystyle c}
d
{\displaystyle d}
w
{\displaystyle w}
δ
(
c
,
w
)
=
δ
(
d
,
w
)
=
28
/
2
=
14
{\displaystyle \delta (c,w)=\delta (d,w)=28/2=14}
更新するエントリは 1 つだけです:
D
4
(
(
c
,
d
)
,
(
(
a
,
b
)
,
e
)
)
=
m
a
x
(
D
3
(
c
,
(
(
a
,
b
)
,
e
)
)
,
D
3
(
d
,
(
(
a
,
b
)
,
e
)
)
)
=
m
a
x
(
39
,
43
)
=
43
{\displaystyle D_{4}((c,d),((a,b),e))=max(D_{3}(c,((a,b),e)),D_{3}(d,((a,b),e)))=max(39,43)=43}
最終ステップ 最終的な マトリックスは次のようになります。
D
4
{\displaystyle D_{4}}
そこで、クラスター とを結合します 。
(
(
a
,
b
)
,
e
)
{\displaystyle ((a,b),e)}
(
c
,
d
)
{\displaystyle (c,d)}
とが現在接続されている (ルート) ノードを とします 。 と を接続するブランチの長さは次 のように なります。
r
{\displaystyle r}
(
(
a
,
b
)
,
e
)
{\displaystyle ((a,b),e)}
(
c
,
d
)
{\displaystyle (c,d)}
(
(
a
,
b
)
,
e
)
{\displaystyle ((a,b),e)}
(
c
,
d
)
{\displaystyle (c,d)}
r
{\displaystyle r}
δ
(
(
(
a
,
b
)
,
e
)
,
r
)
=
δ
(
(
c
,
d
)
,
r
)
=
43
/
2
=
21.5
{\displaystyle \delta (((a,b),e),r)=\delta ((c,d),r)=43/2=21.5}
残りの 2 つの枝の長さを推定します。
δ
(
v
,
r
)
=
δ
(
(
(
a
,
b
)
,
e
)
,
r
)
−
δ
(
e
,
v
)
=
21.5
−
11.5
=
10
{\displaystyle \delta (v,r)=\delta (((a,b),e),r)-\delta (e,v)=21.5-11.5=10}
δ
(
w
,
r
)
=
δ
(
(
c
,
d
)
,
r
)
−
δ
(
c
,
w
)
=
21.5
−
14
=
7.5
{\displaystyle \delta (w,r)=\delta ((c,d),r)-\delta (c,w)=21.5-14=7.5}
完全連鎖樹状図
WPGMA デンドログラム 5S データ これで樹形図が完成しました。すべての先端 (から ) が から等距離にある ため、樹形図は超距離です 。
a
{\displaystyle a}
e
{\displaystyle e}
r
{\displaystyle r}
δ
(
a
,
r
)
=
δ
(
b
,
r
)
=
δ
(
e
,
r
)
=
δ
(
c
,
r
)
=
δ
(
d
,
r
)
=
21.5
{\displaystyle \delta (a,r)=\delta (b,r)=\delta (e,r)=\delta (c,r)=\delta (d,r)=21.5}
したがって、樹形図は 、最も深いノードである によってルート化されます。
r
{\displaystyle r}
他のリンクとの比較 代替のリンク スキームには、単一リンク クラスタリングと 平均リンク クラスタリングがあります。単純なアルゴリズムで異なるリンクを実装するには、近接行列の初期計算と上記のアルゴリズムのステップ 4 で、異なる式を使用してクラスター間距離を計算するだけです。ただし、任意のリンクに対して最適に効率的なアルゴリズムは利用できません。調整する必要がある式は、太字で強調表示されています。
完全連鎖クラスタリングは、代替の単一連鎖 法の欠点である 、いわゆる 連鎖現象 を回避します。連鎖現象とは、単一連鎖クラスタリングによって形成されたクラスターが、各クラスター内の多くの要素が互いに非常に離れている場合でも、単一の要素が互いに近いために強制的に一緒になる可能性がある現象です。完全連鎖は、ほぼ等しい直径のコンパクトなクラスターを見つける傾向があります。 [7]
参照
参考文献
^ Sorensen T (1948). 「種の類似性に基づいて植物社会学で等振幅のグループを確立する方法とデンマークの共有地の植生分析へのその応用」 Biologiske Skrifter . 5 : 1–34. ^ Legendre P, Legendre L (1998). Numerical Ecology (第2英語版). p. 853. ^ Everitt BS、 Landau S 、Leese M (2001)。 クラスター分析 （第4版）。ロンドン：アーノルド 。ISBN 0-340-76119-9 。 ^ Defays D (1977). 「完全なリンク方式のための効率的なアルゴリズム」. The Computer Journal . 20 (4). 英国コンピュータ協会: 364–366. doi :10.1093/comjnl/20.4.364. ^ Erdmann VA、 Wolters J (1986)。「公開された 5S、5.8S 、 および 4.5S リボソーム RNA 配列のコレクション」。 核酸研究 。14 補足 (補足): r1-59。doi :10.1093/ nar /14.suppl.r1。PMC 341310。PMID 2422630 。 ^ Olsen GJ (1988). 「リボソームRNAを用いた系統発生解析」 リボソーム 酵素学の方法 第164巻 pp. 793–812. doi :10.1016/s0076-6879(88)64084-5. ISBN 978-0-12-182065-7 . PMID 3241556。 ^ エヴェリット、ランドー、リース（2001）、62-64ページ。
さらに読む シュペス H (1980)。 クラスター分析アルゴリズム 。チチェスター: エリス・ホーウッド。 
![{\displaystyle d[(r),(s)]=\max d[(i),(j)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28d0b897d784d3831c70b8f2877021ce6a47ed0a)
![{\displaystyle L(m)=d[(r),(s)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66eadf90f909de45d1946b56b1c0a023c3e206ef)
![{\displaystyle d[(r,s),(k)]=\max\{d[(k),(r)],d[(k),(s)]\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/56199e5f99db0c2c152b2a28ee8b9ba1a8ed620c)
