この問題のテーマ・前提知識
- テーマ: 階層的クラスタリング（最近隣法・最遠隣法）とデンドログラムの対応、k-means 法の収束アルゴリズム
- 前提知識: ユークリッド距離・階層的クラスタリングの基礎（ウォード法） / 最近隣法（single linkage）と最遠隣法（complete linkage）の距離更新規則 / k-means 法の初期値依存性と収束手順
問題の概要
5個体の座標データと距離行列が与えられる。[1] 2種類のデンドログラム（ア）（イ）が最近隣法・最遠隣法のどちらに対応するかを、クラスター間距離の計算から特定する。[2] k-means 法で初期クラスター中心を2点に設定し、収束後のクラスター割り当てを求める小問が2つある。
解説
解法の方針：[1] 距離行列から最初に結合するペアを特定し、3グループになった段階で最近隣法・最遠隣法それぞれのクラスター間距離を計算してデンドログラムと照合する。[2] 初期中心との距離比較で各個体を割り当て、重心を更新して再割り当てを繰り返し収束させる。
[1]
1. 最初のクラスター形成
最近隣法、最遠隣法のどちらの手法を用いても、最も距離が近い 2 点が最初に結合する。
表 2 の距離行列を見ると、最小の距離は個体 4 と 5 の間の \(\sqrt{2}\) である。よって、最初に形成されるクラスターは以下のようになる。
\[\{4, 5\}\]
次に小さい距離は個体 1 と 2 の間の 2 である。個体 1 と 2 は最初のクラスター \(\{4, 5\}\) に含まれないため、2 番目に結合して以下のクラスターを形成する。
\[\{1, 2\}\]
デンドログラム（ア）を見ると、最も低い位置で結合しているペアが \(\{D, E\}\)、次に低い位置で結合しているペアが \(\{A, B\}\) である。よって、以下のように特定できる。
- \(\{D, E\} = \{4, 5\}\)
- \(\{A, B\} = \{1, 2\}\)
- 残った \(C\) は 個体 3
2. 個体・クラスター間の距離行列の計算
\(\{1, 2\}\)、\(\{4, 5\}\)、3 の 3 つのグループになった段階での、各グループ間の距離 \(d\) を計算する。
- 最近隣法（最短距離法）の場合
クラスター間の最短距離をとるため、計算式は以下のようになる。
\[d(\{1, 2\}, 3) = \min(d(1, 3), d(2, 3)) = \min(\sqrt{17}, \sqrt{5}) = \sqrt{5}\]
\[d(\{4, 5\}, 3) = \min(d(4, 3), d(5, 3)) = \min(\sqrt{8}, \sqrt{10}) = \sqrt{8}\]
最近隣法では \(\sqrt{5} < \sqrt{8}\) となるため、次は \(\{1, 2\}\) と 3 が結合する。
これは \(\{A, B\}\) と \(C\) が結合している （ア） のデンドログラムと一致する。 - 最遠隣法（最長距離法）の場合
クラスター間の最長距離をとるため、計算式は以下のようになる。
\[d(\{1, 2\}, 3) = \max(d(1, 3), d(2, 3)) = \max(\sqrt{17}, \sqrt{5}) = \sqrt{17}\]
\[d(\{4, 5\}, 3) = \max(d(4, 3), d(5, 3)) = \max(\sqrt{8}, \sqrt{10}) = \sqrt{10}\]
最遠隣法では \(\sqrt{10} < \sqrt{17}\) となるため、次は \(\{4, 5\}\) と 3 が結合する。
これは個体 4, 5 と個体 3 が結合している （イ） のデンドログラムと一致する。
従って、正解は ① である。
[2]
（１）
1. 初期割り当て
初期クラスター中心（個体 1、個体 2）との距離を比較し、近い方に各個体を割り当てると、クラスターは以下のように分かれる。
\[\{1\}, \quad \{2, 3, 4, 5\}\]
2. 中心の更新
それぞれのクラスターの重心（平均値）を計算し、新しい中心ベクトル \(\boldsymbol{\mu}_1, \boldsymbol{\mu}_2\) とする。
\[\boldsymbol{\mu}_1 = (10, 10)\]
\[\boldsymbol{\mu}_2 = \left(\frac{10+9+7+6}{4}, \frac{8+6+8+7}{4}\right) = (8, 7.25)\]
3. 再割り当て
境界付近にいる個体 2 についてのみ、2 つの新しい中心との距離を再評価する。
個体 2 の座標 (10, 8) は、新しい中心 (8, 7.25) よりも (10, 10) に近い。そのため、個体 2 は \(\{1\}\) のクラスターに移動する。
結果として、割り当てられるクラスターは以下のようになる。
\[\{1, 2\}, \quad \{3, 4, 5\}\]
従って、正解は ① である。
（２）
初期点 (a) の場合（中心：個体 2, 個体 4）
距離行列または座標から近い方に割り当てると、クラスターは以下のように形成される。
\[\{1, 2, 3\}, \quad \{4, 5\}\]
（※新しい重心は (9.67, 8) と (6.5, 7.5) となり、これ以上クラスターは変化しないため、これが最終出力となる。）
初期点 (b) の場合（中心：個体 3, 個体 4）
同様に近い方に割り当てると、クラスターは以下のように形成される。
\[\{2, 3\}, \quad \{1, 4, 5\}\]
（※新しい重心は (9.5, 7) と (7.67, 8.33) となり、これ以上変化しない。）
従って、正解は ④ である。
よくある質問
Q. 最近隣法と最遠隣法でデンドログラムの形はどう変わりますか？
最近隣法はクラスター間の最短距離を使うため、細長い鎖状のクラスターが形成されやすい（連鎖効果）。一方、最遠隣法は最長距離を使うため、コンパクトで球状に近いクラスターが形成されやすい。デンドログラムでは、最遠隣法の方が各クラスターが高い位置で結合する傾向がある。
Q. k-means 法は必ず最適解に収束しますか？
k-means 法は局所最適解に収束することは保証されているが、大域的最適解に収束する保証はない。初期値の選び方によって結果が異なる（本問の (a)(b) がその例）。実用上は初期値を変えて複数回実行し、クラスター内平方和が最小のものを採用することが多い。
Q. k-means の収束判定はどのように行いますか？
「クラスターの割り当てが前のステップから変化しなくなった」ことが収束の条件である。具体的には、重心を更新 → 再割り当て → 割り当て変化なし、のサイクルが1回転したら終了。本問では1〜2回の更新で収束しており、試験では手計算できる規模に設定されていることが多い。
コメント