はじめに

クラスタリングでよく使用される手法と評価方法。
これらで考慮している距離についてまとめた。
距離を知ることで活用や考察に有利と考える。

まとめ

項目 \ 手法	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}

証明完了。