Кластеризация K-средних: как это работает и поиск оптимального количества кластеров в данных

Математическая формулировка, Нахождение оптимального количества кластеров и рабочий пример на Python

Вступление

K-means - один из наиболее широко используемых методов неконтролируемой кластеризации.

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

Алгоритм k-средних делит набор N выборок (хранящихся в матрице данных X) на K непересекающихся кластеров C , каждый из которых описывается средним значением μj образцов в кластере. Средние значения обычно называют кластером «центроиды».

Алгоритм K-средних относится к семейству алгоритмов / методов неконтролируемого машинного обучения. Для этого семейства моделей исследование должно иметь под рукой набор данных с некоторыми наблюдениями, без необходимости иметь также метки / классы для наблюдения. Неконтролируемое обучение изучает, как системы могут вывести функцию для описания скрытой структуры из немаркированных данных.

Теперь давайте откроем математические основы алгоритма.

Математическая формулировка

Дан набор наблюдений (x 1, x 2,…, x n), где каждое наблюдение d -мерный действительный вектор, k -значит, что кластеризация направлена на разделение n наблюдений на k (≤ n) устанавливает S = {S 1, S 2,…, Sk}. так, чтобы минимизировать внутрикластерную сумму квадратов (WCSS) (т.е. дисперсию). Формально цель определяется следующим образом:

где μ i - среднее значение точек в группе / кластере Si.

Понимание алгоритма, лежащего в основе

Алгоритм также можно понять через концепцию диаграмм Вороного.

Сначала рассчитывается диаграмма Вороного точек с использованием текущих центроидов. Первоначально центроиды обычно выбираются случайным образом, но это зависит от используемого пакета / библиотеки / программного обеспечения.

Каждый сегмент на диаграмме Вороного становится отдельным кластером.

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

Алгоритм останавливается, когда относительное уменьшение значения целевой функции между итерациями становится меньше. чем заданное значение допуска (ε) или когда центроиды перемещаются (в пространстве) меньше , чем допуск.

Нахождение оптимального количества кластеров

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

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

Более высокий показатель коэффициента силуэта относится к модели с лучше определенными кластерами. Коэффициент силуэта определяется для каждого образца и состоит из двух баллов:

a: среднее расстояние между образцом и всеми другими точками того же класса.
b: среднее расстояние между образцом и всеми другими точками в следующем ближайшем кластере.

Затем коэффициент силуэта s для одного образца определяется как:

Наконец, общий коэффициент силуэта для набора образцов дается как среднее значение коэффициента силуэта для каждого образца.

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

Рабочий пример Python

В этом примере мы создадим искусственные данные, то есть искусственные кластеры. Таким образом мы заранее узнаем основание до, т. Е. точное количество кластеров в нашем наборе данных.

Начнем с импорта необходимых библиотек Python:

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_samples, silhouette_score
import matplotlib.pyplot as plt
import matplotlib.cm as cm
import numpy as np

Затем давайте создадим искусственные данные, содержащие 500 образцов, 2 функции / переменные и K = 4 кластера.

# Generating the data
# This particular setting has one distinct cluster and 3 clusters placed close together.
X, y = make_blobs(n_samples=500,
                  n_features=2,
                  centers=4,
                  cluster_std=1,
                  center_box=(-10.0, 10.0),
                  shuffle=True,
                  random_state=1)

Мы знаем, что у нас есть K = 4 кластера в данных, однако, чтобы понять, как работает Silhouette Score, мы подгоним модель, используя диапазон разного количества кластеров.

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

range_n_clusters = [3, 4, 5]
for n_clusters in range_n_clusters:
    # Create a subplot with 1 row and 2 columns
    fig, (ax1, ax2) = plt.subplots(1, 2)
    fig.set_size_inches(18, 7)
    # The 1st subplot is the silhouette plot
    # The silhouette coefficient can range from -1, 1 but in this example all
    # lie within [-0.1, 1]
    ax1.set_xlim([-0.1, 1])
    # The (n_clusters+1)*10 is for inserting blank space between silhouette
    # plots of individual clusters, to demarcate them clearly.
    ax1.set_ylim([0, len(X) + (n_clusters + 1) * 10])
    # Initialize the clusterer with n_clusters value and a random generator
    # seed of 10 for reproducibility.
    clusterer = KMeans(n_clusters=n_clusters, random_state=10)
    cluster_labels = clusterer.fit_predict(X)
    # The silhouette_score gives the average value for all the samples.
    # This gives a perspective into the density and separation of the formed
    # clusters
    silhouette_avg = silhouette_score(X, cluster_labels)
    print("For n_clusters =", n_clusters,
          "The average silhouette_score is :", silhouette_avg)
    # Compute the silhouette scores for each sample
    sample_silhouette_values = silhouette_samples(X, cluster_labels)
    y_lower = 10
    for i in range(n_clusters):
        # Aggregate the silhouette scores for samples belonging to
        # cluster i, and sort them
        ith_cluster_silhouette_values = \
            sample_silhouette_values[cluster_labels == i]
        ith_cluster_silhouette_values.sort()
        size_cluster_i = ith_cluster_silhouette_values.shape[0]
        y_upper = y_lower + size_cluster_i
        color = cm.nipy_spectral(float(i) / n_clusters)
        ax1.fill_betweenx(np.arange(y_lower, y_upper),
                          0, ith_cluster_silhouette_values,
                          facecolor=color, edgecolor=color, alpha=0.7)
        # Label the silhouette plots with their cluster numbers at the middle
        ax1.text(-0.05, y_lower + 0.5 * size_cluster_i, str(i))
        # Compute the new y_lower for next plot
        y_lower = y_upper + 10  # 10 for the 0 samples
    ax1.set_title("The silhouette plot for the various clusters.")
    ax1.set_xlabel("The silhouette coefficient values")
    ax1.set_ylabel("Cluster label")
    # The vertical line for average silhouette score of all the values
    ax1.axvline(x=silhouette_avg, color="red", linestyle="--")
    ax1.set_yticks([])  # Clear the yaxis labels / ticks
    ax1.set_xticks([-0.1, 0, 0.2, 0.4, 0.6, 0.8, 1])
    # 2nd Plot showing the actual clusters formed
    colors = cm.nipy_spectral(cluster_labels.astype(float) / n_clusters)
    ax2.scatter(X[:, 0], X[:, 1], marker='.', s=30, lw=0, alpha=0.7,
                c=colors, edgecolor='k')
    # Labeling the clusters
    centers = clusterer.cluster_centers_
    # Draw white circles at cluster centers
    ax2.scatter(centers[:, 0], centers[:, 1], marker='o',
                c="white", alpha=1, s=200, edgecolor='k')
    for i, c in enumerate(centers):
        ax2.scatter(c[0], c[1], marker='$%d$' % i, alpha=1,
                    s=50, edgecolor='k')
    ax2.set_title("The visualization of the clustered data.")
    ax2.set_xlabel("Feature space for the 1st feature")
    ax2.set_ylabel("Feature space for the 2nd feature")
    plt.suptitle(("Silhouette analysis for KMeans clustering on sample data "
                  "with n_clusters = %d" % n_clusters),
                 fontsize=14, fontweight='bold')
plt.show()

Мы наблюдаем, что средний / средний балл по силуэту является самым высоким в случае K = 4 кластеров.

Это подтверждает, что показатель силуэта является хорошим показателем степени соответствия K-средних.

Мы также изготовили эти фигурки:

Вертикальная линия - это средняя оценка силуэта для всех значений.

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

Выводы

K-средних - один из наиболее широко используемых методов неконтролируемой кластеризации. Алгоритм группирует данные под рукой, пытаясь разделить выборки на K групп с равной дисперсией, минимизируя критерий, известный как инерция или сумма квадратов внутри кластера. Этот алгоритм требует указания количества кластеров.

Однако, если наземные метки достоверности неизвестны, оценка должна выполняться с использованием самой модели.

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

Это все! Надеюсь, вам понравилась эта новая статья - скоро будут другие!