X-means

X-meansは、クラスタ数を自動的に決定できるクラスタリング手法です。
k-means や k-means++ はクラスタ数 $k$ を事前に指定する必要がありますが、X-means は統計的基準を使って「最適なクラスタ数」を選びます。

pyclustering.cluster.xmeans.xmeans Class Reference

Pelleg, Dan, and Andrew W. Moore. “X-means: Extending k-means with efficient estimation of the number of clusters.” ICML, 2000.

1. 直感：クラスタ数を「分割しながら」決める #

k-means：クラスタ数 $k$ を人間が決める必要がある。
X-means：まず少ないクラスタ数から始める。
- その後、クラスタを分割するかどうかを BIC や MDL の基準で判断する。
これを繰り返して、最適なクラスタ数を自動決定する。

2. 数式でみる X-means #

2.1 BIC（ベイズ情報量基準） #

クラスタ数が増えると「当てはまり」は良くなるが、複雑すぎると過学習になる。
BIC は「モデルの当てはまり」と「複雑さ」のバランスをとる指標。

$$ \mathrm{BIC} = \ln L - \frac{p}{2} \ln n $$

$L$：モデルの尤度（クラスタリングの当てはまりの良さ）
$p$：パラメータ数（クラスタ数が増えると大きくなる）
$n$：データ数

BIC が大きくなるようにクラスタ数を選択。

2.2 MDL（最小記述長） #

「モデルの複雑さ」と「データの説明力」のトレードオフを数値化。
X-means では BIC または MDL を使ってクラスタ数を決定する。

3. Python による実装例 #

k-means でクラスタ数を指定 #

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

def plot_by_kmeans(X, k=5):
    y_pred = KMeans(n_clusters=k, random_state=117117, init="random").fit_predict(X)
    plt.scatter(X[:, 0], X[:, 1], c=y_pred, marker="x")
    plt.title(f"k-means, n_clusters={k}")

# サンプルデータ
n_samples = 1000
random_state = 117117
X, _ = make_blobs(
    n_samples=n_samples, random_state=random_state, cluster_std=1, centers=10
)

plot_by_kmeans(X)

png

X-means でクラスタ数を自動決定 #

from pyclustering.cluster.xmeans import xmeans
from pyclustering.cluster.center_initializer import kmeans_plusplus_initializer

BAYESIAN_INFORMATION_CRITERION = 0
MINIMUM_NOISELESS_DESCRIPTION_LENGTH = 1

def plot_by_xmeans(X, c_min=3, c_max=10, criterion=BAYESIAN_INFORMATION_CRITERION, tolerance=0.025):
    initial_centers = kmeans_plusplus_initializer(X, c_min).initialize()
    xmeans_instance = xmeans(
        X, initial_centers, c_max, criterion=criterion, tolerance=tolerance
    )
    xmeans_instance.process()
    clusters = xmeans_instance.get_clusters()

    for i, cluster_i in enumerate(clusters):
        X_ci = X[cluster_i]
        plt.scatter(X_ci[:, 0], X_ci[:, 1], marker="x")
    plt.title("x-means")

plot_by_xmeans(X, c_min=3, c_max=10, criterion=BAYESIAN_INFORMATION_CRITERION)

png

4. tolerance の影響 #

分割を許す「しきい値（tolerance）」を変えると結果が変わる。

X, _ = make_blobs(n_samples=2000, random_state=117117, cluster_std=0.4, centers=10)

plt.figure(figsize=(25, 5))
for i, ti in enumerate(np.linspace(0.0001, 1, 5)):
    ti = np.round(ti, 4)
    plt.subplot(1, 10, i + 1)
    plot_by_xmeans(X, c_min=3, c_max=10, criterion=BAYESIAN_INFORMATION_CRITERION, tolerance=ti)
    plt.title(f"tol={ti}")

png

5. k-means と X-means の比較 #

いくつかのデータセットで、k-means（固定クラスタ数）と X-means（自動クラスタ数）を比較。

for i in range(3):
    X, _ = make_blobs(
        n_samples=1000, random_state=117117,
        cluster_std=0.7, centers=5 + i * 5
    )
    plt.figure(figsize=(10, 5))
    plt.subplot(1, 2, 1)
    plot_by_kmeans(X)
    plt.subplot(1, 2, 2)
    plot_by_xmeans(X, c_min=3, c_max=20)
    plt.show()

png

6. 実務でのコツ #

k-means は「クラスタ数を決める必要がある」のが弱点。
X-means は「BIC / MDL」を使い、データからクラスタ数を推定。
データ構造が複雑な場合や、クラスタ数を事前に決めにくい場合に有効。
ただし計算コストは k-means より大きい。

まとめ #

k-means：クラスタ数を事前に指定する必要がある。
X-means：クラスタ数を自動決定できる（BIC・MDL を用いる）。
実務では「クラスタ数が不明」な場面で有用。
tolerance などのパラメータ調整によって結果が変わるため注意。