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

"Машинное обучение"

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

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

В этой статье вы получите представление о

Что такое кластеризация K-средних?
Как работают К-средние?
Приложения кластеризации K-средних
Реализация кластеризации K-средних в Python
Поиск оптимальных кластеров с использованием метода локтя, оценки силуэта и статистики зазоров

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

Алгоритм K-средних нацелен на создание сплоченных кластеров на основе определенного количества кластеров K. Он создает сплоченные компактные кластеры, минимизируя общее внутрикластерное изменение, называемое внутрикластерным сумма квадратов (WCSS).

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

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

Кластеризация K-средних может использовать любую из следующих мер расстояния

Евклидово расстояние
Манхэттенское расстояние
Квадрат евклидова расстояния
Косинусное расстояние

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

Метод K-средних итеративно находит лучшие центроиды для кластера, чередуя их

Назначение точек данных кластерам на основе их близости к текущим центроидам и
Повторное вычисление центроидов на основе текущего назначения точек данных кластерам.

Алгоритм K-средних останавливает уточнение кластера, когда

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

Алгоритм K-средних используется для

Обнаружение аномалий, таких как обнаружение мошенничества
Сегментация, такая как сегментация клиентов, сегментация изображений
Интеллектуальный анализ данных

Внедрение K-средних

Набор данных клиентов торгового центра

Прочтите файл CSV во фрейме данных, преобразуйте категориальную переменную в числовой тип данных, а затем уменьшите размер с помощью PCA (анализ главных компонентов)

# Import the required libraries
import numpy as np 
import pandas as pd 
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn.cluster import KMeans
from sklearn.preprocessing import LabelBinarizer
from sklearn.decomposition import PCA
# Read he dataset into a dataframe
dataset = pd.read_csv('Mall_Customers.csv',index_col='CustomerID')
# Drop duplicates
dataset.drop_duplicates(inplace=True)
# Converting categorical column Genre to onehot vector
label_binarizer = LabelBinarizer()
  
#use LabelBinarizer for gender
label_binarizer_output = label_binarizer.fit_transform( dataset['Genre'])
#Adding the categorical and the main dataframe into one dataframe
result_df = pd.DataFrame(label_binarizer_output, columns=['Gender_1'])
dataset_1= pd.concat([dataset, result_df], axis=1, join='inner')
# Creating the input variable
X= dataset_1.iloc[:, [1,2,3,4]].values
# reducing the input dimension using PCA
reduced_data = PCA(n_components=2).fit_transform(X)

Когда мы запускаем KMeans, нам необходимо предоставить n_clusters, которые представляют собой оптимальное количество кластеров, которые необходимо сформировать, и количество центроидов, которые необходимо сгенерировать для набора данных.

kmeans = KMeans(init="k-means++", n_clusters=5, n_init=4)
kmeans.fit(X)

Как лучше всего найти оптимальные кластеры?

Существует 3 популярных метода поиска оптимального кластера для алгоритма кластеризации KMeans.

Метод локтя

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

Постройте WCSS вместе с количеством кластеров K. Выберите значение K на графике, где WCSS начинает сглаживаться или внезапно падает, а добавление еще одного кластера не приводит к значительному улучшению, образуя изгиб. Изгиб считается индикатором оптимального кластера для набора данных.

# Using the elbow method to find the optimal number of clusters
max_k=11 # max no. of clusters to be evaluated
wcss = []
for i in range(1, max_k):
    kmeans = KMeans(n_clusters = i, init = 'k-means++', random_state = 42)
    kmeans.fit(reduced_data)
    # inertia method returns wcss for that model
    wcss.append(kmeans.inertia_)
#plotting the data 
plt.figure(figsize=(5,3))
sns.lineplot(range(1, max_k), wcss,marker='o',color='red')
plt.title('The Elbow Method')
plt.xlabel('Number of clusters')
plt.ylabel('WCSS')
plt.show()

Оценка силуэта

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

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

Если значение показателя силуэта для всех точек данных значительно велико, это дает оптимальное значение для кластеров. Оценка силуэта использует расстояние Минковского или евклидово расстояние, и его значение находится в диапазоне [-1, 1].

Приведенный ниже код адаптирован из https://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_sil Silhouette_analysis.html#.

Код модифицирован для использования сокращенного измерения данных с помощью PCA.

from sklearn.metrics import silhouette_samples, silhouette_score
import matplotlib.cm as cm
for n_clusters in range(2, max_k):
    # 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(reduced_data) + (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(reduced_data)
# 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(reduced_data, 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(reduced_data, 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(reduced_data[:, 0], reduced_data[:, 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()

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

И метод локтя, и оценка по силуэту дают оптимальные кластеры 5

Запуск KMeans с оптимальным кластером, равным 5, а затем построение диаграммы рассеяния с использованием оптимальных кластеров по уменьшенным_data для визуализации кластера

# Fitting K-Means to the dataset
kmeans = KMeans(n_clusters = 5, init = 'k-means++', random_state = 42)
y_kmeans = kmeans.fit_predict(reduced_data)
#Visualising the clusters
plt.figure(figsize=(15,7))
sns.scatterplot(reduced_data[y_kmeans == 0, 0], reduced_data[y_kmeans == 0, 1], color = 'yellow', label = 'Cluster 1',s=50)
sns.scatterplot(reduced_data[y_kmeans == 1, 0], reduced_data[y_kmeans == 1, 1], color = 'blue', label = 'Cluster 2',s=50)
sns.scatterplot(reduced_data[y_kmeans == 2, 0], reduced_data[y_kmeans == 2, 1], color = 'green', label = 'Cluster 3',s=50)
sns.scatterplot(reduced_data[y_kmeans == 3, 0], reduced_data[y_kmeans == 3, 1], color = 'grey', label = 'Cluster 4',s=50)
sns.scatterplot(reduced_data[y_kmeans == 4, 0], reduced_data[y_kmeans == 4, 1], color = 'orange', label = 'Cluster 5',s=50)
sns.scatterplot(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], color = 'red', 
                label = 'Centroids',s=300,marker=',')
plt.grid(False)
plt.title('Clusters of customers')
plt.xlabel('PC-1')
plt.ylabel('PC-2')
plt.legend()
plt.show()

Статистика разрывов

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

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

Статистика разрыва - это разница между E ₙ, который представляет собой ожидание данных с нулевой ссылкой, вычисленное как логарифм общей внутрикластерной вариации и итоговой внутрикластерной вариации для набора данных

Приведенный ниже код вдохновлен и адаптирован из https://glowingpython.blogspot.com/2019/01/a-visual-introduction-to-gap-statistics.html

Набор данных с нулевой ссылкой - это равномерно распределенный набор точек.

from sklearn.datasets import make_blobs
from sklearn.metrics import pairwise_distances
# creating a uniform distributed null refernced dataset
reference = np.random.rand(100, 2)
plt.figure(figsize=(12, 3))
for k in range(1,6):
    kmeans = KMeans(n_clusters=k)
    a = kmeans.fit_predict(reference)
    plt.subplot(1,5,k)
    plt.scatter(reference[:, 0], reference[:, 1], c=a)
    plt.xlabel('k='+str(k))
plt.tight_layout()
plt.show()

Поскольку точки распределены равномерно, алгоритм KMeans равномерно разбивает точки на K кластеров, даже если между ними нет разделения.

def compute_inertia(a, X):
    W = [np.mean(pairwise_distances(X[a == c, :])) for c in np.unique(a)]
    return np.mean(W)
def compute_gap(clustering, data, k_max=5, n_references=5):
    if len(data.shape) == 1:
        data = data.reshape(-1, 1)
    # The Null Reference dataset that is uniformly distributed
    reference = np.random.rand(*data.shape)
    reference_inertia = []
    
    # Calculate the WCSS for the null refrenced data
    for k in range(1, k_max+1):
        local_inertia = []
        for _ in range(n_references):
            clustering.n_clusters = k
            assignments = clustering.fit_predict(reference)
            local_inertia.append(compute_inertia(assignments, reference))
        reference_inertia.append(np.mean(local_inertia))
    
    # Calculate the WCSS for the data
    ondata_inertia = []
    for k in range(1, k_max+1):
        clustering.n_clusters = k
        assignments = clustering.fit_predict(data)
        ondata_inertia.append(compute_inertia(assignments, data))
        
    # Calculate the gao statistics between the WCSS for the null referenced data and the WCSS for the data
    gap = np.log(reference_inertia)-np.log(ondata_inertia)
    return gap, np.log(reference_inertia), np.log(ondata_inertia)

gap, reference_inertia, ondata_inertia = compute_gap(KMeans(), reduced_data, k_max)
plt.plot(range(1, k_max+1), gap, '-o')
plt.ylabel('gap')
plt.xlabel('k')

Статистика разрывов дает оптимальное количество кластеров, равное 10, на основе максимального разрыва между инерцией кластера данных и данными с нулевой ссылкой.

Запуск KMeans для 10 кластеров, а затем визуализация кластеров на диаграмме рассеяния.

# Visualising the clusters
plt.figure(figsize=(15,7))
sns.scatterplot(reduced_data[y_kmeans == 0, 0], reduced_data[y_kmeans == 0, 1], color = 'yellow', label = 'Cluster 1',s=50)
sns.scatterplot(reduced_data[y_kmeans == 1, 0], reduced_data[y_kmeans == 1, 1], color = 'blue', label = 'Cluster 2',s=50)
sns.scatterplot(reduced_data[y_kmeans == 2, 0], reduced_data[y_kmeans == 2, 1], color = 'green', label = 'Cluster 3',s=50)
sns.scatterplot(reduced_data[y_kmeans == 3, 0], reduced_data[y_kmeans == 3, 1], color = 'grey', label = 'Cluster 4',s=50)
sns.scatterplot(reduced_data[y_kmeans == 4, 0], reduced_data[y_kmeans == 4, 1], color = 'orange', label = 'Cluster 5',s=50)
sns.scatterplot(reduced_data[y_kmeans == 5, 0], reduced_data[y_kmeans == 5, 1], color = 'pink', label = 'Cluster 6',s=50)
sns.scatterplot(reduced_data[y_kmeans == 6, 0], reduced_data[y_kmeans == 6, 1], color = 'magenta', label = 'Cluster 7',s=50)
sns.scatterplot(reduced_data[y_kmeans == 7, 0], reduced_data[y_kmeans == 7, 1], color = 'cyan', label = 'Cluster 8',s=50)
sns.scatterplot(reduced_data[y_kmeans == 8, 0], reduced_data[y_kmeans == 8, 1], color = 'purple', label = 'Cluster 9',s=50)
sns.scatterplot(reduced_data[y_kmeans == 9, 0], reduced_data[y_kmeans == 9, 1], color = 'brown', label = 'Cluster 10',s=50)
sns.scatterplot(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], color = 'red', 
                label = 'Centroids',s=300,marker=',')
plt.grid(False)
plt.title('Clusters of customers')
plt.xlabel('PC-1')
plt.ylabel('PC-2')
plt.legend()
plt.show()

Вывод:

Кластеризация K-средних - это

Алгоритм машинного обучения без учителя
Итерационный алгоритм для поиска групп данных со схожими характеристиками для немаркированного набора данных

Популярные методы определения оптимальных кластеров

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