BIRCH と MiniBatchKMeans クラスタリングアルゴリズムの比較

はじめに

この実験では、合成データセット上で 2 つのクラスタリングアルゴリズム、BIRCH と MiniBatchKMeans の実行時間を比較します。両方のアルゴリズムは拡張性があり、大規模なデータセットを効率的にクラスタリングできます。合成データセットには、make_blobs を使用して生成された 25,000 個のサンプルと 2 つの特徴量があります。

VM のヒント

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

Jupyter Notebook が読み込み完了するまで数秒待つ必要がある場合があります。Jupyter Notebook の制限により、操作の検証を自動化することはできません。

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

ライブラリのインポート

最初のステップは、必要なライブラリをインポートすることです。以下のライブラリをインポートします。

numpy
matplotlib
sklearn

from joblib import cpu_count
from itertools import cycle
from time import time
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.colors as colors

from sklearn.cluster import Birch, MiniBatchKMeans
from sklearn.datasets import make_blobs

ブロブの生成

次のステップは、MiniBatchKMeans と BIRCH を比較するためにブロブを生成することです。matplotlib がデフォルトで提供するすべての色を使用します。

## Generate centers for the blobs so that it forms a 10 X 10 grid.
xx = np.linspace(-22, 22, 10)
yy = np.linspace(-22, 22, 10)
xx, yy = np.meshgrid(xx, yy)
n_centers = np.hstack((np.ravel(xx)[:, np.newaxis], np.ravel(yy)[:, np.newaxis]))

## Generate blobs to do a comparison between MiniBatchKMeans and BIRCH.
X, y = make_blobs(n_samples=25000, centers=n_centers, random_state=0)

## Use all colors that matplotlib provides by default.
colors_ = cycle(colors.cnames.keys())

Birch モデル

3 番目のステップは、最終クラスタリングステップを行わない場合と行う場合の両方で Birch を使ってクラスタリングを計算し、プロットすることです。2 つの Birch モデルを作成します。1 つはグローバルクラスタリングステップを行わないもので、もう 1 つはグローバルクラスタリングステップを行うものです。

## Compute clustering with BIRCH with and without the final clustering step and plot.
birch_models = [
    Birch(threshold=1.7, n_clusters=None),
    Birch(threshold=1.7, n_clusters=100),
]
final_step = ["without global clustering", "with global clustering"]

for ind, (birch_model, info) in enumerate(zip(birch_models, final_step)):
    t = time()
    birch_model.fit(X)
    print("BIRCH %s as the final step took %0.2f seconds" % (info, (time() - t)))

    ## Plot result
    labels = birch_model.labels_
    centroids = birch_model.subcluster_centers_
    n_clusters = np.unique(labels).size
    print("n_clusters : %d" % n_clusters)

    ax = fig.add_subplot(1, 3, ind + 1)
    for this_centroid, k, col in zip(centroids, range(n_clusters), colors_):
        mask = labels == k
        ax.scatter(X[mask, 0], X[mask, 1], c="w", edgecolor=col, marker=".", alpha=0.5)
        if birch_model.n_clusters is None:
            ax.scatter(this_centroid[0], this_centroid[1], marker="+", c="k", s=25)
    ax.set_ylim([-25, 25])
    ax.set_xlim([-25, 25])
    ax.set_autoscaley_on(False)
    ax.set_title("BIRCH %s" % info)

MiniBatchKMeans モデル

4 番目のステップは、MiniBatchKMeans を使ってクラスタリングを計算することです。モデルをデータセットに適合させ、MiniBatchKMeans を実行するのにかかった時間を表示します。

## Compute clustering with MiniBatchKMeans.
mbk = MiniBatchKMeans(
    init="k-means++",
    n_clusters=100,
    batch_size=256 * cpu_count(),
    n_init=10,
    max_no_improvement=10,
    verbose=0,
    random_state=0,
)
t0 = time()
mbk.fit(X)
t_mini_batch = time() - t0
print("Time taken to run MiniBatchKMeans %0.2f seconds" % t_mini_batch)
mbk_means_labels_unique = np.unique(mbk.labels_)

ax = fig.add_subplot(1, 3, 3)
for this_centroid, k, col in zip(mbk.cluster_centers_, range(n_clusters), colors_):
    mask = mbk.labels_ == k
    ax.scatter(X[mask, 0], X[mask, 1], marker=".", c="w", edgecolor=col, alpha=0.5)
    ax.scatter(this_centroid[0], this_centroid[1], marker="+", c="k", s=25)
ax.set_xlim([-25, 25])
ax.set_ylim([-25, 25])
ax.set_title("MiniBatchKMeans")
ax.set_autoscaley_on(False)
plt.show()

まとめ

この実験では、合成データセット上で 2 つのクラスタリングアルゴリズム、BIRCH と MiniBatchKMeans の実行時間を比較しました。BIRCH は階層型クラスタリングアルゴリズムで、大規模なデータセットを効率的にクラスタリングできます。MiniBatchKMeans は KMeans アルゴリズムのバリエーションで、同様に大規模なデータセットを効率的にクラスタリングできます。両方のアルゴリズムは、合理的な時間内にデータセットをクラスタリングすることができました。

BIRCH と MiniBatchKMeans の比較