Сегодняшняя история посвящена кластеризации, которая представляет собой задачу группировки набора объектов таким образом, чтобы объекты в одной группе (называемой кластер) были больше похожи (в некотором смысле) друг на друга, чем на те, кто находится в других группах (кластерах). Это основная задача исследовательского анализа данных и общий метод статистического анализа данных, используемый во многих областях, включая распознавание образов, анализ изображений, поиск информации, биоинформатику. сжатие данных, компьютерная графика и машинное обучение (https://en.wikipedia.org/wiki/Cluster_anaлиз). Меня, как поклонника контролируемого машинного обучения, идея неконтролируемых алгоритмов напугала, но поехали. сквозь это! Сначала мы собираемся создать точки данных. Этот набор данных был создан посредством скрининга путем создания блоков определенных центров и со стандартным отклонением. Код ниже предназначен для создания образцов и их построения.

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
import numpy as np
import matplotlib.pyplot as plt
blob_centers = np.array([[ 1,  2], [0 , 4], [-2,  1.],
                         [-2,  4], [-3, 2.5]])
blob_std = np.array([0.3, 0.3, 0.2, 0.2, 0.2])
X, y = make_blobs(n_samples=20000, centers=blob_centers, cluster_std=blob_std,
                  random_state=7)
print(X.shape)
def plot_clusters(X, y):
    unique_labels = np.unique(y)
    colors = plt.cm.get_cmap("tab10", len(unique_labels))  # Get a colormap with enough colors
    for label in unique_labels:
        mask = y == label
        plt.scatter(X[mask, 0], X[mask, 1], c=[colors(label)], s=1, label=f"Cluster {label}")
    plt.xlabel("$x_1$")
    plt.ylabel("$x_2$", rotation=0)
    plt.title('Data For Clustering')
    plt.legend()

plt.figure(figsize=(8, 4))
plot_clusters(X,y)
plt.gca().set_axisbelow(True)
plt.grid()
plt.show()

Результат приведен ниже:

Теперь пришло время применить алгоритм Kmeans, но прежде мы должны предоставить необходимую теорию, лежащую в основе алгоритма. Кроме того, Kmeans кластеризует N точек данных для (ранее известных k) k «команд» с одинаковым стандартным отклонением, пытаясь минимизировать инерцию (для те, кто контактирует с контролируемой моделью, эквивалентны функциям потерь). На практике «среднее значение массы» точек данных является центром каждого кластера. Таким образом, Kmeans попытается найти лучшие центры для кластеров, и новая точка данных будет добавлен в кластер с минимальной инерцией. Следующий код представляет собой создание модели:

k = 5
kmeans = KMeans(n_clusters=k, random_state=42)
y_pred = kmeans.fit_predict(X)

Мы видим, что y_pred представляет собой массив с числами от 0 до 4, поскольку мы создали 5 кластеров, и мы также можем напечатать прогноз центров кластеров:

print(y_pred)
print(kmeans.cluster_centers_)

На первый взгляд мы видим, что центры довольно близки к исходным, и мы можем легко предсказать метку для новых данных:

X_new = np.array([[0, 2], [3, 2], [-3, 3], [-3, 2.5]])
kmeans.predict(X_new)

[0 0 1 1]

На этом этапе я хочу подчеркнуть, что метка — это НЕ то, что мы прогнозируем с помощью Kmeans. Метка связана с тем, к какому кластеру будет добавлена ​​новая точка. Важным фактором для Kmeans являются границы принятия решений, которые показывают «границы» процесса кластеризации. (код ниже):

def plot_centroids(centroids, weights=None, circle_color='w', cross_color='k'):
    if weights is not None:
        centroids = centroids[weights > weights.max() / 10]
    plt.scatter(centroids[:, 0], centroids[:, 1],
                marker='o', s=35, linewidths=8,
                color=circle_color, zorder=10, alpha=0.9)
    plt.scatter(centroids[:, 0], centroids[:, 1],
                marker='x', s=2, linewidths=12,
                color=cross_color, zorder=11, alpha=1)

def plot_decision_boundaries(clusterer, X, resolution=1000, show_centroids=True,
                             show_xlabels=True, show_ylabels=True):
    mins = X.min(axis=0) - 0.1
    maxs = X.max(axis=0) + 0.1
    xx, yy = np.meshgrid(np.linspace(mins[0], maxs[0], resolution),
                         np.linspace(mins[1], maxs[1], resolution))
    Z = clusterer.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)

    plt.contourf(Z, extent=(mins[0], maxs[0], mins[1], maxs[1]),
                cmap="Pastel2")
    plt.contour(Z, extent=(mins[0], maxs[0], mins[1], maxs[1]),
                linewidths=1, colors='k')
    plot_data(X)
    if show_centroids:
        plot_centroids(clusterer.cluster_centers_)

    if show_xlabels:
        plt.xlabel("$x_1$")
    else:
        plt.tick_params(labelbottom=False)
    if show_ylabels:
        plt.ylabel("$x_2$", rotation=0)
    else:
        plt.tick_params(labelleft=False)

plt.figure(figsize=(8, 4))
plot_decision_boundaries(kmeans, X)
plt.title("Decision Boundaries")
plt.show()

Процесс, который мы провели, называется жесткой кластеризацией, и он добавляет новую точку в ближайший кластер. Хотя этот метод может привести к неправильной кластеризации некоторых точек, находящихся рядом с границей двух областей. Поэтому мы также можем применить мягкую кластеризацию, которая группирует точки путем вычисления минимального расстояния от центров кластеров (значение преобразования по умолчанию в Python — евклидово). В заключение, Kmeans инициализирует случайные центроиды, случайным образом выбирая некоторые точки данных. После этого новая точка добавляется в кластер с минимальным расстоянием. Следующим шагом является перерасчет центроидов, и мы перемещаем их в направлении центра масс точки и останавливаемся, когда центры перестали двигаться.

Мы можем применить алгоритм Kmeans для некоторых итераций и посмотреть, как изменяются границы, с помощью следующего кода:

kmeans_iter1 = KMeans(n_clusters=5, init="random", n_init=1, max_iter=1,
                      random_state=5)
kmeans_iter2 = KMeans(n_clusters=5, init="random", n_init=1, max_iter=2,
                      random_state=5)
kmeans_iter3 = KMeans(n_clusters=5, init="random", n_init=1, max_iter=3,
                      random_state=5)
kmeans_iter1.fit(X)
kmeans_iter2.fit(X)
kmeans_iter3.fit(X)

plt.figure(figsize=(10, 8))

plt.subplot(321)
plot_data(X)
plot_centroids(kmeans_iter1.cluster_centers_, circle_color='r', cross_color='w')
plt.ylabel("$x_2$", rotation=0)
plt.tick_params(labelbottom=False)
plt.title("Update the centroids (initially randomly)")

plt.subplot(322)
plot_decision_boundaries(kmeans_iter1, X, show_xlabels=False,
                         show_ylabels=False)
plt.title("Set decision boundaries max_iter=1")

plt.subplot(323)
plot_decision_boundaries(kmeans_iter1, X, show_centroids=False,
                         show_xlabels=False)
plot_centroids(kmeans_iter2.cluster_centers_)
plt.title("Update the centroids max_iter=2")

plt.subplot(324)
plot_decision_boundaries(kmeans_iter2, X, show_xlabels=False,
                         show_ylabels=False)
plt.title("Update decision boundaries max_iter=2")

plt.subplot(325)
plot_decision_boundaries(kmeans_iter2, X, show_centroids=False)
plot_centroids(kmeans_iter3.cluster_centers_)
plt.title("Update the centroids 3")

plt.subplot(326)
plot_decision_boundaries(kmeans_iter3, X, show_ylabels=False)
plt.title("Update decision boundaries max_iter=3")
plt.show()

Мы практически не видим изменений со второй по третью итерацию из-за небольшого стандарта данных. Одним из недостатков этого агоритма является его дисперсия, поскольку при разных случайных состояниях кластеры могут значительно отличаться друг от друга, что также может случиться с нашим очень простым случаем, когда кластеры имеют низкое стандартное значение. Следующий код отображает вышеупомянутое явление:

def plot_clusterer_comparison(clusterer1, clusterer2, X, title1=None,
                              title2=None):
    clusterer1.fit(X)
    clusterer2.fit(X)

    plt.figure(figsize=(10, 3.2))

    plt.subplot(121)
    plot_decision_boundaries(clusterer1, X)
    if title1:
        plt.title(title1)

    plt.subplot(122)
    plot_decision_boundaries(clusterer2, X, show_ylabels=False)
    if title2:
        plt.title(title2)

kmeans_rnd_init1 = KMeans(n_clusters=5, init="random", n_init=1, random_state=29)
kmeans_rnd_init2 = KMeans(n_clusters=5, init="random", n_init=1, random_state=45)

plot_clusterer_comparison(kmeans_rnd_init1, kmeans_rnd_init2, X,
                          "Solution 1",
                          "Solution 2 (with a different random init)")
plt.show()

На этом этапе мы должны обсудить метрику инерции, которая является критерием выбора лучшей модели. Для кластера C инерция определяется как:

где xi — образец, а xcbar — центр каждого кластера. Как мы легко видим, инерция — это сумма квадратного корня расстояния каждой новой точки до c-го центроида каждого кластера, и, как и ожидалось, общая инерция равна сумма инерций для каждого кластера:

Чем меньше инерция, тем меньше дисперсия (std) для каждого кластера, что означает, что у нас более сконцентрированы к центру капли. Мы также можем напечатать инерцию каждой модели с помощью следующего кода (мы ожидаем высокую инерцию третьего кластеризатор, поскольку диаграмма Вороного показала совершенно неправильные центроиды):

print(kmeans.inertia_)
print(kmeans_rnd_init1.inertia_)
print(kmeans_rnd_init2.inertia_)

Для завершения знаний вы также можете использовать AcceleratedKmeans(https://cs.baylor.edu/~hamerly/papers/sdm2016_rysavy_hamerly.pdf). До сих пор мы видим, что единственным обязательным условием модели является количество кластеров, но что происходит, когда мы не знаем?

Давайте визуализируем проблему:

kmeans_k3 = KMeans(n_clusters=3, random_state=42)
kmeans_k8 = KMeans(n_clusters=8, random_state=42)

plot_clusterer_comparison(kmeans_k3, kmeans_k8, X, "$k=3$", "$k=8$")
plt.show()

Распечатав инерцию двух новых кластеризаторов, мы видим, что по мере роста числа значений инерция становится все меньше и меньше до такой степени, что у нас есть N кластеров, а инерция равна 0, поскольку каждая точка данных сама является кластером!

Итак, чтобы решить эту проблему, мы можем построить график инерции для различных значений k кластеров с помощью кода ниже:

kmeans_per_k = [KMeans(n_clusters=k, random_state=42).fit(X)
                for k in range(1, 10)]
inertias = [model.inertia_ for model in kmeans_per_k]

plt.figure(figsize=(8, 3.5))
plt.plot(range(1, 10), inertias, "bo-")
plt.xlabel("$k$")
plt.ylabel("Inertia")
plt.annotate("", xy=(4, inertias[3]), xytext=(4.45, 650),
             arrowprops=dict(facecolor='black', shrink=0.1))
plt.text(4.5, 650, "Elbow", horizontalalignment="center")
plt.axis([1, 8.5, 0, 50000])
plt.grid()
plt.show()

Мы выбираем «колено» диаграммы, которое равно 4 (в нашем случае это не очень хорошо, хотя кластеризация хорошая), и оно показывает наименьшее количество кластеров, которые мы хотим иметь для хорошего выбора и реализации. После построения границ решения мы видим, что два кластера стали одним:

plot_decision_boundaries(kmeans_per_k[4 - 1], X)
plt.show()

Последняя характеристика, которую мы собираемся изучить, — это показатель силуэта, который для каждого образца определяется соотношением (b-a)/max(a,b), где a — среднее расстояние от других образцов в том же кластере, а b — среднее расстояние до ближайшего кластера. из следующего кластера. Диапазон от -1 до 1, где +1 означает, что выборка хорошо добавлена ​​в свой кластер и находится далеко от других кластеров, а -1 означает возможную ошибку при кластеризации этой выборки. Мы можем видеть оценку силуэта модели kmeans. :

0.7745565602350629

Более того, мы можем построить оценку силуэта для различного количества кластеров:

silhouette_scores = [silhouette_score(X, model.labels_)
                     for model in kmeans_per_k[1:]]

plt.figure(figsize=(8, 3))
plt.plot(range(2, 10), silhouette_scores, "bo-")
plt.xlabel("$k$")
plt.ylabel("Silhouette score")
plt.axis([1.8, 8.5, 0.2, 0.9])
plt.grid()
plt.show()

Это гораздо более интересный график, поскольку 5 — это пик, и мы видим, что диаграммы оценок инерции и силуэта могут не согласовываться для лучшего k, но этот график говорит, что 5 — это здорово, но хорошая кластеризация может быть достигнута с помощью 6 или даже 7 кластеров! Импортировав следующие библиотеки, мы можем получить более интерактивный график для выбора наилучшего количества кластеров:

from sklearn.metrics import silhouette_samples
from matplotlib.ticker import FixedLocator, FixedFormatter
plt.figure(figsize=(11, 9))

for k in (3, 4, 5, 6):
    plt.subplot(2, 2, k - 2)

    y_pred = kmeans_per_k[k - 1].labels_
    silhouette_coefficients = silhouette_samples(X, y_pred)

    padding = len(X) // 30
    pos = padding
    ticks = []
    for i in range(k):
        coeffs = silhouette_coefficients[y_pred == i]
        coeffs.sort()

        color = plt.cm.Spectral(i / k)
        plt.fill_betweenx(np.arange(pos, pos + len(coeffs)), 0, coeffs,
                          facecolor=color, edgecolor=color, alpha=0.7)
        ticks.append(pos + len(coeffs) // 2)
        pos += len(coeffs) + padding

    plt.gca().yaxis.set_major_locator(FixedLocator(ticks))
    plt.gca().yaxis.set_major_formatter(FixedFormatter(range(k)))
    if k in (3, 5):
        plt.ylabel("Cluster")

    if k in (5, 6):
        plt.gca().set_xticks([-0.1, 0, 0.2, 0.4, 0.6, 0.8, 1])
        plt.xlabel("Silhouette Coefficient")
    else:
        plt.tick_params(labelbottom=False)

    plt.axvline(x=silhouette_scores[k - 2], color="red", linestyle="--")
    plt.title(f"$k={k}$")
plt.show()

Интерпретация приведенного выше графика заключается в том, что лучший ответ — 5, поскольку все кластеры имеют одинаковый размер (приблизительно) и они прошли красную пунктирную линию, которая является средней оценкой силуэта.

Надеюсь, я объяснил основы алгоритма Kmeans и его реализацию. Не стесняйтесь делиться и комментировать свое мнение!

Сообщение от AI Mind

Спасибо, что являетесь частью нашего сообщества! Перед тем, как ты уйдешь: