📃

論文実装：クラスタリング評価指標入門

に公開
AI
論文
クラスタリング
評価指標
tech

論文実装：クラスタリング評価指標入門

今回の論文

Benchmarking of Clustering Validity Measures Revisitedという論文を読みました。

まず、論文の内容ですが、ざっくり次のような感じです。（英語があまり得意ではないので、違っていたらご指摘ください。）

概要

本論文では、クラスタリングの 内部妥当性指標（internal validity indexes）を対象として、26種類もの指標を対象に包括的なベンチマークを行っている。従来研究における手法の問題点を整理し、新たに３つの評価シナリオを設定、さらに 16,177件という大規模なデータセット集合を生成して、８つの代表的クラスタリングアルゴリズムを適用し、各指標の挙動・優劣を検証している。 
この分析を通して、「ある指標がクラスタリング解をどれだけうまく評価・選択できるか」「指標のバイアス」などに関する知見を提示し、最終的に実務上どの内部指標が有用かについての推薦を行っている。

目的・背景

クラスタリングは教師なし学習の代表的手法であり、解（クラスタ分け）を得た後に「どのクラスタ数／どのアルゴリズムがよいか」を決めるために妥当性指標（validation index）が重要である。
特に、実務では正解ラベル（ground truth）がないケースが多いため、内部妥当性指標（データ＋クラスタ解だけでクラスタリング良否を測る）が重視される。 
ただし、従来のベンチマーク研究には以下のような課題があった：

  • 対象となる指標数が少ない、もしくは新しい指標が含まれていない。

  • データセット数・多様性が十分ではない。

  • 評価方法として「正しいクラスタ数を当てるか」「最良解を選ぶか」など単純化されており、指標が「解をランク付けする能力」を十分に測れていない。 
    よって、本研究の目的はこれらの欠点を補い、より現実的・包括的に内部妥当性指標の性能を比較・理解することである。

調査・実験・検証内容

本節では、本研究が具体的にどのようなデータ・アルゴリズム・指標・評価設計を用いているか、比較的リッチにまとめる。

対象内部妥当性指標

研究では、26種類の内部妥当性指標を対象にしている。 
例えば、従来よく使われるものとしては：

  • Calinski–Harabasz Index（別名 Variance Ratio Criterion, VRC）
  • Davies–Bouldin Index
  • Silhouette Width Criterion
  • DBCV：Density-Based Clustering Validation
  • S_Dbw：Mixed型（分離・密度）

クラスタリング手法・データ

  • クラスタリングアルゴリズムとして、8種類の代表的手法を採用。たとえば、K‑Means、Spectral Clustering、HDBSCAN*、EM‑GMMなど。

  • データセットとして、16177件という大規模な集合を生成・利用。これは従来研究 の 972件を含む形で拡張されており、クラスタ数・次元数・ノイズ・重なり・密度・クラスタ形状・クラスタ数のバランス（size-balance）など 7つのデータ特性を多様に変化させている。 
    この点が、従来に比してかなり充実しており、より実務的なシナリオを想定している。

評価設計：３つの評価シナリオ

研究では内部指標の検証にあたり、次の３つの「評価シナリオ（Evaluation Scenario）」を設定している。

シナリオ 1：クラスタ数を変化させた候補群

  • 各データセットで、クラスタ数 k を変化させた複数のクラスタリング解を生成。

  • 内部指標がそれらの解をどれだけ良く識別（＝良解を高評価／悪解を低評価）できるかを分析。

  • 具体には「最適なクラスタ数を含むか」「ランク付け性能」などを測定。

シナリオ 2：クラスタ数を固定した候補群

  • 各データでクラスタ数 k を固定（例えば真のクラスタ数）し、アルゴリズム・初期値などを変えて複数解を取得。

  • どの指標が解の質（アルゴリズムによる差分）をきちんと捉えられるかを検証。

  • これにより「クラスタ数決定」よりも「アルゴリズム・解の質評価」に重きを置いた評価となる。

シナリオ 3：アルゴリズムおよび外部指標に依存しない評価

  • 内部指標を「外部真値ラベルなし／アルゴリズムに依存しない」形で評価する手法。

  • 具体的には、候補解を「参照ランク付け（reference ranking）」し、それと内部指標のランク付けがどれだけ一致するかを見たり、指標の挙動・傾向（例えばクラスタ数に対して単調増加するなどの望ましくないバイアス）を可視化・分析。

  • このシナリオにより、外部指標のバイアスやアルゴリズム依存性から独立した「指標自身の挙動」を掘ることが可能となる。

主な評価指標／手法

  • 各シナリオで、内部指標が良解を「選び出す」「ランク付けする」能力を、 選出率（“top‐pick percentage”）や 相関（例えばPearson／Spearman） 等を用いて定量化している。

  • さらに、可視化（散布図）を用して、内部指標 vs 外部指標の挙動を分析し、単純な線形相関では捉えきれない非線形・単調性・クラスタ数バイアスなどを議論している。

  • 例として、あるデータでは内部指標 Ratkowsky–Lance Index がクラスタ数 k に対して単調増加を示し、「良い解を選び出している」のではなく「クラスタ数を多く取るほどスコアがよくなる」という望ましくない挙動をしており、それでもPearson 相関が高かったという問題を示している。

主な結果

  • 指標によってクラスタ数・アルゴリズム・データ特性（次元数・ノイズ・クラスタ重なり）への依存性が大きく異なる。

  • 従来、よく使われてきた指標の中にも、クラスタ数増加バイアス・ランク付け性能の欠如などの弱点を持つものがあった。

  • 「クラスタ数を変化させたシナリオ（シナリオ 1）」では、いくつかの指標が他を大きく優る結果を示したが、シナリオ 2／3では別の指標のほうがロバストであることが示された。

  • 概括的な推奨として、どの指標が「汎用的に使いやすいか」「特定のアルゴリズム・データ特性下で強いか」についてまとめられている（Table 13等にて）。

実施内容

Colab 環境とデータセットの準備

実装はすべて Google Colab 上で動くことを前提にしています。必要なライブラリは scikit-learn と matplotlib, pandas だけに絞り、pip でインストールせずに標準で入っているものだけを使います。

最初に、評価に使うデータセットをいくつか用意します。論文では一万六千以上のデータセットを使っていますが、ここでは代表的な形状の違いが分かるように、次のような人工データを生成します。

ひとつにまとめた関数は次のようになります。

import numpy as np
import pandas as pd

from sklearn.datasets import make_blobs, make_moons, make_circles, make_classification
from sklearn.preprocessing import StandardScaler

def generate_datasets(random_state=0):
    rng = np.random.RandomState(random_state)
    datasets = {}

    # 分離のよいガウス分布クラスタ
    X1, y1 = make_blobs(
        n_samples=600, centers=3, cluster_std=0.6, random_state=rng
    )
    X1 = StandardScaler().fit_transform(X1)
    datasets["blobs_easy"] = (X1, y1)

    # 強く重なったガウス分布クラスタ
    X2, y2 = make_blobs(
        n_samples=600, centers=3, cluster_std=1.8, random_state=rng
    )
    X2 = StandardScaler().fit_transform(X2)
    datasets["blobs_overlap"] = (X2, y2)

    # 半月状のクラスタ
    X3, y3 = make_moons(n_samples=600, noise=0.1, random_state=rng)
    X3 = StandardScaler().fit_transform(X3)
    datasets["moons"] = (X3, y3)

    # 同心円状のクラスタ
    X4, y4 = make_circles(
        n_samples=600, factor=0.4, noise=0.05, random_state=rng
    )
    X4 = StandardScaler().fit_transform(X4)
    datasets["circles"] = (X4, y4)

    # 少し次元の高い分類問題
    X5, y5 = make_classification(
        n_samples=800,
        n_features=10,
        n_informative=6,
        n_redundant=2,
        n_clusters_per_class=1,
        n_classes=4,
        random_state=rng,
    )
    X5 = StandardScaler().fit_transform(X5)
    datasets["highdim"] = (X5, y5)

    return datasets

どのデータセットも、真のクラスタラベルを y に持っているので、内部評価指標だけでなく、外部指標も計算できるようになっています。また、StandardScaler でスケーリングしているため、距離ベースの指標が過度にスケールの影響を受けないようにしています。

続いて、クラスタリングアルゴリズムと評価指標をまとめておきます。

from sklearn.cluster import KMeans, AgglomerativeClustering
from sklearn.mixture import GaussianMixture

from sklearn.metrics import (
    silhouette_score,
    calinski_harabasz_score,
    davies_bouldin_score,
    adjusted_rand_score,
    normalized_mutual_info_score,
)

ここまでを一つのセルに書いておくと、以降のシナリオで何度でも使い回すことができます。

シナリオ1: クラスタ数 k を変えた KMeans の評価

論文の評価シナリオ1は、「クラスタ数を変えた候補群の中から、内部指標がどれだけ正しく良い解を選べるか」を比較するものです。

ここではその簡易版として、各データセットに対してクラスタ数 k を変えながら KMeans を実行し、次の五つの指標をすべて計算していきます。

内部指標は Silhouette, Calinski–Harabasz (CH), Davies–Bouldin (DB) です。外部指標は Adjusted Rand Index (ARI) と Normalized Mutual Information (NMI) です。

実験用のループは次のようになります。

datasets = generate_datasets()

records = []

for name, (X, y_true) in datasets.items():
    for k in range(2, 9):
        km = KMeans(n_clusters=k, random_state=0, n_init=10)
        labels = km.fit_predict(X)

        sil = silhouette_score(X, labels)
        ch  = calinski_harabasz_score(X, labels)
        db  = davies_bouldin_score(X, labels)

        ari = adjusted_rand_score(y_true, labels)
        nmi = normalized_mutual_info_score(y_true, labels)

        records.append(
            {
                "dataset": name,
                "k": k,
                "silhouette": sil,
                "calinski_harabasz": ch,
                "davies_bouldin": db,
                "ARI": ari,
                "NMI": nmi,
            }
        )

df_s1 = pd.DataFrame(records)
df_s1.head()

この DataFrame には、データセット名、クラスタ数 k、三つの内部指標値、二つの外部指標値がすべて入ります。たとえば、特定のデータセットだけを取り出して、内部指標と ARI の散布図を描くと、内部指標が上がると ARI も上がるのか、それとも乖離が大きいのかといった傾向を目視できます。

import matplotlib.pyplot as plt

target_ds = "moons"

df_ds = df_s1[df_s1["dataset"] == target_ds]

fig, axes = plt.subplots(1, 3, figsize=(15, 4))

axes[0].scatter(df_ds["silhouette"], df_ds["ARI"])
axes[0].set_xlabel("Silhouette")
axes[0].set_ylabel("ARI")
axes[0].set_title(f"{target_ds}: Silhouette vs ARI")

axes[1].scatter(df_ds["calinski_harabasz"], df_ds["ARI"])
axes[1].set_xlabel("Calinski-Harabasz")
axes[1].set_ylabel("ARI")
axes[1].set_title(f"{target_ds}: CH vs ARI")

axes[2].scatter(df_ds["davies_bouldin"], df_ds["ARI"])
axes[2].set_xlabel("Davies-Bouldin")
axes[2].set_ylabel("ARI")
axes[2].set_title(f"{target_ds}: DB vs ARI")

plt.tight_layout()
plt.show()

直感的な振る舞いとして、分離の良いガウス型クラスタでは、Silhouette と CH が高いときに ARI も高くなりやすく、DB は値が小さいときに ARI が高くなる傾向が見られます。一方で、半月や同心円のように非球面なクラスタ構造を持つデータでは、内部指標がきれいに外部指標と対応しないケースが増えます。これは、これらの指標がそもそも「距離と分散」に基づいた球面クラスタを前提に設計されているためであり、論文でも似たような限界が指摘されています。

シナリオ2: クラスタ数を固定し、アルゴリズムを変える

論文の評価シナリオ2は、「クラスタ数が既知のときに、アルゴリズムや解の質の違いを内部指標がどれだけ正しく反映するか」というものです。
ここではクラスタ数を真のクラスタ数に合わせて固定し、次のアルゴリズムを比較します。

KMeans
GaussianMixture
AgglomerativeClustering（ward と average の二種類）

Colab では次のようなコードになります。

algorithms = {
    "kmeans": lambda k: KMeans(n_clusters=k, random_state=0, n_init=10),
    "gmm": lambda k: GaussianMixture(n_components=k, random_state=0),
    "agg_ward": lambda k: AgglomerativeClustering(n_clusters=k, linkage="ward"),
    "agg_average": lambda k: AgglomerativeClustering(n_clusters=k, linkage="average"),
}

records2 = []

for name, (X, y_true) in datasets.items():
    k_true = len(np.unique(y_true))

    for algo_name, algo_builder in algorithms.items():
        model = algo_builder(k_true)
        labels = model.fit_predict(X)

        sil = silhouette_score(X, labels)
        ch  = calinski_harabasz_score(X, labels)
        db  = davies_bouldin_score(X, labels)

        ari = adjusted_rand_score(y_true, labels)
        nmi = normalized_mutual_info_score(y_true, labels)

        records2.append(
            {
                "dataset": name,
                "algo": algo_name,
                "k": k_true,
                "silhouette": sil,
                "calinski_harabasz": ch,
                "davies_bouldin": db,
                "ARI": ari,
                "NMI": nmi,
            }
        )

df_s2 = pd.DataFrame(records2)
df_s2.head()

この DataFrame から、データセットごとに「外部指標で一番良いアルゴリズム」と「それを内部指標がどれだけ正しく選べているか」を簡易的に確認できます。

たとえば、あるデータセットで ARI が最も高いアルゴリズムを真の意味での一位とみなし、そのアルゴリズムに内部指標が最大値（あるいは最小値）をつけているかどうかを数え上げると、簡単なベンチマーク指標になります。論文ではこれをもっと厳密に定義し、統計的検定やより多くのアルゴリズムを組み合わせて詳細に評価しています。

各評価指標の解説

ここで登場した五つの指標について、改めて考え方と特徴を整理します。

Silhouette 係数

Silhouette 係数は、一つひとつのサンプル i について、同じクラスタ内の距離の平均 a(i) と、他クラスタへの距離の最小平均 b(i) を使って、次の値を定義します。

s(i) = (b(i) - a(i)) / max(a(i), b(i))

値の範囲はおおよそ −1 から 1 で、1 に近いほど「同じクラスタ内では近く、他クラスタからは遠い」ことを意味します。全サンプルの s(i) の平均を取ったものが、クラスタリング全体のスコアです。

直感的で解釈しやすく、クラスタ数 k を変えながら最大値を取る k を探す用途に向いていますが、距離と密度に基づいているため、非球面クラスタや、非常に細かく分割したクラスタに対しては素直に動かない場合があります。

Calinski–Harabasz 指標

Calinski–Harabasz 指標は、クラスタ間分散とクラスタ内分散の比率を用いた指標です。クラスタ数を k、サンプル数を n とすると、概ね次のような形をしています。

クラスタ間分散を B、クラスタ内分散を W とするとき、

CH = (tr(B) / (k - 1)) / (tr(W) / (n - k))

という比率になります。クラスタ間分散が大きく、クラスタ内分散が小さいほど値が大きくなるため、大きいほど良いとみなします。計算が高速で、KMeans のように球面ガウスクラスタを仮定したアルゴリズムと相性が良い一方、やはりクラスタ形状の想定が強く、形がいびつなクラスタ構造があるときには過信できない側面があります。

Davies–Bouldin 指標

Davies–Bouldin 指標は、各クラスタの「広がり」とクラスタ間の「距離」に基づいて、クラスタ間分離度を評価します。クラスタ i の平均的な広がりを s_i、クラスタ i と j の重心間距離を d_ij としたとき、クラスタ i に対するスコア R_i は、

R_i = max_{j ≠ i} (s_i + s_j) / d_ij

として定義されます。全体の DB 指標は、R_i の平均です。クラスタ同士が近くて広がりが大きいと R_i の値が大きくなり、結果として DB も大きくなります。そのため、この指標は小さいほど良いと解釈します。

クラスタ間の分離に敏感で、過剰な細分化に対しては Silhouette よりバイアスが小さいと言われる一方、計算がやや複雑であり、やはり距離と広がりの前提から外れたクラスタ構造では直感どおりに動かないことがあります。

Adjusted Rand Index (ARI)

Rand Index は、二つのクラスタリング結果を比較するときに、「同じクラスタに入っているペア」と「違うクラスタに入っているペア」がどれだけ一致しているかをペアレベルで評価する指標です。Adjusted Rand Index は、この Rand Index を「偶然一致する分」を差し引いて補正したもので、ランダムなクラスタリング同士を比較したときに、期待値がゼロになるように調整されています。

値の範囲は理論的には −1 から 1 で、1 が完全一致、0 がほぼランダム、一より小さい値はランダムより悪い一致を意味します。ラベルの付け替えに不変であり、クラス数が異なっていても比較できるため、外部指標として非常に広く使われています。ただし、全サンプルペアを考えるため、サンプル数が非常に多いと計算コストが上がる点には注意が必要です。

Normalized Mutual Information (NMI)

Normalized Mutual Information は、情報理論の観点からクラスタラベルの一致度を測る指標です。二つのラベル集合の間の相互情報量を、それぞれのエントロピーで正規化したものになっており、一般的な定義では値の範囲は 0 から 1 です。1 に近いほど、ラベル同士が多くの情報を共有していることを意味します。

クラス数が多い場合でも安定して動きやすく、ラベルの付け替えにも不変であるため、マルチクラス・クラスタ数不一致の比較によく使われます。一方で、特定の条件下ではクラスタ間の分離をやや楽観的に評価し過ぎる傾向があることも指摘されています。論文でも、複数の外部指標を併用して評価することが推奨されています。

おわりに

この記事では、論文「Benchmarking of Clustering Validity Measures Revisited」の評価シナリオにならって、Colab 上で簡易的なベンチマーク実験を行い、内部指標三つと外部指標二つの挙動を確認しました。[

実験を通して、分離の良いガウス型データでは Silhouette や CH が外部指標ときれいに相関しやすい一方で、半月や同心円のような非球面構造では内部指標と外部指標の関係が崩れやすいことが改めて確認できました。また、クラスタ数を固定してアルゴリズムを変えた場合でも、内部指標が常に外部指標の一位と一致するわけではないという意味で、「内部指標だけを見てアルゴリズムやパラメータを決める危うさ」も体感できました。

今回の実装は、あくまで少数のデータセットと少数の指標を用いたミニ版です。今後は、論文で扱われているような他の内部指標を少しずつ追加したり、データセットの数を増やして統計的な比較をしやすくしたりすることで、より本格的なベンチマークに近づけていきたいと思います。また、実務のクラスタリング案件にこのノートブックの枠組みをそのまま持ち込み、仮説ごとにシナリオを組んで評価することで、指標に振り回されないクラスタリング設計を少しずつ目指していきたいと考えています。

Discussion