k-means

Коротко

Definition

k-means — это алгоритм кластеризации, который разбивает объекты на заранее заданное число кластеров $K$ , минимизируя расстояния от объектов до центров своих кластеров.

k-means относится к обучению без учителя: у объектов нет заранее известных правильных меток классов. Алгоритм сам ищет группы похожих объектов по их признакам.

Главная идея:

выбрать число кластеров $K$ ;
найти $K$ центроидов;
отнести каждый объект к ближайшему центроиду;
пересчитывать центроиды, пока кластеры не стабилизируются.

Интуиция

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

k-means делает это через центры кластеров — центроиды.

Алгоритм работает как повторение двух шагов:

Каждая точка выбирает ближайший центр.
Каждый центр сдвигается в среднее положение своих точек.

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

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

Формальное описание

Пусть есть набор объектов:

X = {x_{1}, x_{2}, \dots, x_{n}}

где каждый объект $x_{i}$ — это вектор признаков.

Нужно разбить объекты на $K$ кластеров:

C_{1}, C_{2}, \dots, C_{K}

У каждого кластера есть центроид:

μ_{k}

Центроид — это среднее значение всех объектов внутри кластера:

μ_{k} = \frac{1}{∣ C _{k} ∣} x_{i} \in C_{k} \sum x_{i}

Каждый объект относится к тому кластеру, центроид которого находится ближе всего:

c_{i} = argmin_{k \in {1, \dots, K}} ∥ x_{i} - μ_{k} ∥^{2}

Цель k-means — найти такое разбиение, при котором сумма квадратов расстояний от точек до центроидов минимальна.

Входы и выходы

Компонент	Описание
Вход	Матрица признаков объектов
Выход	Номер кластера для каждого объекта
Тип задачи	Кластеризация
Тип обучения	Обучение без учителя
Целевая переменная	Отсутствует
Основной параметр	Количество кластеров $K$

Примеры задач:

сегментация клиентов;
группировка материалов по похожим свойствам;
кластеризация экспериментов;
сжатие набора объектов через центроиды;
поиск грубой структуры в табличных данных;
предварительный анализ данных перед обучением модели.

Как обучается

Алгоритм k-means работает итеративно.

Выбрать количество кластеров $K$ .
Инициализировать $K$ центроидов.
Отнести каждый объект к ближайшему центроиду.
Пересчитать каждый центроид как среднее всех объектов своего кластера.
Повторять шаги 3–4, пока центроиды почти не перестанут двигаться или пока не будет достигнут лимит итераций.

Обычно используется инициализация k-means++: она выбирает начальные центроиды более устойчиво, чем случайный выбор.

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

Функция потерь

k-means минимизирует сумму квадратов расстояний от объектов до центроидов их кластеров.

Эта величина часто называется WCSS или inertia:

J = k = 1 \sum K x_{i} \in C_{k} \sum ∥ x_{i} - μ_{k} ∥^{2}

где:

$C_{k}$ — объекты в кластере $k$ ;
$μ_{k}$ — центроид кластера $k$ ;
$∥ x_{i} - μ_{k} ∥^{2}$ — квадрат расстояния от объекта до центроида.

Чем меньше inertia, тем ближе точки к центрам своих кластеров.

Но важно: inertia почти всегда уменьшается при увеличении $K$ . Поэтому нельзя просто выбрать максимальное число кластеров. Нужно искать баланс между компактностью и осмысленностью кластеров.

Гиперпараметры

Главные гиперпараметры k-means:

Гиперпараметр	Что контролирует
`n_clusters`	Количество кластеров $K$
`init`	Способ инициализации центроидов
`n_init`	Количество запусков с разной инициализацией
`max_iter`	Максимальное число итераций
`tol`	Порог изменения центроидов для остановки
`random_state`	Фиксация случайности для воспроизводимости

Самый важный гиперпараметр — $K$ .

Для выбора $K$ часто используют:

elbow method;
silhouette score;
предметную интерпретацию кластеров;
сравнение нескольких вариантов кластеризации.

Когда использовать

k-means стоит использовать, когда:

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

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

Когда не использовать

k-means плохо подходит, если:

число кластеров заранее неизвестно и его трудно выбрать;
кластеры имеют сложную неокруглую форму;
кластеры сильно различаются по плотности;
в данных много выбросов;
признаки не нормализованы;
есть много категориальных признаков без корректного кодирования;
расстояние Евклида плохо отражает смысловую похожесть объектов.

Если кластеры имеют сложную форму или есть шум, часто лучше попробовать DBSCAN.

Метрики оценки

Для оценки k-means используют метрики качества кластеризации.

Частые варианты:

inertia — сумма квадратов расстояний до центроидов;
silhouette score — насколько объект похож на свой кластер по сравнению с соседними;
Davies–Bouldin index;
Calinski–Harabasz index;
внешние метрики, если есть настоящие метки классов.

Подробнее: Метрики качества кластеризации.

Важно: в кластеризации нет единственной универсальной метрики. Хороший результат должен быть не только численно хорошим, но и интерпретируемым.

Типичные ошибки понимания

Ошибка 1. Думать, что k-means сам выбирает число кластеров

k-means требует заранее задать $K$ . Алгоритм не знает, сколько кластеров действительно есть в данных.

Ошибка 2. Не масштабировать признаки

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

Перед k-means обычно нужна стандартизация или нормализация.

Ошибка 3. Интерпретировать кластеры как реальные классы

Кластеры — это группы, найденные алгоритмом по выбранным признакам и метрике расстояния. Они не обязательно соответствуют настоящим категориям в предметной области.

Ошибка 4. Считать меньшую inertia абсолютным улучшением

Inertia уменьшается при увеличении $K$ . Поэтому сравнивать модели только по inertia без учёта числа кластеров неправильно.

Ошибка 5. Использовать k-means для кластеров сложной формы

k-means хорошо работает с компактными группами, но плохо описывает вытянутые, вложенные или произвольные формы кластеров.

Минимальный пример

import numpy as np
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
 
X = np.array([
    [1.0, 1.2],
    [1.1, 0.9],
    [5.0, 5.1],
    [5.2, 4.9],
    [9.0, 1.0],
    [9.2, 1.1],
])
 
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
 
model = KMeans(
    n_clusters=3,
    n_init=10,
    random_state=42,
)
 
labels = model.fit_predict(X_scaled)
 
print(labels)
print(model.cluster_centers_)

В этом примере k-means делит объекты на три кластера. Масштабирование добавлено потому, что алгоритм зависит от расстояний между объектами.

Машинное обучение

Explorer

k-means

k-means

Коротко

Интуиция

Формальное описание

Входы и выходы

Как обучается

Функция потерь

Гиперпараметры

Когда использовать

Когда не использовать

Метрики оценки

Типичные ошибки понимания

Ошибка 1. Думать, что k-means сам выбирает число кластеров

Ошибка 2. Не масштабировать признаки

Ошибка 3. Интерпретировать кластеры как реальные классы

Ошибка 4. Считать меньшую inertia абсолютным улучшением

Ошибка 5. Использовать k-means для кластеров сложной формы

Минимальный пример

Связанные понятия

Что знать перед этим

Graph View

Table of Contents

Backlinks