Ward法によるクラスタリング基礎

# <font color="Red">Ward法</font>
階層的クラスタリングの一種
得られる結果から表示。コードは[末尾](#全コード)

デンドログラム（樹形図）を得る。
![{6DC4870F-1AE6-4141-83A5-F8E372A41BF5}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3800268/cf00d037-b5cb-4973-95d0-d96cd1267ea1.png)

分類方法は、樹形図の下から始まる。
 - 距離の近いデータ2点を１つのクラスタとしてまとめる
 - 距離の近い２クラスタ、または１クラスタとN点をクラスタとしてまとめる
 - 次々と、距離の近い２個をまとめる

雪だるま式にまとめていき、最後１つにまとまる。

樹形図の意味：
- 縦の線 : 長さが距離を表す
- 横の線 : 特に横の長さには意味はない
- 横軸の値 : 対象で他のインデックス（何行目のデータか）を表示

# <font color="Red">Ward法の式と特徴</font>
非常にシンプルで理解しやすい。
「結合前後に対して、重心から各点のユークリッド距離$^※$の総和を計算する」
（※計算量の都合上、ルートを取らない）
という事と理解している。

- 距離 ： ユークリッド距離
- 距離の基準 ： クラスタ重心
- 結合基準 ： 分散増加の最小化 （クラスタ結合したと仮定し、その時の分散増加量を評価）
- 利点 ： ノイズに強く、他の階層クラスタリングよりよく用いられる
- 欠点 ： 計算コストが高く、大規模データでは厳しい

計算：2つのクラスタ間の分散のような距離$^※$ を求め、最小のものを探す。
　（※重心からのユークリッド距離の2乗和。「サンプル数で割る」操作はしない）
 「クラスタ間の分散のような距離」は以下の式
```math
d(C1,C2)=L(C1∪C2)−L(C1)−L(C2)
```
 - Cn : 評価中のクラスタ。クラスタ2つを対象にして、結合するとどうなるか？を評価
 - d(C1,C2) : クラスタ間の分散距離。これが最小のものを結合
 - L(C1∪C2) : 評価中の2クラスタ結合後の分散のような距離
 - L(C1) : クラスタ1の分散のような距離
 - L(C2) : クラスタ2の分散のような距離

 ```math
 L(C)=\Sigma_{x∈C}D(x,g_C)^2
```
$g_C$ : クラスタの重心



# <font color="Red">コード</font>
Scipyモジュールから可能。
主に、２部に分かれる
クラスタリング実行部と、デンドログラム（樹形図）描画部の２パート。

## <font color="HotPink">クラスタリング部</font>

Scipyをインポートし、linkage_matlixを取得。（linkage：リンクした、繋げた、という感じの意味）
実質、「```linkage_matrix = linkage(X, method='ward')```」だけ

```python
import numpy as np
import pandas as pd
from scipy.cluster.hierarchy import linkage, dendrogram
from sklearn.datasets import load_iris

# Irisデータセットのロード
iris = load_iris()
X = iris.data

# =====Ward法による階層的クラスタリング=====

linkage_matrix = linkage(X, method='ward')

#================================== 

print(linkage_matrix)

```

※linkage_matrixの中身：
```
array([[idx1, idx2, dist, sample_count],
       [idx3, idx4, dist, sample_count],
       ...])
```
 - idx _n_ : 結合した２つのクラスタのインデックス
 - dist：クラスタ間距離
 - sample_count：結合後のクラスタ内のサンプル数

２つのクラスタまたはデータを１つにまとめていく、という仮定を踏むのでidx _n_ は２つになる。
linkage_matrix は「m行４列」、mはデータ数-1。

## <font color="HotPink">デンドログラム（樹形図）描画部</font>

```scipy.cluster.hierarchy``` から ```dendrogram```　をインポートすると描ける。

```python
from scipy.cluster.hierarchy import linkage, dendrogram
import matplotlib.pyplot as plt

# グラフ上に日本語表示できるように
import matplotlib.font_manager as fm

# フォントの設定
# plt.rcParams['font.family'] = 'MS Gothic'
plt.rcParams['font.family'] = 'Meiryo'

# ==========
# ※ linkage_matlix 取得部は省略
# ==========

# デンドログラムの描画
plt.figure(figsize=(10, 5))
dendrogram(linkage_matrix, labels=iris.target, leaf_rotation=90, leaf_font_size=10)
plt.title("Ward法による階層的クラスタリング - Iris Dataset")
plt.xlabel("サンプルインデックス")
plt.ylabel("距離")
plt.show()

```

# <font color="Red">クラスタリング結果をもとのデータと照会</font>
以下の状況が、「結果と元データとを照会」となる。

 - クラスタリング結果：どのデータ点が、どのクラスタに属するか？
 - 結果の照会 : データ点に、クラスタ番号を突き合わせる
 
→ DataFrame右端に「クラスタ結果」列を作成し、クラスタ番号を対応する行に振る 


```fcluster(,t=n,)```　で、クラスタ数nのときのクラスタ番号を取得、という操作になる。

```python
import numpy as np
import pandas as pd
from scipy.cluster.hierarchy import linkage, fcluster

# ダミーデータの作成
np.random.seed(42)
X = np.random.rand(10, 2)  # 10個のデータ点

# DataFrameにしておく
df = pd.DataFrame(X, columns=iris.feature_names)

# Ward法による階層クラスタリング
linkage_matrix = linkage(X, method='ward')

# クラスタラベルの取得 (t=3)でクラスタ数3の時のラベルを取得となる
df["cluster_number"] = fcluster(linkage_matrix, t=3, criterion='maxclust')

# おまけ：距離情報の取得
# t=3の時点での距離を取得（m-3 番目の結合距離）
distance_threshold = linkage_matrix[-(3-1), 2]  # クラスタが3つになった時点の結合距離

print(f"t=3 のクラスタリング時のしきい値距離: {distance_threshold}")
```

# <font color="Red">全コード</font>

```python
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import linkage, dendrogram, fcluster
from sklearn.datasets import load_iris

# グラフ上に日本語表示できるように
import matplotlib.font_manager as fm

# フォントの設定
# plt.rcParams['font.family'] = 'MS Gothic'
plt.rcParams['font.family'] = 'Meiryo'


# Irisデータセットのロード
iris = load_iris()
X = iris.data
df = pd.DataFrame(X, columns=iris.feature_names)

# Ward法による階層的クラスタリング
linkage_matrix = linkage(X, method='ward')

print(linkage_matrix)

# デンドログラムの描画
plt.figure(figsize=(10, 5))
dendrogram(linkage_matrix, labels=iris.target, leaf_rotation=90, leaf_font_size=10)
plt.title("Ward法による階層的クラスタリング - Iris Dataset")
plt.xlabel("サンプルインデックス")
plt.ylabel("距離")
plt.show()

# t=3でのクラスタ番号をDataFrameに結合
df["cluster_number"] = fcluster(linkage_matrix, t=3, criterion='maxclust')

# おまけ：距離情報の取得
# t=3の時点での距離を取得（m-3 番目の結合距離）
distance_threshold = linkage_matrix[-(3-1), 2]  # クラスタが3つになった時点の結合距離
print(f"t=3 のクラスタリング時のしきい値距離: {distance_threshold}")

```