階層的クラスタリングを実装してみる - 距離の測り方からデンドログラムの読み解きまで

クラスタリングについて、なんとなく知っていたけれど、実装はまだしたことがなかったなという自分向けに、階層的クラスタリングについてのメモを残します。

今回は、数あるクラスタリング手法の中でも 「階層的クラスタリング」 に焦点を当てています。

階層的クラスタリングって何？

階層的クラスタリングとは、データ間の類似度に基づいて、データを階層的にグループ分けしていく手法です。まるで木の枝が伸びていくように、データが徐々にまとまっていく様子をイメージください。

この手法の魅力は、クラスタ数を事前に決める必要がない こと。データの構造を可視化しながら、最適なクラスタ数を後から判断できる点が大きなメリットです。

距離と非類似度：データを測るモノサシ

クラスタリングを行う上で、データ同士の「近さ」を測ることは非常に重要です。この「近さ」を測るためのモノサシが 「距離」 や 「非類似度」 と呼ばれるものです。

距離は、二つのデータの間の隔たりを数値で表すもので、値が小さいほどデータが似ていることを意味します。一方、非類似度は、データがどれくらい似ていないかを示すもので、値が大きいほどデータが異なっていることを意味します。

距離行列：データの距離を一気に計算

複数のデータの組み合わせに対して、距離や非類似度を計算した結果をまとめたものが 「距離行列」 です。この距離行列をもとに、階層的なクラスタリングが進められていきます。

距離行列は、計算結果を表形式でまとめたもので、各行と列はそれぞれデータに対応します。例えば、以下のようなイメージです。

データ	データA	データB	データC
データA	0	1.41	2.23
データB	1.41	0	1
データC	2.23	1	0

この例では、データAとデータBの距離は1.41、データBとデータCの距離は1と読み取れます。

よく使われる距離の指標

距離や非類似度を測る方法はいくつかありますが、ここではよく使われる代表的な2つを紹介します。

1. ユークリッド距離

• 日常生活でよく使われる距離の概念で、2点間の直線距離を表します。
• 2次元データの場合は、三平方の定理で計算できます。
• データの値が大きいほど、距離が大きくなる特徴があります。

2. コサイン類似度

• ベクトル間の角度のコサインを使って類似度を測ります。
• 値が1に近いほど類似度が高く、-1に近いほど類似度が低いことを示します。
• テキストデータなど、ベクトルの向きが重要な場合に有効です。

凝集型階層的クラスタリング：ボトムアップでグループ化

階層的クラスタリングには、トップダウン型とボトムアップ型の2種類がありますが、一般的に使われるのは、凝集型階層的クラスタリング（ボトムアップ型）です。

凝集型階層的クラスタリングでは、最初に各データを1つのクラスタとみなし、最も距離が近いクラスタ同士を繰り返し結合していくことで、階層的なクラスタ構造を生成します。

デンドログラム：クラスタリングの結果を可視化

凝集型階層的クラスタリングの結果は、デンドログラム と呼ばれる樹形図で可視化されます。デンドログラムの横軸はデータ、縦軸はクラスタ間の距離を表しています。

デンドログラムを見れば、どのデータがどのグループに属しているのか、そして、どのくらいの距離でクラスタが結合しているのかが一目でわかります。

1次元配列の例

# ランダムなデータに対して階層的クラスタリングを行い、デンドログラムを表示する例  
import numpy as np  
from scipy.cluster import hierarchy  
import matplotlib.pyplot as plt

# 距離データを作成  
# データポイント間のペアワイズ距離を1次元配列として定義  
ytdist = np.array([662., 877., 255., 412., 996., 295., 468., 268.,  
                   400., 754., 564., 138., 219., 869., 669.])

# 階層的クラスタリングを実行  
# 単リンク法（最短距離法）を用いてクラスタリングを行い、リンク行列を作成  
Z = hierarchy.linkage(ytdist, 'single')  

# デンドログラムを描画  
plt.figure()  
dn = hierarchy.dendrogram(Z)

# デンドログラムの線の色を変更  
hierarchy.set_link_color_palette(['m', 'c', 'y', 'k'])

# 2つの異なる向きでデンドログラムを描画  
fig, axes = plt.subplots(1, 2, figsize=(8, 3))  
dn1 = hierarchy.dendrogram(Z, ax=axes[0], above_threshold_color='y',  
                           orientation='top')  # 上向き  
dn2 = hierarchy.dendrogram(Z, ax=axes[1],  
                           above_threshold_color='#bcbddc',  
                           orientation='right')  # 右向き

# デンドログラムの線の色設定をデフォルトに戻す  
hierarchy.set_link_color_palette(None)

# プロットを表示  
plt.show()  

デンドログラムの読み解き方

• 上記のコードで生成されるデンドログラムは、縦軸がクラスタ間の距離を表し、値が高いほど結合したクラスタ間の距離が大きいことを示します。
• 横軸は各データを示しており、横軸で近いデータ同士ほど早い段階で結合されています。このデンドログラムを見ることで、データがどのようにグループ分けされているのかを直感的に把握できます。

2次元配列の例（squareform 関数を使った距離行列の視覚化）

import numpy as np  
import pandas as pd  
from scipy.spatial.distance import pdist, squareform  
from scipy.cluster.hierarchy import linkage, dendrogram  
import matplotlib.pyplot as plt  
import japanize_matplotlib

# サンプルデータを作成  
# ここでは、4つのデータポイントを持つ2次元データを使用  
data = np.array([[1, 2], [3, 4], [5, 6], [7, 8]])

# サンプルのuser_idを作成  
user_id = ['ユーザ1', 'ユーザ2', 'ユーザ3', 'ユーザ4']

# ペアワイズ距離を計算  
# pdistを使用して、データポイント間のユークリッド距離を計算  
distance_matrix = pdist(data, metric='euclidean')

# 距離行列を正方行列に変換  
# squareformを使用して、1次元の距離ベクトルを2次元の正方行列に変換  
distance_matrix_square = squareform(distance_matrix)

# 距離行列をDataFrameとして表示  
# 距離行列をpandasのDataFrameに変換し、行と列のラベルをuser_idに設定  
distance_df = pd.DataFrame(distance_matrix_square,   
                           index=user_id,   
                           columns=user_id)

# 距離行列を表示  
print("距離行列 (正方行列形式):")  
print(distance_df)

# 階層的クラスタリングを実行  
# linkageを使用して、距離行列から階層クラスタリングを実行  
# ここでは、Ward法を使用
linkage_matrix = linkage(distance_matrix, method='ward')

# デンドログラムを描画  
# 階層クラスタリングの結果をデンドログラムとして視覚化  
plt.figure()  
dendrogram(linkage_matrix, labels=user_id)  
plt.title("デンドログラム")  
plt.xlabel("データポイント")  
plt.ylabel("距離")  
plt.show()  

クラスタ間の距離の測り方：様々なリンク法

凝集型階層的クラスタリングでは、クラスタ同士を結合する際に、クラスタ間の距離をどのように測るかが重要になります。この距離の測り方によって、クラスタリングの結果が大きく変わることがあります。

代表的なリンク法を紹介します。

1. 単リンク法（最短距離法）

• 2つのクラスタ間で最も近いデータ同士の距離をクラスタ間距離とする方法です。
• 細長いクラスタを形成しやすいという特徴があります。例えば、チェーン状にデータが連なっているような場合に有効ですが、ノイズに弱いという欠点があります。

2. 完全リンク法（最長距離法）

• 2つのクラスタ間で最も遠いデータ同士の距離をクラスタ間距離とする方法です。
• コンパクトなクラスタを形成しやすいという特徴があります。外れ値の影響を受けにくい一方で、クラスタが小さく分かれすぎる可能性があります。

3. 群平均法

• 2つのクラスタに含まれる全てのデータ間の距離の平均値をクラスタ間距離とする方法です。
• 単リンク法と完全リンク法の中間的な性質を持ち、比較的バランスの取れたクラスタを形成しやすいです。

4. ウォード法

• クラスタ内の分散の増加量を最小にするようにクラスタを結合する方法です。
• クラスタ内の均一性が高まりやすいという特徴があります。比較的コンパクトなクラスタを形成する傾向があります。

5. 重心法

• 各クラスタの重心間の距離をクラスタ間距離とする方法です。
• 計算が容易というメリットがあります。しかし、クラスタが重心を中心に均一でない場合、結果が不安定になることがあります。

6. 重み付き平均法

• クラスタサイズを考慮した上で平均値を計算する方法です。
• クラスタの大きさに偏りがある場合に有効です。

7. メジアン法

• クラスタの中央値を基に距離を計算する方法です。
• 外れ値の影響を軽減したい場合に有効です。

どのリンク法を選択するかは、データの性質やクラスタリングの目的に応じて判断する必要があります。

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

X = [[i] for i in [2, 8, 0, 4, 1, 9, 9, 0]]

# ウォード法でリンクエージ行列を計算
Z_ward = linkage(X, 'ward')
fig = plt.figure(figsize=(15, 5))
dn_ward = dendrogram(Z_ward)
plt.title('dn-ward', fontsize=14, pad=20)  # タイトルを追加

# 単一リンク法でリンクエージ行列を計算
Z_single = linkage(X, 'single')
fig = plt.figure(figsize=(15, 5))
dn_single = dendrogram(Z_single)
plt.title('dn-single', fontsize=14, pad=20)  # タイトルを追加

plt.show()

SciPyの日本語訳

以下のSciPyのドキュメントの日本語訳をGitHubにおいておきます。
https://docs.scipy.org/doc/scipy-1.15.0/reference/cluster.hierarchy.html

SciPyドキュメントを読む際の注意点:
SciPyのドキュメントは非常に詳細ですが、初めて読む際は少し戸惑うかもしれません。特にlinkage関数やdendrogram関数の説明は、パラメータが多くて難しく感じることがあります。まずは、これらの関数の基本的な使い方と、各パラメータが結果にどのように影響するかを理解することから始めると良さそうです。

まとめ：階層的クラスタリングの可能性

今回は、階層的クラスタリングの基本的な考え方から、距離の測り方、デンドログラムの読み方、そして様々なリンク法までを取り上げました。

SciPyのドキュメントの英単語が案外読みづらく躓いてしまったので、日本語でイメージした上で進めると良さそうに思いました！階層的クラスタリングは、クラスタ数を事前に決める必要がなく、データの階層構造を可視化できる強力な手法です。この記事を参考に、ぜひ色々なデータで試してみてください！