k-Means — k-средних

Разбивает объекты на k кластеров, минимизируя суммарное расстояние до центроидов.

k = 1 \sum K x \in C_{k} \sum ∥ x - μ_{k} ∥^{2}; ⟶; min

Что означает каждый компонент

$∥ x - μ_{k} ∥^{2}$ квадрат расстояния от объекта до центра его кластера
$min$ минимизируется суммарный внутрикластерный разброс (инерция). Отсюда требование сферических кластеров

Ключевые тезисы

Алгоритм Ллойда чередует назначение точек и пересчёт центров до сходимости.
Предполагает сферические кластеры сопоставимого размера.
Число k выбирают по методу локтя, силуэту или доменной логике; k-means++ улучшает инициализацию.

Тема также относится к главам:Обучение без учителяКластеризация

Подробный разбор

2 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.

Алгоритм Ллойда

Две операции, которые повторяются до сходимости.

k = 1 \sum K x \in C_{k} \sum ∥ x - μ_{k} ∥^{2} ⟶ min

Обозначения

$μ$ среднее значение
$C$ параметр C: цена нарушения зазора. Большое C — почти не прощаем ошибок
$x$ объект: вектор признаков
$k$ номер или количество: индекс шага, число соседей, кластеров или позиций
$\sum$ суммирование по всем перечисленным элементам
$∥ \cdot ∥$ норма — длина вектора

Внутрикластерная сумма квадратов (WCSS, инерция)

Инициализировать центры (лучше k-means++, а не случайно).
Отнести каждый объект к ближайшему центру.
Пересчитать центры как средние своих объектов.
Повторять шаги 2–3, пока назначения меняются.

кластеров k3

итераций4

инерция (WCSS)0.880

Число кластеров k3Итерации алгоритма4

Увеличивайте число итераций по одной: центры съезжаются к плотным областям, инерция падает

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

Локоть, силуэт и здравый смысл.

Метод локтя: строим WCSS от $k$ и ищем точку, где падение резко замедляется.
Силуэт: максимизируем среднюю величину $\frac{b - a}{m a x ( a , b )}$ , где $a$ — среднее расстояние внутри кластера, $b$ — до ближайшего чужого.
Доменная логика: часто $k$ задаётся бизнесом (три сегмента клиентов, пять тарифов), и это лучший критерий.

На практике

k-means предполагает сферические кластеры сопоставимого размера и плотности. Для вытянутых или вложенных структур результат будет бессмысленным — там нужны GMM, DBSCAN или спектральная кластеризация.

Связанные темы

Метрические и ядровые методы · Кластеризация и её оценка

DBSCAN75%

DBSCAN · Классическое машинное обучение

Плотностная кластеризация: кластеры — это связные области высокой плотности, остальное объявляется шумом.

GMM75%

Смесь гауссиан · Классическое машинное обучение

Вероятностная модель: данные порождаются смесью нормальных распределений, параметры оцениваются EM-алгоритмом.

Clustering75%

Кластеризация · Обучение без учителя

Разбиение объектов на группы похожих без заранее известных меток.

Density Estimation75%

Оценка плотности · Обучение без учителя

Восстановление распределения данных: где объекты встречаются часто, а где почти никогда.

Association Rules75%

Ассоциативные правила · Обучение без учителя

Поиск закономерностей вида «если A, то B» в транзакционных данных.

Silhouette Score75%

Силуэт · Метрики

Сравнивает среднее расстояние объекта до своего кластера и до ближайшего чужого.

Davies–Bouldin75%

Индекс Дэвиса — Болдина · Метрики

Отношение внутрикластерного разброса к расстоянию между кластерами; чем меньше, тем лучше.

Calinski–Harabasz75%

Индекс Калинского — Харабаша · Метрики

Отношение межкластерной дисперсии к внутрикластерной; чем больше, тем лучше разделение.

Mapper75%

Алгоритм Mapper · Топологический анализ данных

Строит граф-скелет данных: проекция фильтрующей функцией, покрытие интервалами, локальная кластеризация и склейка.

k-NN65%

Метод k ближайших соседей · Классическое машинное обучение

Ленивый алгоритм: предсказание — это голосование k ближайших объектов обучающей выборки.

SVM65%

Метод опорных векторов · Классическое машинное обучение

Ищет гиперплоскость с максимальным зазором между классами; ядровой трюк добавляет нелинейность без явного перехода в новое пространство.

Distance65%

Расстояние · Математический справочник

Мера непохожести объектов — основа кластеризации, k-NN и поиска.

Norm65%

Норма · Математический справочник

Мера длины вектора; выбор нормы определяет геометрию задачи.

Normalization & Standardization65%

Нормализация и стандартизация · Данные

Приведение признаков к сопоставимым масштабам, без которого расстояния, градиенты и регуляризация работают некорректно.

Metric spaces65%

Метрические пространства · Топологический анализ данных

Множество с функцией расстояния. Любой TDA-пайплайн начинается с выбора метрики.