距離計算：重心とサンプル：Ward法、k-means、SSE、Silhouette Score

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

# <font color="Red">まとめ</font>
| 項目 \ 手法 | Ward法   | k-means   | SSE 　|Silhouette Score|
|------------|-----------|-----------|-----------|----------|
| 分類| 階層クラスタリング | 非階層クラスタリング | 評価値 |評価値|
| 計算の肝| クラスタ統合前後の総距離和最小化 | 総距離和最小化　最近傍重心点に属する| 総距離和 |<font color="Red">各点の距離と最近傍クラスタ（重心を用いない）</font>|
| A3  | A3B1 | A3B2 | A3B3 ||


Silhouette Score以外、「**重心**をベースとして距離計算をする」という基本的な操作。
Silhouette Scoreは、「ノードとエッジ」の完全グラフを作ってその長さを評価するとイメージできる。


# <font color="Red">クラスタリング手法</font>





## <font color="HotPink">Ward法</font>
- 階層クラスタリング
- １点ずつから開始し、雪だるま式にクラスタを成長させる
- クラスタ数の指定が不要だが、計算量が大きい

クラスタ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は、結合前後での重心-データ点間距離の差を評価していることになる。


**<<INS>計算原理</INS>>**

- 集合A、集合Bの2つを結合することを考える

- 集合Aの重心、集合Bの重心、結合後の重心点を「<font color="Red"><INS>**C**</INS></font>entroid」としてそれぞれ以下に定義
$$重心　\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の小さい２つを統合して新しいクラスタとする

**<<INS>模式図</INS>>**
重心からの距離総和の変化量最小を探す
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3800268/430bd01c-3499-4e0d-91cc-e6690d3d5ad7.png)



**<INS><応用：計算結果></INS>**

調べると、一般に以下の式、またはその類似式がでてくる。
$$ \frac{n_A n_B }{n_A + n_B} || \mu_A - \mu_B ||^2 $$
- $n_X$ : クラスタXのサンプル数
- $\mu_X $：クラスタXの重心位置

計算量が大幅に小さい。
これは式変形により得られるので、参考に、末尾に記しておく。

末尾：[Ward法の式変形](#ward法の式変形)


## <font color="HotPink">k-means</font>

- 非階層クラスタリング
- セントロイド（重心点）の数を定義して、これらの位置を変えながら属する点群を選択していく

**<<INS>計算原理</INS>>**
- クラスタの個数（= 重心点の個数）を任意に決める
- 各重心点を適当に配置する
- =====ループ=====
- 各データ点を、自分から最も近い重心点に所属させる
- 重心位置を再計算　→　自分に所属するデータ点の重心位置に更新
- ループ判定　：　重心位置の移動量を計算し、移動量がほぼ0であれば終了
- =====ループ=====

**<<INS>模式図</INS>>**
図は冗長になるので割愛し、文章で記述。

「重心」が基盤。
- 重心位置「初期：ランダム配置」　→　「2回目以降：自分に所属する点から実計算」
- データ点の所属：重心の更新毎に、最も近い重心点に所属する

以上






# <font color="Red">評価手法</font>





## <font color="HotPink">SSE</font>
Sum of Square Error
重心点を中心とした分散と考えておよそ正しい（サンプル数で割らない）。
サンプル数で割ると、「MSE」(Mean Squared Error)になる。

対象クラスタに属するデータ点とクラスタ重心とのユークリッド距離の総和を計算する

```math
 SSE = \Sigma_{x_i \in C}((x_i -g_c)^2 ) 
```
-$g_c$ : 重心位置

エルボー法：横軸クラスタ数、縦軸SSEとしたグラフを描く




## <font color="HotPink">Silhouette Score</font>
<font color="Red"><INS>**重心**を使用**しない**</INS></font>
<font color="Red"><INS>**1点ずつ**値を持つ</INS></font>

ノード（点）とエッジ（辺）を考えて、**エッジ平均長さ**を考える、というイメージ。
※以下、データ点間の距離を「エッジ長さ」とよぶ（一般的ではないので他者との会話時には注意）

**<<INS>計算イメージ</INS>>**
- 「**凝集度**」と「**分離度**」の2つの尺度のバランスを見る
- 凝集度a　　：　自クラスタ内でのエッジの平均長さ
- 分離度b　　：　最近傍クラスタとのエッジの平均長さ
- 対象点$x_i$　：　Silhouette Scoreは各データ点$x_i$ごとにその値を持つ
- 計算式　　：　$\frac{b-a}{max(a,b)}$分母は正規化用の係数。大きいほうで割ることで、-1~1の範囲にする

クラスタ内で点が近いほどaが小さくなり、他のクラスタとの距離が遠いほどbは大きくなる。
b-aが大きいほど、自クラスタは密集しており他のクラスタとは離れている。

※「最近傍クラスタ」は全クラスタとの比較をした結果決定される

**<<INS>模式図</INS>>**
**凝縮度**：各データ点$x_i$が値を持つので、各データ点に対して同様の計算を行う
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3800268/f5138328-da7c-4dc0-a3a1-d5be399ffaea.png)


**分離度**：各データ点$x_i$が値を持つので、各データ点に対して同様の計算を行う
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3800268/e9740faf-cbe7-4069-b450-155138e3a340.png)

**シルエット図**：各$x_i$に対して求めた値を、クラスタ毎に色分けして書いた図
赤縦点線はシルエットスコアの全点平均値を表示
![{63AA627F-634C-426E-A52C-781CCD1A94D6}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3800268/ff524432-3b1e-4a40-8126-43058e37db71.png)


# <font color="Red">Ward法の式変形</font>

元の定義式：
```math
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} $

すると、

```math
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
```

### <font color="Orange">1.初項について</font>
$x_i^{(A)}\in A$　のデータと$x_i^{(B)}\in B$　のデータに分けて考えることができる。

```math
初項 = \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に属するデータをそれぞれ分けて書く。

```math
\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}
```

```math
\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)}$　のサンプル数)

```math
\Sigma_i (x_i^{(A)} - \mu_A) = n_A\mu_A - n_A\mu_A = 0
```
```math
\Sigma_i (x_i^{(B)} - \mu_B) = n_B\mu_B - n_B\mu_B = 0
```

よって、A、Bに属するデータ点について個別に考えると、初項は以下のようになる。

```math
\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} 
```

### <font color="Orange">2.第２，３項目は消えて平均値情報が残る</font>

もともとの式は、
```math
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
```

初項が、

```math
\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}
```

よって、

```math
d(A,B) =  \Sigma_i^{\in A} ( ||\mu_A - \mu_{AB}||^2) + \Sigma_i^{\in B} (||\mu_B - \mu_{AB}||^2)
```

打ち消しあって、平均情報の総和のみが残った。平均値の$\Sigma$は単に「サンプル数×平均値」になるので、$\Sigma$が無くなり、

```math
\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}
```

### <font color="Orange">3.A、Bの重み付き平均で再表現</font>

$\mu_{AB}$ は、サンプル数Aのデータ群の平均$\mu_A$と、サンプル数Bのデータ分の平均$\mu_B$の平均値となるので、重み月平均として算出できる。

```math
\mu_{AB} = \frac{n_A\mu_A + n_B\mu_B}{n_A + n_B}
```

これより、式を整理すると、

```math
\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}

```

よって、

```math
\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}
```
証明完了。