凝集型クラスタリングとは

階層的クラスタリングの種別。
個々のデータ点をそれぞれ別のクラスタとみなすところからスタートして、最も近いクラスタのペアを順次マージしてクラスタを減らしていく。

主な手法

単連結法（最短距離法）

クラスタのペア \(C_1, C_2\) に対し、クラスタ間をまたぐ 距離が最も近い データサンプルのペアを見つけ、その距離

\[\underset{\boldsymbol{x}^{(i)} \in C_1, \boldsymbol{x}^{(j)} \in C_2}{\min} \left\| \boldsymbol{x}^{(i)} - \boldsymbol{x}^{(j)} \right\|\]

をクラスタ間の遠さとみなす。

完全連結法（最長距離法）

クラスタのペア \(C_1, C_2\) に対し、クラスタ間をまたぐ 距離が最も遠い データサンプルのペアを見つけ、その距離

\[\underset{\boldsymbol{x}^{(i)} \in C_1, \boldsymbol{x}^{(j)} \in C_2}{\max} \left\| \boldsymbol{x}^{(i)} - \boldsymbol{x}^{(j)} \right\|\]

をクラスタ間の遠さとみなす。

群平均法

クラスタのペア \(C_1, C_2\) に対し、クラスタ間をまたぐデータサンプルの 全ペアの組み合わせの平均距離

\[\cfrac{1}{|C_1||C_2|} \displaystyle \sum_{\boldsymbol{x}^{(i)} \in C_1} \sum_{\boldsymbol{x}^{(j)} \in C_2} \left\| \boldsymbol{x}^{(i)} - \boldsymbol{x}^{(j)} \right\|\]

をクラスタ間の遠さとみなす。

ウォード法

クラスタのペア \(C_1, C_2\) に対し、クラスタをマージする前の偏差平方和

\[\begin{eqnarray} SSD(C_1) &=& \displaystyle \sum_{\boldsymbol{x}^{(i)} \in C_1} \left\| \boldsymbol{x}^{(i)} - \overline{\boldsymbol{x}}_{C_1} \right\|^2 \\ SSD(C_2) &=& \displaystyle \sum_{\boldsymbol{x}^{(i)} \in C_2} \left\| \boldsymbol{x}^{(i)} - \overline{\boldsymbol{x}}_{C_2} \right\|^2 \end{eqnarray}\]

と、クラスタをマージした後の偏差平方和

\[SSD(C_1 \cup C_2) = \displaystyle \sum_{\boldsymbol{x}^{(i)} \in C_1 \cup C_2} \left\| \boldsymbol{x}^{(i)} - \overline{\boldsymbol{x}}_{C_1 \cup C_2} \right\|^2\]

を計算する。

マージする前後でクラスタの偏差平方和の変化が少ないほど近いとみなし、偏差平方和の増分

\[SSD(C_1 \cup C_2) - SSD(C_1) - SSD(C_2)\]

をクラスタ間の遠さとする。

実装

コード

動作確認