Эмпирическая оценка инициализации K-Means

Введение

K-means - это алгоритм кластеризации, который разбивает набор данных на k кластеров, где каждая точка принадлежит кластеру, центроид которого находится наиболее близко к ней. Выбор метода инициализации для k-means может значительно повлиять на производительность и сходимость алгоритма. В этом лабораторном занятии мы будем оценивать влияние различных методов инициализации на устойчивость сходимости алгоритма k-means кластеризации.

Советы по работе с ВМ

После запуска ВМ нажмите в левом верхнем углу, чтобы переключиться на вкладку Notebook и получить доступ к 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 сделать алгоритм устойчивым к сходимости. Мы будем измерять относительную стандартную отклоненность инерции кластеризации, которая представляет собой сумму квадратов расстояний до ближайшего центра кластера. Первый график показывает наилучшую инерцию, достигнутую для каждой комбинации модели (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(
        "Example cluster allocation with a single random init\nwith MiniBatchKMeans"
    )

plt.show()

Резюме

В этой лабораторной работе мы оценили влияние различных методов инициализации на устойчивость сходимости алгоритма k-means кластеризации. Мы измерили относительную стандартную отклоненность инерции кластеризации и продемонстрировали один запуск оценщика MiniBatchKMeans с использованием init="random" и n_init=1. Выбор метода инициализации для k-means может значительно повлиять на производительность и сходимость алгоритма.