Демонстрация допущений метода k-средних

Генерация данных

Функция make_blobs генерирует изотропные (сферические) гауссовы облака. Чтобы получить анизотропные (эллиптические) гауссовы облака, необходимо определить линейное transformation.

import numpy as np

from sklearn.datasets import make_blobs

n_samples = 1500
random_state = 170
transformation = [[0.60834549, -0.63667341], [-0.40887718, 0.85253229]]

X, y = make_blobs(n_samples=n_samples, random_state=random_state)
X_aniso = np.dot(X, transformation)  # Anisotropic blobs
X_varied, y_varied = make_blobs(
    n_samples=n_samples, cluster_std=[1.0, 2.5, 0.5], random_state=random_state
)  # Unequal variance
X_filtered = np.vstack(
    (X[y == 0][:500], X[y == 1][:100], X[y == 2][:10])
)  # Unevenly sized blobs
y_filtered = [0] * 500 + [1] * 100 + [2] * 10

Визуализируем полученные данные:

import matplotlib.pyplot as plt

fig, axs = plt.subplots(nrows=2, ncols=2, figsize=(12, 12))

axs[0, 0].scatter(X[:, 0], X[:, 1], c=y)
axs[0, 0].set_title("Mixture of Gaussian Blobs")

axs[0, 1].scatter(X_aniso[:, 0], X_aniso[:, 1], c=y)
axs[0, 1].set_title("Anisotropically Distributed Blobs")

axs[1, 0].scatter(X_varied[:, 0], X_varied[:, 1], c=y_varied)
axs[1, 0].set_title("Unequal Variance")

axs[1, 1].scatter(X_filtered[:, 0], X_filtered[:, 1], c=y_filtered)
axs[1, 1].set_title("Unevenly Sized Blobs")

plt.suptitle("Ground truth clusters").set_y(0.95)
plt.show()

Обучение моделей и визуализация результатов

Сгенерированные ранее данные используются, чтобы показать, как KMeans ведёт себя в следующих ситуациях:

• Неоптимальное число кластеров: в реальных условиях единственного однозначно определённого истинного числа кластеров не существует. Подходящее число кластеров следует определять на основе критериев, связанных с данными, и знаний о цели анализа.
• Анизотропно распределённые облака: метод k-средних минимизирует евклидовы расстояния от объектов выборки до центроида назначенного им кластера. Поэтому метод k-средних лучше подходит для изотропных и нормально распределённых кластеров (то есть сферических гауссовых распределений).
• Неодинаковая дисперсия: метод k-средних эквивалентен оценке максимального правдоподобия для «смеси» из k гауссовых распределений с одинаковыми дисперсиями, но, возможно, разными средними.
• Облака разного размера: теоретических результатов, утверждающих, что для эффективной работы метода k-средних размеры кластеров должны быть близкими, нет. Однако минимизация евклидовых расстояний означает, что чем более разрежена и многомерна задача, тем важнее запускать алгоритм с разными начальными центроидами, чтобы гарантировать достижение глобального минимума инерции.

from sklearn.cluster import KMeans

common_params = {
    "n_init": "auto",
    "random_state": random_state,
}

fig, axs = plt.subplots(nrows=2, ncols=2, figsize=(12, 12))

y_pred = KMeans(n_clusters=2, **common_params).fit_predict(X)
axs[0, 0].scatter(X[:, 0], X[:, 1], c=y_pred)
axs[0, 0].set_title("Non-optimal Number of Clusters")

y_pred = KMeans(n_clusters=3, **common_params).fit_predict(X_aniso)
axs[0, 1].scatter(X_aniso[:, 0], X_aniso[:, 1], c=y_pred)
axs[0, 1].set_title("Anisotropically Distributed Blobs")

y_pred = KMeans(n_clusters=3, **common_params).fit_predict(X_varied)
axs[1, 0].scatter(X_varied[:, 0], X_varied[:, 1], c=y_pred)
axs[1, 0].set_title("Unequal Variance")

y_pred = KMeans(n_clusters=3, **common_params).fit_predict(X_filtered)
axs[1, 1].scatter(X_filtered[:, 0], X_filtered[:, 1], c=y_pred)
axs[1, 1].set_title("Unevenly Sized Blobs")

plt.suptitle("Unexpected KMeans clusters").set_y(0.95)
plt.show()

Возможные решения

Пример того, как определить правильное число облаков, см. в разделе Выбор числа кластеров с помощью анализа силуэта при кластеризации методом KMeans. В этом случае достаточно задать n_clusters=3.

y_pred = KMeans(n_clusters=3, **common_params).fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.title("Optimal Number of Clusters")
plt.show()

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

y_pred = KMeans(n_clusters=3, n_init=10, random_state=random_state).fit_predict(
    X_filtered
)
plt.scatter(X_filtered[:, 0], X_filtered[:, 1], c=y_pred)
plt.title("Unevenly Sized Blobs \nwith several initializations")
plt.show()

Поскольку анизотропия и неодинаковые дисперсии являются реальными ограничениями алгоритма k-средних, вместо него мы предлагаем использовать GaussianMixture. Этот алгоритм также предполагает наличие гауссовых кластеров, но не накладывает ограничений на их дисперсии. Обратите внимание, что правильное число облаков всё равно необходимо определить (см. раздел Выбор модели гауссовой смеси).

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

from sklearn.mixture import GaussianMixture

fig, (ax1, ax2) = plt.subplots(nrows=1, ncols=2, figsize=(12, 6))

y_pred = GaussianMixture(n_components=3).fit_predict(X_aniso)
ax1.scatter(X_aniso[:, 0], X_aniso[:, 1], c=y_pred)
ax1.set_title("Anisotropically Distributed Blobs")

y_pred = GaussianMixture(n_components=3).fit_predict(X_varied)
ax2.scatter(X_varied[:, 0], X_varied[:, 1], c=y_pred)
ax2.set_title("Unequal Variance")

plt.suptitle("Gaussian mixture clusters").set_y(0.95)
plt.show()

Заключительные замечания

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

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

Общее время выполнения скрипта: (0 минут 1.024 секунды)

Download Jupyter notebook: plot_kmeans_assumptions.ipynb

Download Python source code: plot_kmeans_assumptions.py

Download zipped: plot_kmeans_assumptions.zip

Связанные примеры

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

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

Визуализация предсказаний при кросс-валидации

Демонстрация кластеризации методом K-средних на наборе рукописных цифр