K-Means 初期化の実証評価

はじめに

K-means は、データセットを k 個のクラスタに分割するクラスタリングアルゴリズムであり、各ポイントはその重心が最も近いクラスタに属します。k-means の初期化方法の選択は、アルゴリズムの性能と収束に大きな影響を与える可能性があります。この実験では、k-means クラスタリングアルゴリズムの収束安定性に対する異なる初期化方法の影響を評価します。

VM のヒント

VM の起動が完了したら、左上隅をクリックして ノートブック タブに切り替え、Jupyter Notebook を使って練習しましょう。

Jupyter Notebook の読み込みには数秒かかる場合があります。Jupyter Notebook の制限により、操作の検証は自動化できません。

学習中に問題がある場合は、Labby にお問い合わせください。セッション後にフィードバックを提供してください。すぐに問題を解決いたします。

Skills Graph

ライブラリのインポート

この実験に必要なライブラリをインポートして始めましょう。それには、numpy、matplotlib、sklearn が含まれます。

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.cm as cm
from sklearn.utils import shuffle
from sklearn.utils import check_random_state
from sklearn.cluster import MiniBatchKMeans
from sklearn.cluster import KMeans

データセットの生成

等方性ガウスクラスタの離れた間隔のあるデータセットを生成します。データセット生成パラメータには、各中心のサンプル数、グリッドサイズ、スケール、およびクラスタ数が含まれます。

random_state = np.random.RandomState(0)
n_samples_per_center = 100
grid_size = 3
scale = 0.1
n_clusters = grid_size**2

def make_data(random_state, n_samples_per_center, grid_size, scale):
    random_state = check_random_state(random_state)
    centers = np.array([[i, j] for i in range(grid_size) for j in range(grid_size)])
    n_clusters_true, n_features = centers.shape

    noise = random_state.normal(
        scale=scale, size=(n_samples_per_center, centers.shape[1])
    )

    X = np.concatenate([c + noise for c in centers])
    y = np.concatenate([[i] * n_samples_per_center for i in range(n_clusters_true)])
    return shuffle(X, y, random_state=random_state)

X, y = make_data(random_state, n_samples_per_center, grid_size, scale)

初期化方法の定量評価

k-means の初期化戦略がアルゴリズムの収束を安定させる能力を評価します。クラスタリングの不慣性の相対標準偏差を測定します。これは、最も近いクラスタ中心までの二乗距離の合計です。最初のグラフは、初期化の回数を制御する n_init パラメータの値を増やしたときの、モデル (KMeans または MiniBatchKMeans) と初期化方法 (init="random" または init="k-means++") の各組み合わせで達成される最良の不慣性を示しています。

n_runs = 5
n_init_range = np.array([1, 5, 10, 15, 20])

plt.figure()
plots = []
legends = []

cases = [
    (KMeans, "k-means++", {}, "^-"),
    (KMeans, "random", {}, "o-"),
    (MiniBatchKMeans, "k-means++", {"max_no_improvement": 3}, "x-"),
    (MiniBatchKMeans, "random", {"max_no_improvement": 3, "init_size": 500}, "d-"),
]

for factory, init, params, format in cases:
    print("Evaluation of %s with %s init" % (factory.__name__, init))
    inertia = np.empty((len(n_init_range), n_runs))

    for run_id in range(n_runs):
        X, y = make_data(run_id, n_samples_per_center, grid_size, scale)
        for i, n_init in enumerate(n_init_range):
            km = factory(
                n_clusters=n_clusters,
                init=init,
                random_state=run_id,
                n_init=n_init,
                **params,
            ).fit(X)
            inertia[i, run_id] = km.inertia_
    p = plt.errorbar(
        n_init_range, inertia.mean(axis=1), inertia.std(axis=1), fmt=format
    )
    plots.append(p[0])
    legends.append("%s with %s init" % (factory.__name__, init))

plt.xlabel("n_init")
plt.ylabel("inertia")
plt.legend(plots, legends)
plt.title("Mean inertia for various k-means init across %d runs" % n_runs)

収束の定性的な視覚的検査

init="random" および n_init=1 を使用して、MiniBatchKMeans 推定器の 1 回の実行を示します。この実行は、推定された中心が真のクラスタの間に止まってしまう、悪い収束 (局所最適解) をもたらします。

km = MiniBatchKMeans(
    n_clusters=n_clusters, init="random", n_init=1, random_state=random_state
).fit(X)

plt.figure()
for k in range(n_clusters):
    my_members = km.labels_ == k
    color = cm.nipy_spectral(float(k) / n_clusters, 1)
    plt.plot(X[my_members, 0], X[my_members, 1], ".", c=color)
    cluster_center = km.cluster_centers_[k]
    plt.plot(
        cluster_center[0],
        cluster_center[1],
        "o",
        markerfacecolor=color,
        markeredgecolor="k",
        markersize=6,
    )
    plt.title(
        "Example cluster allocation with a single random init\nwith MiniBatchKMeans"
    )

plt.show()

まとめ

この実験では、k-means クラスタリングアルゴリズムの収束安定性に対する異なる初期化方法の影響を評価しました。クラスタリングの不慣性の相対標準偏差を測定し、init="random" および n_init=1 を使用した MiniBatchKMeans 推定器の 1 回の実行を示しました。k-means の初期化方法の選択は、アルゴリズムの性能と収束に大きな影響を与える可能性があります。