Демонстрация предпосылок k-means

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

Функция 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-means состоит в минимизации евклидовых расстояний выборок до центра тяжести кластера, к которому они относятся. Вследствие этого k-means более подходит для кластеров, которые изотропны и нормально распределены (т.е. сферические гауссовы).
• Неравные дисперсии: k-means эквивалентен выбору оценщика максимального правдоподобия для «смеси» k гауссовых распределений с одинаковыми дисперсиями, но с, возможно, различными средними значениями.
• Неравномерно размещённые облака: нет теоретического результата о k-means, который утверждает, что он требует подобных размеров кластеров для хорошей работы, но минимизация евклидовых расстояний означает, что чем разреженнее и многомернее проблема, тем выше потребность в запуске алгоритма с различными начальными точками центра тяжести для обеспечения глобального минимального инерционного момента.

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-means.

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-means, здесь мы предлагаем вместо этого использовать 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-means может решить эту проблему и ускорить вычисления (см. пример Кластеризация текстовых документов с помощью k-means).

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

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

Download Jupyter notebook: plot_kmeans_assumptions.ipynb

Download Python source code: plot_kmeans_assumptions.py

Download zipped: plot_kmeans_assumptions.zip

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

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

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

Вывод перекрестно-валидированных предсказаний

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