Задача кластеризации

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

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

Формальная постановка задачи

Дано: множество объектов X = {x₁, x₂, ..., xₙ}, где xᵢ ∈ ℝᵈ. Требуется: разбить объекты на K кластеров C₁, C₂, ..., Cₖ, минимизировав суммарную внутрикластерную дисперсию (WCSS — within-cluster sum of squares):

min WCSS = Σₖ Σ_{xᵢ ∈ Cₖ} ‖xᵢ - μₖ‖²

где μₖ = (1/|Cₖ|) · Σ_{xᵢ ∈ Cₖ} xᵢ  — центроид кластера k

Эта задача NP-сложна в общем случае. K-means находит приближённое решение через итерационный эвристический алгоритм.

Алгоритм K-means: шаг за шагом

Вход: данные X, число кластеров K
Выход: метки кластеров {c₁,...,cₙ} и центроиды {μ₁,...,μₖ}

1. ИНИЦИАЛИЗАЦИЯ: выбрать K начальных центроидов μ₁,...,μₖ
   (случайно или алгоритмом K-means++)

2. ШАГ E (назначение):
   для каждого xᵢ найти ближайший центроид:
   cᵢ = argmin_k ‖xᵢ - μₖ‖²

3. ШАГ M (обновление центроидов):
   пересчитать μₖ как среднее всех точек в кластере k:
   μₖ = (1/|Cₖ|) · Σ_{xᵢ: cᵢ=k} xᵢ

4. Если центроиды изменились — вернуться к шагу 2
   Если центроиды не изменились — ОСТАНОВКА
EM-интерпретация: K-means — частный случай EM-алгоритма для гауссовой смеси с одинаковыми сферическими ковариационными матрицами (σ²I). Шаг E — мягкое назначение, шаг M — максимизация. K-means использует «жёсткое» назначение.

Проблема инициализации и K-means++

Стандартная случайная инициализация имеет серьёзный недостаток: если центроиды инициализируются близко друг к другу, алгоритм сходится к плохому локальному минимуму WCSS.

Алгоритм K-means++ (Arthur & Vassilvitskii, 2007) решает эту проблему через взвешенную вероятностную инициализацию:

K-means++ инициализация:

1. Выбрать первый центроид μ₁ случайно из X

2. Для k = 2, ..., K:
   - Для каждой точки xᵢ вычислить D(xᵢ) = min_{j

Теоретически доказано, что K-means++ даёт решение не хуже O(log K) от оптимального. На практике он значительно устойчивее и сходится быстрее.

Реализация на Python

import numpy as np
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt

# Синтетические данные: 4 кластера в 2D
X, y_true = make_blobs(n_samples=400, centers=4,
                        cluster_std=0.9, random_state=42)

# Нормализация (важно для K-means!)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Обучение K-means++ (init='k-means++' по умолчанию)
kmeans = KMeans(
    n_clusters=4,
    init='k-means++',
    n_init=10,         # 10 запусков, берём лучший
    max_iter=300,
    random_state=42
)
kmeans.fit(X_scaled)

labels     = kmeans.labels_            # метки кластеров
centroids  = kmeans.cluster_centers_   # центроиды
wcss       = kmeans.inertia_           # WCSS

print(f"WCSS: {wcss:.2f}")
print(f"Итераций до сходимости: {kmeans.n_iter_}")

Как выбрать число кластеров K?

Это главный практический вопрос при работе с K-means. Единого «правильного» ответа нет — нужно использовать несколько методов совместно.

Метод локтя (Elbow Method)

wcss_values = []
K_range = range(1, 12)

for k in K_range:
    km = KMeans(n_clusters=k, init='k-means++',
                n_init=10, random_state=42)
    km.fit(X_scaled)
    wcss_values.append(km.inertia_)

# График: ищем точку перегиба ("локоть")
plt.figure(figsize=(8, 4))
plt.plot(K_range, wcss_values, 'o-', color='teal', linewidth=2)
plt.xlabel("Число кластеров K")
plt.ylabel("WCSS (inertia)")
plt.title("Метод локтя для выбора K")
plt.grid(alpha=0.3)
plt.show()

# Автоматический поиск точки перегиба через вторую производную
deltas = np.diff(wcss_values, 2)
best_k = np.argmin(deltas) + 2  # смещение из-за diff
print(f"Оптимальный K по методу локтя: {best_k}")

Силуэтный коэффициент

Силуэт измеряет, насколько хорошо каждый объект соответствует своему кластеру по сравнению с соседними. Значение от -1 до +1; близкое к +1 — объект в правильном кластере, близкое к 0 — на границе, отрицательное — вероятно, в неправильном.

from sklearn.metrics import silhouette_score, silhouette_samples

# Средний силуэт по всем объектам
sil_scores = []
for k in range(2, 12):  # Минимум 2 кластера
    km = KMeans(n_clusters=k, init='k-means++',
                n_init=10, random_state=42)
    labels_k = km.fit_predict(X_scaled)
    sil = silhouette_score(X_scaled, labels_k)
    sil_scores.append(sil)
    print(f"K={k:2d}  силуэт={sil:.4f}")

best_k_sil = np.argmax(sil_scores) + 2
print(f"\nОптимальный K по силуэту: {best_k_sil}")

Ограничения K-means

ОГРАНИЧЕНИЯ
  • Требует задать K заранее
  • Предполагает сферические кластеры
  • Чувствителен к выбросам
  • Сходится к локальному минимуму
  • Не работает с кластерами разной плотности
АЛЬТЕРНАТИВЫ
  • DBSCAN — произвольная форма кластеров
  • Gaussian Mixture Models — мягкое назначение
  • Hierarchical clustering — дендрограмма
  • Mean-shift — автоматический выбор K
  • HDBSCAN — с шумовыми точками

Практический пример: сегментация клиентов

import pandas as pd

# Синтетические данные клиентов (RFM-анализ)
np.random.seed(42)
n = 500
data = pd.DataFrame({
    'recency':    np.random.exponential(30, n),   # дней с покупки
    'frequency':  np.random.poisson(5, n) + 1,    # кол-во покупок
    'monetary':   np.random.lognormal(5, 1, n)    # сумма покупок
})

X_rfm = scaler.fit_transform(data)

kmeans_rfm = KMeans(n_clusters=4, init='k-means++',
                    n_init=20, random_state=42)
data['segment'] = kmeans_rfm.fit_predict(X_rfm)

# Характеристика сегментов
segment_profile = data.groupby('segment').mean().round(1)
print(segment_profile)
Важно: всегда нормализуйте признаки перед K-means. Признак с большим масштабом (например, сумма покупок в долларах) будет доминировать в евклидовом расстоянии, и алгоритм фактически будет кластеризовать только по нему.

Итог урока

K-means — элегантный итерационный алгоритм, минимизирующий внутрикластерную дисперсию. Ключевые практические аспекты: нормализация признаков, использование K-means++ вместо случайной инициализации, несколько запусков (n_init), и совместное использование метода локтя и силуэтного коэффициента для выбора K. Понимание ограничений алгоритма — основа выбора между K-means и другими методами кластеризации.