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

Ward法

階層的クラスタリングの一種
得られる結果から表示。コードは末尾

デンドログラム（樹形図）を得る。

分類方法は、樹形図の下から始まる。

• 距離の近いデータ2点を１つのクラスタとしてまとめる
• 距離の近い２クラスタ、または１クラスタとN点をクラスタとしてまとめる
• 次々と、距離の近い２個をまとめる

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

樹形図の意味：

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

Ward法の式と特徴

非常にシンプルで理解しやすい。
「結合前後に対して、重心から各点のユークリッド距離の総和を計算する。
ただし、計算量の都合上、ルートを取らない。」
という事と理解している。

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

計算：2つのクラスタ間の分散のような距離$^※$ を求め、最小のものを探す。
　※重心からのユークリッド距離の2乗和。計算量節約しているだけで、重心からの分散と等価。
「クラスタ間の分散のような距離」は以下の式

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の分散のような距離

L(C)=\Sigma_{x∈C}D(x,g_C)^2

$g_C$ : クラスタの重心

コード

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

クラスタリング部

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

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。

デンドログラム（樹形図）描画部

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

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()

クラスタリング結果をもとのデータと照会

以下の状況が、「結果と元データとを照会」となる。

• クラスタリング結果：どのデータ点が、どのクラスタに属するか？
• 結果の照会 : データ点に、クラスタ番号を突き合わせる

→ DataFrame右端に「クラスタ結果」列を作成し、クラスタ番号を対応する行に振る

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

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}")

全コード

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}")