📂機械学習

階層的クラスタリング

アルゴリズム

入力

$p$ 次元のデータ $N$個と距離 $d$が与えられているとする。

---

ステップ 1.

それぞれの点を一つのクラスタと考える。最も近い二つのクラスタを一つにまとめる。

---

ステップ 2.

再び、最も近い二つのクラスタを一つにまとめる。

---

ステップ 3.

最後に、一つのクラスタが残るまで繰り返す。

---

出力

各データがどのクラスタに属しているかと、クラスタ間の距離を返す。

---

• こうして得られた右の木構造の図をデンドログラムという。

説明¹

クラスタリングアルゴリズムに属する教師なし学習法だ。木の図が示すように、階層的に表現されるクラスタを作ることが特徴だ。木を切る場所によって、求めるクラスタ数を得ることができる。

$k$ 平均クラスタリングとの最大の違いは、クラスタの数を定めずにクラスタリングができる点だ。そのため、結果は常に一定である。

長所と短所

区別すべきクラスタの数と初期値に依存せず、常に同じ結果を出す。ただし、計算複雑度が$O(n^{3})$と高い方だ。²

使用される距離関数

クラスタ間の距離の測定方法によって、異なるクラスタリング結果が得られる。

クラスタ内の各要素が他のクラスタ内の要素に比べて相対的に近い場合、クラスタはコンパクトと言われる。各クラスタがコンパクトで、他のクラスタからよく離れていれば、下記の三つの方法は似た結果を出すと言われる。

二つの与えられたクラスタを$G, H$、$i \in G$、$j \in H$とする。

シングルリンケージ^SL

二つのクラスタ間のすべての要素間の距離の中で、最も短い距離を選ぶ。最近傍技術とも呼ばれる。

$$ d_{\text{SL}}(G, H) = \min\limits_{\substack{i\in G \\ j\in H}} d(i,j) $$

コンプリートリンケージ^CL

SLの反対で、二つのクラスタ間のすべての要素間の距離の中で、最も長い距離を選ぶ。最遠傍技術とも呼ばれる。

$$ d_{\text{CL}}(G, H) = \max\limits_{\substack{i\in G \\ j\in H}} d(i,j) $$

グループ平均^GA

名前の通り、すべてのペアの距離の平均をクラスタ間の距離として選ぶ。$N$が各クラスタに含まれる要素の数とする場合、

$$ d_{\text{GA}}(G, H) = \dfrac{1}{N_{G} N_{H}} \sum\limits_{\substack{i\in G \\ j\in H}} d(i,j) $$