K-평균 초기화의 실증적 평가

소개

K-평균은 데이터 집합을 k 개의 클러스터로 분할하는 군집화 알고리즘으로, 각 점은 그 중심점과 가장 가까운 클러스터에 속합니다. K-평균 알고리즘의 초기화 방법 선택은 알고리즘의 성능과 수렴에 큰 영향을 미칠 수 있습니다. 이 실습에서는 서로 다른 초기화 방법이 K-평균 군집화 알고리즘의 수렴 안정성에 미치는 영향을 평가할 것입니다.

VM 팁

VM 시작이 완료되면 왼쪽 상단 모서리를 클릭하여 Notebook 탭으로 전환하여 연습을 위한 Jupyter Notebook에 접근할 수 있습니다.

때때로 Jupyter Notebook 이 완전히 로드되기까지 몇 초 정도 기다려야 할 수 있습니다. Jupyter Notebook 의 제한으로 인해 작업의 유효성 검사를 자동화할 수 없습니다.

학습 중 문제가 발생하면 Labby 에게 문의하십시오. 세션 후 피드백을 제공하면 문제를 신속하게 해결해 드리겠습니다.

라이브러리 가져오기

이 실습에서는 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-평균 초기화 전략이 알고리즘 수렴을 얼마나 강건하게 만드는지 평가할 것입니다. 클러스터링의 관성 (가장 가까운 클러스터 중심점까지의 제곱 거리의 합) 의 상대 표준 편차를 측정할 것입니다. 첫 번째 그림은 모델 (KMeans 또는 MiniBatchKMeans) 과 초기화 방법 (init="random" 또는 init="k-means++") 의 각 조합에 대해 n_init 매개변수 (초기화 횟수를 제어) 값이 증가함에 따라 도달한 최상의 관성을 보여줍니다.

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)

수렴의 질적 시각 검사

MiniBatchKMeans 추정기를 init="random" 및 n_init=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(
        "MiniBatchKMeans 를 사용한 단일 랜덤 초기화로 인한 예시 클러스터 할당\n"
    )

plt.show()

요약

이 실험에서는 k-평균 클러스터링 알고리즘의 수렴 강건성에 미치는 다양한 초기화 방법의 영향을 평가했습니다. 클러스터링의 관성 (inertia) 의 상대 표준 편차를 측정하고 MiniBatchKMeans 추정기를 init="random" 및 n_init=1을 사용한 단일 실행을 보여주었습니다. k-평균 알고리즘의 초기화 방법 선택은 알고리즘의 성능과 수렴에 큰 영향을 미칠 수 있습니다.