[機械学習のはじめ方] Part26: 階層クラスタリングとデンドログラム

データ間の類似度に基づいて段階的にグループ化する手法を学びます。

はじめに：階層クラスタリングとは？

こんにちは！機械学習の旅へようこそ。今回は、教師なし学習の中でも代表的な手法の一つである「階層クラスタリング」について学んでいきましょう。 [1, 2, 15] 階層クラスタリングは、データ間の類似度を計算し、似ているもの同士を段階的にまとめていく（または分割していく）ことで、データの構造を階層的に捉える手法です。[1, 3] 教師なし学習なので、事前に正解データ（ラベル）を与える必要はありません。[1, 15, 16] この手法の大きな特徴は、事前にクラスタ数を決める必要がないことです。[1, 3, 19] k-meansクラスタリングのように最初にクラスタ数を指定するのではなく、分析結果を「デンドログラム」という樹形図で可視化し、それを見てから適切なクラスタ数を判断することができます。[1, 3, 18, 22]

ポイント：

教師なし学習の手法の一つ。[1, 2, 15]
データ間の類似度に基づいて、階層的なクラスタ構造を作る。[1, 3]
事前にクラスタ数を指定する必要がない。（デンドログラムを見て後から決めることが多い）[1, 3, 19, 22]

階層クラスタリングの2つのアプローチ

階層クラスタリングには、大きく分けて2つのアプローチがあります。[2, 3]

凝集型（Agglomerative）: 最初は各データ点をそれぞれ独立したクラスタとし、最も似ている（距離が近い）クラスタ同士を繰り返し併合していく方法です。[2, 3, 9] ボトムアップ・アプローチとも呼ばれます。[2] こちらが一般的に使われることが多いアプローチです。
分割型（Divisive）: 最初は全てのデータ点を一つの大きなクラスタとし、最も似ていない（距離が遠い）部分で繰り返し分割していく方法です。[2, 3, 12] トップダウン・アプローチとも呼ばれます。[2]

このブログでは、より一般的な凝集型階層クラスタリングを中心に解説していきます。

凝集型階層クラスタリングの仕組みと距離計算

凝集型階層クラスタリングは、以下のステップで進められます。[3, 9, 13]

各データ点をそれぞれ独立したクラスタとみなす。
クラスタ間の距離（または類似度）を計算する。
最も距離が近い（類似度が高い）2つのクラスタを併合し、新しいクラスタとする。
クラスタ数が1つになるまで、ステップ2と3を繰り返す。

ステップ2の「クラスタ間の距離」をどのように計算するかが非常に重要で、いくつか代表的な方法があります。[1, 3, 7] どの計算方法（連結法）を選ぶかによって、クラスタリングの結果（クラスタの形状や階層構造）が変わってきます。[2, 3]

手法	説明	特徴
ウォード法 (Ward’s method)	クラスタを併合した際の、クラスタ内の分散（平方和）の増加量が最小になるように併合する。[3, 5, 6, 16, 17]	よく使われる[11, 17]。球状で同じサイズのクラスタを生成しやすい。[5] 外れ値の影響を受けやすい場合がある。計算量が多くなる傾向がある。[13, 15, 19]
完全連結法 (Complete linkage / 最長距離法)	異なるクラスタに属する最も遠いデータ点間の距離をクラスタ間距離とする。[3, 5, 6, 7, 9]	コンパクトなクラスタを生成しやすい。[2] 外れ値の影響を受けにくい傾向があるが、[5] 受けやすいとする情報源もある。[6]
単連結法 (Single linkage / 最短距離法)	異なるクラスタに属する最も近いデータ点間の距離をクラスタ間距離とする。[3, 5, 7, 9]	鎖状につながったクラスタを検出できる。[3] 計算量が少ない。[5, 6] 外れ値の影響を受けやすく、「連鎖効果」と呼ばれる意図しないクラスタが生成されることがある。[3, 5, 7, 22]
群平均法 (Average linkage / UPGMA)	異なるクラスタに属する全てのデータ点のペア間の距離の平均をクラスタ間距離とする。[1, 3, 7, 9, 13, 16, 17]	単連結法と完全連結法の中間的な性質を持つ。[3, 16] 外れ値の影響を受けにくい。[17]
重心法 (Centroid linkage / UPGMC)	各クラスタの重心間の距離をクラスタ間距離とする。[1, 7, 9, 19]	計算が比較的簡単。[1]

どの距離計算方法（連結法）を選ぶかは、データの特性や分析の目的に合わせて慎重に選択することが重要です。🤔 [2, 3]

デンドログラム：階層構造の可視化 🌳

階層クラスタリングの結果は、「デンドログラム（樹形図）」と呼ばれる図で可視化することができます。[1, 3, 15] デンドログラムは、クラスタがどのように併合（または分割）されていくかの過程を示しており、データの階層的な構造を理解するのに役立ちます。[1, 3, 12, 15, 20]

縦軸（高さ）: クラスタが併合されたときの距離（非類似度）を表します。[3, 20, 21] 高さが高いほど、似ていないクラスタ同士が併合されたことを意味します。[3, 20]
横軸: 個々のデータ点またはクラスタを表します。[3, 20]
枝の結合: クラスタの併合を示します。[3, 20]

デンドログラムを見ることで、データの階層的な構造を直感的に理解したり、適切なクラスタ数を決定したりするのに役立ちます。[1, 3, 12, 18, 22] 例えば、デンドログラムを特定の高さで水平に「カット」すると、そのカットラインと交わる枝の数がクラスタ数に対応します。[3, 18, 22] どこでカットするか（＝いくつのクラスタに分けるか）は、分析者がデンドログラムの形状（特に、次の併合までの距離が急に長くなる箇所など）や分析の目的を考慮して決定します。[3, 20, 22]

デンドログラムのカット位置を決める明確なルールはありませんが、枝の長さが急激に長くなる（＝距離が離れたクラスタ同士が結合される）直前でカットするのが一般的な目安とされています。✂️ [3, 20]

Python (scikit-learn & scipy) での実装例

Pythonのライブラリ `scikit-learn` と `scipy` を使って、階層クラスタリングとデンドログラムの描画を実装してみましょう。[4, 10, 12, 19]

必要なライブラリ

numpy: 数値計算用 [14]
matplotlib: グラフ描画用 [4, 10, 14]
sklearn.cluster.AgglomerativeClustering: 凝集型階層クラスタリング用 [10]
sklearn.datasets.make_blobs: サンプルデータ生成用 [14]
scipy.cluster.hierarchy: 連結計算とデンドログラム描画用 [4, 8, 10, 19]

※ 必要に応じて pip install numpy matplotlib scikit-learn scipy でインストールしてください。[4, 14]

まず、`AgglomerativeClustering` を使ってクラスタリングを行います。`AgglomerativeClustering` はクラスタリング結果のラベルを得るのに便利です。


import numpy as np
from sklearn.datasets import make_blobs
from sklearn.cluster import AgglomerativeClustering
import matplotlib.pyplot as plt

# サンプルデータの生成 (簡単のため2次元データ)
# centers=3 で3つの塊を持つデータを生成
X, _ = make_blobs(n_samples=50, centers=3, cluster_std=1.0, random_state=42)

# Ward法を用いた凝集型階層クラスタリング
# n_clusters で最終的なクラスタ数を指定 (デンドログラムを見て決めるのが一般的)
# metric で距離の種類、 linkage で連結法を指定
# distance_threshold=0, n_clusters=None とすると完全なツリーを計算できる [10]
agg_clustering = AgglomerativeClustering(n_clusters=3, metric='euclidean', linkage='ward')

# クラスタリングの実行と各データ点のラベルを取得
labels = agg_clustering.fit_predict(X)

# 結果の可視化 (散布図で色分け)
plt.figure(figsize=(8, 6))
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', s=50, alpha=0.7)
plt.title('Agglomerative Clustering Result (Ward, n_clusters=3)')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.grid(True)
plt.show()

print(f"各データ点のクラスタラベル (n_clusters=3): {labels}")

次に、`scipy.cluster.hierarchy` の `linkage` 関数と `dendrogram` 関数を使って、クラスタリングの過程計算とデンドログラムの描画を行います。`linkage` 関数はクラスタがどのように併合されていったかの情報（リンケージ行列）を返します。[8, 9]


from scipy.cluster.hierarchy import dendrogram, linkage

# linkage関数で階層クラスタリングの計算を行う (Ward法)
# linkage関数はクラスタリングの過程 (併合情報、距離、含まれるデータ点数) を計算する
# method 引数で連結法を指定 ('ward', 'complete', 'single', 'average', 'centroid', etc.) [8]
linked = linkage(X, method='ward')

# デンドログラムの描画 [8, 10]
plt.figure(figsize=(12, 7))
# dendrogram 関数に linkage の結果を渡す
dendrogram(linked,
            orientation='top', # デンドログラムを上向きに表示 (他に 'bottom', 'left', 'right')
            # labels= # 各データ点のラベルを指定できるが、データが多いと見づらい
            distance_sort='descending', # 枝を距離の降順でソートして描画
            show_leaf_counts=True) # 枝の末端に含まれるデータ点数を表示

plt.title('Hierarchical Clustering Dendrogram (Ward)')
plt.xlabel('Data Points (or Cluster Index)')
plt.ylabel('Distance (Ward)')
plt.grid(axis='y') # 横軸のグリッドを表示

# デンドログラムをカットする高さの目安線を描画する例
# plt.axhline(y=10, color='r', linestyle='--') # y=10 の高さでカットすると3クラスタになる

plt.show()

sklearn.cluster.AgglomerativeClustering の linkage 引数と scipy.cluster.hierarchy.linkage の method 引数は対応しており、同じ連結法を指定できます。[8] デンドログラムを描画することで、AgglomerativeClustering で指定する n_clusters や distance_threshold の適切な値を視覚的に判断する助けになります。📈📉 [10, 12]

階層クラスタリングのメリット・デメリット

階層クラスタリングには、以下のようなメリットとデメリットがあります。

メリット 👍

クラスタ数の事前指定が不要: デンドログラムを見てから適切なクラスタ数を柔軟に決定できる。[1, 3, 18, 19]
階層構造の可視化: デンドログラムにより、データ間の類似性の階層的な関係性を視覚的に理解しやすい。[1, 3, 7, 12]
様々な連結法: データの特性や分析目的に合わせて連結法を選択できる。[2]
結果の再現性: アルゴリズムが決定的なので、同じデータに対しては常に同じ結果が得られる（k-meansのように初期値依存性がない）。[13]

デメリット 👎

計算コストが高い: データ数が増えると、距離計算の組み合わせが爆発的に増えるため、計算量が多くなり、処理時間がかかる。[1, 3, 6, 11, 13, 17] 大規模データ（ビッグデータ）には不向きな場合がある。[1, 6, 11, 21]
やり直しができない: 凝集型の場合、一度クラスタが併合されると、後からその併合を取り消すことはできない（貪欲法）。[2]
連結法の選択が難しい: どの連結法が最適かはデータに依存し、結果が大きく変わるため、選択が難しい場合がある。[2, 3]
外れ値の影響: 連結法によっては外れ値の影響を受けやすい場合がある（例：単連結法）。[1, 5]

まとめ

今回は、教師なし学習の手法である階層クラスタリングと、その結果を可視化するデンドログラムについて学びました。

階層クラスタリングは、データ間の類似度に基づき、段階的にクラスタを形成する手法です。[1, 3]
主に凝集型（ボトムアップ）と分割型（トップダウン）のアプローチがあります。[2, 3]
凝集型では、クラスタ間の距離を計算する方法（連結法：ウォード法、完全連結法、単連結法、群平均法など）の選択が重要です。[1, 3, 7]
デンドログラムを使うことで、クラスタの併合過程を視覚的に理解し、適切なクラスタ数を判断するのに役立ちます。[1, 3, 12, 18, 22]
Pythonの`scikit-learn`や`scipy`ライブラリを使うことで、実装やデンドログラムの描画が可能です。[4, 8, 10, 12, 19]
クラスタ数を事前に決める必要がない、階層構造を可視化できるといったメリットがある一方、計算コストが高いというデメリットも理解しておく必要があります。[1, 3, 6, 11, 13, 17, 18, 19]

階層クラスタリングは、データの構造を探索的に理解したい場合や、クラスタ数を事前に決められない場合に特に有効な手法です。他のクラスタリング手法（k-meansやDBSCANなど）との特性の違いを理解し、データや目的に合わせて使い分けられるようになりましょう。

これでStep 5の「階層クラスタリングとデンドログラム」は完了です！次は、密度に基づいてクラスタを発見する「DBSCAN」について学んでいきましょう。お疲れ様でした！🎉