Алгоритм K-средних (K-Means)

Алгоритм K-средних (K-Means) — это один из самых популярных и простых алгоритмов кластеризации (обучение без учителя), который разделяет данные на K кластеров (групп) на основе их схожести.

Основная идея

Алгоритм находит K центров кластеров (центроидов) и распределяет точки данных между кластерами так, чтобы:

Внутри кластера точки были максимально похожи (минимальное расстояние до своего центроида)
Между кластерами точки были максимально различны (максимальное расстояние между центроидами)

Как работает алгоритм (шаги)

Шаг 0: Инициализация

Выбираем количество кластеров K (пользователь задаёт заранее)
Случайным образом выбираем K точек в качестве начальных центроидов

Шаг 1: Назначение кластеров (Assignment)

Для каждой точки данных:

Вычисляем расстояние до каждого центроида
Назначаем точку кластеру с ближайшим центроидом

Шаг 2: Перерасчет центроидов (Update)

Для каждого кластера:

Вычисляем среднее значение всех точек кластера
Перемещаем центроид в эту среднюю точку

Шаг 3: Проверка сходимости

Повторяем шаги 1-2 до тех пор, пока:

Центроиды перестанут значительно меняться (стабилизируются)
Назначения точек кластерам перестанут меняться
Достигнуто максимальное число итераций

Математическая формализация

Алгоритм минимизирует внутрикластерную дисперсию (within-cluster variance):

J = Σ Σ ||x_i - μ_j||²
   j=1 i∈C_j

где:

K — количество кластеров
C_j — множество точек в кластере j
μ_j — центроид кластера j
||x_i - μ_j|| — расстояние между точкой и центроидом

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

from sklearn.cluster import KMeans
import numpy as np
import matplotlib.pyplot as plt
 
# Пример данных
X = np.array([[1, 2], [1, 4], [1, 0],
              [10, 2], [10, 4], [10, 0]])
 
# Создание и обучение модели
kmeans = KMeans(
    n_clusters=2,          # K - количество кластеров
    init='k-means++',      # метод инициализации
    n_init=10,             # количество запусков с разной инициализацией
    max_iter=300,          # максимальное количество итераций
    random_state=42
)
 
# Обучение и предсказание
labels = kmeans.fit_predict(X)
centroids = kmeans.cluster_centers_
 
print("Метки кластеров:", labels)
print("Центроиды:\n", centroids)
print("Инерция (сумма квадратов расстояний):", kmeans.inertia_)

Выбор количества кластеров K

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

inertias = []
K_range = range(1, 11)
 
for k in K_range:
    kmeans = KMeans(n_clusters=k, random_state=42)
    kmeans.fit(X)
    inertias.append(kmeans.inertia_)
 
# Визуализация
plt.plot(K_range, inertias, 'bx-')
plt.xlabel('Количество кластеров K')
plt.ylabel('Инерция')
plt.title('Метод локтя для выбора K')
plt.show()

Силуэтный анализ (Silhouette Analysis)

from sklearn.metrics import silhouette_score
 
silhouette_scores = []
K_range = range(2, 11)
 
for k in K_range:
    kmeans = KMeans(n_clusters=k, random_state=42)
    labels = kmeans.fit_predict(X)
    score = silhouette_score(X, labels)
    silhouette_scores.append(score)
 
# Выбираем K с максимальным силуэтным коэффициентом
optimal_k = K_range[np.argmax(silhouette_scores)]

Инициализация центроидов

Методы:

Случайная инициализация (init='random'):
- Выбираем K случайных точек
- Проблема: может сходиться к локальному минимуму
K-means++ (init='k-means++', используется по умолчанию):
- Первый центроид выбирается случайно
- Каждый следующий выбирается с вероятностью, пропорциональной квадрату расстояния до ближайшего существующего центроида
- Гарантирует лучшую и более стабильную сходимость

Преимущества K-Means

Простота и скорость: Алгоритм легко реализуется и работает быстро
Масштабируемость: Эффективно обрабатывает большие наборы данных (O(n))
Гарантированная сходимость: Всегда сходится к некоторому решению
Универсальность: Применяется в различных областях
Интерпретируемость: Результаты легко понять и визуализировать

Недостатки и ограничения

Необходимость задавать K: Количество кластеров нужно знать заранее
Чувствительность к выбросам: Выбросы сильно влияют на положение центроидов
Чувствительность к инициализации: Разные начальные центроиды могут давать разные результаты
Предположение о сферических кластерах: Предполагает, что кластеры выпуклые и изотропные
Проблема с разномасштабными кластерами: Плохо работает, когда кластеры имеют разный размер или плотность

Вариации и улучшения

K-Medians

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

Mini-Batch K-Means

Использует случайные подвыборки (mini-batches) для ускорения работы на больших данных.

from sklearn.cluster import MiniBatchKMeans
mbk = MiniBatchKMeans(n_clusters=3, batch_size=100)

Fuzzy C-Means

Точка может принадлежать нескольким кластерам с разной степенью принадлежности.

Практические рекомендации

Подготовка данных:

# 1. Масштабирование признаков (обязательно!)
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
 
# 2. Обработка выбросов
from sklearn.preprocessing import RobustScaler
# или удаление выбросов перед кластеризацией

Выбор метрики расстояния:

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

Пример полного пайплайна

import pandas as pd
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.decomposition import PCA
import matplotlib.pyplot as plt
 
# 1. Загрузка данных
data = pd.read_csv('data.csv')
 
# 2. Предобработка и масштабирование
scaler = StandardScaler()
scaled_data = scaler.fit_transform(data)
 
# 3. Выбор оптимального K
inertias = []
K_range = range(1, 11)
for k in K_range:
    kmeans = KMeans(n_clusters=k, random_state=42)
    kmeans.fit(scaled_data)
    inertias.append(kmeans.inertia_)
 
# 4. Обучение модели с оптимальным K
optimal_k = 3  # определено из метода локтя
kmeans = KMeans(n_clusters=optimal_k, random_state=42)
clusters = kmeans.fit_predict(scaled_data)
 
# 5. Визуализация (используем PCA для 2D)
pca = PCA(n_components=2)
reduced_data = pca.fit_transform(scaled_data)
 
plt.scatter(reduced_data[:, 0], reduced_data[:, 1], 
            c=clusters, cmap='viridis', alpha=0.6)
plt.scatter(kmeans.cluster_centers_[:, 0], 
            kmeans.cluster_centers_[:, 1],
            s=300, c='red', marker='X')
plt.title('K-Means кластеризация')
plt.show()

Применение в реальных задачах

Сегментация клиентов: Группировка клиентов по покупательскому поведению
Анализ изображений: Квантование цветов (уменьшение количества цветов)
Анализ текстов: Группировка документов по темам
Аномалии: Выявление выбросов (точки далеко от всех центроидов)
Биоинформатика: Кластеризация генов с похожей экспрессией

Распространённые ошибки

Использование без масштабирования: Признаки в разных масштабах исказят расстояния
Игнорирование выбросов: K-Means очень чувствителен к выбросам
Некорректный выбор K: Использование неоптимального количества кластеров
Интерпретация как классификации: Кластеры не имеют “смысла” по умолчанию

Итог: K-Means — мощный и эффективный инструмент для кластеризации, идеально подходящий для сферических кластеров примерно одинакового размера. Несмотря на простоту, требует внимательной подготовки данных и тщательного выбора параметров для получения значимых результатов. Часто используется как baseline для более сложных алгоритмов кластеризации.

LDS