В каких случаях k-means не справляется с разделением на кластеры

Когда K-Means не справляется с кластеризацией

K-Means — это популярный алгоритм, но у него есть серьёзные ограничения. Расскажу о ситуациях, где он дает плохие результаты, и как их решить.

1. Кластеры неправильной формы

K-Means предполагает, что кластеры сферические и примерно одинакового размера.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans, DBSCAN
from sklearn.datasets import make_moons, make_circles

# Полукруги (K-Means не справится)
X, y = make_moons(n_samples=300, noise=0.05)

kmeans = KMeans(n_clusters=2, random_state=42)
pred_kmeans = kmeans.fit_predict(X)

dbscan = DBSCAN(eps=0.15, min_samples=5)
pred_dbscan = dbscan.fit_predict(X)

fig, axes = plt.subplots(1, 2, figsize=(12, 5))

axes[0].scatter(X[:, 0], X[:, 1], c=pred_kmeans, cmap='viridis')
axes[0].set_title('K-Means (плохо)')

axes[1].scatter(X[:, 0], X[:, 1], c=pred_dbscan, cmap='viridis')
axes[1].set_title('DBSCAN (хорошо)')

plt.show()

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

Решение: Используйте DBSCAN, Hierarchical Clustering или Spectral Clustering.

2. Кластеры разного размера

# Большой кластер и маленький кластер
np.random.seed(42)
X1 = np.random.normal(0, 0.3, (300, 2))      # Плотный большой
X2 = np.random.normal(5, 0.5, (30, 2))       # Редкий маленький
X = np.vstack([X1, X2])

kmeans = KMeans(n_clusters=2, random_state=42)
pred = kmeans.fit_predict(X)

fig, ax = plt.subplots(figsize=(8, 6))
ax.scatter(X[:, 0], X[:, 1], c=pred, cmap='viridis')
ax.scatter(kmeans.cluster_centers_[:, 0], 
           kmeans.cluster_centers_[:, 1], 
           marker='X', s=300, c='red')
ax.set_title('K-Means с кластерами разного размера (неправильно)')
plt.show()

Проблема: K-Means может разделить большой кластер, чтобы приблизить центроиды к малому кластеру.

Решение:

• DBSCAN с параметром eps, которые находят разные плотности
• Hierarchical Clustering
• Gaussian Mixture Models (GMM)

3. Высокая размерность (Curse of Dimensionality)

from sklearn.datasets import make_blobs
from sklearn.decomposition import PCA

# Данные в высокой размерности
X_high, y_true = make_blobs(n_samples=300, centers=3, 
                             n_features=50, random_state=42)

# K-Means в высокой размерности
kmeans = KMeans(n_clusters=3, random_state=42)
pred = kmeans.fit_predict(X_high)

# Проверяем качество через PCA визуализацию
pca = PCA(n_components=2)
X_pca = pca.fit_transform(X_high)

fig, axes = plt.subplots(1, 2, figsize=(12, 5))
axes[0].scatter(X_pca[:, 0], X_pca[:, 1], c=y_true, cmap='viridis', alpha=0.6)
axes[0].set_title('True labels')

axes[1].scatter(X_pca[:, 0], X_pca[:, 1], c=pred, cmap='viridis', alpha=0.6)
axes[1].set_title('K-Means predictions (часто неправильно)')
plt.show()

Проблема: В высоких размерностях все точки далеко от друг друга (проклятие размерности). K-Means становится неэффективным.

Решение:

• Снижение размерности (PCA, t-SNE, UMAP)
• Feature selection
• t-SNE кластеризация

4. Выбросы (Outliers)

X, y = make_blobs(n_samples=300, centers=3, random_state=42)

# Добавляем выбросы
outliers = np.random.uniform(-10, 10, (20, 2))
X = np.vstack([X, outliers])

kmeans = KMeans(n_clusters=3, random_state=42)
pred = kmeans.fit_predict(X)

fig, ax = plt.subplots(figsize=(8, 6))
ax.scatter(X[:-20, 0], X[:-20, 1], c=pred[:-20], cmap='viridis', label='Normal')
ax.scatter(X[-20:, 0], X[-20:, 1], c='red', marker='X', s=100, label='Outliers')
ax.scatter(kmeans.cluster_centers_[:, 0], 
           kmeans.cluster_centers_[:, 1], 
           marker='*', s=500, c='black')
ax.set_title('K-Means чувствителен к выбросам')
ax.legend()
plt.show()

Проблема: K-Means минимизирует сумму квадратов расстояний. Выброс может сильно сдвинуть центроид.

Решение:

• Очистка данных (удаление выбросов)
• K-Medoids (использует медиану вместо средней)
• Robust Clustering методы
• DBSCAN (помечает выбросы как noise)

5. Проблема выбора k

from sklearn.metrics import silhouette_score

X, y = make_blobs(n_samples=300, centers=3, random_state=42)

inertias = []
silhouette_scores = []
K_range = range(1, 11)

for k in K_range:
    kmeans = KMeans(n_clusters=k, random_state=42, n_init=10)
    pred = kmeans.fit_predict(X)
    inertias.append(kmeans.inertia_)
    silhouette_scores.append(silhouette_score(X, pred))

fig, axes = plt.subplots(1, 2, figsize=(12, 5))

# Elbow method
axes[0].plot(K_range, inertias, 'bo-')
axes[0].set_xlabel('k')
axes[0].set_ylabel('Inertia')
axes[0].set_title('Elbow Method')
axes[0].axvline(x=3, color='r', linestyle='--', label='Optimal k=3')
axes[0].legend()

# Silhouette score
axes[1].plot(K_range, silhouette_scores, 'go-')
axes[1].set_xlabel('k')
axes[1].set_ylabel('Silhouette Score')
axes[1].set_title('Silhouette Score Method')
axes[1].axvline(x=3, color='r', linestyle='--', label='Optimal k=3')
axes[1].legend()

plt.show()

Проблема: K-Means требует задать k заранее. Как выбрать правильное число?

Решение:

• Elbow Method — ищем излом на графике inertia
• Silhouette Score — метрика качества кластеризации
• Gap Statistic — сравнение с random данными
• Hierarchical Clustering — дендрограмма показывает естественное число кластеров

6. Локальные минимумы

from sklearn.cluster import KMeans

X, y = make_blobs(n_samples=100, centers=3, random_state=42)

# Разные инициализации могут дать разные результаты
fig, axes = plt.subplots(2, 2, figsize=(10, 10))

for idx, ax in enumerate(axes.flat):
    kmeans = KMeans(n_clusters=3, random_state=idx, n_init=1)  # n_init=1 — одна попытка
    pred = kmeans.fit_predict(X)
    
    ax.scatter(X[:, 0], X[:, 1], c=pred, cmap='viridis')
    ax.scatter(kmeans.cluster_centers_[:, 0], 
               kmeans.cluster_centers_[:, 1], 
               marker='X', s=300, c='red')
    ax.set_title(f'Seed {idx} (Inertia: {kmeans.inertia_:.2f})')

plt.tight_layout()
plt.show()

Проблема: K-Means может застрять в локальном минимуме.

Решение:

• Использовать n_init > 1 (default=10)
• K-Means++ инициализация
• Попробовать разные random states

7. Плотные и разреженные регионы

from sklearn.datasets import load_iris

# Данные с очень разной плотностью
X_dense = np.random.normal(0, 0.1, (200, 2))
X_sparse = np.random.normal([5, 5], 1.5, (50, 2))
X = np.vstack([X_dense, X_sparse])

kmeans = KMeans(n_clusters=2, random_state=42)
pred = kmeans.fit_predict(X)

fig, ax = plt.subplots(figsize=(8, 6))
ax.scatter(X[:, 0], X[:, 1], c=pred, cmap='viridis', s=50, alpha=0.6)
ax.scatter(kmeans.cluster_centers_[:, 0], 
           kmeans.cluster_centers_[:, 1], 
           marker='X', s=300, c='red')
ax.set_title('K-Means с разной плотностью кластеров')
plt.show()

Проблема: Алгоритм не учитывает локальную плотность.

Решение: DBSCAN, Gaussian Mixture Models.

Сравнение методов

from sklearn.cluster import AgglomerativeClustering
from sklearn.mixture import GaussianMixture

X, y = make_moons(n_samples=300, noise=0.05)

methods = {
    'K-Means': KMeans(n_clusters=2, random_state=42),
    'Hierarchical': AgglomerativeClustering(n_clusters=2),
    'DBSCAN': DBSCAN(eps=0.15, min_samples=5),
    'GMM': GaussianMixture(n_components=2, random_state=42)
}

fig, axes = plt.subplots(2, 2, figsize=(12, 10))

for idx, (name, model) in enumerate(methods.items()):
    ax = axes.flat[idx]
    
    if hasattr(model, 'fit_predict'):
        pred = model.fit_predict(X)
    else:
        pred = model.fit(X).predict(X)
    
    ax.scatter(X[:, 0], X[:, 1], c=pred, cmap='viridis')
    ax.set_title(name)

plt.tight_layout()
plt.show()

Заключение

K-Means работает хорошо только для:

• Примерно сферических кластеров
• Одинакового размера
• Известного числа кластеров k
• Низкой размерности
• Без выбросов

Альтернативы:

• DBSCAN — произвольные формы, разные размеры
• Hierarchical Clustering — дендрограмма, не нужно выбирать k
• Gaussian Mixture Models — вероятностный подход
• Spectral Clustering — для сложных форм
• t-SNE + K-Means — для высокой размерности