はじめに
クラスタリングでよく使用される手法と評価方法。
これらで考慮している距離についてまとめた。
距離を知ることで活用や考察に有利と考える。
まとめ
| 項目 \ 手法 | Ward法 | k-means | SSE | Silhouette Score |
|---|---|---|---|---|
| 分類 | 階層クラスタリング | 非階層クラスタリング | 評価値 | 評価値 |
| 計算の肝 | クラスタ統合前後の総距離和最小化 | 総距離和最小化 最近傍重心点に属する | 総距離和 | 各点の距離と最近傍クラスタ（重心を用いない） |
| A3 | A3B1 | A3B2 | A3B3 |
Silhouette Score以外、「重心をベースとして距離計算をする」という基本的な操作。
Silhouette Scoreは、「ノードとエッジ」の完全グラフを作ってその長さを評価するとイメージできる。
クラスタリング手法
Ward法
- 階層クラスタリング
- １点ずつから開始し、雪だるま式にクラスタを成長させる
- クラスタ数の指定が不要だが、計算量が大きい
クラスタA、Bに属するデータをそれぞれ 「$x_i^{(A)} \in A, \space x_j^{(B)} \in B$」 と書く。
クラスタの重心を「$C(A)$」のように書く。
$$d(A,B)=\Sigma_i ||x_i^{(A,B)}-C(A\cup B)||^2 - \Sigma_i ||x_i^{(A)}-C(A)||^2 -\Sigma_i ||x_i^{(B)}-C(B)||^2$$
最小のdを持つ２つのクラスタを統合して新クラスタに採用。
dは、結合前後での重心-データ点間距離の差を評価していることになる。
<計算原理>
-
集合A、集合Bの2つを結合することを考える
-
集合Aの重心、集合Bの重心、結合後の重心点を「Centroid」としてそれぞれ以下に定義
$$重心 \space : \space \space C(A)、C(B)、C(A\cup B)$$ -
結合前のクラスタ内総距離を求める。
$$総距離和d_A\in A \space : \space \space d_A=\Sigma_i ||x_i^{(A)}-C(A)||^2 \space : \space x_i^{(A)}\in C(A)$$
$$総距離和d_B\in B \space : \space \space d_B=\Sigma_i ||x_i^{(B)}-C(B)||^2 \space : \space x_i^{(B)}\in C(B)$$ -
結合後の$C(A\cup B)$の総距離とC(A)、C(B)のそれとの差を求めて、これを 「d(A,B)」 と呼ぶ
$$d(A,B) = d_{(A\cup B)} - d_A - d_B$$ 展開して、
$$d(A,B)=\Sigma_i ||x_i^{(A,B)}-C(A\cup B)||^2 - \Sigma_i ||x_i^{(A)}-C(A)||^2 -\Sigma_i ||x_i^{(B)}-C(B)||^2$$ -
全クラスタから２クラスタを抽出してd(A,B)を評価。最もdの小さい２つを統合して新しいクラスタとする
<模式図>
重心からの距離総和の変化量最小を探す
<応用：計算結果>
調べると、一般に以下の式、またはその類似式がでてくる。
$$ \frac{n_A n_B }{n_A + n_B} || \mu_A - \mu_B ||^2 $$
- $n_X$ : クラスタXのサンプル数
- $\mu_X $：クラスタXの重心位置
計算量が大幅に小さい。
これは式変形により得られるので、参考に、末尾に記しておく。
末尾：Ward法の式変形
k-means
- 非階層クラスタリング
- セントロイド（重心点）の数を定義して、これらの位置を変えながら属する点群を選択していく
<計算原理>
- クラスタの個数（= 重心点の個数）を任意に決める
- 各重心点を適当に配置する
- =====ループ=====
- 各データ点を、自分から最も近い重心点に所属させる
- 重心位置を再計算 → 自分に所属するデータ点の重心位置に更新
- ループ判定 ： 重心位置の移動量を計算し、移動量がほぼ0であれば終了
- =====ループ=====
<模式図>
図は冗長になるので割愛し、文章で記述。
「重心」が基盤。
- 重心位置「初期：ランダム配置」 → 「2回目以降：自分に所属する点から実計算」
- データ点の所属：重心の更新毎に、最も近い重心点に所属する
以上
評価手法
SSE
Sum of Square Error
重心点を中心とした分散と考えておよそ正しい（サンプル数で割らない）。
サンプル数で割ると、「MSE」(Mean Squared Error)になる。
対象クラスタに属するデータ点とクラスタ重心とのユークリッド距離の総和を計算する
SSE = \Sigma_{x_i \in C}((x_i -g_c)^2 )
-$g_c$ : 重心位置
エルボー法：横軸クラスタ数、縦軸SSEとしたグラフを描く
Silhouette Score
重心を使用しない
1点ずつ値を持つ
ノード（点）とエッジ（辺）を考えて、エッジ平均長さを考える、というイメージ。
※以下、データ点間の距離を「エッジ長さ」とよぶ（一般的ではないので他者との会話時には注意）
<計算イメージ>
- 「凝集度」と「分離度」の2つの尺度のバランスを見る
- 凝集度a ： 自クラスタ内でのエッジの平均長さ
- 分離度b ： 最近傍クラスタとのエッジの平均長さ
- 対象点$x_i$ ： Silhouette Scoreは各データ点$x_i$ごとにその値を持つ
- 計算式 ： $\frac{b-a}{max(a,b)}$分母は正規化用の係数。大きいほうで割ることで、-1~1の範囲にする
クラスタ内で点が近いほどaが小さくなり、他のクラスタとの距離が遠いほどbは大きくなる。
b-aが大きいほど、自クラスタは密集しており他のクラスタとは離れている。
※「最近傍クラスタ」は全クラスタとの比較をした結果決定される
<模式図>
凝縮度：各データ点$x_i$が値を持つので、各データ点に対して同様の計算を行う
分離度：各データ点$x_i$が値を持つので、各データ点に対して同様の計算を行う
シルエット図：各$x_i$に対して求めた値を、クラスタ毎に色分けして書いた図
赤縦点線はシルエットスコアの全点平均値を表示
Ward法の式変形
元の定義式：
d(A,B) = \Sigma_i^{\in A\cup B} ||x_i^{(A,B)}-C(A\cup B)||^2 - \Sigma_i^{\in A} ||x_i^{(A)}-C(A)||^2 -\Sigma_i^{\in B} ||x_i^{(B)}-C(B)||^2
「Ward法」で調べると、以下の式、またはその類似式がでてくる。
$$ \frac{n_A n_B }{n_A + n_B} || \mu_A - \mu_B ||^2 $$
- $n_X$ : クラスタXのサンプル数
- $\mu_X $：クラスタXの重心位置
この式が等価であることの証明。
冗長な記号を置き換える。
$C(A\cup B) \rightarrow \mu_{AB} $
$C(A) \rightarrow \mu_{A} $
$C(B) \rightarrow \mu_{B} $
すると、
d(A,B) = \Sigma_i ||x_i^{(A,B)}-\mu_{AB}||^2 - \Sigma_i ||x_i^{(A)}-\mu_A||^2 -\Sigma_i ||x_i^{(B)}-\mu_B||^2
1.初項について
$x_i^{(A)}\in A$ のデータと$x_i^{(B)}\in B$ のデータに分けて考えることができる。
初項 = \Sigma_i ||x_i^{(A,B)}-\mu_{AB}||^2 = \Sigma_i ||x_i^{(A)}-\mu_{AB}||^2 + \Sigma_i ||x_i^{(B)}-\mu_{AB}||^2
Aに属するデータについて、式中に足して0になる値、「$-\mu_A + \mu_A$」を導入。Bに属するデータにも同様に「$-\mu_B + \mu_B$」 を導入し、式展開する。
分かり易いように、Aに属するデータとBに属するデータをそれぞれ分けて書く。
\begin{align}
\Sigma_i ||x_i^{(A)}-\mu_{AB}||^2 &= \Sigma_i ||(x_i^{(A)}-\mu_A) + (\mu_A - \mu_{AB})||^2 \\
&= \Sigma_i (||x_i^{(A)}-\mu_{A}||^2 -2(x_i^{(A)}-\mu_{A})(\mu_A - \mu_{AB}) + ||\mu_A - \mu_{AB}||^2)
\end{align}
\begin{align}
\Sigma_i ||x_i^{(B)}-\mu_{AB}||^2 &= \Sigma_i ||(x_i^{(B)}-\mu_B) + (\mu_B - \mu_{AB})||^2 \\
&= \Sigma_i (||x_i^{(B)}-\mu_{B}||^2 -2(x_i^{(B)}-\mu_{B})(\mu_B - \mu_{AB}) + ||\mu_B - \mu_{AB}||^2)
\end{align}
ここで、$\Sigma_i (x_i^{(A)} - \mu_A)$ は、そもそも $\mu_A = \frac{\Sigma_i x_i^{(A)}}{n_A} $ であり、$\Sigma_i \mu_A = n_A\mu_A $ なので、総和すると０になる。Bも同様。
($n_A$ : $x_i^{(A)}$ のサンプル数)
\Sigma_i (x_i^{(A)} - \mu_A) = n_A\mu_A - n_A\mu_A = 0
\Sigma_i (x_i^{(B)} - \mu_B) = n_B\mu_B - n_B\mu_B = 0
よって、A、Bに属するデータ点について個別に考えると、初項は以下のようになる。
\begin{align}
初項 = \Sigma_i ||x_i^{(A,B)} - \mu_{AB}||^2 &= \Sigma_i^{\in A} ||x_i^{(A)} - \mu_{AB}||^2 + \Sigma_i^{\in B} ||x_i^{(B)} - \mu_{AB}||^2\\
&= \Sigma_i^{\in A} (||x_i^{(A)}-\mu_{A}||^2 + ||\mu_A - \mu_{AB}||^2) + \Sigma_i^{\in B} (||x_i^{(B)}-\mu_{B}||^2 + ||\mu_B - \mu_{AB}||^2)
\end{align}
2.第２，３項目は消えて平均値情報が残る
もともとの式は、
d(A,B) = \Sigma_i^{\in A\cup B} ||x_i^{(A,B)}-\mu_{AB}||^2 - \Sigma_i^{\in A} ||x_i^{(A)}-\mu_A||^2 -\Sigma_i^{\in B} ||x_i^{(B)}-\mu_B||^2
初項が、
\begin{align}
& \Sigma_i^{\in A\cup B} ||x_i^{(A,B)}-\mu_{AB}||^2 = \\
& \Sigma_i^{\in A} (||x_i^{(A)}-\mu_{A}||^2 + ||\mu_A - \mu_{AB}||^2) + \Sigma_i^{\in B} (||x_i^{(B)}-\mu_{B}||^2 + ||\mu_B - \mu_{AB}||^2)
\end{align}
よって、
d(A,B) = \Sigma_i^{\in A} ( ||\mu_A - \mu_{AB}||^2) + \Sigma_i^{\in B} (||\mu_B - \mu_{AB}||^2)
打ち消しあって、平均情報の総和のみが残った。平均値の$\Sigma$は単に「サンプル数×平均値」になるので、$\Sigma$が無くなり、
\begin{align}
d(A,B) &= \Sigma_i^{\in A} ( ||\mu_A - \mu_{AB}||^2) + \Sigma_i^{\in B} (||\mu_B - \mu_{AB}||^2) \\
&= n_A||\mu_A - \mu_{AB}||^2 + n_B||\mu_B - \mu_{AB}||^2
\end{align}
3.A、Bの重み付き平均で再表現
$\mu_{AB}$ は、サンプル数Aのデータ群の平均$\mu_A$と、サンプル数Bのデータ分の平均$\mu_B$の平均値となるので、重み月平均として算出できる。
\mu_{AB} = \frac{n_A\mu_A + n_B\mu_B}{n_A + n_B}
これより、式を整理すると、
\begin{align}
&\mu_A - \mu_{AB} = \mu_A - \frac{n_A\mu_A + n_B\mu_B}{n_A + n_B} = \frac{(n_A + n_B)\mu_A - n_A\mu_A - n_B\mu_B}{n_A + n_B} = \frac{n_B(\mu_A - \mu_B)}{n_A+n_B} \\
&\mu_B - \mu_{AB} = \mu_B - \frac{n_A\mu_A + n_B\mu_B}{n_A + n_B} = \frac{(n_A + n_B)\mu_B - n_A\mu_A - n_B\mu_B}{n_A + n_B} = \frac{n_A(\mu_B - \mu_A)}{n_A+n_B}
\end{align}
よって、
\begin{align}
d(A,B) &= n_A||\mu_A - \mu_{AB}||^2 + n_B||\mu_B - \mu_{AB}||^2 \\
&= n_A||\frac{n_B(\mu_A - \mu_B)}{n_A+n_B}||^2 + n_B||\frac{n_A(\mu_B - \mu_A)}{n_A+n_B}||^2 \\
&= \frac{n_An_B^2}{(n_A+n_B)^2}||\mu_A - \mu_B||^2 + \frac{n_Bn_A^2}{(n_A+n_B)^2}||\mu_A-\mu_B||^2 \\
&= \frac{n_An_B(n_A + n_B)}{(n_A+n_B)^2}||\mu_A-\mu_B||^2 \\
&= \frac{n_A n_B}{n_A + n_B}||\mu_A-\mu_B||^2
\end{align}
証明完了。